Dörfler marking with minimal cardinality is a linear complexity problem

Pfeiler, Carl-Martin; Praetorius, Dirk

doi:10.1090/mcom/3553

Dörfler marking with minimal cardinality is a linear complexity problem
HTML articles powered by AMS MathViewer

by Carl-Martin Pfeiler and Dirk Praetorius;

Math. Comp. 89 (2020), 2735-2752

DOI: https://doi.org/10.1090/mcom/3553

Published electronically: June 24, 2020

HTML | PDF | 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