Multilevel finite element preconditioning for √3 refinement

Maes, Jan; Oswald, Peter

doi:10.1090/S0025-5718-09-02246-7

Multilevel finite element preconditioning for $\sqrt {3}$ refinement
HTML articles powered by AMS MathViewer

by Jan Maes and Peter Oswald PDF

Math. Comp. 78 (2009), 1869-1890 Request permission

Abstract:

We develop a BPX-type multilevel method for the numerical solution of second order elliptic equations in $\mathbb {R}^2$ using piecewise linear polynomials on a sequence of triangulations given by regular $\sqrt {3}$ refinement. A multilevel splitting of the finest grid space is obtained from the nonnested sequence of spaces on the coarser triangulations using prolongation operators based on simple averaging procedures. The main result is that the condition number of the corresponding BPX preconditioned linear system is uniformly bounded independent of the size of the problem. The motivation to consider $\sqrt {3}$ refinement stems from the fact that it is a slower topological refinement than the usual dyadic refinement, and that it alternates the orientation of the refined triangles. Therefore we expect a reduction of the amount of work when compared to the classical BPX preconditioner, although both methods have the same asymptotical complexity. Numerical experiments confirm this statement.

References

Burak Aksoylu and Michael Holst, Optimality of multilevel preconditioners for local mesh refinement in three dimensions, SIAM J. Numer. Anal. 44 (2006), no. 3, 1005–1025. MR 2231853, DOI 10.1137/S0036142902406119
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 Olaf Steinbach, On the stability of the $L^2$ projection in $H^1(\Omega )$, Math. Comp. 71 (2002), no. 237, 147–156. MR 1862992, DOI 10.1090/S0025-5718-01-01314-X
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
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, An optimal-order nonconforming multigrid method for the biharmonic equation, SIAM J. Numer. Anal. 26 (1989), no. 5, 1124–1138. MR 1014877, DOI 10.1137/0726062
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
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
Wolfgang Dahmen, Wavelet and multiscale methods for operator equations, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 55–228. MR 1489256, DOI 10.1017/S0962492900002713
L. Kobbelt, $\sqrt {3}$-subdivision, Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, 2000, pp. 103–112.
U. Labsik and G. Greiner, Interpolatory $\sqrt {3}$-subdivision, Comput. Graph. Forum 19 (2000), no. 3, 131–138.
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
—, On discrete norm estimates related to multilevel preconditioners in the finite element method, Constructive Theory of Functions (K. G. Ivanov, P. Petrushev, and B. Sendov, eds.), Proc. Int. Conf. Varna, 1991, Bulg. Acad. Sci., Sofia, 1992, pp. 203–214.
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
Peter Oswald, Intergrid transfer operators and multilevel preconditioners for nonconforming discretizations, Appl. Numer. Math. 23 (1997), no. 1, 139–158. Multilevel methods (Oberwolfach, 1995). MR 1438084, DOI 10.1016/S0168-9274(96)00065-7
P. Oswald, Optimality of multilevel preconditioning for nonconforming P1 finite elements, Numer. Math. 111 (2008), no. 2, 267–291. MR 2456833, DOI 10.1007/s00211-008-0182-6
Harry Yserentant, On the multilevel splitting of finite element spaces, Numer. Math. 49 (1986), no. 4, 379–412. MR 853662, DOI 10.1007/BF01389538