Keywords: 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 [1] 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 [2] distinguish three classes of approximate inverses:

1. approximate inverses based on Frobenius norm minimization [3];
2. approximate inverses in factored form [4,5];
3. inverse ILU techniques [6].

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 inverse variant.

[1]

Y. Saad, "Iterative methods for sparse linear systems", SIAM, Philadelphia, 2003. doi:10.1137/1.9780898718003

[2]

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

[3]

M.J. Grote, T. Huckle, "Parallel preconditioning with sparse approximate inverses", SIAM Journal on Scientific Computing, 18, 838-853, 1997. doi:10.1137/S1064827594276552

[4]

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

[5]

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

[6]

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.

[7]

L. Bergamaschi, A. Martinez, "Banded target matrices and recursive FSAI for parallel preconditioning", Numerical Algorithms, 2012. (to appear)

[8]

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

[9]

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

[10]

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

[11]

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)