Parallelization and vectorization aspects of the solution of tridiagonal linear systems (Q913446)

The solution of one or several tridiagonal systems is one of the basic operations in numerical computations. The authors develop, investigate and compare some parallel tridiagonal system solvers suitable for message-based MIMD computers with vector processors. The basic idea of the algorithm presented consists in subdividing the tridiagonal system into p \((=\) number of processes) parts by splitting the ``interface'' equations which couple the parts, eliminating the ``inner'' unknowns, solving the assembled ``interface'' system for the coupling unknowns, and calculating back the ``inner'' unknowns. The elimination of the ``inner'' unkowns and the back-calculation can be fully done in parallel. Only the assembling and the solution of the ``interface'' system is connected with communication between the processors. The several solution strategies discussed in the paper were tested and compared on the iPSC2-VX.