Optimal-complexity Multigrid Solvers for High-order FEM in the de Rham Complex
B1 L3 R3119
In this work we present multigrid solvers for high-order finite element discretizations of these Riesz maps with optimal complexity in polynomial degree, i.e. With the same time and space complexity as sum-factorized operator application.
Overview
Abstract
The Riesz maps of the $L^2$ de Rham complex frequently arise as subproblems in the construction of fast preconditioners for more complicated problems. In this work we present multigrid solvers for high-order finite element discretizations of these Riesz maps with optimal complexity in polynomial degree, i.e.~with the same time and space complexity as sum-factorized operator application. The key idea of our approach is to build new finite elements for each space in the de Rham complex with orthogonality properties in both the $L^2$ and $H(\mathrm{d})$ inner products ($\mathrm{d} \in \{\mathrm{grad}, \mathrm{curl}, \mathrm{div}\})$ on the reference hexahedron. The resulting sparsity enables the fast solution of the patch problems arising in the Arnold--Falk--Winther and Hiptmair--Xu space decompositions, in the separable case. In the non-separable case, the method can be applied to a spectrally-equivalent auxiliary operator. With exact Cholesky factorizations of the sparse patch problems, the application complexity is optimal but the setup costs and storage are not. We overcome this with the use of incomplete Cholesky factorizations with carefully specified sparsity patterns arising from static condensation. This yields multigrid relaxations with computational complexity and storage that are both optimal in the polynomial degree.
Brief Biography
Patrick Farrell is an associate professor in the numerical analysis group of the University of Oxford. He studied for his undergraduate degree at the National University of Ireland, Galway, and for his PhD at Imperial College London. His research interests are in finite element methods, bifurcation analysis of nonlinear PDEs, adjoint techniques, and fast preconditioners and solvers. He has been awarded an EPSRC Early Career Research Fellowship (2013-2018), the 2015 Wilkinson Prize for Numerical Software, a 2015 Leslie Fox Prize in Numerical Analysis, the 2021 Charles Broyden Prize in optimisation, and a 2021 Whitehead Prize from the London Mathematical Society.
