A highly scalable parallel algorithm for solving Toeplitz tridiagonal systems of linear equations

• A parallel algorithm for solving Toeplitz tridiagonal systems is proposed.
• The algorithm allows an effective use of the 2D/3D fast Poisson solvers.
• The dependence of the speedup on the number of processors is almost linear.
• A large number of processors can be used (up to 16 384).

Based on a modification of the dichotomy algorithm, we propose a novel parallel procedure for solving tridiagonal systems of equations with Toeplitz matrices. Taking the structure of the Toeplitz matrices, we may substantially reduce the number of the preliminary calculations of the dichotomy algorithm, which makes possible to efficiently solve systems of linear equations with both one and several right-hand sides. On examples of solving the 2D Poisson equation by the variable separation method and the 3D Poisson equation by a combination of the alternating direction implicit and the variable separation methods we show that the computation accuracy is comparable with the sequential version of the Thomas method, the dependence of the speedup on the number of processors being almost linear. The proposed modification is aimed at parallel implementation of a broad class of numerical methods including the Toeplitz tridiagonal matrices inversion.