Approximate Inverse Preconditioners via Sparse-Sparse Iterations
- 1 May 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 19 (3) , 995-1023
- https://doi.org/10.1137/s1064827594270415
Abstract
The standard incomplete LU (ILU) preconditioners often fail for general sparse indefinite matrices because they give rise to "unstable" factors L and U. In such cases, it may be attractive to approximate the inverse of the matrix directly. This paper focuses on approximate inverse preconditioners based on minimizing ||I-AM||F, where AM is the preconditioned matrix. An iterative descent-type method is used to approximate each column of the inverse. For this approach to be efficient, the iteration must be done in sparse mode, i.e., with "sparse-matrix by sparse-vector" operations. Numerical dropping is applied to maintain sparsity; compared to previous methods, this is a natural way to determine the sparsity pattern of the approximate inverse. This paper describes Newton, "global," and column-oriented algorithms, and discusses options for initial guesses, self-preconditioning, and dropping strategies. Some limited theoretical results on the properties and convergence of approximate inverses are derived. Numerical tests on problems from the Harwell--Boeing collection and the FIDAP fluid dynamics analysis package show the strengths and limitations of approximate inverses. Finally, some ideas and experiments with practical variations and applications are presented.Keywords
This publication has 17 references indexed in Scilit:
- Approximate Inverse Techniques for Block-Partitioned MatricesSIAM Journal on Scientific Computing, 1997
- Parallel Preconditioning with Sparse Approximate InversesSIAM Journal on Scientific Computing, 1997
- Factorized Sparse Approximate Inverse Preconditionings I. TheorySIAM Journal on Matrix Analysis and Applications, 1993
- Approximate inverse preconditionings for sparse linear systemsInternational Journal of Computer Mathematics, 1992
- Relaxed and stabilized incomplete factorizations for non-self-adjoint linear systemsBIT Numerical Mathematics, 1989
- Sparse matrix test problemsACM Transactions on Mathematical Software, 1989
- On approximate factorization methods for block matrices suitable for vector and parallel processorsLinear Algebra and its Applications, 1986
- On a family of two-level preconditionings of the incomplete block factorization typeRussian Journal of Numerical Analysis and Mathematical Modelling, 1986
- On some versions of incomplete block-matrix factorization iterative methodsLinear Algebra and its Applications, 1984
- Variational Iterative Methods for Nonsymmetric Systems of Linear EquationsSIAM Journal on Numerical Analysis, 1983