Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Convergence of nonconforming $V$-cycle and $F$-cycle multigrid algorithms for second order elliptic boundary value problems

Author: Susanne C. Brenner
Journal: Math. Comp. 73 (2004), 1041-1066
MSC (2000): Primary 65N55, 65N30
Published electronically: August 19, 2003
MathSciNet review: 2047077
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The convergence of $V$-cycle and $F$-cycle multigrid algorithms with a sufficiently large number of smoothing steps is established for nonconforming finite element methods for second order elliptic boundary value problems.

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

  • 1. T. Arbogast and Z. Chen, On the implementation of mixed methods as nonconforming methods for second order elliptic problems, Math. Comp. 64 (1995), 943-972. MR 95k:65102
  • 2. D.N. Arnold and F. Brezzi, Mixed and nonconforming finite element methods: implementation, postprocessing and error estimates, R.A.I.R.O Modél. Math. Anal. Numér. 19 (1985), 7-32. MR 87g:65126
  • 3. 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
  • 4. 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
  • 5. 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
  • 6. D. Braess and R. Verfürth, Multigrid methods for nonconforming finite element methods, SIAM J. Numer. Anal. 27 (1990), 979-986. MR 91j:65164
  • 7. J.H. Bramble, Multigrid Methods, Longman Scientific & Technical, Essex, 1993. MR 95b:65002
  • 8. J.H. Bramble and S.R. Hilbert, Estimation of linear functionals on Sobolev spaces with applications to Fourier transforms and spline interpolation, SIAM J. Numer. Anal. 7 (1970), 113-124. MR 41:7819
  • 9. J.H. Bramble and J.E. Pasciak, New convergence estimates for multigrid algorithms, Math. Comp. 49 (1987), 311-329. MR 89b:65234
  • 10. -, New estimates for multigrid algorithms including the V-cycle, Math. Comp. 60 (1993), 447-471. MR 94a:65064
  • 11. -, Uniform convergence estimates for multigrid V-cycle algorithms with less than full elliptic regularity, Domain Decomposition Methods in Science and Engineering (A. Quarteroni et al., ed.), Amer. Math. Soc., Providence, 1994, Contemporary Mathematics 157, pp. 17-26. MR 95f:65202
  • 12. J.H. Bramble, J.E. Pasciak, J. Wang, and J. Xu, Convergence estimates for multigrid algorithms without regularity assumptions, Math. Comp. 57 (1991), 23-45. MR 91m:65158
  • 13. -, Convergence estimates for product iterative methods with applications to domain decomposition and multigrid, Math. Comp. 57 (1991), 1-21. MR 92d:65094
  • 14. J.H. Bramble, J.E. Pasciak, and J. Xu, The analysis of multigrid algorithms with nonnested spaces or noninherited quadratic forms, Math. Comp. 56 (1991), 1-34. MR 91h:65159
  • 15. J.H. Bramble and J. Xu, Some estimates for a weighted $L^2$ projection, Math. Comp. 56 (1991), 463-476.MR 91k:65140
  • 16. J.H. Bramble and X. Zhang, The Analysis of Multigrid Methods, Handbook of Numerical Analysis, VII (P.G. Ciarlet and J.L. Lions, eds.), North-Holland, Amsterdam, 2000, pp. 173-415.MR 2001m:65183
  • 17. A. Brandt, Multigrid solvers for non-elliptic and singular-perturbation steady-state problems, Weizmann Institute of Science, Rehovot, Israel, 1981.
  • 18. S.C. Brenner, Multigrid methods for nonconforming finite elements, Proceedings of the Fifth Copper Mountain Conference on Multigrid Methods (J. Mandel et al., ed.), SIAM, Philadelphia, 1989, pp. 54-65.MR 91h:65189
  • 19. -, An optimal-order multigrid method for $\mathrm{P}1$ nonconforming finite elements, Math. Comp. 52 (1989), 1-15.MR 89f:65119
  • 20. -, A multigrid algorithm for the lowest-order Raviart-Thomas mixed triangular finite element method, SIAM J. Numer. Anal. 29 (1992), 647-678.MR 93j:65175
  • 21. -, Convergence of nonconforming multigrid methods without full elliptic regularity, Math. Comp. 68 (1999), 25-53.MR 99c:65229
  • 22. -, Convergence of the multigrid V-cycle algorithm for second order boundary value problems without full elliptic regularity, Math. Comp. 71 (2002), 507-525.MR 2003b:65132
  • 23. -, Smoothers, mesh dependent norms, interpolation and multigrid, Appl. Numer. Math. 43 (2002), 45-56.
  • 24. -, Poincaré-Friedrichs inequalities for piecewise $H^1$ functions, SIAM J. Numer. Anal. 41 (2003), 306-324 (electronic).
  • 25. S.C. Brenner and L.R. Scott, The Mathematical Theory of Finite Element Methods $($Second Edition$)$, Springer-Verlag, New York-Berlin-Heidelberg, 2002.MR 2003a:65103
  • 26. F. Brezzi, M. Fortin, and R. Stenberg, Error analysis of mixed-interpolated elements for Reissner-Mindlin plates, Math. Models and Methods in Appl. Sci. 1 (1991), 125-151.MR 92e:73030
  • 27. Z. Cai, J. Douglas, Jr., J.E. Santos, D. Sheen, and X. Ye, Nonconforming quadrilateral finite elements: a correction, Calcolo 37 (2000), 253-254.MR 2001k:65169
  • 28. Z. Cai, J. Douglas, Jr., and X. Ye, A stable nonconforming quadrilateral finite element method for the stationary Stokes and Navier-Stokes equations, Calcolo 36 (1999), 215-232.MR 2001b:65122
  • 29. Z. Chen, On the convergence of Galerkin-multigrid methods for nonconforming finite elements, East-West J. Numer. Math. 7 (1999), 79-104.MR 2000e:65116
  • 30. P.G. Ciarlet, The Finite Element Method for Elliptic Problems, North-Holland, Amsterdam, 1978.MR 58:25001
  • 31. M. Crouzeix and P.-A. Raviart, Conforming and nonconforming finite element methods for solving the stationary Stokes equations I, RAIRO Anal. Numér. 7 (1973), 33-75.MR 49:8401
  • 32. M. Dauge, Elliptic Boundary Value Problems on Corner Domains, Lecture Notes in Mathematics 1341, Springer-Verlag, Berlin-Heidelberg, 1988.MR 91a:35078
  • 33. J. Douglas, Jr., J.E. Santos, D. Sheen, and X. Ye, Nonconforming Galerkin methods based on quadrilateral elements for second order elliptic problems, M$^2$AN Math. Model. Numer. Anal. 33 (1999), 747-770. MR 2000k:65206
  • 34. M. Griebel and P. Oswald, On the abstract theory of additive and multiplicative Schwarz algorithms, Numer. Math. 70 (1995), 163-180.MR 96a:65164
  • 35. W. Hackbusch, Multigrid convergence theory, Multigrid Methods (Lecture Notes in Mathematics 960) (W. Hackbusch and U. Trottenberg, eds.), Springer-Verlag, Berlin, 1982, pp. 177-219.MR 84k:65113
  • 36. -, Multi-grid Methods and Applications, Springer-Verlag, Berlin-Heidelberg-New York-Tokyo, 1985.MR 87e:65082
  • 37. G.H. Hardy, J.E. Littlewood, and G. Pólya, Inequalities, Cambridge University Press, Cambridge, 1934.
  • 38. S.G. Kre{\u{\i}}\kern.15emn, Ju.I. Petunin, and E.M. Semenov, Interpolation of Linear Operators, Translations of Mathematical Monographs 54, American Mathematical Society, Providence, 1982.MR 84j:46103
  • 39. J. Mandel, S. McCormick, and R. Bank, Variational Multigrid Theory, Multigrid Methods, Frontiers In Applied Mathematics 3 (S. McCormick, ed.), SIAM, Philadelphia, 1987, pp. 131-177.
  • 40. J. Mandel and S. Parter, On the multigrid F-cycle, Appl. Math. Comput. 37 (1990), 19-36.MR 91g:65266
  • 41. N. Neuss, V-cycle convergence with unsymmetric smoothers and applications to an anisotropic model problem, SIAM J. Numer. Anal. 35 (1998), 1201-1212.MR 99d:65109
  • 42. R. Rannacher and S. Turek, Simple nonconforming quadrilateral Stokes element, Numer. Meth. PDE 8 (1992), 97-111.MR 92i:65170
  • 43. P.-A. Raviart and J.M. Thomas, A mixed finite element method for second order elliptic problems, Mathematical Aspects of the Finite Element Method, Lecture Notes in Mathematics 606 (I.Galligani and E. Magenes, eds.), Springer-Verlag, Berlin, 1977, pp. 292-315.MR 58:3547
  • 44. Z. Shi and X. Xu, Cascadic multigrid method for elliptic problems, East-West J. Numer. Math 7 (1999), 199-209.MR 2000h:65185
  • 45. -, A V-cycle multigrid method for TRUNC plate element, Comput. Methods Appl. Mech. Engrg. 188 (2000), 483-493.MR 2001g:74059
  • 46. -, V-cycle multigrid methods for Wilson nonconforming element, Sci. China Ser. A 43 (2000), 673-684.MR 2002c:65217
  • 47. R. Stevenson, Nonconforming finite element and the cascadic multi-grid method, Numer. Math. 91 (2002), 351-387.MR 2003c:65139
  • 48. H. Triebel, Interpolation Theory, Function Spaces, Differential Operators, North-Holland, Amsterdam, 1978.MR 80i:46032a
  • 49. U. Trottenberg, C. Oosterlee, and A. Schüller, Multigrid, Academic Press, San Diego, 2001.MR 2002b:65002
  • 50. S. Turek, Efficient Solvers for Incompressible Flow Problems, Springer-Verlag, Berlin, 1999.MR 2000g:76071
  • 51. P. Wesseling, An Introduction to Multigrid Methods, John Wiley & Sons, Chichester, 1992.MR 93g:65006
  • 52. J. Xu, Convergence estimates for some multigrid algorithms, Third International Symposium on Domain Decomposition Methods for Partial Differential Equations, SIAM, Philadelphia, 1990, pp. 174-187. MR 91f:65194
  • 53. -, Iterative methods by space decomposition and subspace correction, SIAM Review 34 (1992), 581-613.MR 93k:65029
  • 54. X. Xu and L. Li, A note on convergence of V-cycle nonconforming multigrid methods, Appl. Math. Comput. 104 (1999), 191-206. MR 2000h:65186
  • 55. -, A V-cycle multigrid method for the plate bending problem discretized by nonconforming finite elements, J. Comput. Math. 17 (1999), 533-544.MR 2000k:65230
  • 56. H. Yserentant, Old and new convergence proofs for multigrid methods, Acta Numerica (1993), 285-326.MR 94i:65128
  • 57. X. Zhang, Multilevel Schwarz methods, Numer. Math. 63 (1992), 521-539.MR 93h:65047
  • 58. J. Zhao, Multigird Methods for Fourth Order Problems, Ph.D. thesis, University of South Carolina, in preparation.

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: Multigrid, $V$-cycle, $F$-cycle, nonconforming finite elements
Received by editor(s): May 29, 2001
Received by editor(s) in revised form: January 10, 2003
Published electronically: August 19, 2003
Additional Notes: This work was supported in part by the National Science Foundation under Grant No. DMS-00-74246.
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society