Scalable tensor-product preconditioners for high-order finite-element methods: Scalar equations

Highlights: • A tensor-product preconditioner for spectral-element discretizations is presented. • The preconditioner minimizes the error between the block-diagonal of the Jacobian matrix and a given tensor-product form. • The preconditioner can be formed and applied at a cost which scales linearly in solution order N per degree of freedom, i.e. at the same cost as a residual evaluation. -- Abstract: We present a tensor-product-based preconditioner for high-order discontinuous-Galerkin (DG) discretizations. The preconditioner is based on approximating the block diagonal of the Jacobian matrix corresponding to element-wise coupling with the sum of tensor products of small one-dimensional matrices. The preconditioner is obtained through an algebraic procedure which minimizes the error between the tensor-product approximation and the exact elemental block Jacobian. Inverting the full elemental block Jacobian requires $O\left(N^d\right)$ memory storage and $O\left(N^{2d}\right)$ operations, while applying its inverse requires $O\left(N^d\right)$ operations per degree of freedom, where N is the solution order and d is the dimension of the problem. Thus, traditional block preconditioners become impractical with increasing dimension, d, and order, N. The cost of forming, storing, or applying the current tensor-product-based preconditioner scales linearly with solution order ($O\left(N\right)$) per degree of freedom for arbitrary number of dimensions. Furthermore, the tensor-product-based preconditioner recovers the exact block-Jacobi preconditioner in the case of constant-coefficient scalar problems on right parallelepiped elements. Numerical results demonstrate the effectiveness of the preconditioner for solving 4D (3D-space+time) DG discretizations of scalar advection-diffusion problems up to 32nd order.