Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



A generalized BPX multigrid framework covering nonnested V-cycle methods

Authors: Huo-Yuan Duan, Shao-Qin Gao, Roger C. E. Tan and Shangyou Zhang
Journal: Math. Comp. 76 (2007), 137-152
MSC (2000): Primary 65N55, 65N30, 65F10
Published electronically: August 31, 2006
Erratum: Math. Comp 76 (2007), 2251
MathSciNet review: 2261015
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: More than a decade ago, Bramble, Pasciak and Xu developed a framework in analyzing the multigrid methods with nonnested spaces or noninherited quadratic forms. It was subsequently known as the BPX multigrid framework, which was widely used in the analysis of multigrid and domain decomposition methods. However, the framework has an apparent limit in the analysis of nonnested V-cycle methods, and it produces a variable V-cycle, or nonuniform convergence rate V-cycle methods, or other nonoptimal results in analysis thus far.

This paper completes a long-time effort in extending the BPX multigrid framework so that it truly covers the nonnested V-cycle. We will apply the extended BPX framework to the analysis of many V-cycle nonnested multigrid methods. Some of them were proven previously only for two-level and W-cycle iterations. Some numerical results are presented to support the theoretical analysis of this paper.

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

  • 1. R.E. Bank and T. Dupont, An optimal order process for solving finite element equations, Math. Comp., 36(1981), 35-51. MR 0595040 (82b:65113) 10pt
  • 2. D. Braess, M. Dryja and W. Hackbusch, A multigrid method for nonconforming FE-discretizations, with application to no-matching grids, Computing, 63(1999), 1-25. MR 1702163 (2000h:65048)
  • 3. 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 0714691 (85h:65233)
  • 4. D. Braess and R. Verfürth, Multigrid methods for nonconforming finite element methods, SIAM J. Numer. Anal., 27(1990), 979-986.MR 1051117 (91j:65164)
  • 5. J. H. Bramble, Multigrid Methods, Pitman Research Notes in Mathematics, V. 294, John Wiley and Sons, 1993. MR 1247694 (95b:65002)
  • 6. J. H. Bramble, D.Y. Kwak and J. E. Pasciak, Uniform convergence of multigrid V-cycle iterations for indefinite and nonsymmetric problems, SIAM J. Numer. Anal., 31(1994), 1746-1763. MR 1302683 (95i:65170)
  • 7. J. H. Bramble and J.E. Pasciak, New convergence estimates for multigrid algorithms, Math. Comp., 49 (1987), 311-329.MR 0906174 (89b:65234)
  • 8. J. H. Bramble and J. E. Pasciak, The analysis of smoothers for multigrid algorithms, Math. Comp., 58(1992) 453-470.MR 1122058 (92f:65146)
  • 9. J. H. Bramble and J. E. Pasciak, New estimates for multilevel algorithms including the V-cycle, Math. Comp., 60(1993) 447-471. MR 1176705 (94a:65064)
  • 10. J. H. Bramble and J. E. Pasicak, Uniform convergence estimates for multigrid V-cycle algorithms with less than full elliptic regularity, in: Domain Decomposition methods in science andEngineering, A. Quarteroni, J. Periaux, Y. A. Kuznetsov and O. B. Widlund, Eds, Contemporary Mathematics Series 157 Am. Math. Soc. (1994) 17-26. MR 1262601 (95f:65202)
  • 11. 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 1052086 (91h:65159)
  • 12. J. H. Bramble and X. Zhang, Uniform convergence of the multigrid V-cycle for an anisotropic problem, Math. Comp., 70(2001), 979-986. MR 1709148 (2001g:65134)
  • 13. S. C. Brenner, An optimal-order multigrid method for $ {\mathcal P}_1$ nonconforming finite elements, Math. Comp., 52(1989), 1-15.MR 0946598 (89f:65119)
  • 14. S. C. Brenner, A nonconforming multigrid method for the stationary Stokes equations, Math. Comp., 55(1990), 411-437. MR 1035927 (91d:65167)
  • 15. S. C. Brenner, Convergence of nonconforming multigrid methods without full elliptic regularity, Math. Comp., 68(1999), 25-53. MR 1620215 (99c:65229)
  • 16. S. C. Brenner, Convergence of the multigrid V-cycle algorithms for second order boundary value problems without full elliptic regularity, Math. Comp., 71 (2002), 507-525. MR 1885612 (2003b:65132)
  • 17. S. C. Brenner, Convergence of nonconforming V-cycle and F-cycle multigrid algorithms for second order elliptic boundary value problems, Math. Comp., 73 (2004), 1041-1066. MR 2047077 (2005f:65167)
  • 18. S. C. Brenner and L. R. Scott, The Mathematical Theory of Finite Element Methods, Springer-Verlag, New-York, (1996). MR 1278258 (95f:65001)
  • 19. P. G. Ciarlet, The Finite Element Method for Elliptic Problems, North-Holland, Amsterdam, (1978). MR 0520174 (58:25001)
  • 20. Z. Chen, On the convergence of Galerkin-multigrid methods for nonconforming finite elements, East-West J. Numer. Math., 7(1999), 79-107.MR 1699247 (2000e:65116)
  • 21. Z. Chen, On the convergence of nonnested multigrid methods with nested spaces on coarse grids, Numer. Methods PDE, 16(2000), 265-284. MR 1752413 (2001c:65154)
  • 22. Z. Chen and P. Oswald, Multigrid and multilevel methods for nonconforming rotated $ Q1$ elements, Math. Comp., 67(1998), 667-693. MR 1451319 (98g:65118)
  • 23. Q. Deng and X. Feng, Multigrid methods for the generalized Stokes equations based on mixed finite element methods, J. Comp. Math., 20(2002), 129-152.MR 1884415 (2002k:76084)
  • 24. C.I. Goldstein, Multigrid analysis of finite element methods with numerical integration, Math. Comp., 56(1991), 409-436. MR 1066832 (91h:65190)
  • 25. J. Gopalakrishnan and J. E. Pasciak, Multigrid for the Mortar finite element method, SIAM J. Numer. Anal. 37 (2000) 1029-1052. MR 1749248 (2001b:65124)
  • 26. J.Gopalakrishnan and G. Kanschat, Application of unified DG analysis to preconditioning DG methods, in: Bathe, K. J. eds., Computational Fluid and Solid Mechanics 2003, Elsevier, Amsterdam, (2003) 1943-1945. MR 2029558 (2004i:74002)
  • 27. J.Gopalakrishnan and G. Kanschat, A multilevel discontinuous Galerkin method, Numer. Math. 95 (2003) 527-550. MR 2012931 (2004m:65179)
  • 28. W. Hackbusch, Multi-grid Methods and Applications, Springer-Verlag, Berlin, 1985. MR 0814495 (87e:65082) 15pt
  • 29. C. Lee, A nonconforming multigrid method using conforming subspaces, in: Proc. Sixth Copper Mountain Conf. on Multigrid Methods, N. Melson et al., eds, NASA Conference Publication 3224, Part 1, Washington, DC, 1993, 317-330.
  • 30. P. Monk and S. Zhang, Multigrid computation of vector potentials, J. Comp. Appl. Math. 62 (1995), 301-320. MR 1363678 (96h:65149)
  • 31. S. F. McCormick, ed., Multigrid Methods, SIAM Frontiers in Applied Mathematics, Philadelphia, 1987. MR 0972752 (89m:65004)
  • 32. L. R. Scott and S. Zhang, Higher-dimensional nonnested multigrid methods, Math. Comp. 58 (1992), 457-466. MR 1122077 (92g:65133)
  • 33. V. V. Shaidurov, Multigrid Methods for Finite Elements, Kluwer Academic, the Netherlands, 1989. MR 1335921 (97e:65142)
  • 34. R. Stevevson, An analysis of nonconforming multi-grid methods, leading to an improved method for the Morley element, Math. Comp. 72 (2002), 55-81. MR 1933814 (2003i:65127)
  • 35. G. Strang and G. J. Fix, An Analysis of the Finite Element Method, Prentice-Hall, Englewood Cliffs, NJ, 1973. MR 0443377 (56:1747)
  • 36. S. Turek, Multigrid techniques for a divergence free finite element discretization, East-West J, Numer. Math., 2(1994), 229-255. MR 1296984 (96c:65195)
  • 37. J. Wang, Convergence analysis of multigrid algorithms for nonselfadjoint and indefinite elliptic problems, SIAM J. Numer. Anal. 30 (1993), 275-285. MR 1202666 (93k:65100)
  • 38. J. Xu, Theory of Multilevel Methods, PhD thesis, Cornell University, 1989.
  • 39. X. Xu and J. Chen, Multigrid for the mortar element method for P1 nonconforming element, Numer. Math. 88 (2001), 381-398. MR 1826859 (2002d:65146)
  • 40. X. Xu , L. Li and W. Chen, A multigrid method for the mortar-type Morley element approximation of a plate bending problem, SIAM J. Numer. Anal. 39 (2002), 1712-1731. MR 1885713 (2002m:74050)
  • 41. X. Yu, Multigrid method of nonconforming Wilson finite element, Math. Numer. Sinica, 14(1993), 346-351. MR 1391414 (97b:65143)
  • 42. S. Zhang, Optimal order nonnested multigrid methods for solving finite element equations, Math. Comp., 55(1990), I: on quasi-uniform meshes, 23-36; II: on non-quasi-uniform meshes, 439-450. MR 1023054 (91g:65268); MR 1035947 (91g:65269)
  • 43. S. Zhang and Z. Zhang, Treatments of discontinuity and bubble functions in the multigrid method, Math. Comput., 66(1997), 1055-1072.MR 1415804 (97k:65285)
  • 44. J. Zhao, Convergence of nonconforming V-cycle and F-cycle multigrid methods for the biharmonic problem using the Morley element, IMI Research Report, Math Dept, University of South Caroline, 2003.

Similar Articles

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

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

Additional Information

Huo-Yuan Duan
Affiliation: Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore 117543

Shao-Qin Gao
Affiliation: College of Mathematics and Computers, Hebei University, 071002, 1 Hezuo Road, Baoding, Hebei, China

Roger C. E. Tan
Affiliation: Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore 117543

Shangyou Zhang
Affiliation: Department of Mathematical Sciences, University of Delaware, Newark, Delaware 19716

Keywords: V-cycle nonnested multigrid method
Received by editor(s): July 21, 2001
Received by editor(s) in revised form: November 27, 2005
Published electronically: August 31, 2006
Article copyright: © Copyright 2006 American Mathematical Society

American Mathematical Society