Preconditioning by incomplete block elimination. (English) Zbl 1051.65055

Summary: The recursive construction of Schur complements is used to construct a multi-level preconditioner for an iterative linear solver. For each level, the removed unknowns are selected in such a way that the eliminated matrix block is strictly diagonally dominant. A Newton-type iteration scheme is used to construct a sparse approximate inverse of this sub-matrix. The threshold for the diagonal dominance controls the computational effort to achieve a certain accuracy in the Newton iteration. We present a modification of the greedy algorithm in order to identify a suitable sub-matrix that is diagonally dominant and ensures a stable forward and backward substitution. Some examples are presented.


65F35 Numerical computation of matrix norms, conditioning, scaling
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices


Full Text: DOI


[1] Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, 1994.
[2] Iterative Solution Methods. Cambridge University Press, 1994.
[3] Iterative Methods for Sparse Linear Systems. PWS Publishing: Boston, MA, 1996.
[4] Meijerink, Journal of Chemical Physics 44 pp 134– (1981)
[5] Saad, Numerical Linear Algebra with Applications 1 pp 387– (1994)
[6] Saad, SIAM Journal on Scientific Computing 17 pp 830– (1996)
[7] Huckle, SIAM Journal on Scientific Computing 18 pp 838– (1997)
[8] Chow, SIAM Journal on Scientific Computing 19 pp 995– (1998)
[9] Kolotilina, SIAM Journal on Matrix Analysis and Applications 14 pp 45– (1993)
[10] Benzi, SIAM Journal on Scientific Computing 19 pp 968– (1998)
[11] Saad, SIAM Journal on Scientific Computing 20 pp 2103– (1999)
[12] Axelsson, Numerical Linear Algebra with Applications 1 pp 213– (1994)
[13] ARMS: An algebraic recursive multilevel solver for general sparse linear systems. Research Report UMSI 99-107, Supercomputer Institute, University of Minnesota, Minneapolis, MN, USA, 1999.
[14] On residual smoothing in ILUM-type preconditioning. In Proceedings of the Computational Techniques and Application Conference, Canberra, 1999; to be published.
[15] Saad, Numerical Linear Algebra with Applications 21 pp 257– (1999)
[16] Pan, SIAM Journal on Scientific and Statistical Computing 12 pp 1109– (1991)
[17] Parallel implicit unstructured grid Euler solvers. Research Report, NASA CR-191594, NASA Langley Research Center, Hampton VA, USA, 1994. · Zbl 0852.76071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.