Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Convergence of the multigrid $V$-cycle algorithm for second-order boundary value problems without full elliptic regularity

Author: Susanne C. Brenner
Journal: Math. Comp. 71 (2002), 507-525
MSC (2000): Primary 65N55, 65N30
Published electronically: November 19, 2001
MathSciNet review: 1885612
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The multigrid $V$-cycle algorithm using the Richardson relaxation scheme as the smoother is studied in this paper. For second-order elliptic boundary value problems, the contraction number of the $V$-cycle algorithm is shown to improve uniformly with the increase of the number of smoothing steps, without assuming full elliptic regularity. As a consequence, the $V$-cycle convergence result of Braess and Hackbusch is generalized to problems without full elliptic regularity.

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

  • 1. R.E. Bank and C.C. Douglas, Sharp estimates for multigrid rates of convergence with general smoothing and acceleration, SIAM J. Numer. Anal. 22 (1985), 617-633. MR 86j:65037
  • 2. R.E. Bank and T.F. Dupont, An optimal order process for solving finite element equations, Math. Comp. 36 (1981), 35-51. MR 82b:65113
  • 3. C. Bennett and R. Sharpley, Interpolation of operators, Academic Press, Boston, 1988. MR 89e:46001
  • 4. D. Braess and W. Hackbusch, A new convergence proof for the multigrid method including the V-cycle, SIAM J. Numer. Anal. 20 (1983), 967-975. MR 85h:65233
  • 5. J.H. Bramble, Multigrid Methods, Pitman Research Notes in Mathematics Series 294, Longman Scientific & Technical, New York, 1993. MR 95b:65002
  • 6. J.H. Bramble and S.R. Hilbert, Estimation of linear functionals on Sobolev spaces with application to Fourier transforms and spline interpolation, SIAM J. Numer. Anal. 7 (1970), 113-124. MR 41:7819
  • 7. J.H. Bramble and J.E. Pasciak, New convergence estimates for multigrid algorithms, Math. Comp. 49 (1987), 311-329. MR 89b:65234
  • 8. -, New estimates for multigrid algorithms including the V-cycle, Math. Comp. 60 (1993), 447-471. MR 94a:65064
  • 9. -, Uniform convergence estimates for multigrid $V$-cycle algorithms with less than full elliptic regularity, Domain Decomposition Methods in Science and Engineering (Como, 1992), Contemp. Math. 157, Amer. Math. Soc., Providence, RI, 1994, pp. 17-26. MR 95f:65202
  • 10. J.H. Bramble and X. Zhang, The analysis of multigrid methods, Handb. Numer. Anal. VII, North-Holland, Amsterdam, 2000, 173-415. CMP 2001:08
  • 11. -, Uniform convergence of the multigrid $V$-cycle for an anisotropic problem, Math. Comp. 70 (2001), 453-470.
  • 12. S.C. Brenner, Multigrid methods for the computation of singular solutions and stress intensity factors I: Corner singularities, Math. Comp. 68 (1999), 559-583. MR 99i:65138
  • 13. -, A nonstandard finite element interpolation estimate, Numer. Funct. Anal. Optim. 20 (1999), 245-250. MR 2000b:65210
  • 14. S.C. Brenner and L.R. Scott, The mathematical theory of finite element methods, Springer-Verlag, New York-Berlin-Heidelberg, 1994. MR 95f:65001
  • 15. S.C. Brenner and L.-Y. Sung, Multigrid methods for the computation of singular solutions and stress intensity factors II: Crack singularities, BIT 37 (1997), 623-643. MR 99i:65139
  • 16. P.-G. Ciarlet, The Finite Element Method for Elliptic Problems, North Holland, Amsterdam-New York-Oxford, 1978. MR 58:25001
  • 17. P. Clément, Approximation by finite element functions using local regularization, R.A.I.R.O. Sér. Rouge Anal. Numér. 9 (1975), 77-84. MR 53:4569
  • 18. M. Dauge, Elliptic boundary value problems on corner domains (Lecture Notes in Mathematics 1341), Springer-Verlag, Berlin-Heidelberg, 1988. MR 91a:35078
  • 19. T. Dupont and R. Scott, Polynomial approximation of functions in Sobolev spaces, Math. Comp. 34 (1980), 441-463. MR 81h:65014
  • 20. M. Griebel and P. Oswald, On the abstract theory of additive and multiplicative Schwarz algorithms, Numer. Math. 70 (1995), 163-180. MR 96a:65164
  • 21. P. Grisvard, Elliptic problems in nonsmooth domains, Pitman, Boston, 1985. MR 86m:35044
  • 22. W. Hackbusch, Multigrid convergence theory, Proceedings of the Conference Held at Köln-Porz, November 23-27, 1981 (W. Hackbusch and U. Trottenberg, eds.), Lecture Notes in Mathematics 960, Springer-Verlag, Berlin, 1982, pp. 177-219. MR 84k:65113
  • 23. -, Multigrid methods and applications, Springer-Verlag, Berlin, 1985. MR 87e:65082
  • 24. G.H. Hardy, J.E. Littlewood and G. Pólya, Inequalities, Cambridge University Press, Cambridge, 1934.
  • 25. J. Mandel, S. McCormick and R. Bank, Variational multigrid theory, Multigrid Methods (S.F. McCormick, ed.), Frontiers In Applied Mathematics 3, SIAM, Philadelphia, 1987, pp. 131-177. CMP 21:05
  • 26. S.F. McCormick, Multigrid methods for variational problems: further results, SIAM J. Numer. Anal. 21 (1984), 255-263. MR 85h:65115
  • 27. S.A. Nazarov and B.A. Plamenevsky, Elliptic problems in domains with piecewise smooth boundaries, Expositions in Mathematics 13, de Gruyter, Berlin-New York, 1994. MR 95h:35001
  • 28. N. Neuss, $V$-cycle convergence with unsymmetric smoothers and applications to an anisotropic model problem, SIAM J. Numer. Anal. 35 (1998), 1201-1212.
  • 29. L.R. Scott and S. Zhang, Finite element interpolation of nonsmooth functions satisfying boundary conditions, Math. Comp. 54 (1990), 483-493. MR 90j:65021
  • 30. H. Triebel, Interpolation theory, function spaces, differential operators, North-Holland, Amsterdam, 1978. MR 80i:46032b
  • 31. J. Xu, Iterative methods by space decomposition and subspace correction, SIAM Review 34 (1992), 581-613. MR 93k:65029
  • 32. H. Yserentant, Old and new convergence proofs for multigrid methods, Acta Numer. (1993), 285-326. MR 94i:65128
  • 33. X. Zhang, Multilevel Schwarz methods, Numer. Math. 63 (1992), 521-539. MR 93h:650247

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65N55, 65N30

Retrieve articles in all journals with MSC (2000): 65N55, 65N30

Additional Information

Susanne C. Brenner
Affiliation: Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208

Keywords: $V$-cycle multigrid algorithm, second-order boundary value problems without full elliptic regularity
Received by editor(s): August 18, 1999
Received by editor(s) in revised form: October 27, 1999, and July 10, 2000
Published electronically: November 19, 2001
Additional Notes: This work was supported in part by the National Science Foundation under Grant Nos. DMS-96-00133 and DMS-00-74246.
Article copyright: © Copyright 2001 American Mathematical Society