Scaling to the stars -- a linearly scaling elliptic solver for $p$-multigrid

Abstract

High-order methods gain increased attention in computational fluid dynamics. However, due to the time step restrictions arising from the semi-implicit time stepping for the incompressible case, the potential advantage of these methods depends critically on efficient elliptic solvers. Due to the operation counts of operators scaling with with the polynomial degree $p$ times the number of degrees of freedom $n_{\mathrm{DOF}}$, the runtime of the best available multigrid solvers scales with $\mathcal{O}(p\cdot n_{\mathrm{DOF}})$. This scaling with $p$ significantly lowers the applicability of high-order methods to high orders. While the operators for residual evaluation can be linearized when using static condensation, Schwarz-type smoothers require their inverses on fixed subdomains. No explicit inverse is known in the condensed case and matrix-matrix multiplications scale with $p\cdot n_{\mathrm{DOF}}$. This paper derives a matrix-free explicit inverse for the static condensed operator in a cuboidal subdomain. It scales with $p^3$ per element, i.e. $n_{\mathrm{DOF}}$ globally, and allows for a linearly scaling additive Schwarz smoother, yielding a $p$-multigrid cycle with an operation count of $\mathcal{O}(n_{\mathrm{DOF}})$. The resulting solver uses fewer than four iterations for all polynomial degrees to reduce the residual by ten orders and has a runtime scaling linearly with $n_{\mathrm{DOF}}$ for polynomial degrees at least up to $48$. Furthermore the runtime is less than one microsecond per unknown over wide parameter ranges when using one core of a CPU, leading to time-stepping for the incompressible Navier-Stokes equations using as much time for explicitly treated convection terms as for the elliptic solvers.

References in corpus (8)

• Nodal Discontinuous Galerkin Methods on Graphics Processors
• Fast matrix-free evaluation of discontinuous Galerkin finite element operators
• FFT, FMM, or Multigrid? A comparative Study of State-Of-the-Art Poisson Solvers for Uniform and Nonuniform Grids in the Unit Cube
• Efficiency of high-performance discontinuous Galerkin spectral element methods for under-resolved turbulent incompressible flows
• On thin plate spline interpolation
• High-performance Implementation of Matrix-free High-order Discontinuous Galerkin Methods
• Robust multigrid for high-order discontinuous Galerkin methods: A fast Poisson solver suitable for high-aspect ratio Cartesian grids
• Factorizing the factorization - a spectral-element solver for elliptic equations with linear operation count

Cited by in corpus (5)

• Hybrid multigrid methods for high-order discontinuous Galerkin discretizations
• A scalable and robust vertex-star relaxation for high-order FEM
• Multilevel Interior Penalty Methods on GPUs
• Linearizing the hybridizable discontinuous Galerkin method: A linearly scaling operator
• A natural decomposition of viscous dissipation in DG methods for turbulent incompressible flows