Abstract
We consider the Fourier analysis of multigrid methods (of Galerkin type) for symmetric positive definite and semi-positive definite linear systems arising from the discretization of scalar partial differential equations (PDEs). We relate the so-called smoothing factor to the actual two-grid convergence rate and also to the convergence rate of the V-cycle multigrid. We derive a two-sided bound that defines an interval containing both the two-grid and V-cycle convergence rate. This interval is narrow and away from 1 when both the smoothing factor and an additional parameter are small enough. Besides the smoothing factor, the convergence mainly depends on the angle between the range of the prolongation and the eigenvectors of the system matrix associated with small eigenvalues. Nice V-cycle convergence is guaranteed if the tangent of this angle has an upper bound proportional to the eigenvalue, whereas nice two-grid convergence requires a bound proportional to the square root of the eigenvalue. We also discuss the well-known rule which relates the order of the prolongation to that of the differential operator associated to the problem. We first define a frequency based order which in most cases amounts to the so-called high frequency order as defined in Hemker (J Comput Appl Math 32:423–429, 1990). We give a firmer basis to the related order rule by showing that, together with the requirement of having the smoothing factor away from one, it provides necessary and sufficient conditions for having the two-grid convergence rate away from 1. A stronger condition is further shown to be sufficient for optimal convergence with the V-cycle. The presented results apply to rigorous Fourier analysis for regular discrete PDEs, and also to local Fourier analysis via the discussion of semi-positive systems as may arise from the discretization of PDEs with periodic boundary conditions.
Similar content being viewed by others
References
Ben Israel A., Greville T.N.E.: Generalized Inverses: Theory and Applications. Wiley, New York (1974)
Brandt A.: Guide to multigrid development. In: Hackbusch, W., Trottenberg, U. (eds) Multigrid Methods. Lectures Notes in Mathematics No. 960, pp. 220–312. Springer, Berlin (1982)
Brandt A.: Rigorous quantitative analysis of multigrid, I: constant coefficients two-level cycle with L2-norm. SIAM J. Numer. Anal. 31, 1695–1730 (1994)
Brezina M., Cleary A.J., Falgout R.D., Henson V.E., Jones J.E., Manteuffel T.A., McCormick S.F., Ruge J.W.: Algebraic multigrid based on element interpolation (AMGe). SIAM J. Sci. Comput. 22, 1570–1592 (2000)
Chartier T., Falgout R.D., Henson V.E., Jones J., Manteuffel T., McCormick S., Ruge J., Vassilevski P.S.: Spectral AMGe (ρAMGe). SIAM J. Sci. Comput. 25, 1–26 (2004)
Donatelli M.: An algebraic generalization of local fourier analysis for grid transfer operators in multigrid based on Toeplitz matrices. Numer. Linear Algebra Appl. 17, 179–197 (2010)
Hackbusch W.: Multi-grid Methods and Applications. Springer, Berlin (1985)
Hemker P.: On the order of prolongations and restrictions in multigrid procedures. J. Comput. Appl. Math. 32, 423–429 (1990)
Mandel J., McCormick S.F., Ruge J.W.: An algebraic theory for multigrid methods for variational problems. SIAM J. Numer. Anal. 25, 91–110 (1988)
McCormick S.F.: Multigrid methods for variational problems: general theory for the V-cycle. SIAM J. Numer. Anal. 22, 634–643 (1985)
Muresan A.C., Notay Y.: Analysis of aggregation-based multigrid. SIAM J. Sci. Comput. 30, 1082–1103 (2008)
Napov, A.: Algebraic analysis of V-cycle multigrid and aggregation-based two-grid methods. PhD thesis, Service de Métrologie Nucléaire, Université Libre de Bruxelles, Brussels, Belgium (2010)
Napov A., Notay Y.: Comparison of bounds for V-cycle multigrid. Appl. Numer. Math. 60, 176–192 (2010)
Napov A., Notay Y.: When does two-grid optimality carry over to the V-cycle?. Numer. Linear Algebra Appl. 17, 273–290 (2010)
Ruge J.W., Stüben K.: Algebraic multigrid (AMG). In: McCormick, S.F. (eds) Multigrid Methods. Frontiers in Applied Mathematics, vol. 3, pp. 73–130. SIAM, Philadelphia (1987)
Serra-Capizzano S.: Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix-sequences. Numerische Mathematik 92, 433–465 (2002)
Stevenson, R.: On the validity of local mode analysis of multi-grid methods. PhD thesis, Utrecht University (1990)
Stevenson R.: More on the order of prolongations and restrictions. Appl. Numer. Math. 58, 1875–1880 (2007)
Stüben K., Trottenberg K.U.: Multigrid methods: fundamental algorithms, model problem analysis and applications. In: Hackbusch, W., Trottenberg, U. (eds) Multigrid Methods. Lectures Notes in Mathematics No. 960, pp. 1–176. Springer, Berlin (1982)
Trottenberg U., Oosterlee C.W., Schüller A.: Multigrid. Academic Press, London (2001)
Vassilevski P.S.: Multilevel Block Factorization Preconditioners. Springer, New York (2008)
Wesseling P.: An Introduction to Multigrid Methods. Wiley, Chichester (1992)
Wienands R., Joppich W.: Practical Fourier Analysis for Multigrid Methods. Chapman & Hall/CRC Press, Boca Raton (2005)
Wienands R., Oosterlee C.W.: On three-grid Fourier analysis for multigrid. SIAM J. Sci. Comput. 23, 651–671 (2001)
Yavneh I.: Coarse-grid correction for nonelliptic and singular perturbation problems. SIAM J. Sci. Comput. 19, 1682–1699 (1998)
Author information
Authors and Affiliations
Corresponding author
Additional information
A. Napov was supported by the Belgian FNRS (“Aspirant”). Y. Notay was supported by the Belgian FNRS (“Directeur de recherches”).
Rights and permissions
About this article
Cite this article
Napov, A., Notay, Y. Smoothing factor, order of prolongation and actual multigrid convergence. Numer. Math. 118, 457–483 (2011). https://doi.org/10.1007/s00211-011-0362-7
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00211-011-0362-7