A parallel balance scheme for banded linear systems

A parallel algorithm is proposed for the solution of narrow banded non-symm etric linear systems. The linear system is partitioned into blocks of rows with a small number of unknown ns common to multiple blocks. Our technique yields a reduced system defined only on these common unknowns which can the n be solved by a direct or iterative method. A projection based extension t o this approach is also proposed for computing the reduced system implicitl y, which gives rise to an inner-outer iteration method. In addition, the pr oduct of a vector. with the reduced system matrix can be computed efficient ly on a multiprocessor by concurrent projections onto subspaces of block ro ws. Scalable implementations of the algorithm can be devized for hierarchic al parallel architectures by exploiting the two-level parallelism inherent in the method. Our experiments indicate that the proposed algorithm is a ro bust and competitive alternative to existing methods, particularly for diff icult problems with strong indefinite symmetric part. Copyright (C) 2001 Jo hn Wiley & Sons, Ltd.