A survey of direct parallel algorithms for banded linear systems
Peter Arbenz, Walter Gander · Repository for Publications and Research Data (ETH Zurich) · 1994
We investigate direct algorithms to solve linear banded systems of equations on MIMD multiprocessor computers with distributed memory. We compare the coarse-grain parallel algorithms with ordinary one-processor Gaussian elimination. The parallel algorithms behave satisfactory only if the ratio of bandwidth and matrix order is very small. As a result of the high redundancy of the parallel algorithms efficencies are in general not high. The theoretical considerations are complemented with numerical experiments performed on the Intel Paragon. Keywords. Banded Linear Systems, Divide and Conquer, Parallel Computation, Scalability. 1 Introduction In this paper we discuss using direct methods on parallel computers to solve a system of linear equations Ax = b (1.1) where A is a real banded n \\Theta n matrix with lower half-bandwidth r and upper half-bandwidth s, a ij = 0 for i \\Gamma j ? r and j \\Gamma i ? s: (1.2) We assume that the matrix A has a narrow band, such that r +s ø n: Only in t...