PaperlayerView exact revision on arXiv

Source-linked AI summary

Closure complexity of B\"ansch-type algorithms for tetrahedral mesh refinement

Yuwen Li, Zhiyuan Yang

arXiv:2609.29616v1math.NAcs.NA

TL;DR

Cumulative conformity overhead must scale with the number of marked elements for AFEM optimal complexity, but Bänsch–AMP closure complexity remained open. The paper analyzes conformity propagation with a causal forest and weighted packing, establishing unconditional cumulative closure estimates for arbitrary conforming initial tetrahedral meshes.

  • Problem

    Cumulative conformity overhead must scale with cumulative marked elements for AFEM optimal complexity, but Bänsch–AMP closure complexity remained open.

    Source: §1 · pp. 1, 3

  • Method

    The proof constructs intrinsic marked-face refinement trees and a causal forest, then combines same-scale descendant control with weighted packing.

    Source: §1 · p. 3

  • Results

    The paper establishes the first unconditional cumulative closure estimates for AMP and Bänsch on arbitrary conforming initial tetrahedral meshes, including nondeterministic Bänsch choices.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The proof is intrinsic to the physical three-dimensional mesh and requires neither an initial compatibility condition nor a higher-dimensional embedding.

    Source: §1 · p. 3

    RefineToConformity need not return a conforming mesh for arbitrary marked input, though it terminates along histories from an initial AMP marked mesh.

    Source: §2.3 · p. 8

Abstract

from arXiv · show

We prove, to our knowledge, the first unconditional cumulative closure estimates for the Arnold--Mukherjee--Pouly (AMP) refinement algorithm and the original face-marked tetrahedral algorithm of B\"ansch on arbitrary conforming initial tetrahedral meshes. Let $T_0,\ldots,T_L$ be an adaptive mesh sequence generated by either algorithm, with $M_\ell\subseteq T_\ell$ denoting the marking set at step $\ell$. Then $$\#T_L-\#T_0\leq C_{\mathrm{clos}}(T_0)\sum_{\ell=0}^{L-1}\#M_\ell.$$ The proof is intrinsic to the physical three-dimensional mesh and requires neither an initial compatibility condition nor a higher-dimensional embedding. It organizes conformity refinements into a causal forest and combines a uniform horizontal-propagation estimate with a weighted packing argument to obtain an explicit closure constant. For the original B\"ansch algorithm, every history-dependent resolution of the initial two-edge ambiguity is represented by one of finitely many AMP histories. The estimate therefore holds uniformly for arbitrary deterministic or nondeterministic choices. This resolves a long-standing complexity question for the B\"ansch--AMP family.

1. Introduction

The introduction frames cumulative closure as the requirement that conformity overhead remain proportional to marked elements, a condition needed for AFEM optimal complexity. It presents unconditional Bänsch–AMP closure estimates on arbitrary conforming tetrahedral meshes, using intrinsic propagation and locality arguments.

1. Introduction

  • Three-dimensional conformity completion is delicate because one bisection can trigger long propagation chains, while repeated refinement calls can revisit regions at multiple scales.Cumulative completion overhead must remain proportional to cumulative marked elements for AFEM optimal complexity.Source: §1 · pp. 1–2
  • Bänsch–AMP uses face-based edge marks that can be initialized on any conforming tetrahedral mesh from one global edge order, without preliminary refinement or global compatibility construction.AMP is described as a later finite-state realization of the Bänsch algorithm.Source: §1 · pp. 2–3
  • The paper proves unconditional cumulative closure estimates for Bänsch and AMP on arbitrary conforming initial tetrahedral meshes, without compatibility assumptions or higher-dimensional embedding.The estimate also covers the original Bänsch algorithm's history-dependent two-edge choices.Source: §1 · pp. 3–4
  • The proof builds intrinsic marked-face refinement trees and a causal forest, then establishes macro-generation monotonicity and uniform horizontal propagation.The propagation bound comes from finite analysis of five physical edge classes, two transition tables, and vertex- and edge-star bounds.Source: §1 · p. 3
  • Causal descendants remain in controlled same-scale neighborhoods of their roots, allowing weighted packing to charge refinement cost to marked elements and yield an explicit closure constant.The introduction gives the resulting constant in terms of H_AMP.Source: §1 · pp. 3–4
  • Every history-dependent resolution of Bänsch's initial two-edge ambiguity is represented by one of finitely many AMP histories, transferring the estimate uniformly to deterministic or nondeterministic choices.Each Bänsch child has a unique global refinement edge.Source: §1 · p. 4

2. The AMP refinement algorithm

This section defines AMP’s marked-tetrahedron data and refinement rules, then establishes the initialization, conformity, and uniform-refinement structure used in the analysis.

2. The AMP refinement algorithm

  • AMP marking is equivalent to Bänsch’s face-based formulation once an edge is selected in the ambiguous two-edge case; a global edge order initializes any conforming mesh without coloring or matching-neighbor conditions.Each face receives its maximal edge, and every tetrahedron uses its maximal edge as its refinement edge.Source: §2 · p. 4, §2.3 · p. 8

2.1. Tetrahedral meshes and marked tetrahedra.

  • A marked tetrahedron stores a refinement edge, one marked edge per face, and a Boolean flag; the face-mark configurations classify it as P, A, O, or M.P splits into Pu and Pf according to the flag; only Pf has the flag set.Source: §2.1 · pp. 4–5

2.2. The marked-tetrahedron bisection.

  • BisectTet splits the refinement edge at its midpoint and assigns inherited-face, cut-face, and new-face marks by rules B1–B4.The two children share the new face; child flags are set if and only if the parent is Pu.Source: §2.2 · pp. 5–6

2.3. Conforming initialization and local refinement.

  • RefineAMP bisects the marked set, then repeatedly bisects active tetrahedra with hanging vertices as conformity batches.The routine terminates and produces a conformingly marked AMP mesh along a history starting from an initial AMP marked mesh.Source: §2.3 · p. 8
  • The conformity guarantee is history-dependent: RefineToConformity need not conform an arbitrary marked input, even when no hanging vertices remain.Theorem 2.2 gives termination and conformity along histories from an initial AMP marked mesh.Source: §2.3 · pp. 8–9

2.4. The three-bisection macrostructure.

  • Uniformly bisecting each initial tetrahedron 3q times defines macro-mesh Uq; edges in E(Uq) have macro-generation q.One AMP macrostep is the passage from Uq to Uq+1.Source: §2.3 · p. 9, §2.4 · p. 9
  • For gen(K)=3q+s, the possible types and edge macro-generations depend on s; types M and O occur only when q=0.The uniform refinement tree also has finitely many similarity classes and is uniformly shape regular.Source: §2.2 · p. 6, §2.4 · p. 9

3. Intrinsic causal structure

The section builds intrinsic refinement trees and a causal forest for AMP calls, then uses macro-generation monotonicity and macro-star counting to control conformity propagation.

3.1. Geometry of AMP descendants.

  • AMP descendants have uniform scale and valence bounds depending only on the fixed initial mesh and its markings.The uniform vertex and edge valence follows from a positive lower bound on descendant solid angles.Source: §3.1 · p. 10

3.2.1. The intrinsic refinement tree of a marked face

  • Marked-face bisections induce the same binary refinement tree from either side, with the root split before any proper descendant appears.A cut face is marked by the edge opposite the new midpoint, while an inherited face retains its mark.Source: §3.2.1 · p. 12
  • The causal forest links each non-root conformity event to an earlier bisection that created its hanging vertex, and macro-generations decrease by at most one along each chain.The forest roots are the batch-zero marked-element events.Source: §3.2.2 · pp. 12–14

3.3. Macro-star counting along causal chains.

  • At most 7 events in a causal chain lie over each macro-element, and at most 7ν events bisect any fixed geometric edge.Here ν is the uniform macro-vertex valence; the bounds use the seven possible ancestry nodes across three generations.Source: §3.3 · pp. 14–15

4. Horizontal propagation

The section proves uniform bounds on same-macro-generation propagation by classifying tetrahedral edges and exhaustively analyzing transitions in AMP macrosteps. The resulting finite transition structure lets the authors bound horizontal blocks using macro-star counts.

4.1. The horizontal-propagation bound.

  • Each horizontal block of a causal chain has a uniform event bound depending on the initial mesh size and its macro-vertex valence.The proof combines macro-star counting with a finite classification of possible edge transitions within one macrostep.Source: §4.1 · p. 15, §4 · p. 15

4.2. The five edge classes in one AMP macrostep.

  • Every AMP macrostep edge has a unique carrier-based class, and the two canonical parent patterns exhaust macrochildren up to relabeling.The five classes are H, V, Mf, IA, and IP; the classification is independent of the incident macro-tetrahedron.Source: §4.2 · pp. 15–16

4.3. Finite horizontal transition tables.

  • The finite transition enumeration checks 48 target configurations and covers every different-edge horizontal transition up to relabeling.It starts from canonical type-A and type-Pu representatives and inspects each target and candidate edge.Source: §4.3 · p. 16, §4.2 · p. 16, §4.3.1 · p. 17

4.3.1. The full class table.

  • The exhaustive class table permits only a restricted set of ordered edge-class transitions, with H-to-H, H-to-V, and V-to-V transitions preserving their anchor.The type-A and type-Pu transition sets together yield the table’s allowed class pairs.Source: §4.3.1 · pp. 17–18

4.3.2. The spine relation.

  • Spine transitions have their own finite class table, and H-to-H, H-to-V, and V-to-V preserve the anchor.The enumeration is exhaustive because the macro-parent is type A or Pu.Source: §4.3.2 · pp. 18–19

4.3.3. Projection of medial transitions.

  • A different-edge Mf-to-Mf transition either keeps its projected σ-edge or follows one of the parent tetrahedron’s spine relations.This projects medial transitions onto the finite spine analysis.Source: §4.3.3 · p. 19

4.4. Proof of the horizontal-propagation bound.

  • The class graph and macro-star counts bound the interior, half-edge, and spoke blocks; anchor preservation localizes H and V events to vertex stars.Medial blocks are controlled through fixed edges or projected spine relations, yielding the uniform horizontal bound.Source: §4.4 · pp. 19–20

5. Closure complexity of AMP refinement

The section turns the horizontal-propagation bound into geometric locality for each refinement call, then uses witness histories and weighted packing to prove unconditional cumulative closure complexity for AMP.

5. Closure complexity of AMP refinement

  • The fixed horizontal-propagation constant depends only on the initial mesh and underlies the subsequent locality and closure estimates.It is not displayed as a separate argument of the later constants.Source: §5 · p. 21

5.1. Geometric locality.

  • Every new tetrahedron in a refinement call lies within a scale-dependent distance of a causal root in the marking set.Causal chains may cross arbitrarily many macro-generations; the proof controls same-scale events and sums geometrically decreasing diameters.Source: §5.1 · pp. 21–22

5.2. A self-contained weighted closure theorem.

  • A weighted packing argument combines locality with level-wise packing to derive the cumulative closure estimate.The proof assigns causal witnesses to new elements and bounds their weights above and below.Source: §5.2 · p. 22, §5.2.2 · p. 25

5.2.1. Causal witnesses.

  • Each new tetrahedron is assigned a causal-root witness, and tracing witnesses backward through creation times yields a finite history ending in the initial mesh.Successive witness levels increase by at most one, with distance controlled at the scale of the later witness.Source: §5.2.1 · p. 23

5.2.2. Weights.

  • The weight argument bounds each marked element’s total upper weight and gives each new element a uniform lower weight, producing an explicit closure constant.The theorem’s constant is bounded in terms of the horizontal-propagation constant.Source: §5.2.2 · pp. 23–25

6. Closure complexity of B¨ansch refinement

This section formulates Bänsch refinement using intrinsic face marks, then transfers its history-dependent choices to AMP. It establishes termination and a cumulative closure estimate for admissible initial meshes.

6.1. Intrinsic face marking.

  • An admissible intrinsic face marking gives each tetrahedron one or two global refinement edges; if there are two, they are opposite.A shared face carries the same mark from either incident tetrahedron.Source: §6.1 · p. 26, Figure 5 · p. 26

6.2. One B¨ansch bisection.

  • After a Bänsch bisection, both children have the same configuration and a unique global refinement edge, so only initial tetrahedra can remain ambiguous.For the black–black case, the common new face is marked by [z, w] rather than the ordinary [c, d].Source: §6.2 · pp. 28–29, Figure 7 · p. 28

6.3. B¨ansch refinement.

  • A selection strategy resolves an initial tetrahedron’s two-edge choice when first bisected and may depend on the preceding batch history.The refinement loop repeatedly bisects selected tetrahedra and then selects those with hanging vertices for conformity refinement.Source: §6.3 · pp. 29–30

6.4. Finite resolution and AMP correspondence.

  • The finitely many initial resolutions encode every possible ambiguity, and each resulting Bänsch history corresponds at batch boundaries to an AMP history with matching bisection edges.Once a global refinement edge is selected, a Bänsch bisection and AMP application produce the same children, face marks, and refinement edges.Source: §6.4 · pp. 30–31

6.5. Uniform B¨ansch closure complexity.

  • Theorem 6.7 gives termination and a finite cumulative closure bound for every finite Bänsch process, with the constant depending only on the initial marked mesh.An edge order on any finite conforming tetrahedral mesh supplies an admissible initial face marking.Source: §6.5 · pp. 31–32

7. Numerical experiments

The experiments compare AMP with DGS and AGK on two tetrahedral meshes and examine sensitivity to vertex numbering. AMP has the smallest reported estimator at comparable terminal degrees of freedom, while its observed shape and closure statistics are favorable in these tests.

7.1. Experimental setting.

  • The test used continuous piecewise affine elements, squared residual indicators, Dörfler marking with θ = 0.3, and stopped at the first iterate with at least 105 degrees of freedom.Because the domains lack an exact solution, the figures report the residual estimator rather than exact energy error.Source: §7.1 · pp. 32–33

7.2. Fichera corner.

  • The Fichera-corner test used the cube [−1, 1]3 with its positive octant removed and a Gmsh mesh whose greedy DGS color parameter was 9.Terminal statistics are presented in Table 2.Source: §7.2 · p. 33, Table 2 · p. 34

7.3. Star-shaped prism.

  • The star-prism test extruded a ten-vertex star with alternating radii 1 and 0.45 over −1 ≤ z ≤ 1, using a Gmsh Delaunay mesh with DGS color parameter 7.Terminal numerical results are presented in Table 3.Source: §7.3 · p. 34, Table 3 · p. 34

7.4. Sensitivity to the initial vertex numbering.

  • Five random vertex-number permutations per fixed mesh tested label sensitivity; Table 4 reports each measure as a six-numbering mean followed by its range.The physical coordinates and tetrahedra remained unchanged, and all trials used the same model problem, marking parameter, and stopping criterion.Source: §7.3 · p. 35, §7.4 · p. 35, Table 4 · p. 36
  • AMP selected a diameter-carrying edge for every initial tetrahedron under every vertex permutation, while its final shape ratio was invariant on both meshes.On the star prism, terminal data were completely invariant; on Fichera, equal-length tie-breaking changed some histories, but observed closure and shape statistics remained more stable than DGS and AGK.Source: §7.4 · p. 35, §7.3 · p. 35, Table 4 · p. 36

7.5. Observed behavior.

  • Observed closure ratios ranged from 2.786 to 3.053, and Bänsch and AMP recorded identical star-prism histories, with only a small Fichera-history difference.The Fichera difference came from resolving the initial ambiguity differently.Source: Table 3 · p. 34, Table 2 · p. 34, §7.5 · pp. 35–36
  • AMP's final shape ratios were 2.058–2.060, versus 3.860–4.554 for DGS and AGK; at comparable terminal degrees of freedom, AMP had the smallest estimator.The results are illustrative and do not assert a theoretical comparison with DGS or AGK.Source: §7 · p. 32, Table 2 · p. 34, Table 3 · p. 34
  • AMP's Euclidean-length edge ordering may explain its observed behavior, while its original-numbering closure values were slightly below DGS and AGK in these histories.The reported AMP values were Cemp = 2.786 and 2.815, compared with 2.895–3.053 for DGS and AGK; the authors suggest less conforming completion was required.Source: §7.5 · p. 36
Loading 2609.29616v1…