Accelerated Iterative Methods for the Solution of Tridiagonal Systems on Parallel Computers

Abstract

Iterative methods for the solution of tridiagonal systems are considered, and a new iteration is presented, whose rate of convergence is comparable to that of the optimal two-cyclic Chebyshev iteration but which does not require the calculation of optimal parameters. The convergence rate depends only on the magnitude of the elements of the tridiagonal matrix and not on its dimension or spectrum. The theory also has a natural extension to block tridiagonal systems. Numerical experiments suggest that on a parallel computer this new algorithm is the best of the iterative algorithms considered.