Premium
An algebraic preconditioning method for M ‐matrices: linear versus non‐linear multilevel iteration
Author(s) -
Kraus J. K.
Publication year - 2002
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.281
Subject(s) - preconditioner , mathematics , schur complement , linear system , matrix (chemical analysis) , diagonal , linear algebra , polynomial , sparse matrix , mathematical analysis , eigenvalues and eigenvectors , gaussian , physics , materials science , geometry , quantum mechanics , composite material
Abstract In a recent work, the author introduced a robust multilevel incomplete factorization algorithm using spanning trees of matrix graphs (Proceedings of the 1999 International Conference on Preconditioning Techniques for Large Sparse Matrix Problems in Industrial Applications, Hubert H. Humphrey Center, University of Minnesota, 1999, 251–257). Based on this idea linear and non‐linear algebraic multilevel iteration (AMLI) methods are investigated in the present paper. In both cases, the preconditioner is constructed recursively from the coarsest to finer and finer levels. The considered W ‐cycles only need diagonal solvers on all levels and additionally evaluate a second‐degree matrix polynomial (linear case), or, perform ν inner GCG‐type iterations (non‐linear case) on every other level. This involves the same type of preconditioner for the corresponding Schur complement. The non‐linear variant has the additional benefit of being free from any method parameters to be estimated. Based on the same type of approximation property similar convergence rates are obtained for linear and non‐linear AMLI, even for a very small number ν of inner iterations, e.g. ν =2,3. The presented methods are robust with respect to anisotropy and discontinuities in the coefficients of the PDEs and can also be applied to unstructured‐grid problems. Copyright © 2002 John Wiley & Sons, Ltd.