PaperlayerView exact revision on arXiv

Source-linked AI summary

The DUNE Framework: Basic Concepts and Recent Developments

Peter Bastian, Markus Blatt, Andreas Dedner, Nils-Arne Dreier, Christian Engwer, René Fritze, Carsten Gräser, Christoph Grüninger, Dominic Kempf, Robert Klöfkorn, Mario Ohlberger, Oliver Sander

arXiv:1909.13672v3cs.MScs.DC

TL;DR

Dune addresses the need for a flexible and efficient framework for grid-based PDE computation and evolving numerical methods. The paper reviews its modular abstractions and recent advanced features, including vectorized solvers, grid modification, domain coupling, and cut-cell discretizations. It reports reduced communication overhead from fused vectorized messages and describes scope boundaries for Python bindings and matrix-free preconditioning.

  • Problem

    Dune must support diverse PDE components and numerical methods without committing to a single grid structure, linear algebra implementation, or discretization approach.

  • Method

    The paper presents Dune’s modular interfaces and reusable concepts, then surveys advanced capabilities including grid adaptation, moving domains, domain coupling, cut cells, and performance-oriented solver techniques.

  • Results

    Vectorized solvers reduce communication costs from k(αD + β) to kαD + β by fusing k messages into one.

  • Takeaways & Limitations

    Dune provides exchangeable components and advanced numerical infrastructure for developing grid-based PDE applications across varied computational settings.

  • Takeaways & Limitations

    Python bindings prioritize interface compatibility over very high efficiency, while matrix-free solvers require preconditioners that preserve low memory bandwidth and good convergence.

Abstract

from arXiv · show

This paper presents the basic concepts and the module structure of the Distributed and Unified Numerics Environment and reflects on recent developments and general changes that happened since the release of the first Dune version in 2007 and the main papers describing that state [1, 2]. This discussion is accompanied with a description of various advanced features, such as coupling of domains and cut cells, grid modifications such as adaptation and moving domains, high order discretizations and node level performance, non-smooth multigrid methods, and multiscale methods. A brief discussion on current and future development directions of the framework concludes the paper.

1. Introduction

Dune is an open-source framework for grid-based PDE computation whose central design combines flexibility with efficiency. It achieves this through modular, generic interfaces that separate data structures from algorithms and support reuse of existing code.

  • Dune is a free, open-source framework for grid-based numerical solutions of partial differential equations, developed collaboratively for more than 15 years.
  • Its distinguishing feature is flexibility combined with efficiency, rather than commitment to one grid structure, sparse linear algebra implementation, or discretization method.
  • Dune separates data structures and algorithms through abstract interfaces with specialized implementations.
  • Generic C++ template programming removes the runtime overhead of abstract interfaces at compile time.
  • The modular approach supports reuse of legacy code from different projects within one common platform.
  • The paper reviews Dune’s modular structure, core concepts, advanced features, and current development trends.

2. The Dune ecosystem

The Dune ecosystem is organized as interdependent modules built around a maintained core and extended by independently developed functionality. Its infrastructure supports hosting, development, building, testing, and collaboration across module categories.

  • Dune’s modular structure splits the code into separate, interdependent libraries called Dune-modules.
  • The core modules provide a common foundation including build infrastructure, geometry, grids, sparse linear algebra and iterative solvers, and finite elements.
  • Additional modules include grid modules, discretization modules, extension modules, application modules, and user modules.
  • Application modules use the ecosystem for application-specific physical laws, third-party libraries, or methods outside Dune’s scope.
  • Dune’s GitLab infrastructure supports repository access, project creation, issue discussion, merge requests, review, and continuous-integration tests.

3. Dune core modules and re-usable concepts

Dune’s core modules expose reusable abstractions for grids, geometry, finite elements, and related numerical operations. The Dune-Grid interface separates topology, geometry, and attached data while supporting diverse dimensions, element types, refinement, and parallel processing.

  • The core-module overview focuses on mathematical abstractions needed in finite element methods, especially Dune-Grid, Dune-ISTL, Dune-LocalFunctions, Dune-Functions, and Dune-Python.
  • Grid concepts: A grid partitions a domain into nonoverlapping subdomains, supporting manifold description, integral computation, and function approximation.
  • Dune-Grid: Dune-Grid describes grid subdivisions through a generic C++ interface supporting arbitrary dimension, world dimension, element types, local refinement, and parallel processing.
  • Grid concepts: Dune separates geometrical maps from topology, which describes hierarchical construction and how grid elements are glued together.
  • Grid concepts: Grid constituents are dimension-independent entities, with codimension used to distinguish vertices, edges, facets, and elements.
  • Grid concepts: Algorithms can operate generically across multiple grid implementations that conform to the Dune-Grid interface.
  • Core-module evolution: Dune-Geometry provides reference elements, geometry mappings, and quadrature formulas independently of Dune-Grid.
  • Core-module evolution: The framework’s design experience identifies separation of topology and geometry, separation of mesh and data, entities as views, and modularity as successful principles.

3.2. The template library for iterative solvers –

Dune-ISTL combines flexible vector and matrix abstractions with configurable iterative solvers, preconditioners, and parallel execution. Recent developments improve runtime configurability, support richer block structures, and reduce communication overhead through vectorized solvers.

  • Core abstractions: Its vector and matrix classes support nested structures, multiple field types, dense and sparse blocks, and examples including Taylor–Hood discretizations of Navier–Stokes equations.Nested examples include complex block vectors, low-precision dense blocks, and sparse matrices with sparse entries.
  • Core abstractions: Dune-ISTL provides abstract interfaces for operators, scalar products, solvers, and preconditioners, allowing solver and preconditioner implementations to be mixed dynamically.Solvers remain strongly typed on underlying vector types while exposing high-level interfaces.
  • Parallel execution: Dune-ISTL supports parallel solvers through locally consecutive numbering and parallel operators, preconditioners, and scalar products rather than requiring globally consecutive unknown numbering.The linear solvers themselves do not need information about parallel data distribution.
  • Parallel execution: A transparent switch between sequential and parallel computations is enabled by the library’s parallel abstractions and preconditioner design.BlockPreconditioner can turn sequential preconditioners into parallel ones using inexact block Jacobi or Schwarz-type methods.
  • Recent developments: Scalar values can now terminate nested vector and matrix structures directly, with compiler optimization removing the internal indirections needed for transparent scalar and blocked entries.Previously, scalar entries had to be represented as length-one vectors or 1×1 matrices.
  • Recent developments: Recent runtime configuration introduces abstract base classes, shared pointers, parameter-tree configuration, and a solver factory under development.These changes allow solvers to be configured at runtime, including parameters such as restart and maximum iterations.
  • Recent developments: C++11-enabled MultiTypeBlockVector and MultiTypeBlockMatrix classes support fully featured dense blocks with different block types in different entries.The library had supported varying block structures conceptually since its first release, but complete support became practical with newer C++ language features.
  • Recent developments: Vectorized solvers load the matrix once for k matrix–vector products and reduce communication costs from k(αD + β) to kαD + β.The approach also supports block Krylov methods for systems with multiple right-hand sides.

3.3. Finite element spaces on discretization grids

Dune separates local finite-element descriptions from global function-space construction, enabling reusable basis components and flexible product spaces on discretization grids. Dune-Functions provides a common GlobalBasis framework with customizable hierarchical indexing for complex finite-element applications.

  • Local and global spaces: Dune keeps ansatz functions separate from grid and linear-algebra interfaces, supporting finite-element and finite-volume applications through independent modules.Local finite elements are provided independently of global grids and linear algebra.
  • Local and global spaces: Each LocalFiniteElement exposes its reference-domain geometry, local basis functions, interpolation functionals, and coefficient mappings.These components identify basis functions and their association with local degrees of freedom.
  • Global function spaces: Dune-Functions addresses the lack of a common core interface for global finite-element spaces by defining interfaces and implementations for nested and elementary spaces.The module also provides convenient construction of product spaces.
  • Global function spaces: GlobalBasis is the central abstraction because the same finite-element space may use different bases for discretization and hierarchical error estimation.This abstraction supports flexible bases of hierarchically structured product spaces.
  • Global function spaces: Product spaces are built from elementary bases using compositional mechanisms such as power and composite, including Taylor–Hood spaces with velocity and pressure components.Descriptors can be nested to construct products of possibly different bases.
  • Global function spaces: A GlobalBasis separates whole-basis operations from element-local operations exposed through LocalView, which is bound to a grid element and provides localized basis data.Local views expose non-vanishing basis functions and local trees for generic traversal.
  • Indexing: Shape-function indices map from local finite-element indices to LocalView indices and then to global indices, which may be hierarchical multi-indices.Global indices can be explored by prefixes and can efficiently address hierarchically structured containers.
  • Indexing: Dune-Functions allows global degree-of-freedom indices to be customized for flat, nested, or multi-type matrix and vector containers.Strategies include prepending or appending child identifiers or producing consecutive flat indices.

3.4. Python interfaces for Dune

Dune-Python provides bindings that make Dune numerical algorithms accessible from Python while preserving a path to efficient C++ production code. The interface adds Python-oriented changes and vectorization mechanisms to reduce binding overhead.

  • Since the 2.6 release in 2018, Dune supports Python scripting through bindings for central core-module interfaces.The bindings aim to stay close to the corresponding C++ interfaces, enabling rapid prototyping of numerical algorithms.
  • Close adherence to the C++ interface can cause significant efficiency loss, so Dune reduces Python-to-C++ calls and provides vectorized interfaces.The strategies include returning iterable structures and accepting vectors of arguments for vectorization.
  • Python interface changes include iterable plural methods, dynamic arguments, properties, and Python-specific handling of grids, partitions, and mappings.For example, plural methods return iterable objects instead of only counts, reducing repeated calls into C++.
  • Python bindings enable non-performance-critical preprocessing and postprocessing in Python while time-critical code remains in C++.C++ functions can be called directly from Python, allowing performance-sensitive parts to be replaced incrementally.
  • Dune-Python also provides infrastructure for adding bindings to other Dune modules and supports describing PDE models with UFL.The bindings therefore extend beyond the central interfaces presented in this section.

3.5. Build system and testing

Dune transitioned to a CMake-based build system in version 2.4, organizing each module as a separate project with managed dependencies. Testing is integrated into the development workflow through convenience functions and dedicated infrastructure.

  • Starting with version 2.4, Dune replaced Autotools with a CMake-based build system.Each module is treated as an independent CMake project, while inter-module dependencies and configuration results are managed centrally.
  • The CMake system emphasizes testing because Dune core-module development relies heavily on Continuous Integration.The dune_add_test convenience function lowers the barrier to adding tests.
  • Dune-TestTools provides additional testing infrastructure for the module ecosystem.

4. Selected advanced features with applications

The advanced-features section presents examples that combine Dune extension modules with the core modules. Its examples cover selected capabilities beyond the central framework components.

  • The advanced-feature examples combine Dune extension modules with the core modules.The section is intended to highlight capabilities built on the framework’s central concepts.

4.1. Grid modification

Dune supports dynamic local grid adaptation and moving domains through grid-view abstractions that separate topology, geometry, and user data. Applications demonstrate adaptive discretizations on conforming and nonconforming grids, as well as geometric evolution.

  • Grid modification: Dynamic local grid adaptation and moving domains are the two grid-modification mechanisms discussed.Dynamic adaptation can reduce computational costs but is technically challenging, especially in parallel settings.
  • Grid modification: Dune-Fem provides AdaptiveGridView for refinement and coarsening and GeometryGridView for replacing element geometries.AdaptiveGridView adds index-set information to simplify data transfer during grid changes.
  • Grid modification: The grid interface supports adaptive computations with conforming and nonconforming refinement, including parallel dynamic adaptation in UGGrid and ALUGrid.AlbertaGrid supports adaptation but not parallel computations.
  • Dynamic local grid adaptation: The Barkley reaction-diffusion model is solved with quadratic Lagrange approximation, DG stabilization for nonconforming grids, and a residual-based error estimator for adaptation.The estimator is formulated over the solution space and a scalar finite-volume space using UFL.
  • Dynamic local grid adaptation: On conforming meshes without hanging nodes, the residual error estimator coincides with standard results from the literature.The additional DG terms stabilize nonconforming refinement and coarsening with hanging nodes, while vanishing when basis functions are smooth across conforming intersections.
  • Moving domains: A mean-curvature-flow example uses a moving-domain formulation in which the evolving surface is represented as a map from a reference surface.The evolution is governed by mean curvature and the outward normal, and the resulting surface evolution is presented in Figure 7.

4.2. Grid coupling and complex domains

Dune supports three approaches for coupling PDE subdomains: separate grids, partitions of a host grid, and cut-cell grids. These mechanisms are implemented in specialized modules and address increasingly complex geometries, while cut cells require specialized discretizations because they may be non-shape-regular.

  • Dune distinguishes coupling individual grids, partitioning one host grid, and constructing cut-cell grids from an independent geometry.
  • Coupling strategies: Separate grids require geometric coupling interfaces and generally use weak coupling methods such as mortar, penalty, or flux-based schemes.
  • Coupling strategies: Host-grid partitioning makes coupling interfaces straightforward and permits strong coupling conditions, but complicated subdomain shapes make initial mesh generation involved.
  • Cut-cell grids: Cut-cell grids intersect arbitrary host-grid elements with a level-set geometry, producing fragments that need methods such as UDG or CutFEM.
  • Dune-Grid-Glue: Dune-Grid-Glue represents cross-grid neighborhood relationships as RemoteIntersections, including intersections between different grid implementations or dimensions.
  • Host-grid partitioning: The Dune-MultiDomainGrid module wraps a host grid and exposes subdomains through cooperating MultiDomainGrid and SubDomainGrid implementations.
  • Cut-cell grids: Dune-TPMC identifies cut-cell topology from vertex signs of a piecewise multilinear level-set function, while polygonal-domain quadrature achieves O(h^2) error convergence.

4.3. Non-smooth multigrid

Dune-TNNMG applies truncated nonsmooth Newton multigrid to block-separable convex minimization problems arising in nonsmooth PDEs. Its alternating local smoothing and inexact Newton correction has global convergence theory and is observed to attain multigrid rates asymptotically, with a three-dimensional elastoplasticity example illustrating the implementation.

  • Dune-TNNMG targets nonsmooth convex minimization problems with block-separable structure arising in applications such as computational mechanics.
  • Algorithm: The algorithm alternates nonlinear local minimization over blocks with a damped inexact Newton correction, typically one multigrid iteration for the linearized problem.
  • Convergence: Global convergence holds with inexact local smoothers, while practical iterations are observed to become multigrid methods after finitely many steps.
  • Implementation: Dune-TNNMG operates on algebraic functionals and depends on Dune-ISTL and Dune-Solvers rather than directly on grids or finite element spaces.
  • Elastoplasticity example: The elastoplasticity implementation combines continuous piecewise linear displacement elements with piecewise constant plastic strains.
  • Elastoplasticity example: The example uses mixed block vector and matrix types, with multigrid operating directly on the resulting MultiTypeBlockMatrix.
  • Elastoplasticity example: The three-dimensional benchmark shows the evolution of the plastification front at several times under a time-dependent normal load.

4.4. Multiscale methods

Dune’s multiscale framework constructs coarse-scale approximations for heterogeneous diffusion using local fine-scale problems on admissible oversampling environments. Its implementation exploits local data independence, overlapping distributions, multithreading, and a coarse solve whose global communication requirements permit parallel scaling.

  • The multiscale model problem is heterogeneous diffusion with a microscopically varying diffusion tensor on a polygonal domain.
  • MsFEM formulation: MsFEM uses nested coarse and fine partitions, piecewise linear spaces, and admissible environments that support oversampling around each coarse element.
  • MsFEM formulation: The oversampling formulation includes a conforming projection to convert locally constructed discontinuous contributions into a globally continuous approximation.
  • Implementation: Dune-Multiscale is implemented using Dune-GDT, Dune-XT, and Dune core modules, and can operate as either an application or library.
  • Parallelization: The implementation uses overlapping coarse-grid distributions to support globally continuous solutions and TBB to dynamically load-balance work within CPUs.
  • Parallelization: Cell corrector problems are locally solvable with respect to neighboring coarse cells, enabling parallel assembly across partitions and threads.
  • Implementation: Cell problems are factorized once and reused for multiple right-hand sides, with runtime switching between direct and iterative solvers when needed.
  • Parallelization: BiCGSTAB preconditioned by AMG solves the distributed coarse system, which is the only algorithmic step requiring global communication.

4.5. Sum-factorization for high order discretizations to improve node level performance

Dune uses matrix-free, high-order finite-element kernels and explicit SIMD vectorization to address memory-bandwidth limits on modern CPUs. On an Intel Haswell node, the approach reaches roughly 40% of theoretical peak performance for a DG operator, while requiring compatible preconditioners to preserve solver efficiency.

  • Approach: Dune demonstrates HPC simulation code for modern architectures using matrix-free techniques for high-order discretizations.The implementation was developed in Dune-PDELab and continued in Dune-codegen.
  • Approach: Matrix-free sparse-matrix application shifts arithmetic intensity toward the compute-bound regime of modern CPUs.This approach targets hardware where memory bandwidth has not kept pace with increasing floating-point capability.
  • Vectorization: Explicit SIMD vectorization batches sum-factorization kernels because compilers often cannot adequately autovectorize degree-dependent tensor contractions.The implementation uses a SIMD abstraction layer to support different instruction sets.
  • Performance: Roughly 40% of the theoretical 1.17 TFlops/s peak is achieved for a DG finite-element operator on a 32-core Intel Haswell node.The measurements use MPI to saturate the node and extensively use SIMD instructions.
  • Implementation: The FastDGAssembler avoids gather/scatter operations by using views onto global data, eliminating unnecessary copies and index calculations.This assembler is essential for the presented node-level performance and can also benefit traditional DG implementations.
  • Solver considerations: Matrix-free iterative solvers still require preconditioners that preserve low memory bandwidth while maintaining good convergence.Otherwise, faster iterations can be offset by substantially more solver iterations.

5. Development trends in Dune

Dune’s development continues across asynchronous communication, thread parallelism, Python and DSL integration, and automated code generation. These efforts aim to extend scalability and make high-performance optimizations more accessible while preserving the framework’s modular structure.

  • Scope and stability: Dune supports use cases from personal laptops to TOP500 supercomputers, across methodologies, engineering applications, and educational and corporate research.
  • Scope and stability: The framework’s stable modular structure permits experimentation and public release of new features without compromising core stability.The authors acknowledge that modularity can produce multiple implementations of the same problem.
  • Asynchronous communication: Asynchronous communication is being developed to address increasing communication overhead as future HPC systems use more processes.Dune’s planned abstractions build on MPI 3.0 and encapsulate requests and buffers in MPIFuture objects.
  • Asynchronous communication: Dune is incorporating asynchronous solvers such as pipelined CG to overlap global communication with operator application and hide communication costs.
  • Thread parallelism: Future thread-parallel development follows the MPI+X model, with Intel Thread Building Blocks planned as Dune’s thread interface.Exa-Dune has prototyped threaded assemblers, specialized solvers, mesh partitioning, and block-structured matrix formats.
  • DSLs and code generation: UFL and Dune-codegen connect scripting-language descriptions with efficient PDE implementations through code generation.UFL is used for model descriptions, while Dune-codegen exposes performance optimizations developed in Exa-Dune.
  • DSLs and code generation: Dune-codegen generates optimized LocalOperator classes, explores SIMD strategies by autotuning, and supports additional mesh optimizations.The toolchain is still described as an ongoing effort in early development.
Loading 1909.13672v3…