MSP: A Class of Parallel Multistep Successive Sparse
Approximate Inverse Preconditioning Strategies

Kai Wang and Jun Zhang
Laboratory for High Performance Scientific Computing and Computer Simulation
Department of Computer Science
University of Kentucky
773 Anderson Hall
Lexington, KY 40506-0046, USA


We develop new concepts and parallel algorithms of multistep successive preconditioning strategies to enhance efficiency and robustness of standard sparse approximate inverse preconditioning techniques. The key idea is to compute a series of simple sparse matrices to approximate the inverse of the original matrix. Studies are conducted to show the advantages of such an approach in terms of both improving preconditioning accuracy and reducing computational cost. Numerical experiments using one prototype implementation to solve a few general sparse matrices on a distributed memory parallel computer are reported.

Key words: Sparse matrices, parallel preconditioning, sparse approximate inverse.

Mathematics Subject Classification: 65F10, 65F50, 65N55, 65Y05.

Download the PDF file kaiwang03a.pdf.
This paper has been published in SIAM Journal on Scientific Computing, Vol. 24, No. 4, pp. 1141-1156 (2003).

Previously published as Technical Report 331-02, Department of Computer Science, University of Kentucky, Lexington, KY, 2002. Download the compressed postscript file, or the PDF file multisail.pdf.

This research was supported in part by the U.S. National Science Foundation under the grant CCR-9902022, CCR-9988165, and CCR-0092532, in part by the Japanese Research Organization for Information Science & Technology, and in part by the University of Kentucky Research Committee.