Gene Golub Symposium
Parallel Schemes for Solving Linear Systems of Equations
A. Grama, M. Manguoglu, and A. Sameh, Purdue University
Reordering general sparse systems to extract effective narrow banded preconditioners has yielded robust iterative sparse system solvers. In this talk, we focus on the development of scalable parallel algorithms for solving those systems involving the banded preconditioner. The preconditioner is partitioned into blocks of rows with a small number of unknowns common to multiple blocks. Our technique yields a reduced system 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 giving rise to an inner-outer iteration. 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 devised 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 Krylov schemes, particularly for problems with strong indefinite symmetric parts.
