Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T04:54:37.883Z Has data issue: false hasContentIssue false
  • English
  • Français

Algebraic Theory of Two-Grid Methods

Published online by Cambridge University Press:  28 May 2015

Yvan Notay
Yvan Notay*
Affiliation:
Université Libre de Bruxelles, Service de Métrologie Nucléaire (C.P. 165-84), 50 Av. F.D.Roosevelt, B-1050 Brussels, Belgium
*
*Email addresses: ynotay@ulb.ac.be (Yvan Notay) Yvan Notay is Research Director of the Fonds de la Recherche Scientifique - FNRS

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

About thirty years ago, Achi Brandt wrote a seminal paper providing a convergence theory for algebraic multigrid methods [Appl. Math. Comput., 19 (1986), pp. 23–56]. Since then, this theory has been improved and extended in a number of ways, and these results have been used in many works to analyze algebraic multigrid methods and guide their developments. This paper makes a concise exposition of the state of the art. Results for symmetric and nonsymmetric matrices are presented in a unified way, highlighting the influence of the smoothing scheme on the convergence estimates. Attention is also paid to sharp eigenvalue bounds for the case where one uses a single smoothing step, allowing straightforward application to deflation-based preconditioners and two-level domain decomposition methods. Some new results are introduced whenever needed to complete the picture, and the material is self-contained thanks to a collection of new proofs, often shorter than the original ones.

Keywords

65F0865F1065F50Multigridconvergence analysisalgebraic multigridpreconditioningtwo-level method

Information

Type
Research Article
Information
Numerical Mathematics: Theory, Methods and Applications , Volume 8 , Issue 2 , May 2015, pp. 168 - 198
Copyright
Copyright © Global-Science Press 2015 

References

[1]Axelsson, O., Iterative Solution Methods, Cambridge University Press, Cambridge, UK, 1994.CrossRefGoogle Scholar
[2]Baker, A.H., Falgout, R.D., Kolev, T.V., and Yang, U.M., Multigrid smoothers for ultraparallel computing, SIAM J. Sci. Comput., 33 (2011), pp. 2864–2887.CrossRefGoogle Scholar
[3]Bank, R. and Douglas, C., Sharp estimates for multigrid rates of convergence with general smoothing and acceleration, SIAM J. Numer. Anal., 22 (1985), pp. 617–633.CrossRefGoogle Scholar
[4]Bank, R.E., Dupont, T.F., and Yserentant, H., The hierarchical basis multigrid method, Numer. Math., 52 (1988), pp. 427–458.CrossRefGoogle Scholar
[5]Bramble, J.H., Pasciak, J.E., Wang, J., and Xu, J., Convergence estimates for product iterative methods with applications to domain decomposition, Math. Comp., 57 (1991), pp. 1–21.CrossRefGoogle Scholar
[6]Brandt, A., Algebraic multigrid theory: The symmetric case, Appl. Math. Comput., 19 (1986), pp. 23–56.Google Scholar
[7]Brandt, A., General highly accurate algebraic coarsening, Electron. Trans. Numer. Anal., 10 (2000), pp. 1–20.Google Scholar
[8]Brandt, A., McCormick, S.F., and Ruge, J.W., Algebraic multigrid (AMG) for sparse matrix equations, in Sparsity and its Application, Evans, D.J., ed., Cambridge University Press, Cambridge, 1984, pp. 257–284.Google Scholar
[9]Brannick, J.J. and Falgout, R.D., Compatible relaxation and coarsening in algebraic multigrid, SIAM J. Sci. Comput., 32 (2010), pp. 1393–1416.CrossRefGoogle Scholar
[10]Brezina, M., Cleary, A.J., Falgout, R.D., Henson, V.E., Jones, J.E., Manteuffel, T.A., McCormick, S.F., and Ruge, J.W., Algebraic multigrid based on element interpolation (AMGe), SIAM J. Sci. Comput., 22 (2000), pp. 1570–1592.CrossRefGoogle Scholar
[11]Brezina, M., Falgout, R., Maclachlan, S., Manteuffel, T., McCormick, S., and Ruge, J., Adaptive smoothed aggregation (αSA), SIAM Review, 47 (2005), pp. 317–346.CrossRefGoogle Scholar
[12]Brezina, M., Ketelsen, C., Manteuffel, T., McCormick, S., Park, M., and Ruge, J., Relaxation-corrected bootstrap algebraic multigrid (rBAMG), Numer. Linear Algebra Appl., 19 (2012), pp. 178–193.CrossRefGoogle Scholar
[13]Brezina, M., Manteuffel, T., McCormick, S., Ruge, J., and Sanders, G., Towards adaptive smoothed aggregation (αSA) for nonsymmetric problems, SIAM J. Sci. Comput., 32 (2010), pp. 14–39.CrossRefGoogle Scholar
[14]Chartier, T., Falgout, R.D., Henson, V.E., Jones, J., Manteuffel, T., McCormick, S., Ruge, J., and Vassilevski, P.S., Spectral AMGe (ρAMGe), SIAM J. Sci. Comput., 25 (2004), pp. 1–26.CrossRefGoogle Scholar
[15]Dendy, J.E., Black box multigrid for nonsymmetric problems, Appl. Math. Comput., 13 (1983), pp. 261–283.Google Scholar
[16]Erlangga, Y.A. and Nabben, R. , Multilevel projection-based nested Krylov iteration for boundary value problems, SIAM J. Sci. Comput., 30 (2008), pp. 1572–1595.CrossRefGoogle Scholar
[17]Falgout, R.D. and Vassilevski, P.S., On generalizing the algebraic multigrid framework, SIAM J. Numer. Anal., 42 (2004), pp. 1669–1693.CrossRefGoogle Scholar
[18]Falgout, R.D., Vassilevski, P.S., and Zikatanov, L.T., On two-grid convergence estimates, Numer. Linear Algebra Appl., 12 (2005), pp. 471–494.CrossRefGoogle Scholar
[19]Frank, J. and Vuik, C., On the construction of deflation-based preconditioners, SIAM J. Sci. Comput., 23 (2001), pp. 442–462.CrossRefGoogle Scholar
[20]Hackbusch, W., Convergence of multi-grid iterations applied to difference equations, Math. Comp., 34 (1980), pp. 425–440.Google Scholar
[21]Hackbusch, W., Multi-grid Methods and Applications, Springer, Berlin, 1985.CrossRefGoogle Scholar
[22]Hogben, L., ed., Handbook of Linear Algebra, CRC Press, Boca Raton, 2007.Google Scholar
[23]Horn, R. and Johnson, C., Matrix Analysis, 2nd Ed., Cambridge University Press, New York, 2013.Google Scholar
[24]Livne, O.E., Coarsening by compatible relaxation, Numer. Linear Algebra Appl., 11 (2004), pp. 205–227.CrossRefGoogle Scholar
[25]Maclachlan, S.P. and Olson, L.N., Theoretical bounds for algebraic multigrid performance: review and analysis, Numer. Linear Algebra Appl., 21 (2014), pp. 194–220.CrossRefGoogle Scholar
[26]Maitre, J. and Musy, F., Algebraic formalization of the multigrid method in the symmetric and positive definite case – a convergence estimation for the V-cycle, in Multigrid Methods for Integral and Differential Equations (Bristol, 1983), Paddon, D. and Holsein, H., eds., vol. 3 of Institute of Mathematics and Its Applications Conference Series, Oxford, 1985, Clarendon Press, p. 213223.Google Scholar
[27]Mandel, J., Algebraic study of multigrid methods for symmetric, definite problems, Appl. Math. Comput., 25 (1988), pp. 39–56.Google Scholar
[28]Mandel, J., Balancing domain decomposition, Comm. Numer. Methods Engrg., 9 (1993), pp. 233–241.CrossRefGoogle Scholar
[29]Mandel, J. and Brezina, M., Balancing domain decomposition for problems with large jumps in coefficients, Math. Comp., 65 (1996), pp. 1387–1401.CrossRefGoogle Scholar
[30]Mandel, J., McCormick, S.F., and Ruge, J.W., An algebraic theory for multigrid methods for variational problems, SIAM J. Numer. Anal., 25 (1988), pp. 91–110.CrossRefGoogle Scholar
[31]McCormick, S., An algebraic interpretation of multigrid methods, SIAM J. Numer. Anal., 19 (1982), pp. 548–560.CrossRefGoogle Scholar
[32]McCormick, S., Multigrid methods for variational problems: Further results, SIAM J. Numer. Anal., 21 (1984), pp. 255–263.CrossRefGoogle Scholar
[33]McCormick, S., Multigrid methods for variational problems: general theory for the V-cycle, SIAM J. Numer. Anal., 22 (1985), pp. 634–643.CrossRefGoogle Scholar
[34]Nabben, R. and Vuik, C., A comparison of deflation and coarse grid correction applied to porous media flow, SIAM J. Numer. Anal., 42 (2004), pp. 1631–1647.CrossRefGoogle Scholar
[35]Nabben, R. and Vuik, C., A comparison of deflation and the balancing preconditioner, SIAM J. Sci. Comput., 27 (2006), pp. 1742–1759.CrossRefGoogle Scholar
[36]Nabben, R. and Vuik, C., A comparison of abstract versions of deflation, balancing and additive coarse grid correction preconditioners, Numer. Linear Algebra Appl., 15 (2008), pp. 355–372.CrossRefGoogle Scholar
[37]Napov, A. and Notay, Y., Comparison of bounds for V-cycle multigrid, Appl. Numer. Math., 60 (2010), pp. 176–192.CrossRefGoogle Scholar
[38]Napov, A. and Notay, Y., Algebraic analysis of aggregation-based multigrid, Numer. Linear Algebra Appl., 18 (2011), pp. 539–564.CrossRefGoogle Scholar
[39]Napov, A. and Notay, Y., An algebraic multigrid method with guaranteed convergence rate, SIAM J. Sci. Comput., 34 (2012), pp. A1079–A1109.CrossRefGoogle Scholar
[40]Notay, Y., Algebraic multigrid and algebraic multilevel methods: A theoretical comparison, Numer. Linear Algebra Appl., 12 (2005), pp. 419–451.CrossRefGoogle Scholar
[41]Notay, Y., Convergence analysis of perturbed two-grid and multigrid methods, SIAM J. Numer. Anal., 45 (2007), pp. 1035–1044.CrossRefGoogle Scholar
[42]Notay, Y., Algebraic analysis of two-grid methods: The nonsymmetric case, Numer. Linear Algebra Appl., 17 (2010), pp. 73–96.CrossRefGoogle Scholar
[43]Notay, Y., Aggregation-based algebraic multigrid for convection-diffusion equations, SIAM J. Sci. Comput., 34 (2012), pp. A2288–A2316.CrossRefGoogle Scholar
[44]Notay, Y. and Napov, A., Further comparison of additive and multiplicative coarse grid correction, Appl. Numer. Math., 65 (2013), pp. 53–62.CrossRefGoogle Scholar
[45]Notay, Y. and Vassilevski, P.S., Recursive Krylov-based multigrid cycles, Numer. Linear Algebra Appl., 15 (2008), pp. 473–487.CrossRefGoogle Scholar
[46]Oswald, P., Multilevel Finite Element Approximation: Theory and Applications, Teubner Skripte zur Numerik, Teubner, Stuttgart, 1994.Google Scholar
[47]Quarteroni, A. and Valli, A., Domain Decomposition Methods for Partial Differential Equations, Oxford Science Publications, Oxford, 1999.CrossRefGoogle Scholar
[48]Ruge, J.W. and Stüben, K., Algebraic multigrid (AMG), in Multigrid Methods, McCormick, S.F., ed., vol. 3 of Frontiers in Applied Mathematics, SIAM, Philadelphia, PA, 1987, pp. 73–130.CrossRefGoogle Scholar
[49]Sala, M. and Tuminaro, R.S., A new Petrov-Galerkin smoothed aggregation preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput., 31 (2008), pp. 143–166.CrossRefGoogle Scholar
[50]Smith, B., Bjørstad, P., and Gropp, W., Domain Decomposition, Cambridge University Press, Cambridge, 1996.Google Scholar
[51]Stüben, K., An introduction to algebraic multigrid, in Trottenberg, et al. [55], 2001, pp. 413–532. Appendix A.Google Scholar
[52]Tang, J., Maclachlan, S., Nabben, R., and Vuik, C., A comparison of two-level preconditioners based on multigrid and deflation, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1715–1739.CrossRefGoogle Scholar
[53]Tang, J., Nabben, R., Vuik, C., and Erlangga, Y., Comparison of two-level preconditioners derived fromdeflation, domain decomposition and multigrid methods, J. Sci. Comput., 39 (2009), pp. 340–370.CrossRefGoogle Scholar
[54]Toselli, A. and Widlund, W., Domain Decomposition, Springer Ser. Comput. Math. 34, Springer-Verlag, Berlin, 2005.Google Scholar
[55]Trottenberg, U., Oosterlee, C.W., and Schüller, A., Multigrid, Academic Press, London, 2001.Google Scholar
[56]Vaněk, P., Brezina, M., and Mandel, J., Convergence of algebraic multigrid based on smoothed aggregation, Numer. Math., 88 (2001), pp. 559–579.Google Scholar
[57]Vassilevski, P.S., Multilevel Block Factorization Preconditioners, Springer, New York, 2008.Google Scholar
[58]Vuik, C., Segal, A., El YAAKOUBI, L., and Dufour, E., A comparison of various deflation vectors applied to elliptic problems with discontinuous coefficients, Appl. Numer. Math., 41 (2002), pp. 219–233.CrossRefGoogle Scholar
[59]Vuik, C., Segal, A., and Meijerink, J.A., An efficient preconditioned cg method for the solution of a class of layered problems with extreme contrasts in the coefficients, J. Comput. Physics, 152 (1999), pp. 385–403.CrossRefGoogle Scholar
[60]Vuik, C., Segal, A., Meijerink, J.A., and Wijma, G.T., The construction of projection vectors for a deflated ICCG method applied to problems with extreme contrasts in the coefficients, J. Comput. Physics, 172 (2001), pp. 426–450.CrossRefGoogle Scholar
[61]Wienands, R. and Oosterlee, C.W., On three-grid Fourier analysis for multigrid, SIAM J. Sci. Comput., 23 (2001), pp. 651–671.CrossRefGoogle Scholar
[62]Xu, J., Iterative methods by space decomposition and subspace correction, SIAM Review, 34 (1992) , pp. 581–613.CrossRefGoogle Scholar
[63]Yserentant, H., Old and new convergence proofs for multigrid methods, Acta Numer., 2 (1993) , pp. 285–326.CrossRefGoogle Scholar