Scalable Tensor-Product Preconditioners for High-Order Finite-Element Methods: Scalar Equations

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 ( N d ) memory storage and O ( N 2 d ) operations, while applying its inverse requires O ( N d ) 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 ( N ) ) 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.