Parallel solution of almost block diagonal systems on a hypercube (Q1923143)

The authors are interested in solution of problems arising from finite difference discretization of systems of linear ordinary differential equations with separated boundary conditions. These problems have coefficient matrices which are almost of block diagonal form. They are interested in solution of these problems on hypercube computers which are characterized by relatively expensive interprocessor communication costs in a single-tasking environment. The authors present a two-stage approach to factorization of these linear matrices. The original matrix is divided among \(p\) processors with several blocks per processor. The first stage of the factorization involves, for each processor, an LU factorization of the portion of the matrix referring only to variables stored on the same processor. The method used for this stage is similar to the one introduced by \textit{M. Paprzycki} and \textit{I. Gladwell} [Parallel Comput. 17, No. 2/3, 133-153 (1991; Zbl 0729.65012)]. This stage involves roughly \(\log_2 p\) steps, each of which starts with a sharing of information with adjacent processors and performs a factorization of the same resulting matrix on pairs of processors. Duplication of the matrices results in additional arithmetic operations, but these operations are performed on processors which would otherwise be idle. This duplication reduces the amount of interprocess communication required in the solution. The authors provide precise descriptions of the algorithms used, arithmetical operation counts, and memory requirements. They compare these operation counts and memory requirements with the earlier algorithm and also with the best sequential algorithm.