A Sparse Approximate Inverse Preconditioner for
Parallel Preconditioning of General Sparse Matrices

Jun Zhang
Department of Computer Science
University of Kentucky
773 Anderson Hall
Lexington, KY 40506--0046, USA

Abstract

A factored sparse approximate inverse is computed and used as a preconditioner for solving general sparse matrices. The algorithm is derived from a matrix decomposition algorithm for inverting dense nonsymmetric matrices. Several strategies and special data structures are proposed to implement the algorithm efficiently. Sparsity patterns of the the factored inverse are exploited to reduce computational cost. The preconditioner possesses greater inherent parallelism than traditional preconditioners based on incomplete LU factorizations. Numerical experiments are used to show the effectiveness and efficiency of the proposed sparse approximate inverse preconditioner.


Key words: Sparse matrices, sparse approximate inverse, incomplete LU factorization, Krylov subspace methods.


Download the compressed postscript file fapinv.ps.gz, or the PDF file fapinv.pdf.gz.
This paper has been published in Applied Mathematics and Computation, Vol. 130, No. 1, pp. 63-85 (2002).

Technical Report No. 281-98, Department of Computer Science, University of Kentucky, Lexington, KY, 1998. This research was supported in part by the University of Kentucky Center for Computational Sciences.