×

On two-grid convergence estimates. (English) Zbl 1164.65343

This paper deals with solving \(Au=f\), where \(A\) is a symmetric and positive definite matrix, with two-level hierarchical basis (TL) or two-grid (TG) iterative methods. Fundamentally, the methods differ in the two-component decomposition of the underlying vector space of unknowns: in the TL method, the sum is direct, which is not necessarily true for the TG method. The authors construct \(B_{\text{TL}}\), a TL preconditioner, and infer the best value of the constant that appears in the spectral equivalence relation between \(A\) and \(B_{\text{TL}}\). An analogous analysis for the TB method results in the corresponding preconditioner and spectral equivalence constant. The constants determine the convergence factors of the TL and TG preconditioners. Three mutually equivalent necessary conditions for uniform convergence of the TG method are given. The final part of the paper focuses on constructing an efficient window-based algebraic two-grid method.

MSC:

65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
Full Text: DOI

References:

[1] Axelsson, Mathematics of Computation 40 pp 219– (1983)
[2] Falgout, SIAM Journal on Numerical Analysis 42 pp 1669– (2004)
[3] Brandt, Electronic Transactions on Numerical Analysis 10 pp 1– (2000)
[4] Chartier, SIAM Journal on Scientific Computing 25 pp 1– (2003)
[5] Analysis of a two-level scheme for solving finite element equations. Report CNA-159, Center for Numerical Analysis, The University of Texas at Austin, Austin, TX, 1980.
[6] Braess, Numerische Mathematik 37 pp 387– (1981)
[7] Yserentant, Numerische Mathematik 49 pp 379– (1986)
[8] Bank, Numerische Mathematik 52 pp 427– (1988)
[9] Hierarchical Bases and the Finite Element Method. Acta Numerica, vol. 5. Cambridge University Press: Cambridge, 1996; 1-43. · Zbl 0865.65078
[10] Eijkhout, SIAM Review 33 pp 405– (1991)
[11] Vassilevski, SIAM Review 39 pp 18– (1997)
[12] Xu, Journal of the American Mathematical Society 15 pp 573– (2002)
[13] Iterative Solution Methods. Cambridge University Press: Cambridge, 1994. · doi:10.1017/CBO9780511624100
[14] Demko, Mathematics of Computation 43 pp 491– (1984)
[15] Algebraic multigrid (AMG). In Multigrid Methods, (ed.). Frontiers in Applied Mathematics, vol. 3. SIAM: Philadelphia, PA, 1987; 73-130. · doi:10.1137/1.9781611971057.ch4
[16] A Multigrid Tutorial (2nd edn). SIAM: Philadelphia, PA, 2000. · Zbl 0958.65128 · doi:10.1137/1.9780898719505
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.