Parallel solution of block-tridiagonal systems

First, several parallel tridiagonal linear system solvers are discussed. For convenience, a brief description of the ordinary odd-even method and the partition method are attached.

Then, a new block tridiagonal systems solver (BTSS) is given. The BTSS is a generalization of the ordinary odd-even method for block tridiagonal systems.

Finally, a new tridiagonal system solver (TSS) is presented. The algorithm is based on the partition method [24]; however, it is oriented in parallel throughout all the steps. The new solver is designed for the case where the number of equations is much larger than the number of processors, while the classical solver can handle only the case where the number of equations is less than or equal to the number of processors.

The two new solvers are suitable for both MIMD(Multiple Instruction streams Multiple Data streams) and SIMD(Single Instruction Multiple Data streams) organizations. The BTSS is compared with the Gaussian Elimination Method and the TSS is compared with the partition method. Numerical results obtained on the MasPar are presented to show the effectiveness of the TSS and the BTSS.