The stable parallel solution of general narrow banded linear systems
Peter Arbenz, Markus Hegland · ANU Open Research (Australian National University) · 1996
. We propose a stable algorithm for the parallel solution of banded and periodically banded linear systems. While most of the known parallel algorithms are stable only for symmetric positive definite or diagonally dominant systems, the new algorithm incorporates pivoting without sacrificing efficiency. The principle ingredient of the algorithm is a bidiagonal cyclic reduction that admits pivoting. We report on numerical experiments conducted on various multiprocessor computers. 1. Introduction Methods will be discussed for the solution of linear systems Ax = b (1.1) with n unknowns and a banded matrix A. The system matrix A has upper bandwidth k u if ff ij = 0 for j ? i + k u and lower bandwidth k l if ff ij = 0 for i ? j + k l . If k u + k l is small compared to n then A is said to be narrow banded. This is the case which shall be considered here. Frequently occurring problems include bidiagonal systems (k u + k l = 1), tridiagonal systems (k u + k l = 2) and systems obtained fro...