Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



New convergence estimates for multigrid algorithms

Authors: James H. Bramble and Joseph E. Pasciak
Journal: Math. Comp. 49 (1987), 311-329
MSC: Primary 65Nxx; Secondary 65F10
MathSciNet review: 906174
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, new convergence estimates are proved for both symmetric and nonsymmetric multigrid algorithms applied to symmetric positive definite problems. Our theory relates the convergence of multigrid algorithms to a "regularity and approximation" parameter $ \alpha \in (0,1]$ and the number of relaxations m. We show that for the symmetric and nonsymmetric $ \mathcal{V}$ cycles, the multigrid iteration converges for any positive m at a rate which deteriorates no worse than $ 1 - c{j^{ - (1 - \alpha )/\alpha }}$, where j is the number of grid levels. We then define a generalized $ \mathcal{V}$ cycle algorithm which involves exponentially increasing (for example, doubling) the number of smoothings on successively coarser grids. We show that the resulting symmetric and nonsymmetric multigrid iterations converge for any $ \alpha $ with rates that are independent of the mesh size. The theory is presented in an abstract setting which can be applied to finite element multigrid and finite difference multigrid methods.

References [Enhancements On Off] (What's this?)

  • [1] A. K. Aziz & I. Babuška, "Survey lectures on the mathematical foundations of the finite element method," in The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations. Part I (A. K. Aziz, ed.), Academic Press, New York, 1972, pp. 1-362. MR 0421106 (54:9111)
  • [2] R. E. Bank & C. C. Douglas, "Sharp estimates for multigrid rates of convergence with general smoothing and acceleration," SIAM J. Numer. Anal., v. 22, 1985, pp. 617-633. MR 795944 (86j:65037)
  • [3] R. E. Bank & T. F. Dupont, "An optimal order process for solving elliptic finite element equations," Math. Comp., v. 36, 1981, pp. 35-51. MR 595040 (82b:65113)
  • [4] D. Braess & W. Hackbusch, "A new convergence proof for the multigrid method including the V-cycle," SIAM J. Numer. Anal., v. 20, 1983, pp. 967-975. MR 714691 (85h:65233)
  • [5] A. Brandt, "Multi-level adaptive solutions to boundary-value problems," Math. Comp., v. 31, 1977, pp. 333-390. MR 0431719 (55:4714)
  • [6] P. G. Ciarlet, The Finite Element Method for Elliptic Problems, North-Holland, New York, 1978. MR 0520174 (58:25001)
  • [7] T. Dupont, R. P. Kendall & H. H. Rachford, "An approximate factorization procedure for solving self-adjoint elliptic difference equations," SIAM J. Numer. Anal., v. 5, 1968, pp. 559-573. MR 0235748 (38:4051)
  • [8] R. P. Fedorenko, "The speed of convergence of one iterative process," USSR Comput. Math. and Math. Phys., v. 1, 1961, pp. 1092-1096.
  • [9] W. Hackbusch, Multi-Grid Methods and Applications, Springer-Verlag, New York, 1985.
  • [10] J. L. Lions & E. Magenes, Problèmes aux Limites non Homogènes et Applications, Dunod, Paris, 1968.
  • [11] J. F. Maitre & F. Musy, "Algebraic normalization of the multigrid method in the symmetric and positive definite case--a convergence estimation for the V-cycle," Multigrid Methods for Integral and Differential Equations (D. J. Paddon and H. Holstein, eds.), Clarendon Press, Oxford, 1985. MR 849375 (87i:65044)
  • [12] J. Mandel, "Multigrid convergence for nonsymmetric, indefinite variational problems and one smoothing step," in Proc. Copper Mtn. Conf. Multigrid Methods, Applied Math. Comput., 1986, pp. 201-216. MR 849837 (87i:65097)
  • [13] J. Mandel, "Algebraic study of multigrid methods for symmetric, definite problems." (Preprint) MR 923402 (89d:65036)
  • [14] J. Mandel, S. F. McCormick & J. Ruge, "An algebraic theory for multigrid methods for variational problems." (Preprint)
  • [15] S. F. McCormick, "Multigrid methods for variational problems: Further results," SIAM J. Numer. Anal., v. 21, 1984, pp. 255-263. MR 736329 (85h:65115)
  • [16] S. F. McCormick, "Multigrid methods for variational problems: General theory for the V-cycle," SIAM J. Numer. Anal., v. 22, 1985, pp. 634-643. MR 795945 (86m:65030)
  • [17] J. Nečas, Les Méthodes Directes en Théorie des Équations Elliptiques, Academia, Prague, 1967.
  • [18] R. A. Nicolaides, "On the $ {l^2}$ convergence of an algorithm for solving finite element equations," Math. Comp., v. 31, 1977, pp. 892-906. MR 0488722 (58:8239)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65Nxx, 65F10

Retrieve articles in all journals with MSC: 65Nxx, 65F10

Additional Information

Article copyright: © Copyright 1987 American Mathematical Society

American Mathematical Society