A parallel balance scheme for banded linear systems Academic Article uri icon

abstract

  • A parallel algorithm is proposed for the solution of narrow banded non-symmetric linear systems. The linear system is partitioned into blocks of rows with a small number of unknowns common to multiple blocks. Our technique yields a reduced system defined only on these common unknowns which can then be solved by a direct or iterative method. A projection based extension to this approach is also proposed for computing the reduced system implicitly, which gives rise to an inner-outer iteration method. In addition, the product of a vector with the reduced system matrix can be computed efficiently on a multiprocessor by concurrent projections onto subspaces of block rows. Scalable implementations of the algorithm can be devized for hierarchical parallel architectures by exploiting the two-level parallelism inherent in the method. Our experiments indicate that the proposed algorithm is a robust and competitive alternative to existing methods, particularly for difficult problems with strong indefinite symmetric part. Copyright 2001 John Wiley & Sons, Ltd.

published proceedings

  • NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS

author list (cited authors)

  • Golub, G. H., Sameh, A. H., & Sarin, V.

citation count

  • 13

complete list of authors

  • Golub, GH||Sameh, AH||Sarin, V

publication date

  • January 2001

publisher