Multigrid and multilevel methods for nonconforming 𝑄₁ elements

Chen, Zhangxin; Oswald, Peter

doi:10.1090/S0025-5718-98-00920-X

Multigrid and multilevel methods for nonconforming $Q_1$ elements
HTML articles powered by AMS MathViewer

by Zhangxin Chen and Peter Oswald PDF

Math. Comp. 67 (1998), 667-693 Request permission

Abstract:

In this paper we study theoretical properties of multigrid algorithms and multilevel preconditioners for discretizations of second-order elliptic problems using nonconforming rotated $Q_1$ finite elements in two space dimensions. In particular, for the case of square partitions and the Laplacian we derive properties of the associated intergrid transfer operators which allow us to prove convergence of the $\mathcal {W}$-cycle with any number of smoothing steps and close-to-optimal condition number estimates for $\mathcal {V}$-cycle preconditioners. This is in contrast to most of the other nonconforming finite element discretizations where only results for $\mathcal {W}$-cycles with a sufficiently large number of smoothing steps and variable $\mathcal {V}$-cycle multigrid preconditioners are available. Some numerical tests, including also a comparison with a preconditioner obtained by switching from the nonconforming rotated $Q_1$ discretization to a discretization by conforming bilinear elements on the same partition, illustrate the theory.

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
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 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, Joseph E. Pasciak, and Jinchao Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), no. 191, 1–22. MR 1023042, DOI 10.1090/S0025-5718-1990-1023042-6
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
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, 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
S. Brenner, Convergence of nonconforming multigrid methods without full elliptic regularity, Preprint, 1995, submitted.
Zhangxin Chen, Analysis of mixed methods using conforming and nonconforming finite element methods, RAIRO Modél. Math. Anal. Numér. 27 (1993), no. 1, 9–34 (English, with English and French summaries). MR 1204626, DOI 10.1051/m2an/1993270100091
Zhangxin Chen, Projection finite element methods for semiconductor device equations, Comput. Math. Appl. 25 (1993), no. 8, 81–88. MR 1205422, DOI 10.1016/0898-1221(93)90173-S
Zhangxin Chen, Equivalence between and multigrid algorithms for nonconforming and mixed methods for second order elliptic problems, East-West J. Numer. Math. 4 (1996), 1–33.
Zhangxin Chen, R. E. Ewing, Y. Kuznetsov, R. Lazarov, and S. Maliassov, Multilevel preconditioners for mixed methods for second order elliptic problems, J. Numer. Lin. Alg. Appl. 30 (1996), 427–453.
Zhangxin Chen, Richard E. Ewing, and Raytcho Lazarov, Domain decomposition algorithms for mixed methods for second-order elliptic problems, Math. Comp. 65 (1996), no. 214, 467–490. MR 1333307, DOI 10.1090/S0025-5718-96-00703-X
Zhangxin Chen, D. Y. Kwak, and Y. J. Yon, Multigrid algorithms for nonconforming and mixed methods for nonsymmetric and indefinite problems, IMA Preprint Series #1277, 1994, SIAM J. Scientific Computing, 1998 to appear.
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
Petr Klouček, Bo Li, and Mitchell Luskin, Analysis of a class of nonconforming finite elements for crystalline microstructures, Math. Comp. 65 (1996), no. 215, 1111–1135. MR 1344616, DOI 10.1090/S0025-5718-96-00735-1
P. Klouček and M. Luskin, The computation of the dynamics of the martensitic transformation, Contin. Mech. Thermodyn. 6 (1994), no. 3, 209–240. MR 1285922, DOI 10.1007/BF01135254
C. Lee, A nonconforming multigrid method using conforming subspaces, Proceedings of the Sixth Copper Mountain Conference on Multigrid Methods, N. Melson et al., eds., NASA Conference Publication, vol. 3224, 1993, pp. 317–330.
P. Oswald, On a hierarchical basis multilevel method with nonconforming $\textrm {P}1$ elements, Numer. Math. 62 (1992), no. 2, 189–212. MR 1165910, DOI 10.1007/BF01396226
Peter Oswald, Multilevel finite element approximation, Teubner Skripten zur Numerik. [Teubner Scripts on Numerical Mathematics], B. G. Teubner, Stuttgart, 1994. Theory and applications. MR 1312165, DOI 10.1007/978-3-322-91215-2
Peter Oswald, Preconditioners for nonconforming discretizations, Math. Comp. 65 (1996), no. 215, 923–941. MR 1333322, DOI 10.1090/S0025-5718-96-00717-X
P. Oswald, Intergrid transfer operators and multilevel preconditioners for nonconforming discretizations, Appl. Numer. Math. 23 (1997), 139–158.
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
S. Turek, Multigrid techniques for a divergence-free finite element discretization, East-West J. Numer. Math. 2 (1994), no. 3, 229–255. MR 1296984
Ming Wang, The $W$-cycle multigrid method for finite elements with nonnested spaces, Adv. in Math. (China) 23 (1994), no. 3, 238–250 (English, with English and Chinese summaries). MR 1292754
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
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