Computational Mathematics and Applications Seminar

In space dimension 2 we present a finite element complex for the deformation operator acting on vectorfields and the linearized curvature operator acting on symmetric 2 by 2 matrices. We also present the tools that were used in the construction, namely the BGG diagram chase and the framework of finite element systems. For this general framework we can prove a de Rham theorem on cohomology groups in the flat case and a Bianchi identity in the case with curvature.

Hilbert complexes are chains of spaces linked by operators, with properties that are crucial to establishing the well-posedness of certain systems of partial differential equations. Designing stable numerical schemes for such systems, without resorting to nonphysical stabilisation processes, requires reproducing the complex properties at the discrete level. Finite-element complexes have been extensively developed since the late 2000's, in particular by Arnold, Falk, Winther and collaborators. These are however limited to certain types of meshes (mostly, tetrahedral and hexahedral meshes), which limits options for, e.g., local mesh refinement.

In this talk we will introduce the Discrete De Rham complex, a discrete version of one of the most popular complexes of differential operators (involving the gradient, curl and divergence), that can be applied on meshes consisting of generic polytopes. We will use a simple magnetostatic model to motivate the need for (continuous and discrete) complexes, then give a presentation of the lowest-order version of the complex and sketch its links with the CW cochain complex on the mesh. We will then briefly explain how this lowest-order version is naturally extended to an arbitrary-order version, and briefly present the associated properties (Poincaré inequalities, primal and adjoint consistency, commutation properties, etc.) that enable the analysis of schemes based on this complex.

Tensor structured linear operators play an important role in matrix equations and low-rank modelling. Motivated by this we consider the problem of approximating a matrix by a sum of Kronecker products. It is known that an optimal approximation in Frobenius norm can be obtained from the singular value decomposition of a rearranged matrix, but when the goal is to approximate the matrix as a linear map, an operator norm would be a more appropriate error measure. We present an alternating optimization approach for the corresponding approximation problem in spectral norm that is based on semidefinite programming, and report on its practical performance for small examples.
This is joint work with Venkat Chandrasekaran and Mareike Dressler.

That the linear systems arising upon the discretization of elliptic PDEs can be solved efficiently is well-known, and iterative solvers that often attain linear complexity (multigrid, Krylov methods, etc) have proven very successful. Interestingly, it has recently been demonstrated that it is often possible to directly compute an approximate inverse to the coefficient matrix in linear (or close to linear) time. The talk will argue that such direct solvers have several compelling qualities, including improved stability and robustness, the ability to solve certain problems that have remained intractable to iterative methods, and dramatic improvements in speed in certain environments.

After a general introduction to the field, particular attention will be paid to a set of recently developed randomized algorithms that construct data sparse representations of large dense matrices that arise in scientific computations. These algorithms are entirely black box, and interact with the linear operator to be compressed only via the matrix-vector multiplication.

There is a wide range of problems in continuum mechanics that involve transformation fronts, which are non-stationary interfaces between two different phases in a phase-transforming or a chemically-transforming material. From the mathematical point of view, the considered problems are represented by systems of non-linear PDEs with discontinuities across non-stationary interfaces, kinetics of which depend on the solution of the PDEs. Such problems have a significant industrial relevance – an example of a transformation front is the localised stress-affected chemical reaction in Li-ion batteries with Si-based anodes. Since the kinetics of the transformation fronts depends on the continuum fields, the transformation front propagation can be decelerated and even blocked by the mechanical stresses. This talk will focus on three topics: (1) the stability of the transformation fronts in the vicinity of the equilibrium position for the chemo-mechanical problem, (2) a fictitious-domain finite-element method (CutFEM) for solving non-linear PDEs with transformation fronts and (3) an applied problem of Si lithiation.

Polynomial preconditioning for linear solvers is well-known but not frequently used in current scientific applications.  Furthermore, polynomial preconditioning has long been touted as well-suited for parallel computing; does this claim still hold in our new world of GPU-dominated machines?  We give details of the GMRES polynomial preconditioner and discuss its simple implementation, its properties such as eigenvalue remapping, and choices such as the starting vector and added roots.  We compare polynomial preconditioned GMRES to related methods such as FGMRES and full GMRES without restarting. We conclude with initial evaluations of the polynomial preconditioner for parallel and GPU computing, further discussing how polynomial preconditioning can become useful to real-word applications.

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact @email.

Climate- and weather prediction centres such as the Met Office rely on efficient numerical methods for simulating large scale atmospheric flow. One computational bottleneck in many models is the repeated solution of a large sparse system of linear equations. Preconditioning this system is particularly challenging for state-of-the-art discretisations, such as (mimetic) finite elements or Discontinuous Galerkin (DG) methods. In this talk I will present recent work on developing efficient multigrid preconditioners for practically relevant modelling codes. As reported in a REF2021 Industrial Impact Case Study, multigrid has already led to runtime savings of around 10%-15% for operational global forecasts with the Unified Model. Multigrid also shows superior performance in the Met Office next-generation LFRic model, which is based on a non-trivial finite element discretisation.

Let $A$ be an $n$ by $n$ matrix or a bounded linear operator on a complex Hilbert space $(H, \langle \cdot , \cdot \rangle , \| \cdot \|)$. A closed set $\Omega \subset \mathbb{C}$ is a $K$-spectral set for $A$ if the spectrum of $A$ is contained in $\Omega$ and if, for all rational functions $f$ bounded in $\Omega$, the following inequality holds:
\[\| f(A) \| \leq K \| f \|_{\Omega} ,\]
where $\| \cdot \|$ on the left denotes the norm in $H$ and $\| \cdot \|_{\Omega}$ on the right denotes the $\infty$-norm on $\Omega$. A simple way to obtain a $K$ value for a given set $\Omega$ is to use the Cauchy integral formula and replace the norm of the integral by the integral of the resolvent norm:
\[f(A) = \frac{1}{2 \pi i} \int_{\partial \Omega} ( \zeta I - A )^{-1}
f( \zeta )\,d \zeta \Rightarrow
\| f(A) \| \leq \frac{1}{2 \pi} \left( \int_{\partial \Omega}
\| ( \zeta I - A )^{-1} \|~| d \zeta | \right) \| f \|_{\Omega} .\]
Thus one can always take
\[K = \frac{1}{2 \pi} \int_{\partial \Omega} \| ( \zeta I - A )^{-1} \| | d \zeta | .\]
In M. Crouzeix and A. Greenbaum, Spectral sets: numerical range and beyond, SIAM J. Matrix Anal. Appl., 40 (2019), pp. 1087-1101, different bounds on $K$ were derived.  I will show how these compare to that from the Cauchy integral formula for a variety of applications.  In case $A$ is a matrix and $\Omega$ is simply connected, we can numerically compute what we believe to be the optimal value for $K$ (and, at least, is a lower bound on $K$).  I will show how these values compare with the proven bounds as well.

(joint with  Michel Crouzeix and Natalie Wellen)
 

---

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact @email.

I will discuss new work on practically popular algorithms, including the kernel polynomial method (KPM) and moment matching method, for approximating the spectral density (eigenvalue distribution) of an n x n symmetric matrix A. We will see that natural variants of these algorithms achieve strong worst-case approximation guarantees: they can approximate any spectral density to epsilon accuracy in the Wasserstein-1 distance with roughly O(1/epsilon) matrix-vector multiplications with A. Moreover, we will show that the methods are robust to *in accuracy* in these matrix-vector multiplications, which allows them to be combined with any approximation multiplication algorithm. As an application, we develop a randomized sublinear time algorithm for approximating the spectral density of a normalized graph adjacency or Laplacian matrices. The talk will cover the main tools used in our work, which include random importance sampling methods and stability results for computing orthogonal polynomials via three-term recurrence relations.

---

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact @email.

Solving large-scale Bayesian inverse problems governed by complex models suffers from the twin difficulties of the high dimensionality of the uncertain parameters and computationally expensive forward models. In this talk, we focus on 1. reducing the computational cost when solving these problems (via joint parameter and state dimension reduction) and 2. accounting for the error due to using a reduced order forward model (via Bayesian Approximation Error (BAE)).  To reduce the parameter dimension, we exploit the underlying problem structure (e.g., local sensitivity of the data to parameters, the smoothing properties of the forward model, the fact that the data contain limited information about the (infinite-dimensional) parameter field, and the covariance structure of the prior) and identify a likelihood-informed parameter subspace that shows where the change from prior to posterior is most significant. For the state dimension reduction, we employ a proper orthogonal decomposition (POD) combined with the discrete empirical interpolation method (DEIM) to approximate the nonlinear term in the forward model. We illustrate our approach with a model ice sheet inverse problem governed by the nonlinear Stokes equation for which the basal sliding coefficient field (a parameter that appears in a Robin boundary condition at the base of the geometry) is inferred from the surface ice flow velocity. The results show the potential to make the exploration of the full posterior distribution of the parameter or subsequent predictions more tractable.

This is joint work with Ki-Tae Kim (UC Merced), Benjamin Peherstorfer (NYU) and Tiangang Cui (Monash University).