A Class of Parallel Multilevel Sparse Approximate
Inverse Preconditioners for Sparse Linear Systems

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


We investigate the use of the multistep successive preconditioning strategies (MSP) to construct a class of parallel multilevel sparse approximate inverse (SAI) preconditioners. We do not use independent set ordering, but a diagonal dominance based matrix permutation to build a multilevel structure. The purpose of introducing multilevel structure into SAI is to enhance the robustness of SAI for solving difficult problems. Forward and backward preconditioning iteration and two Schur complement preconditioning strategies are proposed to improve the performance and to reduce the storage cost of the multilevel preconditioners. One version of the parallel multilevel SAI preconditioner based on the MSP strategy is implemented. Numerical experiments for solving a few sparse matrices on a distributed memory parallel computer are reported.

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

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

Download the compressed postscript file mlsparse.ps.gz, or the PDF file mlsparse.pdf.gz.
This paper has been accepted for publication in Journal of Parallel and Distributed Computing Practice.

Technical Report 360-02, Department of Computer Science, University of Kentucky, Lexington, KY, 2002.

This research work supported in part by the U.S. National Science Foundation under the grant CCR-9902022, CCR-9988165, CCR-0092532, and ACI-0202934, in part by the U.S. Department of Energy Office of Sceince under grant DE-FG02-02ER45961, in part by the Japanese Research Organization for Information Science & Technology, and in part by the University of Kentucky Research Committee.