Algebraic analysis of two-grid methods: the nonsymmetric case. (English) Zbl 1240.65358
Summary: Two-grid methods constitute the building blocks of multigrid methods, which are among the most efficient solution techniques for solving large sparse systems of linear equations. In this paper, an analysis is developed that does not require any symmetry property. Several equivalent expressions are provided that characterize all eigenvalues of the iteration matrix. In the symmetric positive-definite (SPD) case, these expressions reproduce the sharp two-grid convergence estimate obtained by R. D. Falgout, P. S. Vassilevski and L. T. Zikatanov [Numer. Linear Algebra Appl. 12, No. 5-6, 471–494 (2005; Zbl 1164.65343)], and also previous algebraic bounds, which can be seen as corollaries of this estimate. These results allow to measure the convergence by checking “approximation properties”.
In this work, proper extensions of the latter to the nonsymmetric case are presented. Sometimes approximation properties for the SPD case are summarized in loose terms (e.g., [M. Brezina at al., SIAM J. Sci. Comput. 22, No. 5, 1570–1592 (2001; Zbl 0991.65133)]). It is shown that this can be applied to nonsymmetric problems too, understanding “size” as “modulus”. Eventually, an analysis is developed, for the nonsymmetric case, of the theoretical foundations of “compatible relaxation”, according to which a fine/coarse partitioning may be checked and possibly improved.
In this work, proper extensions of the latter to the nonsymmetric case are presented. Sometimes approximation properties for the SPD case are summarized in loose terms (e.g., [M. Brezina at al., SIAM J. Sci. Comput. 22, No. 5, 1570–1592 (2001; Zbl 0991.65133)]). It is shown that this can be applied to nonsymmetric problems too, understanding “size” as “modulus”. Eventually, an analysis is developed, for the nonsymmetric case, of the theoretical foundations of “compatible relaxation”, according to which a fine/coarse partitioning may be checked and possibly improved.
MSC:
| 65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |
| 65F10 | Iterative numerical methods for linear systems |
| 65F50 | Computational methods for sparse matrices |
Keywords:
multigrid; convergence analysis; convergence measure; compatible relaxation; large sparse systems; eigenvalues of the iteration matrix; symmetric positive-definiteReferences:
| [1] | Trottenberg, Multigrid (2001) |
| [2] | Hackbusch, Multi-grid Methods and Applications (1985) · doi:10.1007/978-3-662-02427-0 |
| [3] | Oswald, Multilevel Finite Element Approximation: Theory and Applications (1994) · Zbl 0830.65107 · doi:10.1007/978-3-322-91215-2 |
| [4] | StÃ{\(\tfrac14\)}ben, Multigrid Methods pp 1– (1982) |
| [5] | Reusken, Fourier analysis of a robust multigrid method for convectionâdiffusion equations, Numerische Mathematik 71 pp 365– (1995) · Zbl 0833.65130 |
| [6] | Notay, A robust algebraic multilevel preconditioner for non symmetric M-matrices, Numerical Linear Algebra with Applications 7 pp 243– (2000) · Zbl 1051.65058 |
| [7] | Brandt, Algebraic multigrid theory: the symmetric case, Applied Mathematics and Computation 19 pp 23– (1986) · Zbl 0616.65037 |
| [8] | Brezina, Algebraic multigrid based on element interpolation (AMGe), SIAM Journal on Scientific Computing 22 pp 1570– (2000) · Zbl 0991.65133 |
| [9] | Falgout, On generalizing the algebraic multigrid framework, SIAM Journal on Numerical Analysis 42 pp 1669– (2005) · Zbl 1077.65129 |
| [10] | Falgout, On two-grid convergence estimates, Numerical Linear Algebra with Applications 12 pp 471– (2005) |
| [11] | Ruge, Multigrid Methods pp 73– (1987) · doi:10.1137/1.9781611971057.ch4 |
| [12] | StÃ{\(\tfrac14\)}ben, Multigrid pp 413– (2001) |
| [13] | Chartier, Spectral AMGe (ÏAMGe), SIAM Journal on Scientific Computing 25 pp 1– (2004) |
| [14] | Henson, Element-free AMGe: general algorithms for computing interpolation weights in AMG, SIAM Journal on Scientific Computing 23 pp 629– (2002) |
| [15] | VaneÌk, Algebraic multigrid based on smoothed aggregation for second and fourth order elliptic problems, Computing 56 pp 179– (1996) |
| [16] | Brandt, General highly accurate algebraic coarsening, Electronic Transactions on Numerical Analysis 10 pp 1– (2000) · Zbl 0951.65096 |
| [17] | Livne, Coarsening by compatible relaxation, Numerical Linear Algebra with Applications 11 pp 205– (2004) · Zbl 1164.65353 |
| [18] | MacLachlan, A greedy strategy for coarse-grid selection, SIAM Journal on Scientific Computing 29 pp 1825– (2007) · Zbl 1154.65016 |
| [19] | Mense, On algebraic multilevel methods for non-symmetric systemsâcomparison results, Linear Algebra and its Applications 429 pp 2567– (2008) · Zbl 1171.65022 |
| [20] | Mense, On algebraic multilevel methods for non-symmetric systemsâconvergence results, Electronic Transactions on Numerical Analysis 20 pp 323– (2008) · Zbl 1171.65022 |
| [21] | Notay, Algebraic multigrid and algebraic multilevel methods: a theoretical comparison, Numerical Linear Algebra with Applications 12 pp 419– (2005) · Zbl 1164.65356 |
| [22] | Vassilevski, Multilevel Block Factorization Preconditioners (2008) |
| [23] | MacLachlan, Algebraic multigrid solvers for complex-valued matrices, SIAM Journal on Scientific Computing 30 pp 1548– (2008) · Zbl 1165.65013 |
| [24] | Dendy, Black box multigrid for nonsymmetric problems, Applied Mathematics and Computation 13 pp 261– (1983) · Zbl 0533.65063 |
| [25] | Wienands, On three-grid Fourier analysis for multigrid, SIAM Journal on Scientific Computing 23 pp 651– (2001) · Zbl 0992.65137 |
| [26] | Brezina M, Manteuffel T, McCormick S, Ruge J, Sanders G. Towards adaptive smoothed aggregation (Î{\(\pm\)} SA) for nonsymmetric problems. Technical Report, University of Colorado at Boulder, 2008. · Zbl 1210.65075 |
| [27] | Clees T. AMG strategies for PDE systems with applications in industrial semiconductor simulation. Ph.D. Dissertation, University of Cologne, Germany, 2004. |
| [28] | Notay Y. An aggregation-based algebraic multigrid method. Technical Report GANMN 08â02, Université Libre de Bruxelles, Brussels, Belgium, 2008. Available from: http://homepages.ulb.ac.be/â{\(\tfrac14\)}ynotay. |
| [29] | Zikatanov, Two-sided bounds on the convergence rate of two-level methods, Numerical Linear Algebra with Applications 15 pp 439– (2007) |
| [30] | Brannick, Domain Decomposition Methods in Science and Engineering XVI pp 15– (2007) |
| [31] | Axelsson, Iterative Solution Methods (1994) · doi:10.1017/CBO9780511624100 |
| [32] | Axelsson, A survey of algebraic multilevel iterations (AMLI) methods, BIT 43 pp 863– (2003) · Zbl 1049.65139 |
| [33] | Eijkhout, The role of the strengthened c.b.s. inequality in multilevel methods, SIAM Review 33 pp 405– (1991) · Zbl 0737.65026 |
| [34] | Chow, Multilevel block factorizations in generalized hierarchical bases, Numerical Linear Algebra with Applications 10 pp 105– (2003) |
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.
