14:00
The numerical solution of elliptic PDEs is often the most computationally intensive task in large-scale continuum mechanics simulations. High-order finite element methods can efficiently exploit modern parallel hardware while offering very rapid convergence properties. As the polynomial degree is increased, the efficient solution of such PDEs becomes difficult. In this talk we introduce preconditioners for high-order discretizations. We build upon the pioneering work of Pavarino, who proved in 1993 that the additive Schwarz method with vertex patches and a low-order coarse space gives a solver for symmetric and coercive problems that is robust to the polynomial degree.
However, for very high polynomial degrees it is not feasible to assemble or factorize the matrices for each vertex patch, as the patch matrices contain dense blocks, which couple together all degrees of freedom within a cell. The central novelty of the preconditioners we develop is that they have the same time and space complexity as sum-factorized operator application on unstructured meshes of tensor-product cells, i.e., we can solve $A x=b$ with the same complexity as evaluating $b-A x$. Our solver relies on new finite elements for the de Rham complex that enable the blocks in the stiffness matrix corresponding to the cell interiors to become diagonal for scalar PDEs or block diagonal for vector-valued PDEs. With these new elements, the patch problems are as sparse as a low-order finite difference discretization, while having a sparser Cholesky factorization. In the non-separable case, themethod can be applied as a preconditioner by approximating the problem with a separable surrogate. Through the careful use of incomplete factorizations and choice of space decomposition we achieve optimal fill-in in the patch factors, ultimately allowing for optimal-complexity storage and computational cost across the setup and solution stages.
We demonstrate the approach by solving the Riesz maps of $H^1$, $H(\mathrm{curl})$, and $H(\mathrm{div})$ in three dimensions at $p = 15$.