Multigrid Treatment and Robustness Enhancement for
Factored Sparse Approximate Inverse Preconditioning

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

Abstract

We investigate the use of sparse approximate inverse techniques (SAI) in a grid based multilevel ILU preconditioner (GILUM) to design a robust parallelizable preconditioner for solving general sparse matrix. Taking the advantages of grid based multilevel methods, the resulting preconditioner outperforms sparse approximate inverse in robustness and efficiency. Conversely, taking the advantages of sparse approximate inverse, it affords an easy and convenient way to introduce parallelism within multilevel structure. Moreover, an independent set search strategy with automatic diagonal thresholding and a relative threshold dropping strategy are proposed to improve preconditioner performance. Numerical experiments are used to show the effectiveness and efficiency of the proposed preconditioner, and to compare it with some single and multilevel preconditioners.

Key words: Sparse matrices, incomplete LU factorization, multilevel ILU preconditioner, sparse approximate inverse, algebraic multigrid method, Krylov subspace methods

Download the compressed postscript file mspar.ps.gz, or the PDF file mspar.pdf.gz.
This paper has been published in Applied Numerical Mathematics, Vol. 43, No. 4, pp. 483-500 (2002).

Technical Report No. 306-00, Department of Computer Science, University of Kentucky, Lexington, KY, 2000. This research work was supported in part by the U.S. National Science Foundation under grants CCR-9902022, CCR-9988165 and CCR-0043861.