Convergence of nonconforming 𝑉-cycle and 𝐹-cycle multigrid algorithms for second order elliptic boundary value problems

Brenner, Susanne

doi:10.1090/S0025-5718-03-01578-3

Convergence of nonconforming $V$-cycle and $F$-cycle multigrid algorithms for second order elliptic boundary value problems
HTML articles powered by AMS MathViewer

by Susanne C. Brenner PDF

Math. Comp. 73 (2004), 1041-1066 Request permission

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

Todd Arbogast and Zhangxin Chen, On the implementation of mixed methods as nonconforming methods for second-order elliptic problems, Math. Comp. 64 (1995), no. 211, 943–972. MR 1303084, DOI 10.1090/S0025-5718-1995-1303084-8
D. N. Arnold and F. Brezzi, Mixed and nonconforming finite element methods: implementation, postprocessing and error estimates, RAIRO Modél. Math. Anal. Numér. 19 (1985), no. 1, 7–32 (English, with French summary). MR 813687, DOI 10.1051/m2an/1985190100071
Randolph E. Bank and Craig C. Douglas, Sharp estimates for multigrid rates of convergence with general smoothing and acceleration, SIAM J. Numer. Anal. 22 (1985), no. 4, 617–633. MR 795944, DOI 10.1137/0722038
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 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
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), 112–124. MR 263214, DOI 10.1137/0707006
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, 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, Jun Ping Wang, and Jinchao Xu, Convergence estimates for multigrid algorithms without regularity assumptions, Math. Comp. 57 (1991), no. 195, 23–45. MR 1079008, DOI 10.1090/S0025-5718-1991-1079008-4
James H. Bramble, Joseph E. Pasciak, Jun Ping Wang, and Jinchao Xu, Convergence estimates for product iterative methods with applications to domain decomposition, Math. Comp. 57 (1991), no. 195, 1–21. MR 1090464, DOI 10.1090/S0025-5718-1991-1090464-8
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 Jinchao Xu, Some estimates for a weighted $L^2$ projection, Math. Comp. 56 (1991), no. 194, 463–476. MR 1066830, DOI 10.1090/S0025-5718-1991-1066830-3
James H. Bramble and Xuejun Zhang, The analysis of multigrid methods, Handbook of numerical analysis, Vol. VII, Handb. Numer. Anal., VII, North-Holland, Amsterdam, 2000, pp. 173–415. MR 1804746
A. Brandt, Multigrid solvers for non-elliptic and singular-perturbation steady-state problems, Weizmann Institute of Science, Rehovot, Israel, 1981.
Susanne C. Brenner, Multigrid methods for nonconforming finite elements, Proceedings of the Fourth Copper Mountain Conference on Multigrid Methods (Copper Mountain, CO, 1989) SIAM, Philadelphia, PA, 1989, pp. 54–65. MR 1065626
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 multigrid algorithm for the lowest-order Raviart-Thomas mixed triangular finite element method, SIAM J. Numer. Anal. 29 (1992), no. 3, 647–678. MR 1163350, DOI 10.1137/0729042
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
—, Smoothers, mesh dependent norms, interpolation and multigrid, Appl. Numer. Math. 43 (2002), 45–56.
—, Poincaré-Friedrichs inequalities for piecewise $H^1$ functions, SIAM J. Numer. Anal. 41 (2003), 306–324 (electronic).
Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, 2nd ed., Texts in Applied Mathematics, vol. 15, Springer-Verlag, New York, 2002. MR 1894376, DOI 10.1007/978-1-4757-3658-8
Franco Brezzi, Michel Fortin, and Rolf Stenberg, Error analysis of mixed-interpolated elements for Reissner-Mindlin plates, Math. Models Methods Appl. Sci. 1 (1991), no. 2, 125–151. MR 1115287, DOI 10.1142/S0218202591000083
Z. Cai, J. Douglas Jr., J. E. Santos, D. Sheen, and X. Ye, Nonconforming quadrilateral finite elements: a correction, Calcolo 37 (2000), no. 4, 253–254. MR 1812789, DOI 10.1007/s100920070004
Zhiqiang Cai, Jim Douglas Jr., and Xiu Ye, A stable nonconforming quadrilateral finite element method for the stationary Stokes and Navier-Stokes equations, Calcolo 36 (1999), no. 4, 215–232. MR 1740354, DOI 10.1007/s100920050031
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
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
M. Crouzeix and P.-A. Raviart, Conforming and nonconforming finite element methods for solving the stationary Stokes equations. I, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge 7 (1973), no. R-3, 33–75. MR 343661
Monique Dauge, Elliptic boundary value problems on corner domains, Lecture Notes in Mathematics, vol. 1341, Springer-Verlag, Berlin, 1988. Smoothness and asymptotics of solutions. MR 961439, DOI 10.1007/BFb0086682
Jim Douglas Jr., Juan E. Santos, Dongwoo Sheen, and Xiu Ye, Nonconforming Galerkin methods based on quadrilateral elements for second order elliptic problems, M2AN Math. Model. Numer. Anal. 33 (1999), no. 4, 747–770. MR 1726483, DOI 10.1051/m2an:1999161
M. Griebel and P. Oswald, On the abstract theory of additive and multiplicative Schwarz algorithms, Numer. Math. 70 (1995), no. 2, 163–180. MR 1324736, DOI 10.1007/s002110050115
W. Hackbusch, Multigrid convergence theory, Multigrid methods (Cologne, 1981) Lecture Notes in Math., vol. 960, Springer, Berlin-New York, 1982, pp. 177–219. MR 685774
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
G.H. Hardy, J.E. Littlewood, and G. Pólya, Inequalities, Cambridge University Press, Cambridge, 1934.
S. G. Kreĭn, Yu. Ī. Petunīn, and E. M. Semënov, Interpolation of linear operators, Translations of Mathematical Monographs, vol. 54, American Mathematical Society, Providence, R.I., 1982. Translated from the Russian by J. Szűcs. MR 649411
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.
Jan Mandel and Seymour V. Parter, On the multigrid $F$-cycle, Appl. Math. Comput. 37 (1990), no. 1, 19–36. MR 1054733, DOI 10.1016/0096-3003(90)90108-F
Nicolas Neuss, $V$-cycle convergence with unsymmetric smoothers and application to an anisotropic model problem, SIAM J. Numer. Anal. 35 (1998), no. 3, 1201–1212. MR 1619887, DOI 10.1137/S0036142996310848
R. Rannacher and S. Turek, Simple nonconforming quadrilateral Stokes element, Numer. Methods Partial Differential Equations 8 (1992), no. 2, 97–111. MR 1148797, DOI 10.1002/num.1690080202
P.-A. Raviart and J. M. Thomas, A mixed finite element method for 2nd order elliptic problems, Mathematical aspects of finite element methods (Proc. Conf., Consiglio Naz. delle Ricerche (C.N.R.), Rome, 1975) Lecture Notes in Math., Vol. 606, Springer, Berlin, 1977, pp. 292–315. MR 0483555
Z.-C. Shi and X. Xu, Cascadic multigrid method for elliptic problems, East-West J. Numer. Math. 7 (1999), no. 3, 199–209. MR 1719603
Zhong-Ci Shi and Xuejun Xu, A $V$-cycle multigrid method for TRUNC plate element, Comput. Methods Appl. Mech. Engrg. 188 (2000), no. 1-3, 483–493. MR 1774170, DOI 10.1016/S0045-7825(99)00190-5
Zhongci Shi and Xuejun Xu, $V$-cycle multigrid methods for Wilson nonconforming element, Sci. China Ser. A 43 (2000), no. 7, 673–684. MR 1790171, DOI 10.1007/BF02878433
Rob Stevenson, Nonconforming finite elements and the cascadic multi-grid method, Numer. Math. 91 (2002), no. 2, 351–387. MR 1900924, DOI 10.1007/s002110100344
H. Triebel, Interpolation theory, function spaces, differential operators, VEB Deutscher Verlag der Wissenschaften, Berlin, 1978. MR 500580
U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid, Academic Press, Inc., San Diego, CA, 2001. With contributions by A. Brandt, P. Oswald and K. Stüben. MR 1807961
Stefan Turek, Efficient solvers for incompressible flow problems, Lecture Notes in Computational Science and Engineering, vol. 6, Springer-Verlag, Berlin, 1999. An algorithmic and computational approach; With 1 CD-ROM (“Virtual Album”: UNIX/LINUX, Windows, POWERMAC; “FEATFLOW 1.1”: UNIX/LINUX). MR 1691839, DOI 10.1007/978-3-642-58393-3
Pieter Wesseling, An introduction to multigrid methods, Pure and Applied Mathematics (New York), John Wiley & Sons, Ltd., Chichester, 1992. MR 1156079
Jinchao Xu, Convergence estimates for some multigrid algorithms, Third International Symposium on Domain Decomposition Methods for Partial Differential Equations (Houston, TX, 1989) SIAM, Philadelphia, PA, 1990, pp. 174–187. MR 1064343
Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI 10.1137/1034116
Xuejun Xu and Likang Li, A note on convergence of $V$-cycle nonconforming multigrid methods, Appl. Math. Comput. 104 (1999), no. 2-3, 191–206. MR 1704174, DOI 10.1016/S0096-3003(98)10079-6
Xue-jun Xu and Li-kang Li, A $V$-cycle multigrid method for the plate bending problem discretized by nonconforming finite elements, J. Comput. Math. 17 (1999), no. 5, 533–544. MR 1712644
Harry Yserentant, Old and new convergence proofs for multigrid methods, Acta numerica, 1993, Acta Numer., Cambridge Univ. Press, Cambridge, 1993, pp. 285–326. MR 1224685, DOI 10.1017/S0962492900002385
Xuejun Zhang, Multilevel Schwarz methods, Numer. Math. 63 (1992), no. 4, 521–539. MR 1189535, DOI 10.1007/BF01385873
J. Zhao, Multigird Methods for Fourth Order Problems, Ph.D. thesis, University of South Carolina, in preparation.