Computational Technology Reviews
Computational Technology Reviews
Volume 7, 2013
Approximate Inverse Preconditioning for the Solution of Large Sparse Linear Systems
, M. Ferronato1,2
and G. Gambolati1,2
1Department ICEA, University of Padova, Italy
2M3E S.r.l., Padova, Italy
Full Bibliographic Reference for this paper
C. Janna, M. Ferronato, G. Gambolati, "Approximate Inverse Preconditioning for the Solution of Large Sparse Linear Systems", Computational Technology Reviews, vol. 7, pp. 25-41, 2013. doi:10.4203/ctr.7.2
preconditioning, approximate inverses, Krylov subspace methods.
The efficient parallel solution to large sparse linear systems of equations
is a central issue in many numerical computations in
science and engineering. In fact, the solution of linear systems of equations is frequently the most
time-consuming phase of several simulation codes with the development of efficient parallel algorithms
virtually mandatory to permit the large scale computations required in recent applications.
Iterative methods based on Krylov subspaces involve matrix-vector products, dot
products, and vector updates only, so they can be, at least in principle, almost ideally
implemented on parallel computers. However, to allow for convergence in realistic problems these methods
need to be preconditioned, and the computation and application of an effective preconditioner is often
the most decisive and difficult task to be carried out in parallel.
Incomplete LU (ILU) factorizations  represent one of the most popular and general-purpose
family of algebraic preconditioners and have been used widely over the last two decades in several different
research areas. Unfortunately, they are intrinsically serial making their use in large scale parallel
computers difficult. By contrast, sparse approximate inverses are conceptually parallel in nature, as they provide an
explicit approximation of the system matrix inverse which can be applied to a vector by a matrix-by-vector product only.
This family of preconditioners has been investigated in depth in recent years and many different variants are
presently available in literature. Benzi and Tůma in  distinguish three classes of
- approximate inverses based on Frobenius norm minimization ;
- approximate inverses in factored form [4,5];
- inverse ILU techniques .
Nowadays, this classification is still valid but much work has been done to improve the performance
of approximate inverses and increase their scalability and effectiveness [7,8,9,10,11].
In the present review, the most noticeable advancements in this field will be addressed with a short
description of the algorithms and a discussion on the strong and weak points of each approximate
- Y. Saad, "Iterative methods for sparse linear systems", SIAM, Philadelphia, 2003. doi:10.1137/1.9780898718003
- M. Benzi, M. Tůma, "A comparative study of sparse approximate inverse preconditioners", Applied Numerical Mathematics, 30, 305-340, 1999. doi:10.1016/S0168-9274(98)00118-4
- M.J. Grote, T. Huckle, "Parallel preconditioning with sparse approximate inverses", SIAM Journal on Scientific Computing, 18, 838-853, 1997. doi:10.1137/S1064827594276552
- L.Y. Kolotilina, A.Y. Yeremin, "Factorized sparse approximate inverse preconditionings. I. Theory", SIAM Journal on Matrix Analysis with Applications, 14, 45-58, 1993. doi:10.1137/0614004
- M. Benzi, C. D. Meyer, M. Tůma, "A sparse approximate inverse preconditioner for the conjugate gradient method", SIAM Journal on Scientific Computing, 17, 1135-1149, 1996. doi:10.1137/S1064827594271421
- F. Alvarado, H. Dag, "Sparsified and incomplete sparse factored inverse preconditioners", in "Proceedings of the 1992 Copper Mountain Conference on Iterative Methods", I, 9-14 April 1992.
- L. Bergamaschi, A. Martinez, "Banded target matrices and recursive FSAI for parallel preconditioning", Numerical Algorithms, 2012. (to appear)
- K. Chen, M.D. Hughes, "A two-level sparse approximate inverse preconditioner for unsymmetric matrices", IMA Journal of Numerical Analysis, 26, 11-24, 2005. doi:10.1093/imanum/dri031
- Z. Jia, B. Zhu, "A power sparse approximate inverse preconditioning procedure for large sparse linear systems", Numerical Linear Algebra with Applications, 16, 259-299, 2009. doi:10.1002/nla.614
- C. Janna, M. Ferronato, G. Gambolati, "A block FSAI-ILU parallel preconditioner for symmetric positive definite linear systems", SIAM Journal on Scientific Computing, 32, 2468-2484, 2010. doi:10.1137/090779760
- C. Janna, M. Ferronato, "Adaptive pattern research for block FSAI preconditioning", SIAM Journal on Scientific Computing, 33, 3357-3380, 2011. doi:10.1137/100810368
purchase the full-text of this paper (price £20)
go to the previous paper
go to the next paper
return to the table of contents
return to Computational Technology Reviews
purchase this volume (price £80 +P&P)