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