Diagonally compensated reduction and related preconditioning methods. (English) Zbl 0837.65023

Summary: When solving linear algebraic equations with large and sparse coefficient matrices, arising, for instance, from the discretization of partial differential equations, it is quite common to use preconditioning to accelerate the convergence of a basic iterative scheme. Incomplete factorizations and sparse approximate inverses can provide efficient preconditioning methods but their existence and convergence theory is based mostly on M-matrices (H-matrices). In some application areas, however, the arising coefficient matrices are not H-matrices. This is the case, for instance, when higher-order finite element approximations are used, which is typical for structural mechanics problems.
We show that modification of a symmetric, positive definite matrix by reduction of positive offdiagonal entries and diagonal compensation of them leads to an M-matrix. This diagonally compensated reduction can take place in the whole matrix or only at the current pivot block in a recursive incomplete factorization method. Applications for constructing preconditioning matrices for finite element matrices are described.


65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
Full Text: DOI


[1] Preconditioning methods for block H-matrices. In editor, Computer Algorithms for Solving Linear Systems, NATO ASI Series, Vol. 77, pages 169-184, Springer Verlag, Berlin, 1991. · Zbl 0825.65022
[2] and . Finite Element Solution of Boundary Value Problems. Academic Press, Orlando, Florida, 1984.
[3] and . A preconditioned conjugate gradient method for finite element equations, which is stable for rounding errors. In editor, IFIP 1980, Information Processing 80 pages 723-728. North-Holland, Amsterdam.
[4] Axelsson, Math. Comp. 40 pp 219– (1983)
[5] and . A robust preconditioner based on algebraic substructuring and two-level grids. In editor, Robust Multi-Grid Methods, pages 1-16. Vieweg, Braunschweig, 1988.
[6] Axelsson, SIAM J. Numer. Anal. 27 pp 1589– (1990)
[7] A family of explicit preconditionings for simultaneous linear algebraic equations with sparse matrices, Preprint LOMI, P-8- 1986. (In Russian.)
[8] Kolotilina, H-matrices. Linear Algebra Appl. 178 pp 111– (1993)
[9] Kolotilina, Sov. J. Numer. Anal. Math. Modelling 1 pp 293– (1986)
[10] Kolotilina, SIAM J. Matrix Anal. Appl. 14 pp 45– (1993)
[11] and . Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York, 1970.
[12] Polman, Linear Algebra Appl. 90 pp 119– (1987)
[13] Matrix Iterative Analysis. Prentice Hall, Englewood Cliffs, NJ, 1962. · Zbl 0133.08602
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.