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
Additional Information
- Jan Maes
- Affiliation: The first author’s work was done while at the Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, B-3001 Heverlee, Belgium
- Email: janm31415@gmail.com
- Peter Oswald
- Affiliation: School of Engineering and Science, Jacobs University Bremen, Campus Ring 1, 28759 Bremen, Germany.
- Email: p.oswald@jacobs-university.de
- Received by editor(s): June 1, 2007
- Received by editor(s) in revised form: August 30, 2008
- Published electronically: May 5, 2009
- © Copyright 2009
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 78 (2009), 1869-1890
- MSC (2000): Primary 65F10, 65F35, 65N30, 35J20
- DOI: https://doi.org/10.1090/S0025-5718-09-02246-7
- MathSciNet review: 2521270