The next seminar “Modelling of materials – theory, model reduction and efficient numerical methods” will take place on Wednesday from 9:00 in lecture room K3. The talks will be given by Patrick Farrell. Please see the details below.
Speaker: Patrick Farrell
Title: Optimal-complexity solvers for canonical problems of grad, curl, and div
Abstract: The $L^2$ de Rham complex is one of the central objects of mathematical physics, as it encodes the fundamental topological relationships between the operators grad, curl, and div. The Riesz maps of the $L^2$ de Rham complex are PDE problems that arise naturally from this complex. Their numerical solutions frequently arise as subproblems in the construction of fast solvers for more complicated problems; for example, fast numerical solvers for the incompressible Stokes equations can be built from solvers for the $H(grad)$ and $L^2$ Riesz maps.
In this work we present multigrid solvers for high-order finite element discretizations of these Riesz maps. The striking feature of these solvers is that they exhibit optimal complexity in polynomial degree $p$, i.e.~we can solve $Ax = b$ to a given tolerance with the same time- and space-complexity in $p$ as computing the residual $x \mapsto Ax – b$.
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(grad/curl/div)$ inner products on the reference hexahedron. Remarkably, the resulting mass and stiffness matrices have sparsities akin to those of low-order finite difference discretisations, independent of $p$. This sparsity enables the fast solution of certain key subproblems arising in preconditioners with $p$-robust convergence, in the separable case. In the non-separable case, the method can be applied to a spectrally-equivalent auxiliary operator.
There is one further twist of linear algebra. 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 delicately chosen sparsity patterns arising from static condensation. This final step yields overall solvers with computational complexity and storage that are both optimal in the polynomial degree $p$.
We demonstrate the approach by building high-order solvers for linear elasticity and the incompressible Stokes equations at p = 11 in three dimensions.