Approximate tensor-product preconditioners for very high order discontinuous Galerkin methods
This work addresses the computational bottleneck of high-order discontinuous Galerkin methods for large-scale simulations, offering a practical preconditioner that drastically reduces storage and work for high polynomial degrees.
The paper develops a tensor-product preconditioner for high-order discontinuous Galerkin methods that reduces storage from O(p^{2d}) to O(p^{d+1}) and computational work from O(p^{3d}) to O(p^{d+1}) in 2D and O(p^{d+2}) in 3D, enabling linear time per degree of freedom in 2D and reducing complexity from O(p^9) to O(p^5) in 3D. Numerical results for advection and Euler equations up to p=15 show similar iteration counts to exact block Jacobi with significantly improved performance.
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$.