Search

Four parallel algorithms for the solution of block bidiagonal linear systems on distributed memory computers are presented. All the algorithms belong to the class of direct methods. The first is a variant of the sequential algorithm and is suitable for a small number of processors. The remaining three algorithms are based on the parallel methods for banded systems and are much better suited for parallel computations on multiple processors. The arithmetical complexity functions of the proposed algorithms are derived. The results of experiments with the four algorithms implemented in Parallel Fortran on a linear array of 32 Transputers are presented and discussed.

A parallel version of the cyclic reduction algorithm for the solution of tridiagonal linear systems is presented. The original problem is divided into subproblems which may be solved almost independently. Synchronizations among the processors involved is only needed to solve a reduced tridiagonal system whose dimension depends on the number of processors. Numerical tests have been performed on a linear array of processors. The obtained speedups show that this is the best possible parallel implementation of the cyclic reduction and one of the fastest algorithms for the solution of tridiagonal systems on a parallel computer with medium grain parallelism.