Recursive algorithms for distributed forests of octrees
From MaRDI portal
performancesoftwarecomplexityrecursive algorithmsparallel adaptive mesh refinementlarge-scale scientific computingforest of octreesfinite element librarymorton code
Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20) Packaged methods for numerical algorithms (65Y15) Mesh generation, refinement, and adaptive methods for the numerical solution of initial value and initial-boundary value problems involving PDEs (65M50) Finite element, Rayleigh-Ritz and Galerkin methods for initial value and initial-boundary value problems involving PDEs (65M60) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30) Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs (65N50)
Abstract: The forest-of-octrees approach to parallel adaptive mesh refinement and coarsening (AMR) has recently been demonstrated in the context of a number of large-scale PDE-based applications. Although linear octrees, which store only leaf octants, have an underlying tree structure by definition, it is not often exploited in previously published mesh-related algorithms. This is because the branches are not explicitly stored, and because the topological relationships in meshes, such as the adjacency between cells, introduce dependencies that do not respect the octree hierarchy. In this work we combine hierarchical and topological relationships between octree branches to design efficient recursive algorithms. We present three important algorithms with recursive implementations. The first is a parallel search for leaves matching any of a set of multiple search criteria. The second is a ghost layer construction algorithm that handles arbitrarily refined octrees that are not covered by previous algorithms, which require a 2:1 condition between neighboring leaves. The third is a universal mesh topology iterator. This iterator visits every cell in a domain partition, as well as every interface (face, edge and corner) between these cells. The iterator calculates the local topological information for every interface that it visits, taking into account the nonconforming interfaces that increase the complexity of describing the local topology. To demonstrate the utility of the topology iterator, we use it to compute the numbering and encoding of higher-order nodal basis functions. We analyze the complexity of the new recursive algorithms theoretically, and assess their performance, both in terms of single-processor efficiency and in terms of parallel scalability, demonstrating good weak and strong scaling up to 458k cores of the JUQUEEN supercomputer.
Recommendations
- p4est: scalable algorithms for parallel adaptive mesh refinement on forests of octrees
- Parallel tree algorithms for AMR and non-standard data access
- An optimized, parallel computation of the ghost layer for adaptive hybrid forest meshes
- Bottom-Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel
- RefficientLib: an efficient load-rebalanced adaptive mesh refinement algorithm for high-performance computational physics meshes
Cites work
- scientific article; zbMATH DE number 1324388 (Why is no real title available?)
- scientific article; zbMATH DE number 1953302 (Why is no real title available?)
- A high-order discontinuous Galerkin method for wave propagation through coupled elastic-acoustic media
- Algorithms and data structures for massively parallel generic adaptive finite element codes
- Bottom-Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel
- Controlling Unstructured Mesh Partitions for Massively Parallel Simulations
- Gerris: A tree-based adaptive solver for the incompressible Euler equations in complex geometries.
- On a Data Structure for Adaptive Finite Element Mesh Refinements
- PARAMESH: A parallel adaptive mesh refinement community toolkit
- Spectral element formulations on non-conforming grids: a comparative study of pointwise matching and integral projection methods
- Spectral element methods for transitional flows in complex geometries
- deal.II—A general-purpose object-oriented finite element library
- p4est: scalable algorithms for parallel adaptive mesh refinement on forests of octrees
Cited in
(34)- Nonconforming Mesh Refinement for High-Order Finite Elements
- A scalable parallel finite element framework for growing geometries. Application to metal additive manufacturing
- Scalable implicit solvers with dynamic mesh adaptation for a relativistic drift-kinetic Fokker-Planck-Boltzmann model
- A tetrahedral space-filling curve for nonconforming adaptive meshes
- Enclave Tasking for DG Methods on Dynamically Adaptive Meshes
- An adaptive rectangular mesh administration and refinement technique with application in cancer invasion models
- A new adaptive mesh refinement data structure with an application to detonation
- CPAFT: a consistent parallel advancing front technique for unstructured triangular/tetrahedral mesh generation
- A subcycling/non-subcycling time advancement scheme-based DLM immersed boundary method framework for solving single and multiphase fluid-structure interaction problems on dynamically adaptive grids
- Fast and scalable algorithms for constructing solvent-excluded surfaces of large biomolecules
- A parallel cell-centered adaptive level set framework for efficient simulation of two-phase flows with subcycling and non-subcycling
- Bottom-Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel
- Parallel level-set methods on adaptive tree-based grids
- A Generic Finite Element Framework on Parallel Tree-Based Adaptive Meshes
- Segmentation of macrophages on a quadtree grid using the p4est library
- Fully parallel mesh I/O using PETSc DMPlex with an application to waveform modeling
- A numerical method for self-similar solutions of ideal magnetohydrodynamics
- An energy stable approach for discretizing hyperbolic equations with nonconforming discontinuous Galerkin methods
- Coarse mesh partitioning for tree-based AMR
- A level-wise load balance method underlying block-structured adaptive mesh refinement for LBM
- The aggregated unfitted finite element method on parallel tree-based adaptive meshes
- High-order accurate entropy-stable discontinuous collocated Galerkin methods with the summation-by-parts property for compressible CFD frameworks: scalable SSDC algorithms and flow solver
- High-order adaptive mesh refinement multigrid Poisson solver in any dimension
- Parallel tree algorithms for AMR and non-standard data access
- An efficient adaptive mesh refinement (AMR) algorithm for the discontinuous Galerkin method: applications for the computation of compressible two-phase flows
- p4est: scalable algorithms for parallel adaptive mesh refinement on forests of octrees
- Enhancing speed and scalability of the ParFlow simulation code
- An optimized, parallel computation of the ghost layer for adaptive hybrid forest meshes
- Parallel simulations for fast-moving landslides: space-time mesh adaptation and sharp tracking of the wetting front
- Direct numerical simulation of incompressible flows on parallel octree grids
- An Immersed Boundary Method Based on Parallel Adaptive Cartesian Grids for High Reynolds Number Turbulent Flow
- An explicit local space-time adaptive framework for monodomain models in cardiac electrophysiology
- Machine learning algorithms for three-dimensional mean-curvature computation in the level-set method
- Landau Collision Integral Solver with Adaptive Mesh Refinement on Emerging Architectures
Describes a project that uses
Uses Software
This page was built for publication: Recursive algorithms for distributed forests of octrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947047)
