Recursive algorithms for distributed forests of octrees
From MaRDI portal
complexityfinite element libraryforest of octreeslarge-scale scientific computingmorton codeparallel adaptive mesh refinementperformancerecursive algorithmssoftware
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) Parallel numerical computation (65Y05) Packaged methods for numerical algorithms (65Y15) Complexity and performance of numerical algorithms (65Y20)
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
- 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
- deal.II—A general-purpose object-oriented finite element library
- Gerris: A tree-based adaptive solver for the incompressible Euler equations in complex geometries.
- scientific article; zbMATH DE number 1324388 (Why is no real title available?)
- scientific article; zbMATH DE number 1953302 (Why is no real title available?)
- On a Data Structure for Adaptive Finite Element Mesh Refinements
- p4est: scalable algorithms for parallel adaptive mesh refinement on forests of octrees
- 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
Cited in
(34)- An efficient adaptive mesh refinement (AMR) algorithm for the discontinuous Galerkin method: applications for the computation of compressible two-phase flows
- Enhancing speed and scalability of the ParFlow simulation code
- An energy stable approach for discretizing hyperbolic equations with nonconforming discontinuous Galerkin methods
- 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
- Direct numerical simulation of incompressible flows on parallel octree grids
- 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
- A numerical method for self-similar solutions of ideal magnetohydrodynamics
- A parallel cell-centered adaptive level set framework for efficient simulation of two-phase flows with subcycling and non-subcycling
- An adaptive rectangular mesh administration and refinement technique with application in cancer invasion models
- Fast and scalable algorithms for constructing solvent-excluded surfaces of large biomolecules
- Machine learning algorithms for three-dimensional mean-curvature computation in the level-set method
- High-order adaptive mesh refinement multigrid Poisson solver in any dimension
- A tetrahedral space-filling curve for nonconforming adaptive meshes
- p4est: scalable algorithms for parallel adaptive mesh refinement on forests of octrees
- Bottom-Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel
- Coarse mesh partitioning for tree-based AMR
- Landau Collision Integral Solver with Adaptive Mesh Refinement on Emerging Architectures
- The aggregated unfitted finite element method on parallel tree-based adaptive meshes
- An optimized, parallel computation of the ghost layer for adaptive hybrid forest meshes
- Parallel tree algorithms for AMR and non-standard data access
- Enclave Tasking for DG Methods on Dynamically Adaptive Meshes
- Nonconforming Mesh Refinement for High-Order Finite Elements
- A Generic Finite Element Framework on Parallel Tree-Based Adaptive Meshes
- Fully parallel mesh I/O using PETSc DMPlex with an application to waveform modeling
- 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
- A new adaptive mesh refinement data structure with an application to detonation
- Parallel simulations for fast-moving landslides: space-time mesh adaptation and sharp tracking of the wetting front
- Scalable implicit solvers with dynamic mesh adaptation for a relativistic drift-kinetic Fokker-Planck-Boltzmann model
- A scalable parallel finite element framework for growing geometries. Application to metal additive manufacturing
- A level-wise load balance method underlying block-structured adaptive mesh refinement for LBM
- CPAFT: a consistent parallel advancing front technique for unstructured triangular/tetrahedral mesh generation
- Segmentation of macrophages on a quadtree grid using the p4est library
- Parallel level-set methods on adaptive tree-based grids
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)
