Dörfler marking with minimal cardinality is a linear complexity problem
Carl‐Martin Pfeiler, Dirk Praetorius
Abstract
Most adaptive finite element strategies employ the Dörfler marking strategy to single out certain elements <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper M subset-of-or-equal-to script upper T"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">M</mml:mi> </mml:mrow> <mml:mo> ⊆ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">T</mml:mi> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {M} \subseteq \mathcal {T}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of a triangulation <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper T"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">T</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {T}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for refinement. In the literature, different algorithms have been proposed to construct <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper M"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">M</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {M}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , where usually two goals compete. On the one hand, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper M"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">M</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {M}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> should contain a minimal number of elements. On the other hand, one aims for linear costs with respect to the cardinality of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper T"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">T</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {T}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Unlike expected in the literature, we formulate and analyze an algorithm, which constructs a minimal set <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper M"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">M</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {M}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> at linear costs. Throughout, pseudocodes are given.