Dörfler marking with minimal cardinality is a linear complexity problem
HTML articles powered by AMS MathViewer
- by Carl-Martin Pfeiler and Dirk Praetorius HTML | PDF
- Math. Comp. 89 (2020), 2735-2752 Request permission
Abstract:
Most adaptive finite element strategies employ the Dörfler marking strategy to single out certain elements $\mathcal {M} \subseteq \mathcal {T}$ of a triangulation $\mathcal {T}$ for refinement. In the literature, different algorithms have been proposed to construct $\mathcal {M}$, where usually two goals compete. On the one hand, $\mathcal {M}$ should contain a minimal number of elements. On the other hand, one aims for linear costs with respect to the cardinality of $\mathcal {T}$. Unlike expected in the literature, we formulate and analyze an algorithm, which constructs a minimal set $\mathcal {M}$ at linear costs. Throughout, pseudocodes are given.References
- Peter Binev, Wolfgang Dahmen, and Ron DeVore, Adaptive finite element methods with convergence rates, Numer. Math. 97 (2004), no. 2, 219–268. MR 2050077, DOI 10.1007/s00211-003-0492-7
- Manuel Blum, Vaughan Pratt, Robert E. Tarjan, Robert W. Floyd, and Ronald L. Rivest, Time bounds for selection, J. Comput. System Sci. 7 (1973), 448–461. MR 329916, DOI 10.1016/S0022-0000(73)80033-9
- C. Carstensen, M. Feischl, M. Page, and D. Praetorius, Axioms of adaptivity, Comput. Math. Appl. 67 (2014), no. 6, 1195–1253. MR 3170325, DOI 10.1016/j.camwa.2013.12.003
- J. Manuel Cascon, Christian Kreuzer, Ricardo H. Nochetto, and Kunibert G. Siebert, Quasi-optimal convergence rate for an adaptive finite element method, SIAM J. Numer. Anal. 46 (2008), no. 5, 2524–2550. MR 2421046, DOI 10.1137/07069047X
- J. Manuel Cascón and Ricardo H. Nochetto, Quasioptimal cardinality of AFEM driven by nonresidual estimators, IMA J. Numer. Anal. 32 (2012), no. 1, 1–29. MR 2875241, DOI 10.1093/imanum/drr014
- Willy Dörfler, A convergent adaptive algorithm for Poisson’s equation, SIAM J. Numer. Anal. 33 (1996), no. 3, 1106–1124. MR 1393904, DOI 10.1137/0733054
- M. Feischl, T. Führer, and D. Praetorius, Adaptive FEM with optimal convergence rates for a certain class of nonsymmetric and possibly nonlinear problems, SIAM J. Numer. Anal. 52 (2014), no. 2, 601–625. MR 3176325, DOI 10.1137/120897225
- Thomas Führer, Alexander Haberl, Dirk Praetorius, and Stefan Schimanko, Adaptive BEM with inexact PCG solver yields almost optimal computational costs, Numer. Math. 141 (2019), no. 4, 967–1008. MR 3923519, DOI 10.1007/s00211-018-1011-1
- Gregor Gantner, Alexander Haberl, Dirk Praetorius, and Bernhard Stiftner, Rate optimal adaptive FEM with inexact solver for nonlinear operators, IMA J. Numer. Anal. 38 (2018), no. 4, 1797–1831. MR 3867383, DOI 10.1093/imanum/drx050
- C. A. R. Hoare, Algorithm 65: Find, Commun. ACM 4 (1961), no. 7, 321–322., DOI 10.1145/366622.366647
- ISO, ISO\slash IEC 14882:2017 Information technology — Programming languages — C++, Fifth edition, ISO, 2017.
- Khamron Mekchay and Ricardo H. Nochetto, Convergence of adaptive finite element methods for general second order linear elliptic PDEs, SIAM J. Numer. Anal. 43 (2005), no. 5, 1803–1827. MR 2192319, DOI 10.1137/04060929X
- Pedro Morin, Ricardo H. Nochetto, and Kunibert G. Siebert, Data oscillation and convergence of adaptive FEM, SIAM J. Numer. Anal. 38 (2000), no. 2, 466–488. MR 1770058, DOI 10.1137/S0036142999360044
- Pedro Morin, Kunibert G. Siebert, and Andreas Veeser, A basic convergence result for conforming adaptive finite elements, Math. Models Methods Appl. Sci. 18 (2008), no. 5, 707–737. MR 2413035, DOI 10.1142/S0218202508002838
- David R. Musser, Introspective sorting and selection algorithms, Software: Practice and Experience 27 (1997), no. 8, 983–993.
- C.-M. Pfeiler and D. Praetorius, Dörfler marking with minimal cardinality is a linear complexity problem, arXiv:1907.13078 (2019).
- Kunibert G. Siebert, A convergence proof for adaptive finite elements without lower bound, IMA J. Numer. Anal. 31 (2011), no. 3, 947–970. MR 2832786, DOI 10.1093/imanum/drq001
- Rob Stevenson, Optimality of a standard adaptive finite element method, Found. Comput. Math. 7 (2007), no. 2, 245–269. MR 2324418, DOI 10.1007/s10208-005-0183-0
Additional Information
- Carl-Martin Pfeiler
- Affiliation: TU Wien, Institute of Analysis and Scientific Computing, Wiedner Hauptstr. 8-10/E101/4, 1040 Vienna, Austria
- MR Author ID: 1323723
- Email: carl-martin.pfeiler@asc.tuwien.ac.at
- Dirk Praetorius
- Affiliation: TU Wien, Institute of Analysis and Scientific Computing, Wiedner Hauptstr. 8-10/E101/4, 1040 Vienna, Austria
- MR Author ID: 702616
- ORCID: 0000-0002-1977-9830
- Email: dirk.praetorius@asc.tuwien.ac.at
- Received by editor(s): July 31, 2019
- Received by editor(s) in revised form: February 25, 2020
- Published electronically: June 24, 2020
- Additional Notes: The authors thankfully acknowledge support by the Austrian Science Fund (FWF) through the doctoral school Dissipation and dispersion in nonlinear PDEs (grant W1245) and through the research project Optimal adaptivity for BEM and FEM-BEM coupling (grant P27005).
The first author is the corresponding author. - © Copyright 2020 American Mathematical Society
- Journal: Math. Comp. 89 (2020), 2735-2752
- MSC (2010): Primary 65N50, 65N30, 68Q25
- DOI: https://doi.org/10.1090/mcom/3553
- MathSciNet review: 4136545