Solving banded systems on a parallel processor (Q1107261)

Direct algorithms based on a partitioning scheme for solving banded systems of linear equations, without pivoting \(\lambda\) (which is not needed for, say, positive definite or diagonally dominant matrices) on a parallel processor are considered. There are chosen two ways of partitioning scheme: cyclic and consecutive. The last giving rise to block-factorization methods. Attention is paid to the two-way factorization, starting simultaneously from the top and from the bottom of the matrix. Ring, mesh, hypercube and shared-memory architectures are considered. The communication complexity and an analysis of the operations cost of algorithms that exploit independence of operations in eliminating a single variable or in eliminating different variables are given. Measurements that compare the predicted speedup of the parallel algorithms versus the real one achieved on Alliant FX/8 for different number of processors (1,2,4,8) are presented.