A two-scale approach for efficient on-the-fly operator assembly in massively parallel high performance multigrid codes

DOI10.1016/J.APNUM.2017.07.006zbMATH Open1375.65168arXiv1608.06473OpenAlexW2963879940WikidataQ122918470 ScholiaQ122918470MaRDI QIDQ2408508FDOQ2408508

Authors: Yanyan Li 

Publication date: 12 October 2017

Published in: Applied Numerical Mathematics (Search for Journal in Brave)

Abstract: Matrix-free finite element implementations of massively parallel geometric multigrid save memory and are often significantly faster than implementations using classical sparse matrix techniques. They are especially well suited for hierarchical hybrid grids on polyhedral domains. In the case of constant coefficients all fine grid node stencils in the interior of a coarse macro element are equal. However, for non-polyhedral domains the situation changes. Then even for the Laplace operator, the non-linear element mapping leads to fine grid stencils that can vary from grid point to grid point. This observation motivates a new two-scale approach that exploits a piecewise polynomial approximation of the fine grid operator with respect to the coarse mesh size. The low-cost evaluation of these surrogate polynomials results in an efficient stencil assembly on-the-fly for non-polyhedral domains that can be significantly more efficient than matrix-free techniques that are based on an element-wise assembly. The performance analysis and additional hardware-aware code optimizations are based on the Execution-Cache-Memory model. Several aspects such as two-scale a priori error bounds and double discretization techniques are presented. Weak and strong scaling results illustrate the benefits of the new technique when used within large scale PDE solvers.

Full work available at URL: https://arxiv.org/abs/1608.06473

Recommendations

• A stencil scaling approach for accelerating matrix-free finite element implementations
• A Parallel Geometric Multigrid Method for Finite Elements on Octree Meshes
• Stencil scaling for vector-valued PDEs on hybrid grids with applications to generalized Newtonian fluids
• Fast matrix-free evaluation of discontinuous Galerkin finite element operators
• A generic interface for parallel cell-based finite element operator application

zbMATH Keywords

Laplace operatorsparse matrixerror boundfinite elementexecution-cache-memory modellarge scale scaling resultsmassively parallel multigridmatrix free on-the-fly assemblysurrogate operatortwo-scale PDE discretization

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Packaged methods for numerical algorithms (65Y15) Numerical computation of matrix norms, conditioning, scaling (65F35) Boundary value problems for second-order elliptic equations (35J25) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30)

Cites Work

• Title not available (Why is that?)
• Automated solution of differential equations by the finite element method. The FEniCS book
• A unified sparse matrix data format for efficient general sparse matrix-vector multiplication on modern processors with wide SIMD units
• Title not available (Why is that?)
• Isogeometric analysis. Toward integration of CAD and FEA
• Computational fluid-structure interaction. Methods and applications
• Tetrahedral grid refinement
• A generic interface for parallel cell-based finite element operator application
• Multigrid techniques. 1984 guide with applications to fluid dynamics
• A scalable multi-level preconditioner for matrix-free µ-finite element analysis of human bone structures
• A massively parallel solver for discrete Poisson-like problems
• Title not available (Why is that?)
• Icosahedral Discretization of the Two-Sphere
• Mortar methods with curved interfaces
• Hierarchical hybrid grids: data structures and core algorithms for multigrid
• Cache optimization for structured and unstructured grid multigrid
• Title not available (Why is that?)
• Optimizing sparse matrix-matrix multiplication for the GPU
• A scalable, matrix-free multigrid preconditioner for finite element discretizations of heterogeneous Stokes flow
• Performance and scalability of hierarchical hybrid multigrid solvers for Stokes systems
• Computational seismology. A practical introduction
• Title not available (Why is that?)
• Reducing parallel communication in algebraic multigrid through sparsification
• Rendering curves and surfaces with hybrid subdivision and forward differencing
• Title not available (Why is that?)

Cited In (11)

• Towards robust, fast solutions of elliptic equations on complex domains through hybrid high-order discretizations and non-nested multigrid methods
• A Massively Parallel Eulerian-Lagrangian Method for Advection-Dominated Transport in Viscous Fluids
• A Matrix-Free ILU Realization Based on Surrogates
• A stencil scaling approach for accelerating matrix-free finite element implementations
• The surrogate matrix methodology: accelerating isogeometric analysis of waves
• The surrogate matrix methodology: low-cost assembly for isogeometric analysis
• Solver comparison for Poisson-like equations on tokamak geometries
• Automatic stabilization of finite-element simulations using neural networks and hierarchical matrices
• Stencil scaling for vector-valued PDEs on hybrid grids with applications to generalized Newtonian fluids
• Textbook efficiency: massively parallel matrix-free multigrid for the Stokes system
• The Surrogate Matrix Methodology: A Priori Error Estimation

Uses Software

• hypre
• FEniCS
• FFC
• SELL_C_sigma
• Exa-Dune

This page was built for publication: A two-scale approach for efficient on-the-fly operator assembly in massively parallel high performance multigrid codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408508)