Local Fourier Analysis of Domain Decomposition and Multigrid Methods for High-Order Matrix-Free Finite Elements

Abstract

High-order matrix-free finite element operators offer superior performance on modern high performance computing hardware when compared to assembled sparse matrices, both with respect to floating point operations needed for operator evaluation and the memory transfer needed for a matrix-vector product. However, high-order matrix-free operators require iterative solvers, such as Krylov subspace methods, and these methods converge slowly for ill-conditioned operators. Preconditioning techniques are needed to improve the convergence of these iterative solvers independent of problem size and resolution.

P-multigrid and domain decomposition methods are particularly well suited for problems on unstructured meshes, but these methods can involve parameters that require careful tuning to ensure proper convergence. Local Fourier Analysis (LFA) of these preconditioners describes how these methods affect frequency modes in the error for the operator defined on an infinite or periodic domain and can provide sharp convergence estimates and parameter tuning while only requiring computation on a single representative element or macro-element patch.

We develop LFA of high-order finite element operators, focusing on multigrid and domain decomposition preconditioning techniques. The LFA of p-multigrid is validated with numerical experiments, and we extend this LFA to reproduce previous work with h-multigrid by using macro-elements consisting of multiple low-order finite elements.

We also develop LFA of the lumped and Dirichlet versions of Balancing Domain Decomposition by Constraints (BDDC) preconditioners for high-order finite elements. By using Fast Diagonalization Method approximate subdomain solvers, the increased setup costs for the Dirichlet BDDC preconditioner, relative to the lumped variant, can be substantially reduced, making Dirichlet BDDC an attractive preconditioner. We validate this work against previous numerical experiments and exactly reproduce previous work on the LFA of BDDC for subdomains with multiple low-order finite elements.

Aggressive coarsening in p-multigrid is not supported by traditional polynomial smoothers, such as Chebyshev.Dirichlet BDDC can be used as a smoother for p-multigrid to target a wider range of frequency modes, which facilitates more aggressive coarsening. We provide LFA of p-multigrid with Dirichlet BDDC smoothing to demonstrate the suitability of this approach for preconditioning high-order matrix-free finite element operators.