Mathematics of Computation

Convergence of nonconforming

-cycle and

-cycle multigrid algorithms for second order elliptic boundary value problems

Author(s): Susanne C. Brenner.
Journal: Math. Comp. 73 (2004), 1041-1066.
MSC (2000): Primary 65N55, 65N30
Posted: August 19, 2003
Retrieve article in: PDF DVI PostScript

Abstract: The convergence of

-cycle and

-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.

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 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 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, MAN 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.15em$ n, 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.

Susanne C. Brenner
Affiliation: Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208
Email: brenner@math.sc.edu

DOI: 10.1090/S0025-5718-03-01578-3
PII: S 0025-5718(03)01578-3
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
Posted: August 19, 2003
Additional Notes: This work was supported in part by the National Science Foundation under Grant No. DMS-00-74246.
Copyright of article: Copyright 2003, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS