PaperlayerView exact revision on arXiv

Source-linked AI summary

On 2D Newest Vertex Bisection: Optimality of Mesh-Closure and H1-Stability of L2-Projection

Michael Karkulik, David Pavlicek, Dirk Praetorius

arXiv:1210.0367v1math.NAcs.NA

TL;DR

Adaptive finite-element analyses using NVB rely on mesh-refinement properties, while earlier H1-stability results retained mesh or initial-mesh conditions. This paper establishes quasi-optimal mesh closure and H1-stability of the L2-projection under its general setup, without requiring a special initial-edge distribution.

  • Problem

    Earlier H1-stability results imposed mesh conditions, and adaptive 2D results retained a weakened BDD-type initial-mesh assumption, while mesh-independent projection stability has several stated applications.

    Source: §1 · p. 3

  • Method

    The paper studies NVB meshes generated from arbitrary initial reference-edge distributions and marked-element sets, proving results for mesh closure and the L2-projection.

    Source: §2 · pp. 4, 7

  • Results

    The mesh-closure step is quasi-optimal, and the L2-projection onto S1(Tℓ) is H1-stable under the stated general assumption.

    Source: §2 · pp. 7–8

  • Takeaways & Limitations

    Avoiding initial-mesh assumptions addresses costly BDD-satisfying initialization, while mesh-independent projection stability is relevant to the listed finite- and boundary-element applications.

    Source: §1 · pp. 2–3

    The stated regular-triangulation setup presumes a polygonal, piecewise-flat domain and excludes hanging nodes.

    Source: §2 · p. 3

Abstract

from arXiv · show

Newest vertex bisection (NVB) is a popular local mesh-refinement strategy for regular triangulations which consist of simplices. For the 2D case, we prove that the mesh-closure step of NVB, which preserves regularity of the triangulation, is quasi-optimal and that the corresponding L2-projection onto lowest-order Courant finite elements (P1-FEM) is always H1-stable. Throughout, no additional assumptions on the initial triangulation are imposed. Our analysis thus improves results of Binev, Dahmen & DeVore (Numer. Math. 97, 2004), Carstensen (Constr. Approx. 20, 2004), and Stevenson (Math. Comp. 77, 2008) in the sense that all assumptions of their theorems are removed. Consequently, our results relax the requirements under which adaptive finite element schemes can be mathematically guaranteed to convergence with quasi-optimal rates.

1. Introduction

Adaptive finite-element analyses using NVB rely on mesh-refinement properties, while earlier H1-stability results retained mesh or initial-mesh conditions. This work proves quasi-optimal mesh closure and H1-stability of the L2-projection without requiring a special initial-edge distribution.

1. Introduction

  • Adaptive NVB analyses need a manageable common refinement of an optimal and an algorithm-generated mesh, as well as a closure estimate controlling refinement overhead.The closure estimate bounds the extra elements introduced when marked elements are refined to preserve a regular mesh.Source: §1 · p. 2
  • An iteration-independent bound on each step's mesh growth by the number of marked elements cannot hold in general.The passage gives an example ruling out this stronger per-step estimate.Source: §1 · p. 2
  • Earlier closure proofs required BDD labeling, while uniform bisec(3) initialization can multiply element counts by 4 in 2D and 16 in 3D.The paper proves the closure estimate without initial-mesh assumptions, addressing this practical initialization cost.Source: §1 · p. 2
  • Mesh-independent L2-projection stability is relevant to hybrid methods, preconditioners, a-posteriori error estimation, and adaptive convergence analyses.The cited applications include finite and boundary element methods, including adaptive FEM with inhomogeneous Dirichlet data.Source: §1 · pp. 2–3
  • Prior H1-stability results imposed mesh conditions, and adaptive 2D results still required a weakened BDD-type assumption on the initial mesh.This work proves H1-stability without initial-mesh conditions, for all 0 ≤ s ≤ 1, with a constant depending only on T0.Source: §1 · p. 3

2. Newest Vertex Bisection Algorithm & Main Results

NVB recursively bisects reference edges and closes the mesh to avoid hanging nodes. The paper establishes quasi-optimal mesh closure and H1-stability of the L2-projection under arbitrary initial reference-edge distributions.

Newest vertex bisection

  • NVB bisects an element’s reference edge at its midpoint; the new vertex determines the reference edges of the two sons, and further bisections close the mesh to avoid hanging nodes.The resulting mesh remains a regular triangulation.Source: §2 · pp. 3–4

Modified newest vertex bisection

  • When all three edges are marked, modified NVB allows bisec(3), red, or bisec(5) refinement, and the analysis covers these cases.The modified algorithm uses ordinary NVB rules when one or two edges are marked.Source: §2 · pp. 5–6, Figure 3 · p. 5

Main results

  • Mesh closure is quasi-optimal for arbitrary initial reference-edge distributions, with a constant depending only on initial-mesh shape regularity and not on the marked sets.The theorem bounds the number of elements in each mesh by a closure estimate.Source: §2 · p. 7
  • Earlier 2D closure results required a BDD-type initial labeling, for which no efficient linear-complexity construction was known.The cited earlier result was generalized to dimensions d ≥ 2.Source: §2 · p. 7
  • The L2-projection onto lowest-order Courant P1 finite elements is H1-stable, with a constant depending only on initial-mesh shape regularity and not on the marked sets.The target space consists of piecewise-affine, globally continuous functions.Source: §2 · pp. 7–8
  • Carstensen’s earlier H1-stability result used a weakened BDD assumption; this analysis removes that assumption for its modified NVB setting.Carstensen’s modification uses red refinement when all three edges are marked.Source: §2 · p. 8

3. Preliminaries

This section establishes mesh and refinement notation and collects auxiliary results for NVB and its variants. It addresses generation-level and compatibility controls, the equivalence of two mesh-closure procedures, and claims for modified refinements and Algorithm 2 without restrictions on its step (iii).

3.1. Notation & abbreviations

  • The notation fixes refinement relations from an initial mesh and defines generation levels, reference neighbors, compatible divisibility, BDD properties, and refinement chains.Generation increases by 1 under bisection and by 2 under red-refinement.Source: §3.1 · p. 9

3.2. Auxiliary results for NVB (Algorithm 1)

  • Under a BDD-type initial reference-edge distribution, adjacent elements differ in generation level by at most 1.Lemma 7 also characterizes compatible divisibility between a reference neighbor and its neighbor or a son of that neighbor.Source: §3.2 · p. 9
  • For arbitrary initial reference-edge distributions, Proposition 9 bounds generation-level differences across adjacent elements by 2.It also bounds same-level reference-neighbor chains by a constant depending only on the initial mesh.Source: §3.2 · p. 10
  • If a reference neighbor has a higher generation level, the pair is compatibly divisible and differs in level by exactly 1.Equal-level neighboring successors are compatibly divisible when they share an ancestor or have compatibly divisible ancestors; an incompatible equal-level reference-neighbor pair can share only a coarse-mesh edge.Source: §3.2 · pp. 10, 12, 13

3.3. Auxiliary results for MNVB with bisec(3)-refinement only (Algorithm 2)

  • The bisec(3)-only MNVB variant also satisfies Proposition 9’s conclusions.Each bisec(3)-NVB step can be realized by two successive usual NVB steps.Source: §3.3 · p. 14

3.4. Auxiliary results for MNVB with bisec(3)- and red-refinement (Algorithm 2)

  • Algorithm 2’s marked-edge set is the unique set of minimal cardinality, and is smallest by inclusion, among sets satisfying (10).The supplied passage does not state the properties in (10).Source: §3.3 · p. 14
  • For red-refined meshes, a sequence of corresponding bisec(3)-only meshes can be constructed with at most twice as many marked edges at each step.The corresponding meshes preserve element counts, generation levels, adjacency, reference edges, and compatible divisibility.Source: §3.3 · pp. 14–15

3. Preliminaries

  • The sets X and M(k) are equal, so transferring marked elements before closure or transferring them afterward yields the same mesh T^k+1.The equality follows from Lemma 11; the equivalence concerns the two procedures using refineNVB3 and refine, respectively.Source: §3.3 · p. 17
  • The correspondence corr^k+1 is defined locally for bisection and red-refinement cases, and it satisfies all properties of Definition 12.For elements corresponding to two elements, the construction uses the Figure 8 cases; refinements yield a new correspondence as in Figure 9.Source: §3.3 · p. 18
  • Proposition 15 establishes claims (i) and (ii) of Proposition 9 for refineNVBred.The following analysis only requires claims (i) and (ii) for refineNVB3; Lemma 14 also transfers claims (iii)–(vi) to refineNVBred.Source: §3.3 · p. 18
  • Claims (i) and (ii) of Proposition 9 hold for Algorithm 2 without restrictions on step (iii).An unrestricted call of refine can be carried out by two calls of refineNVBred.Source: §3.5 · p. 18, §3.3 · p. 18

4. Proof of Theorem 5 (Quasi-Optimality of Mesh-Closure)

The proof establishes estimate (4) through successive refinement variants, then removes the restrictions on the refinement pattern. Its chain and local-refinement arguments provide intermediate bounds for this bootstrapping.

4. Proof of Theorem 5 (Quasi-Optimality of Mesh-Closure)

  • For arbitrary initial reference-edge layouts, Lemma 18 provides a local generation bound for sons created by refining one element.The lemma concerns an arbitrary refinement produced by refineNVB.Source: §4 · p. 18
  • The distance constant Cdist depends solely on the initial mesh.The passage gives Cdist as a combination of proof constants and states its dependence on T0.Source: §4 · p. 18
  • Along chain(Tk,T), an element above gen(T) can only be the last chain element, at level gen(T)+1; its sons have level gen(T)+2.The proof uses the fact that refinement increases the level locally by at most 2.Source: §4 · p. 18
  • The proof establishes estimate (4) in four stages: refineNVB, refineNVB3, refineNVBred, and finally unrestricted refine.The proof describes each later stage as a bootstrap from the preceding refinement algorithm.Source: §4 · p. 20
  • The refinement-variant bootstrap uses two refineNVB calls for refineNVB3 and two refineNVBred steps for unrestricted refine.The proof states these reductions when extending the estimate to the more general algorithms.Source: §4 · p. 23

5. Proof of Theorem 6 (H1-stability of L2-projection)

The proof constructs mesh-dependent nodal values to obtain local mass-matrix eigenvalue bounds, then uses these bounds to establish H1-stability of the L2-projection. The stability constant depends only on the initial mesh.

5. Proof of Theorem 6 (H1-stability of L2-projection)

  • The proof chooses nodal values for each mesh so that local mass-matrix eigenvalue estimates can be established.These estimates are then used to apply the H1-stability criterion.Source: §5 · p. 23
  • A local eigenvalue criterion converts uniform bounds on element mass matrices into H1-stability of the L2-projection.The criterion's stability constant depends on the mesh shape regularity and the constants in the local bounds.Source: §5 · p. 24
  • The nodal weights are defined using element-graph distance and generation, and the proof checks that they satisfy the bounds required by the stability criterion.The construction uses the number of element steps between nodes and the generations of nearby elements.Source: §5 · pp. 26–27
  • The L2-projection onto S1(T) is H1-stable on meshes generated by MNVB, with its constant depending only on the initial mesh T0.The proof also uses the uniform shape regularity of the generated meshes.Source: §5 · p. 27
Loading 1210.0367v1…