A generalized BPX multigrid framework covering nonnested V-cycle methods

Duan, Huo-Yuan; Gao, Shao-Qin; Tan, Roger; Zhang, Shangyou

doi:10.1090/S0025-5718-06-01897-7

A generalized BPX multigrid framework covering nonnested V-cycle methods
HTML articles powered by AMS MathViewer

by Huo-Yuan Duan, Shao-Qin Gao, Roger C. E. Tan and Shangyou Zhang PDF

Math. Comp. 76 (2007), 137-152 Request permission

Erratum: Math. Comp. 76 (2007), 2251-2251.

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

Randolph E. Bank and Todd Dupont, An optimal order process for solving finite element equations, Math. Comp. 36 (1981), no. 153, 35–51. MR 595040, DOI 10.1090/S0025-5718-1981-0595040-2
D. Braess, M. Dryja, and W. Hackbusch, A multigrid method for nonconforming FE-discretisations with application to non-matching grids, Computing 63 (1999), no. 1, 1–25. MR 1702163, DOI 10.1007/s006070050048
D. Braess and W. Hackbusch, A new convergence proof for the multigrid method including the $V$-cycle, SIAM J. Numer. Anal. 20 (1983), no. 5, 967–975. MR 714691, DOI 10.1137/0720066
D. Braess and R. Verfürth, Multigrid methods for nonconforming finite element methods, SIAM J. Numer. Anal. 27 (1990), no. 4, 979–986. MR 1051117, DOI 10.1137/0727056
James H. Bramble, Multigrid methods, Pitman Research Notes in Mathematics Series, vol. 294, Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1993. MR 1247694
James H. Bramble, Do Y. Kwak, and Joseph E. Pasciak, Uniform convergence of multigrid $V$-cycle iterations for indefinite and nonsymmetric problems, SIAM J. Numer. Anal. 31 (1994), no. 6, 1746–1763. MR 1302683, DOI 10.1137/0731089
James H. Bramble and Joseph E. Pasciak, New convergence estimates for multigrid algorithms, Math. Comp. 49 (1987), no. 180, 311–329. MR 906174, DOI 10.1090/S0025-5718-1987-0906174-X
James H. Bramble and Joseph E. Pasciak, The analysis of smoothers for multigrid algorithms, Math. Comp. 58 (1992), no. 198, 467–488. MR 1122058, DOI 10.1090/S0025-5718-1992-1122058-0
James H. Bramble and Joseph E. Pasciak, New estimates for multilevel algorithms including the $V$-cycle, Math. Comp. 60 (1993), no. 202, 447–471. MR 1176705, DOI 10.1090/S0025-5718-1993-1176705-9
James H. Bramble and Joseph E. Pasciak, 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., vol. 157, Amer. Math. Soc., Providence, RI, 1994, pp. 17–26. MR 1262601, DOI 10.1090/conm/157/01401
James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, The analysis of multigrid algorithms with nonnested spaces or noninherited quadratic forms, Math. Comp. 56 (1991), no. 193, 1–34. MR 1052086, DOI 10.1090/S0025-5718-1991-1052086-4
James H. Bramble and Xuejun Zhang, Uniform convergence of the multigrid $V$-cycle for an anisotropic problem, Math. Comp. 70 (2001), no. 234, 453–470. MR 1709148, DOI 10.1090/S0025-5718-00-01222-9
Susanne C. Brenner, An optimal-order multigrid method for $\textrm {P}1$ nonconforming finite elements, Math. Comp. 52 (1989), no. 185, 1–15. MR 946598, DOI 10.1090/S0025-5718-1989-0946598-X
Susanne C. Brenner, A nonconforming multigrid method for the stationary Stokes equations, Math. Comp. 55 (1990), no. 192, 411–437. MR 1035927, DOI 10.1090/S0025-5718-1990-1035927-5
Susanne C. Brenner, Convergence of nonconforming multigrid methods without full elliptic regularity, Math. Comp. 68 (1999), no. 225, 25–53. MR 1620215, DOI 10.1090/S0025-5718-99-01035-2
Susanne C. Brenner, Convergence of the multigrid $V$-cycle algorithm for second-order boundary value problems without full elliptic regularity, Math. Comp. 71 (2002), no. 238, 507–525. MR 1885612, DOI 10.1090/S0025-5718-01-01361-8
Susanne C. Brenner, Convergence of nonconforming V-cycle and F-cycle multigrid algorithms for second order elliptic boundary value problems, Math. Comp. 73 (2004), no. 247, 1041–1066. MR 2047077, DOI 10.1090/S0025-5718-03-01578-3
Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, Texts in Applied Mathematics, vol. 15, Springer-Verlag, New York, 1994. MR 1278258, DOI 10.1007/978-1-4757-4338-8
Philippe G. Ciarlet, The finite element method for elliptic problems, Studies in Mathematics and its Applications, Vol. 4, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. MR 0520174
Z. Chen, On the convergence of Galerkin-multigrid methods for nonconforming finite elements, East-West J. Numer. Math. 7 (1999), no. 2, 79–104. MR 1699247
Zhangxin Chen, On the convergence of nonnested multigrid methods with nested spaces on coarse grids, Numer. Methods Partial Differential Equations 16 (2000), no. 3, 265–284. MR 1752413, DOI 10.1002/(SICI)1098-2426(200005)16:3<265::AID-NUM1>3.0.CO;2-8
Zhangxin Chen and Peter Oswald, Multigrid and multilevel methods for nonconforming $Q_1$ elements, Math. Comp. 67 (1998), no. 222, 667–693. MR 1451319, DOI 10.1090/S0025-5718-98-00920-X
Qing-ping Deng and Xiao-ping Feng, Multigrid methods for the generalized Stokes equations based on mixed finite element methods, J. Comput. Math. 20 (2002), no. 2, 129–152. MR 1884415
Charles I. Goldstein, Multigrid analysis of finite element methods with numerical integration, Math. Comp. 56 (1991), no. 194, 409–436. MR 1066832, DOI 10.1090/S0025-5718-1991-1066832-7
Jayadeep Gopalakrishnan and Joseph E. Pasciak, Multigrid for the mortar finite element method, SIAM J. Numer. Anal. 37 (2000), no. 3, 1029–1052. MR 1749248, DOI 10.1137/S0036142998341040
K. J. Bathe (ed.), Computational fluid and solid mechanics 2003. Vol. 1, Elsevier Science Ltd., Oxford, 2003. MR 2029558
J. Gopalakrishnan and G. Kanschat, A multilevel discontinuous Galerkin method, Numer. Math. 95 (2003), no. 3, 527–550. MR 2012931, DOI 10.1007/s002110200392
Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR 814495, DOI 10.1007/978-3-662-02427-0
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.
Peter Monk and Shangyou Zhang, Multigrid computation of vector potentials, J. Comput. Appl. Math. 62 (1995), no. 3, 301–320. MR 1363678, DOI 10.1016/0377-0427(94)00106-8
Stephen F. McCormick (ed.), Multigrid methods, Frontiers in Applied Mathematics, vol. 3, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1987. MR 972752, DOI 10.1137/1.9781611971057
L. Ridgway Scott and Shangyou Zhang, Higher-dimensional nonnested multigrid methods, Math. Comp. 58 (1992), no. 198, 457–466. MR 1122077, DOI 10.1090/S0025-5718-1992-1122077-4
V. V. Shaĭdurov, Multigrid methods for finite elements, Mathematics and its Applications, vol. 318, Kluwer Academic Publishers Group, Dordrecht, 1995. Translated from the 1989 Russian original by N. B. Urusova and revised by the author. MR 1335921, DOI 10.1007/978-94-015-8527-9
Rob Stevenson, An analysis of nonconforming multi-grid methods, leading to an improved method for the Morley element, Math. Comp. 72 (2003), no. 241, 55–81. MR 1933814, DOI 10.1090/S0025-5718-02-01410-2
Gilbert Strang and George J. Fix, An analysis of the finite element method, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973. MR 0443377
S. Turek, Multigrid techniques for a divergence-free finite element discretization, East-West J. Numer. Math. 2 (1994), no. 3, 229–255. MR 1296984
Jun Ping Wang, Convergence analysis of multigrid algorithms for nonselfadjoint and indefinite elliptic problems, SIAM J. Numer. Anal. 30 (1993), no. 1, 275–285. MR 1202666, DOI 10.1137/0730013
J. Xu, Theory of Multilevel Methods, PhD thesis, Cornell University, 1989.
Xuejun Xu and Jinru Chen, Multigrid for the mortar element method for $P1$ nonconforming element, Numer. Math. 88 (2001), no. 2, 381–398. MR 1826859, DOI 10.1007/PL00005450
Xuejun Xu, Likang Li, and Wenbin Chen, A multigrid method for the mortar-type Morley element approximation of a plate bending problem, SIAM J. Numer. Anal. 39 (2001/02), no. 5, 1712–1731. MR 1885713, DOI 10.1137/S0036142999364728
Xi Jun Yu, A multigrid method with nonconforming Wilson finite elements, Math. Numer. Sinica 15 (1993), no. 3, 346–351 (Chinese, with English summary). MR 1391414
Shangyou Zhang, Optimal-order nonnested multigrid methods for solving finite element equations. I. On quasi-uniform meshes, Math. Comp. 55 (1990), no. 191, 23–36. MR 1023054, DOI 10.1090/S0025-5718-1990-1023054-2
Shangyou Zhang and Zhimin Zhang, Treatments of discontinuity and bubble functions in the multigrid method, Math. Comp. 66 (1997), no. 219, 1055–1072. MR 1415804, DOI 10.1090/S0025-5718-97-00853-3
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.