[Paper] A Morton-Type Space-Filling Curve for Pyramid Subdivision and Hybrid Adaptive Mesh Refinement

Source: arXiv - 2602.20887v1

Overview

The paper introduces a pyramid element into the forest‑of‑refinement‑trees (FoRT) framework for adaptive mesh refinement (AMR). By giving pyramids a well‑defined Morton‑type space‑filling curve (SFC), the authors enable seamless hybrid meshes that mix tetrahedra, hexahedra, and now pyramids—crucial for connecting different element types without creating hanging edges.

Key Contributions

• New functional element type: Formal definition and refinement rules for the pyramid, allowing it to bridge tetrahedral and hexahedral regions.
• Morton‑type SFC for pyramids: A deterministic, locality‑preserving indexing scheme that integrates pyramids into the existing global ordering used for parallel AMR.
• Extended FoRT algorithms: Generalized parallel procedures for refinement, coarsening, load‑balancing partitioning, and ghost‑cell exchange to handle hybrid meshes containing pyramids.
• Scalable implementation: Demonstrated that the hybrid‑element AMR framework retains the near‑linear scalability of the original FoRT approach on large distributed‑memory systems.
• Open‑source reference: The authors contribute their implementation to the widely used p4est library, making the technique immediately available to developers.

Methodology

1. Element hierarchy: The authors define a refinement pattern where a pyramid splits into a set of smaller pyramids, tetrahedra, and/or hexahedra, preserving conformity across element boundaries.
2. Space‑filling curve design: They extend the classic Morton (Z‑order) curve by assigning a unique binary key to each pyramid child based on its position in a 3‑D grid, ensuring that neighboring pyramids receive nearby keys.
3. Forest management: Each refinement tree stores its elements’ SFC keys; global ordering across trees is achieved by concatenating these keys, which drives parallel partitioning and communication.
4. Parallel algorithms: Existing FoRT operations (refine/coarsen, repartition, ghost exchange) are rewritten to interpret pyramid keys correctly, allowing the same code paths to work for all element types.
5. Performance evaluation: The authors run strong‑ and weak‑scaling experiments on up to several hundred thousand cores, measuring overhead introduced by pyramids versus pure tetrahedral/hexahedral meshes.

Results & Findings

• Negligible overhead: Adding pyramids increased total runtime by < 3 % compared with a pure tetrahedral/hexahedral forest, confirming that the SFC and tree operations remain cheap.
• Scalability: The hybrid framework achieved > 90 % parallel efficiency up to 262 144 MPI ranks, matching the scaling behavior of the original FoRT implementation.
• Mesh quality: Hybrid meshes with pyramids eliminated hanging edges at material or geometry interfaces, leading to smoother solution fields in benchmark PDE problems (e.g., Poisson and Navier‑Stokes).
• Load balance: The Morton‑type ordering kept element distribution balanced across processes even when pyramids were heavily concentrated in transition zones.

Practical Implications

• Seamless geometry handling: Engineers can now model domains that require both structured (hexahedral) and unstructured (tetrahedral) regions—think fluid‑structure interaction, geological reservoirs, or aerospace components—without manual mesh stitching.
• Simplified code bases: Existing FoRT‑based AMR libraries (e.g., p4est, t8code) can adopt the pyramid extension with minimal changes, letting developers reuse their parallel infrastructure.
• Performance‑critical simulations: Since the added cost is tiny, large‑scale time‑dependent simulations (weather, combustion, plasma) can benefit from hybrid meshes that improve accuracy near complex boundaries while retaining fast AMR updates.
• GPU/heterogeneous readiness: The deterministic SFC ordering is friendly to data‑parallel kernels, making it easier to port hybrid‑element AMR to GPUs or other accelerators.

Limitations & Future Work

• Refinement depth: The current pyramid refinement scheme limits the maximum depth to avoid excessively small sliver elements; deeper hierarchies may need additional quality controls.
• Higher‑order elements: The study focuses on linear (first‑order) elements; extending the SFC and load‑balancing strategies to high‑order spectral elements remains an open challenge.
• Dynamic topology changes: While the framework handles refinement/coarsening, supporting fully dynamic topology (e.g., element insertion/removal due to fracture) would require further algorithmic extensions.
• Broader element families: Future research could explore other mixed‑element shapes (e.g., prisms with curved faces) and integrate them into the same SFC‑based forest.

---

Bottom line: By giving pyramids a clean Morton‑type space‑filling curve and integrating them into the forest‑of‑refinement‑trees paradigm, the authors unlock truly hybrid 3‑D AMR that is both practically usable and scalable—a win for developers building next‑generation simulation tools.

Authors

• David Knapp
• Johannes Albrecht Holke
• Thomas Spenke
• Carsten Burstedde

Paper Information

• arXiv ID: 2602.20887v1
• Categories: cs.DC, cs.CG
• Published: February 24, 2026
• PDF: Download PDF