A fast algorithm for solving special tridiagonal systems (Q1319048)

The authors describe a fast algorithm for solution of the special tridiagonal Toeplitz matrix system \(Ax = b\), where \(A\) given below is assumed to be strictly diagonally dominant \((| \beta| > 2 | \gamma|)\). \[ A = \left[ \begin{matrix} \beta & \gamma & & &\gamma\\ \gamma & \beta & \gamma\\ & \cdot & \cdot & \cdot \\ & & \gamma & \beta & \gamma\\ \gamma & & & \beta & \gamma \end{matrix}\right],\quad B' = \left[\begin{matrix} a & 1 \\ 1 & d & 1 \\ & \cdot & \cdot & \cdot\\ & & 1 & d & 1\\ & & & 1 & d\end{matrix} \right]. \] If \(B'\) is given above, with \(d = \beta/\gamma\), the first phase of the method first solves the tridiagonal system \(B' x' = b/\gamma\), using a Toeplitz factorization of \(B'\). If \(B\) is the tridiagonal part of \(A\), the second phase solves \(Bx = b\) approximately by adding a multiple of a certain vector \(p\) to \(x'\). The final third phase updates \(x'\) to \(x\). Error analysis of the process is given and it is shown that the method is competitive with previous fastest methods [cf. \textit{R. F. Boisvert}, SIAM J. Sci. Stat. Comput. 12, No. 2, 423-442 (1991; Zbl 0723.65016)].