Matrix-free multigrid block-preconditioners for higher order Discontinuous Galerkin discretisations

Peter Bastian, Eike Müller, Steffen Muething, Marian Piatkowski

Research output: Contribution to journalArticle

Abstract

Efficient and suitably preconditioned iterative solvers for elliptic partial differential equations (PDEs) of the convection-diffusion type are used in all fields of science and engineering, including for example computational fluid dynamics, nuclear reactor simulations and combustion models. To achieve optimal performance, solvers have to exhibit high arithmetic intensity and need to exploit every form of parallelism available in modern manycore CPUs. This includes both distributed- or shared memory parallelisation between processors and vectorisation on individual cores. The computationally most expensive components of the solver are the repeated applications of the linear operator and the preconditioner. For discretisations based on higher-order Discontinuous Galerkin methods, sum-factorisation results in a dramatic reduction of the computational complexity of the operator application while, at the same time, the matrix-free implementation can run at a significant fraction of the theoretical peak floating point performance. Multigrid methods for high order methods often rely on block-smoothers to reduce high-frequency error components within one grid cell. Traditionally, this requires the assembly and expensive dense matrix solve in each grid cell, which counteracts any improvements achieved in the fast matrix-free operator application. To overcome this issue, we present a new matrix-free implementation of block-smoothers. Inverting the block matrices iteratively avoids storage and factorisation of the matrix and makes it is possible to harness the full power of the CPU. We implemented a hybrid multigrid algorithm with matrix-free block-smoothers in the high order Discontinuous Galerkin (DG) space combined with a low order coarse grid correction using algebraic multigrid where only low order components are explicitly assembled. The effectiveness of this approach is demonstrated by solving a set of representative elliptic PDEs of increasing complexity, including a convection dominated problem and the stationary SPE10 benchmark.

Original languageEnglish
Pages (from-to)417-439
Number of pages23
JournalJournal of Computational Physics
Volume394
DOIs
Publication statusPublished - 1 Oct 2019

Fingerprint

matrices
elliptic differential equations
grids
Factorization
factorization
partial differential equations
Partial differential equations
Program processors
convection
multigrid methods
harnesses
linear operators
operators
Galerkin method
Galerkin methods
cells
floating
Computational complexity
assembly
engineering

Keywords

  • DUNE
  • Discontinuous Galerkin
  • Elliptic PDE
  • Matrix-free methods
  • Multigrid
  • Preconditioners

ASJC Scopus subject areas

  • Numerical Analysis
  • Modelling and Simulation
  • Physics and Astronomy (miscellaneous)
  • Physics and Astronomy(all)
  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics

Cite this

Matrix-free multigrid block-preconditioners for higher order Discontinuous Galerkin discretisations. / Bastian, Peter; Müller, Eike; Muething, Steffen; Piatkowski, Marian.

In: Journal of Computational Physics, Vol. 394, 01.10.2019, p. 417-439.

Research output: Contribution to journalArticle

@article{5e04e60208ef4d918a4de085bdd9fccb,
title = "Matrix-free multigrid block-preconditioners for higher order Discontinuous Galerkin discretisations",
abstract = "Efficient and suitably preconditioned iterative solvers for elliptic partial differential equations (PDEs) of the convection-diffusion type are used in all fields of science and engineering, including for example computational fluid dynamics, nuclear reactor simulations and combustion models. To achieve optimal performance, solvers have to exhibit high arithmetic intensity and need to exploit every form of parallelism available in modern manycore CPUs. This includes both distributed- or shared memory parallelisation between processors and vectorisation on individual cores. The computationally most expensive components of the solver are the repeated applications of the linear operator and the preconditioner. For discretisations based on higher-order Discontinuous Galerkin methods, sum-factorisation results in a dramatic reduction of the computational complexity of the operator application while, at the same time, the matrix-free implementation can run at a significant fraction of the theoretical peak floating point performance. Multigrid methods for high order methods often rely on block-smoothers to reduce high-frequency error components within one grid cell. Traditionally, this requires the assembly and expensive dense matrix solve in each grid cell, which counteracts any improvements achieved in the fast matrix-free operator application. To overcome this issue, we present a new matrix-free implementation of block-smoothers. Inverting the block matrices iteratively avoids storage and factorisation of the matrix and makes it is possible to harness the full power of the CPU. We implemented a hybrid multigrid algorithm with matrix-free block-smoothers in the high order Discontinuous Galerkin (DG) space combined with a low order coarse grid correction using algebraic multigrid where only low order components are explicitly assembled. The effectiveness of this approach is demonstrated by solving a set of representative elliptic PDEs of increasing complexity, including a convection dominated problem and the stationary SPE10 benchmark.",
keywords = "DUNE, Discontinuous Galerkin, Elliptic PDE, Matrix-free methods, Multigrid, Preconditioners",
author = "Peter Bastian and Eike M{\"u}ller and Steffen Muething and Marian Piatkowski",
year = "2019",
month = "10",
day = "1",
doi = "10.1016/j.jcp.2019.06.001",
language = "English",
volume = "394",
pages = "417--439",
journal = "Journal of Computational Physics",
issn = "0021-9991",
publisher = "Elsevier Academic Press Inc",

}

TY - JOUR

T1 - Matrix-free multigrid block-preconditioners for higher order Discontinuous Galerkin discretisations

AU - Bastian, Peter

AU - Müller, Eike

AU - Muething, Steffen

AU - Piatkowski, Marian

PY - 2019/10/1

Y1 - 2019/10/1

N2 - Efficient and suitably preconditioned iterative solvers for elliptic partial differential equations (PDEs) of the convection-diffusion type are used in all fields of science and engineering, including for example computational fluid dynamics, nuclear reactor simulations and combustion models. To achieve optimal performance, solvers have to exhibit high arithmetic intensity and need to exploit every form of parallelism available in modern manycore CPUs. This includes both distributed- or shared memory parallelisation between processors and vectorisation on individual cores. The computationally most expensive components of the solver are the repeated applications of the linear operator and the preconditioner. For discretisations based on higher-order Discontinuous Galerkin methods, sum-factorisation results in a dramatic reduction of the computational complexity of the operator application while, at the same time, the matrix-free implementation can run at a significant fraction of the theoretical peak floating point performance. Multigrid methods for high order methods often rely on block-smoothers to reduce high-frequency error components within one grid cell. Traditionally, this requires the assembly and expensive dense matrix solve in each grid cell, which counteracts any improvements achieved in the fast matrix-free operator application. To overcome this issue, we present a new matrix-free implementation of block-smoothers. Inverting the block matrices iteratively avoids storage and factorisation of the matrix and makes it is possible to harness the full power of the CPU. We implemented a hybrid multigrid algorithm with matrix-free block-smoothers in the high order Discontinuous Galerkin (DG) space combined with a low order coarse grid correction using algebraic multigrid where only low order components are explicitly assembled. The effectiveness of this approach is demonstrated by solving a set of representative elliptic PDEs of increasing complexity, including a convection dominated problem and the stationary SPE10 benchmark.

AB - Efficient and suitably preconditioned iterative solvers for elliptic partial differential equations (PDEs) of the convection-diffusion type are used in all fields of science and engineering, including for example computational fluid dynamics, nuclear reactor simulations and combustion models. To achieve optimal performance, solvers have to exhibit high arithmetic intensity and need to exploit every form of parallelism available in modern manycore CPUs. This includes both distributed- or shared memory parallelisation between processors and vectorisation on individual cores. The computationally most expensive components of the solver are the repeated applications of the linear operator and the preconditioner. For discretisations based on higher-order Discontinuous Galerkin methods, sum-factorisation results in a dramatic reduction of the computational complexity of the operator application while, at the same time, the matrix-free implementation can run at a significant fraction of the theoretical peak floating point performance. Multigrid methods for high order methods often rely on block-smoothers to reduce high-frequency error components within one grid cell. Traditionally, this requires the assembly and expensive dense matrix solve in each grid cell, which counteracts any improvements achieved in the fast matrix-free operator application. To overcome this issue, we present a new matrix-free implementation of block-smoothers. Inverting the block matrices iteratively avoids storage and factorisation of the matrix and makes it is possible to harness the full power of the CPU. We implemented a hybrid multigrid algorithm with matrix-free block-smoothers in the high order Discontinuous Galerkin (DG) space combined with a low order coarse grid correction using algebraic multigrid where only low order components are explicitly assembled. The effectiveness of this approach is demonstrated by solving a set of representative elliptic PDEs of increasing complexity, including a convection dominated problem and the stationary SPE10 benchmark.

KW - DUNE

KW - Discontinuous Galerkin

KW - Elliptic PDE

KW - Matrix-free methods

KW - Multigrid

KW - Preconditioners

UR - http://www.scopus.com/inward/record.url?scp=85067062086&partnerID=8YFLogxK

U2 - 10.1016/j.jcp.2019.06.001

DO - 10.1016/j.jcp.2019.06.001

M3 - Article

VL - 394

SP - 417

EP - 439

JO - Journal of Computational Physics

JF - Journal of Computational Physics

SN - 0021-9991

ER -