Preconditioning by incomplete block elimination. (English) Zbl 1051.65055

Grosz, L.

Numer. Linear Algebra Appl. 7, No. 7-8, 527-541 (2000).

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.

MSC:

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

Keywords:

multi-level preconditioning; Schur complement; numerical examples; Newton-type iteration scheme; sparse approximate inverse; diagonal dominance; greedy algorithm

Software:

ARMS

References:

[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