Approximate tensor-product preconditioners for very high order discontinuous Galerkin methods

Abstract

In this paper, we develop a new tensor-product based preconditioner for discontinuous Galerkin methods with polynomial degrees higher than those typically employed. This preconditioner uses an automatic, purely algebraic method to approximate the exact block Jacobi preconditioner by Kronecker products of several small, one-dimensional matrices. Traditional matrix-based preconditioners require $\mathcal{O}(p^{2d})$ storage and $\mathcal{O}(p^{3d})$ computational work, where $p$ is the degree of basis polynomials used, and $d$ is the spatial dimension. Our SVD-based tensor-product preconditioner requires $\mathcal{O}(p^{d+1})$ storage, $\mathcal{O}(p^{d+1})$ work in two spatial dimensions, and $\mathcal{O}(p^{d+2})$ work in three spatial dimensions. Combined with a matrix-free Newton-Krylov solver, these preconditioners allow for the solution of DG systems in linear time in $p$ per degree of freedom in 2D, and reduce the computational complexity from $\mathcal{O}(p^9)$ to $\mathcal{O}(p^5)$ in 3D. Numerical results are shown in 2D and 3D for the advection and Euler equations, using polynomials of degree up to $p=15$. For many test cases, the preconditioner results in similar iteration counts when compared with the exact block Jacobi preconditioner, and performance is significantly improved for high polynomial degrees $p$.

40 pages, 15 figures

Cited by in corpus (19)

• Efficient Exascale Discretizations: High-Order Finite Element Methods
• Sparse invariant domain preserving discontinuous Galerkin methods with subcell convex limiting
• Hybrid multigrid methods for high-order discontinuous Galerkin discretizations
• Efficient low-order refined preconditioners for high-order matrix-free continuous and discontinuous Galerkin methods
• An Entropy Stable Nodal Discontinuous Galerkin Method for the resistive MHD Equations. Part II: Subcell Finite Volume Shock Capturing
• A matrix-free high-order discontinuous Galerkin compressible Navier-Stokes solver: A performance comparison of compressible and incompressible formulations for turbulent incompressible flows
• Nektar++: Design and implementation of an implicit, spectral/$hp$ element, compressible flow solver using a Jacobian-free Newton Krylov approach
• Analysis and entropy stability of the line-based discontinuous Galerkin method
• High-order matrix-free incompressible flow solvers with GPU acceleration and low-order refined preconditioners
• Fast Tensor Product Schwarz Smoothers for High-Order Discontinuous Galerkin Methods
• A scalable and robust vertex-star relaxation for high-order FEM
• Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions
• Matrix-free GPU-accelerated saddle-point solvers for high-order problems in $H(\mathrm{div})$
• Conservative and accurate solution transfer between high-order and low-order refined finite element spaces
• Stable nodal projection method on octree grids
• Multilevel Interior Penalty Methods on GPUs
• Uniform subspace correction preconditioners for discontinuous Galerkin methods with $hp$-refinement
• AutoHOOT: Automatic High-Order Optimization for Tensors
• A high-order discontinuous Galerkin pressure robust splitting scheme for incompressible flows