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.
Additional Information
- Susanne C. Brenner
- Affiliation: Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208
- Email: brenner@math.sc.edu
- 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.
- © Copyright 2003 American Mathematical Society
- Journal: Math. Comp. 73 (2004), 1041-1066
- MSC (2000): Primary 65N55, 65N30
- DOI: https://doi.org/10.1090/S0025-5718-03-01578-3
- MathSciNet review: 2047077