Mathematical Institute (University of Oxford)

Kirchhoff's celebrated matrix tree theorem expresses the number of spanning trees of a graph as the maximal minor of the Laplacian matrix of the graph. In modern language, this determinantal counting formula reflects the fact that spanning trees form a regular matroid. In this talk, I will give a short historical overview of the tree-counting problem and a related quantity from electrical circuit theory: the effective resistance. I will describe a characterization of effective resistances in terms of a certain polytope and discuss some recent applications to discrete notions of curvature on graphs. More details can be found in the recent preprint: https://arxiv.org/abs/2410.07756

Quantum computers are becoming a reality and current generations of machines are already well beyond the 50-qubit frontier. However, hardware imperfections still overwhelm these devices and it is generally believed the fault-tolerant, error-corrected systems will not be within reach in the near term: a single logical qubit needs to be encoded into potentially thousands of physical qubits which is prohibitive.
 
Due to limited resources, in the near term, hybrid quantum-classical protocols are the most promising candidates for achieving early quantum advantage but these need to resort to quantum error mitigation techniques. I will explain the basic concepts and introduce hybrid quantum-classical protocols are the most promising candidates for achieving early quantum advantage. These have the potential to solve real-world problems---including optimisation or ground-state search---but they suffer from a large number of circuit repetitions required to extract information from the quantum state. I will detail a range of application areas of randomised quantum circuits, such as quantum algorithms, classical shadows, and quantum error mitigation introducing recent results that help lower the barrier for practical quantum advantage.

 

Conferences and networking are important parts of academic life, particularly early in your academic career.  But how do you make the most out of conferences?  And what are the does and don'ts of networking?  Learn about the answers to these questions and more in this panel discussion by postdocs from across the Mathematical Institute.

Dispersive nonlinear partial differential equations can be used to describe a range of physical systems, from water waves to spin states in ferromagnetism. The numerical approximation of solutions with limited differentiability (low-regularity) is crucial for simulating fascinating phenomena arising in these systems including emerging structures in random wave fields and dynamics of domain wall states, but it poses a significant challenge to classical algorithms. Recent years have seen the development of tailored low-regularity integrators to address this challenge. Inherited from their description of physicals systems many such dispersive nonlinear equations possess a rich geometric structure, such as a Hamiltonian formulation and conservation laws. To ensure that numerical schemes lead to meaningful results, it is vital to preserve this structure in numerical approximations. This, however, results in an interesting dichotomy: the rich theory of existent structure-preserving algorithms is typically limited to classical integrators that cannot reliably treat low-regularity phenomena, while most prior designs of low-regularity integrators break geometric structure in the equation. In this talk, we will outline recent advances incorporating structure-preserving properties into low-regularity integrators. Starting from simple discussions on the nonlinear Schrödinger and the Korteweg–de Vries equation we will discuss the construction of such schemes for a general class of dispersive equations before demonstrating an application to the simulation of low-regularity vortex filaments. This is joint work with Yvonne Alama Bronsard, Valeria Banica, Yvain Bruned and Katharina Schratz.

Fourth-order elliptic problems arise in a variety of applications from thin plates to phase separation to liquid crystals. A conforming Galerkin discretization requires a finite dimensional subspace of H2, which in turn means that conforming finite element subspaces are C1-continuous. In contrast to standard H1-conforming C0-elements, C1-elements, particularly those of high order, are less understood from a theoretical perspective and are not implemented in many existing finite element codes. In this talk, we address the implementation of the elements. In particular, we present algorithms that compute C1-finite element approximations to fourth-order elliptic problems and which only require elements with at most C0-continuity. The algorithms are suitable for use in almost all standard finite element packages. Iterative methods and preconditioners for the subproblems in the algorithm will also be presented.

We consider the problem of approximating singular values of a matrix when provided with approximations to the leading singular vectors. In particular, we focus on the Generalized Nystrom (GN) method, a commonly used low-rank approximation, and its error in extracting singular values. Like other approaches, the GN approximation can be interpreted as a perturbation of the original matrix. Up to orthogonal transformations, this perturbation has a peculiar structure that we wish to exploit. Thus, we use the Jordan-Wieldant Theorem and similarity transformations to generalize a matrix perturbation theory result on eigenvalues of a perturbed Hermitian matrix. Finally, combining the above,  we can derive a bound on the GN singular values approximation error. We conclude by performing preliminary numerical examples. The aim is to heuristically study the sharpness of the bound, to give intuitions on how the analysis can be used to compare different approaches, and to provide ideas on how to make the bound computable in practice.

High-order tensor methods for solving both convex and nonconvex optimization problems have recently generated significant research interest, due in part to the natural way in which higher derivatives can be incorporated into adaptive regularization frameworks, leading to algorithms with optimal global rates of convergence and local rates that are faster than Newton's method. On each iteration, to find the next solution approximation, these methods require the unconstrained local minimization of a (potentially nonconvex) multivariate polynomial of degree higher than two, constructed using third-order (or higher) derivative information, and regularized by an appropriate power of the change in the iterates. Developing efficient techniques for the solution of such subproblems is currently, an ongoing topic of research,  and this talk addresses this question for the case of the third-order tensor subproblem.

In particular, we propose the CQR algorithmic framework, for minimizing a nonconvex Cubic multivariate polynomial with  Quartic Regularisation, by sequentially minimizing a sequence of local quadratic models that also incorporate both simple cubic and quartic terms. The role of the cubic term is to crudely approximate local tensor information, while the quartic one provides model regularization and controls progress. We provide necessary and sufficient optimality conditions that fully characterise the global minimizers of these cubic-quartic models. We then turn these conditions into secular equations that can be solved using nonlinear eigenvalue techniques. We show, using our optimality characterisations, that a CQR algorithmic variant has the optimal-order evaluation complexity of $O(\epsilon^{-3/2})$ when applied to minimizing our quartically-regularised cubic subproblem, which can be further improved in special cases.  We propose practical CQR variants that judiciously use local tensor information to construct the local cubic-quartic models. We test these variants numerically and observe them to be competitive with ARC and other subproblem solvers on typical instances and even superior on ill-conditioned subproblems with special structure.

Fourth-order elliptic problems arise in a variety of applications from thin plates to phase separation to liquid crystals. A conforming Galerkin discretization requires a finite dimensional subspace of $H^2$, which in turn means that conforming finite element subspaces are $C^1$-continuous. In contrast to standard $H^1$-conforming $C^0$ elements, $C^1$ elements, particularly those of high order, are less understood from a theoretical perspective and are not implemented in many existing finite element codes. In this talk, we address the implementation of the elements. In particular, we present algorithms that compute $C^1$ finite element approximations to fourth-order elliptic problems and which only require elements with at most $C^0$-continuity. We also discuss solvers for the resulting subproblems and illustrate the method on a number of representative test problems.

We present new high-order finite elements discretizing the $L^2$ de Rham complex on triangular and tetrahedral meshes. The finite elements discretize the same spaces as usual, but with different basis functions. They allow for fast linear solvers based on static condensation and space decomposition methods.

The new elements build upon the definition of degrees of freedom given by (Demkowicz et al., De Rham diagram for $hp$ finite element spaces. Comput.~Math.~Appl., 39(7-8):29--38, 2000.), and consist of integral moments on a symmetric reference simplex with respect to a numerically computed polynomial basis that is orthogonal in both the $L^2$- and $H(\mathrm{d})$-inner products ($\mathrm{d} \in \{\mathrm{grad}, \mathrm{curl}, \mathrm{div}\}$).

On the reference symmetric simplex, the resulting stiffness matrix has diagonal interior block, and does not couple together the interior and interface degrees of freedom. Thus, on the reference simplex, the Schur complement resulting from elimination of interior degrees of freedom is simply the interface block itself.

This sparsity is not preserved on arbitrary cells mapped from the reference cell. Nevertheless, the interior-interface coupling is weak because it is only induced by the geometric transformation. We devise a preconditioning strategy by neglecting the interior-interface coupling. We precondition the interface Schur complement with the interface block, and simply apply point-Jacobi to precondition the interior block.

The combination of this approach with a space decomposition method on small subdomains constructed around vertices, edges, and faces allows us to efficiently solve the canonical Riesz maps in $H^1$, $H(\mathrm{curl})$, and $H(\mathrm{div})$, at very high order. We empirically demonstrate iteration counts that are robust with respect to the polynomial degree.

In this talk, we investigate distributionally robust optimization (DRO) in a dynamic context. We consider a general penalized DRO problem with a causal transport-type penalization. Such a penalization naturally captures the information flow generated by the models. We derive a tractable dynamic duality formula under a measure theoretic framework. Furthermore, we apply the duality to distributionally robust average value-at-risk and stochastic control problems.