Forthcoming events in this series


Tue, 05 Mar 2024

14:30 - 15:00
L6

Error Bound on Singular Values Approximations by Generalized Nystrom

Lorenzo Lazzarino
(Mathematical Institute (University of Oxford))
Abstract

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.

Tue, 05 Mar 2024

14:00 - 14:30
L6

A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format

Alberto Bucci
(University of Pisa)
Abstract

The Nyström method offers an effective way to obtain low-rank approximation of SPD matrices, and has been recently extended and analyzed to nonsymmetric matrices (leading to the randomized, single-pass, streamable, cost-effective, and accurate alternative to the randomized SVD, and it facilitates the computation of several matrix low-rank factorizations. In this presentation, we take these advancements a step further by introducing a higher-order variant of Nyström's methodology tailored to approximating low-rank tensors in the Tucker format: the multilinear Nyström technique. We show that, by introducing appropriate small modifications in the formulation of the higher-order method, strong stability properties can be obtained. This algorithm retains the key attributes of the generalized Nyström method, positioning it as a viable substitute for the randomized higher-order SVD algorithm.

Tue, 20 Feb 2024

14:30 - 15:00
L6

CMA Light: A novel Minibatch Algorithm for large-scale non convex finite sum optimization

Corrado Coppola
(Sapienza University of Rome)
Abstract
The supervised training of a deep neural network on a given dataset consists of the unconstrained minimization of the finite sum of continuously differentiable functions, commonly referred to as loss with respect to the samples. These functions depend on the network parameters and most of the times are non-convex.  We develop CMA Light, a new globally convergent mini-batch gradient method to tackle this problem. We consider the recently introduced Controlled Minibatch Algorithm (CMA) framework and we overcome its main bottleneck, removing the need for at least one evaluation of the whole objective function per iteration. We prove global convergence of CMA Light under mild assumptions and we discuss extensive computational results on the same experimental test bed used for CMA, showing that CMA Light requires less computational effort than most of the state-of-the-art optimizers. Eventually, we present early results on a large-scale Image Classification task.
 
The reference pre-print is already on arXiv at https://arxiv.org/abs/2307.15775
Tue, 20 Feb 2024

14:00 - 14:30
L6

Tensor Methods for Nonconvex Optimization using Cubic-quartic regularization models

Wenqi Zhu
(Mathematical Institute (University of Oxford))
Abstract

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.

Tue, 06 Feb 2024

14:30 - 15:00
L6

Computing $H^2$-conforming finite element approximations without having to implement $C^1$-elements

Charlie Parker
(Mathematical Institute (University of Oxford))
Abstract

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.

Tue, 06 Feb 2024

14:00 - 14:30
L6

Fast High-Order Finite Element Solvers on Simplices

Pablo Brubeck Martinez
(Mathematical Institute (University of Oxford))
Abstract

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.

Tue, 23 Jan 2024

14:30 - 15:00
L6

Manifold-Free Riemannian Optimization

Boris Shustin
(Mathematical Institute (University of Oxford))
Abstract

Optimization problems constrained to a smooth manifold can be solved via the framework of Riemannian optimization. To that end, a geometrical description of the constraining manifold, e.g., tangent spaces, retractions, and cost function gradients, is required. In this talk, we present a novel approach that allows performing approximate Riemannian optimization based on a manifold learning technique, in cases where only a noiseless sample set of the cost function and the manifold’s intrinsic dimension are available.

Tue, 23 Jan 2024

14:00 - 14:30
L6

Scalable Gaussian Process Regression with Quadrature-based Features

Paz Fink Shustin
(Oxford)
Abstract

Gaussian processes provide a powerful probabilistic kernel learning framework, which allows high-quality nonparametric learning via methods such as Gaussian process regression. Nevertheless, its learning phase requires unrealistic massive computations for large datasets. In this talk, we present a quadrature-based approach for scaling up Gaussian process regression via a low-rank approximation of the kernel matrix. The low-rank structure is utilized to achieve effective hyperparameter learning, training, and prediction. Our Gauss-Legendre features method is inspired by the well-known random Fourier features approach, which also builds low-rank approximations via numerical integration. However, our method is capable of generating high-quality kernel approximation using a number of features that is poly-logarithmic in the number of training points, while similar guarantees will require an amount that is at the very least linear in the number of training points when using random Fourier features. The utility of our method for learning with low-dimensional datasets is demonstrated using numerical experiments.

Tue, 21 Nov 2023

14:00 - 15:00
L5

Proximal Galekin: A Structure-Preserving Finite Element Method For Pointwise Bound Constraints

Brendan Keith
(Brown University)
Abstract

The proximal Galerkin finite element method is a high-order, nonlinear numerical method that preserves the geometric and algebraic structure of bound constraints in infinitedimensional function spaces. In this talk, we will introduce the proximal Galerkin method and apply it to solve free-boundary problems, enforce discrete maximum principles, and develop scalable, mesh-independent algorithms for optimal design. The proximal Galerkin framework is a natural consequence of the latent variable proximal point (LVPP) method, which is an stable and robust alternative to the interior point method that will also be introduced in this talk.

In particular, LVPP is a low-iteration complexity, infinite-dimensional optimization algorithm that may be viewed as having an adaptive barrier function that is updated with a new informative prior at each (outer loop) optimization iteration. One of the main benefits of this algorithm is witnessed when analyzing the classical obstacle problem. Therein, we find that the original variational inequality can be replaced by a sequence of semilinear partial differential equations (PDEs) that are readily discretized and solved with, e.g., high-order finite elements. Throughout the talk, we will arrive at several unexpected contributions that may be of independent interest. These include (1) a semilinear PDE we refer to as the entropic Poisson equation; (2) an algebraic/geometric connection between high-order positivity-preserving discretizations and an infinite-dimensional Lie group; and (3) a gradient-based, bound-preserving algorithm for two-field density-based topology optimization.

The complete latent variable proximal Galerkin methodology combines ideas from nonlinear programming, functional analysis, tropical algebra, and differential geometry and can potentially lead to new synergies among these areas as well as within variational and numerical analysis. This talk is based on [1].

 

Keywords: pointwise bound constraints, bound-preserving discretization, entropy regularization, proximal point

 

Mathematics Subject Classifications (2010): 49M37, 65K15, 65N30

 

References  [1] B. Keith, T.M. Surowiec. Proximal Galerkin: A structure-preserving finite element method for pointwise bound constraints arXiv preprint arXiv:2307.12444 2023.

Brown University Email address: @email

Simula Research Laboratory Email address: @email

Tue, 07 Nov 2023

14:30 - 15:00
VC

A Finite-Volume Scheme for Fractional Diffusion on Bounded Domains

Stefano Fronzoni
(Mathematical Institute (University of Oxford))
Abstract

Diffusion is one of the most common phenomenon in natural sciences and large part of applied mathematics have been interested in the tools to model it. Trying to study different types of diffusions, the mathematical ways to describe them and the numerical methods to simulate them is an appealing challenge, giving a wide range of applications. The aim of our work is the design of a finite-volume numerical scheme to model non-local diffusion given by the fractional Laplacian and to build numerical solutions for the Lévy-Fokker-Planck equation that involves it. Numerical methods for fractional diffusion have been indeed developed during the last few years and large part of the literature has been focused on finite element methods. Few results have been rather proposed for different techniques such as finite volumes.

 
We propose a new fractional Laplacian for bounded domains, which is expressed as a conservation law. This new approach is therefore particularly suitable for a finite volumes scheme and allows us also to prescribe no-flux boundary conditions explicitly. We enforce our new definition with a well-posedness theory for some cases to then capture with a good level of approximation the action of fractional Laplacian and its anomalous diffusion effect with our numerical scheme. The numerical solutions we get for the Lévy-Fokker-Planck equation resemble in fact the known analytical predictions and allow us to numerically explore properties of this equation and compute stationary states and long-time asymptotics.

Tue, 24 Oct 2023

14:30 - 15:00
VC

Redefining the finite element

India Marsden
(Oxford)
Abstract

The Ciarlet definition of a finite element has been used for many years to describe the requisite parts of a finite element. In that time, finite element theory and implementation have both developed and improved, which has left scope for a redefinition of the concept of a finite element. In this redefinition, we look to encapsulate some of the assumptions that have historically been required to complete Ciarlet’s definition, as well as incorporate more information, in particular relating to the symmetries of finite elements, using concepts from Group Theory. This talk will present the machinery of the proposed new definition, discuss its features and provide some examples of commonly used elements.

Tue, 24 Oct 2023

14:00 - 14:30
VC

Analysis and Numerical Approximation of Mean Field Game Partial Differential Inclusions

Yohance Osborne
(UCL)
Abstract

The PDE formulation of Mean Field Games (MFG) is described by nonlinear systems in which a Hamilton—Jacobi—Bellman (HJB) equation and a Kolmogorov—Fokker—Planck (KFP) equation are coupled. The advective term of the KFP equation involves a partial derivative of the Hamiltonian that is often assumed to be continuous. However, in many cases of practical interest, the underlying optimal control problem of the MFG may give rise to bang-bang controls, which typically lead to nondifferentiable Hamiltonians. In this talk we present results on the analysis and numerical approximation of second-order MFG systems for the general case of convex, Lipschitz, but possibly nondifferentiable Hamiltonians.
In particular, we propose a generalization of the MFG system as a Partial Differential Inclusion (PDI) based on interpreting the partial derivative of the Hamiltonian in terms of subdifferentials of convex functions.

We present theorems that guarantee the existence of unique weak solutions to MFG PDIs under a monotonicity condition similar to one that has been considered previously by Lasry & Lions. Moreover, we introduce a monotone finite element discretization of the weak formulation of MFG PDIs and prove the strong convergence of the approximations to the value function in the H1-norm and the strong convergence of the approximations to the density function in Lq-norms. We conclude the talk with some numerical experiments involving non-smooth solutions. 

This is joint work with my supervisor Iain Smears. 

Tue, 10 Oct 2023

14:00 - 14:30
L4

A sparse hp-finite element method for the Helmholtz equation posed on disks, annuli and cylinders

Ioannis Papadopoulos
(Imperial)
Abstract

We introduce a sparse and very high order hp-finite element method for the weak form of the Helmholtz equation.  The domain may be a disk, an annulus, or a cylinder. The cells of the mesh are an innermost disk (omitted if the domain is an annulus) and concentric annuli.

We demonstrate the effectiveness of this method on PDEs with radial direction discontinuities in the coefficients and data. The discretization matrix is always symmetric and positive-definite in the positive-definite Helmholtz regime. Moreover, the Fourier modes decouple, reducing a two-dimensional PDE solve to a series of one-dimensional solves that may be computed in parallel, scaling with linear complexity. In the positive-definite case, we utilize the ADI method of Fortunato and Townsend to apply the method to a 3D cylinder with a quasi-optimal complexity solve.

Tue, 13 Jun 2023
14:30
L3

Approximating Functions of Sparse Matrices using Matrix-vector Products

Taejun Park
(University of Oxford)
Abstract

The computation of matrix function is an important task appearing in many areas of scientific computing. We propose two algorithms, one for banded matrices and the other for general sparse matrices that approximate f(A) using matrix-vector products only. Our algorithms are inspired by the decay bound for the entries of f(A) when A is banded or sparse. We show its exponential convergence when A is banded or sufficiently sparse and we demonstrate its performance using numerical experiments.

Tue, 13 Jun 2023
14:00
L3

Constructing Structure-Preserving Timesteppers via Finite Elements in Time

Boris Andrews
(University of Oxford)
Abstract

For many stationary-state PDEs, solutions can be shown to satisfy certain key identities or structures, with physical interpretations such as the dissipation of energy. By reformulating these systems in terms of new auxiliary functions, finite-element models can ensure these structures also hold exactly for the numerical solutions. This approach is known to improve the solutions' accuracy and reliability.

In this talk, we extend this auxiliary function approach to the transient case through a finite-element-in-time interpretation. This allows us to develop novel structure-preserving timesteppers for various transient problems, including the Navier–Stokes and MHD equations, up to arbitrary order in time.

 

Tue, 30 May 2023
14:30
L3

High-Order Finite Element Schemes for Multicomponent Flow Problems

Aaron Baier-Reinio
(University of Oxford)
Abstract

The Stokes–Onsager–Stefan–Maxwell (SOSM) equations model the flow of concentrated mixtures of distinct chemical species in a common thermodynamic phase. We derive a novel variational formulation of these nonlinear equations in which the species mass fluxes are treated as unknowns. This new formulation leads to a large class of high-order finite element schemes with desirable linear-algebraic properties. The schemes are provably convergent when applied to a linearization of the SOSM problem.

Tue, 16 May 2023
14:30
L3

On the Initialisation of wide Neural Networks: the Edge of Chaos

Thiziri Nait Saada
(University of Oxford)
Abstract

 Wide Neural Networks are well known for their Gaussian Process behaviour. Based upon this fact, an initialisation scheme for the weights and biases of a network preserving some geometrical properties of the input data is presented — The edge-of-chaos. This talk will introduce such a scheme before briefly mentioning a recent contribution related to the edge-of-chaos dynamics of wide randomly initialized low-rank feedforward networks. Formulae for the optimal weight and bias variances are extended from the full-rank to low-rank setting and are shown to follow from multiplicative scaling. The principle second order effect, the variance of the input-output Jacobian, is derived and shown to increase as the rank to width ratio decreases. These results inform practitioners how to randomly initialize feedforward networks with a reduced number of learnable parameters while in the same ambient dimension, allowing reductions in the computational cost and memory constraints of the associated network.

Tue, 16 May 2023
14:00
L3

Discrete Tensor-Product BGG Sequences: Splines and Finite Elements

Duygu Sap
(University of Oxford)
Abstract

Placeholder entry; date+time TBC. 

Abstract for talk: In this talk, we present a systematic discretization of the Bernstein-Gelfand-Gelfand (BGG) diagrams and complexes over cubical meshes of arbitrary dimension via the use of tensor-product structures of one-dimensional piecewise-polynomial spaces, such as spline and finite element spaces. We demonstrate the construction of the Hessian, the elasticity, and div-div complexes as examples for our construction.

Tue, 02 May 2023
14:30
L3

Newton-MR methods for nonconvex optimization

Yang Liu
(University of Oxford)
Abstract

In this talk, we introduce Newton-MR variants for solving nonconvex optimization problems. Unlike the overwhelming majority of Newton-type methods, which rely on conjugate gradient method as the primary workhorse for their respective sub-problems, Newton-MR employs minimum residual (MINRES) method. With certain useful monotonicity properties of MINRES as well as its inherent ability to detect non-positive curvature directions as soon as they arise, we show that our algorithms come with desirable properties including the optimal first and second-order worst-case complexities. Numerical examples demonstrate the performance of our proposed algorithms.

Tue, 02 May 2023
14:00
L3

A Nematic Theory For a Nonspherical Rarefied Gas

Umberto Zerbinati
(Universiy of Oxford)
Abstract

We propose a nematic model for polyatomic gas, intending to study anisotropic phenomena. Such phenomena stem from the orientational degree of freedom associated with the rod-like molecules composing the gas. We adopt as a primer the Curitss-Boltzmann equation. The main difference with respect to Curtiss theory of hard convex body fluids is the fact that the model here presented takes into account the emergence of a nematic ordering. We will also derive from a kinetic point of view an energy functional similar to the Oseen-Frank energy. The application of the Noll-Coleman procedure to derive new expressions for the stress tensor and the couple-stress tensor will lead to a model capable of taking into account anisotropic effects caused by the emergence of a nematic ordering. In the near future, we hope to adopt finite-element discretisations together with multi-scale methods to simulate the integro-differential equation arising from our model.

Tue, 07 Mar 2023

14:30 - 15:00
Lecture Room 3

Discrete complexes for the incompressible Navier-Stokes equations

Marien Hanot
Abstract

Coupled differential equations generally present an important algebraic structure.
For example in the incompressible Navier-Stokes equations, the velocity is affected only by the selenoidal part of the applied force.
This structure can be translated naturally by the notion of complex.
One idea is then to exploit this complex structure at the discrete level in the creation of numerical methods.

The goal of the presentation is to expose the notion of complex by motivating its uses. 
We will present in more detail the creation of a scheme for the Navier-Stokes equations and study its properties.
 

Tue, 07 Mar 2023

14:00 - 15:00
Lecture Room 3

Dehomogenization: a new technique for multi-scale topology optimization

Alex Ferrer
Abstract

The recent advancements in additive manufacturing have enabled the creation of lattice structures with intricate small-scale details. This has led to the need for new techniques in the field of topology optimization that can handle a vast number of design variables. Despite the efforts to develop multi-scale topology optimization techniques, their high computational cost has limited their application. To overcome this challenge, a new technique called dehomogenization has shown promising results in terms of performance and computational efficiency for optimizing compliance problems.

In this talk, we extend the application of the dehomogenization method to stress minimization problems, which are crucial in structural design. The method involves homogenizing the macroscopic response of a proposed family of microstructures. Next, the macroscopic structure is optimized using gradient-based methods while orienting the cells according to the principal stress components. The final step involves dehomogenization of the structure. The proposed methodology also considers singularities in the orientation field by incorporating singular functions in the dehomogenization process. The validity of the methodology is demonstrated through several numerical examples.

Tue, 21 Feb 2023

14:30 - 15:00
Lecture Room 3

Generalising Quasi-Newton Updates to Higher Orders

Karl Welzel
Abstract

At the heart of all quasi-Newton methods is an update rule that enables us to gradually improve the Hessian approximation using the already available gradient evaluations. Theoretical results show that the global performance of optimization algorithms can be improved with higher-order derivatives. This motivates an investigation of generalizations of quasi-Newton update rules to obtain for example third derivatives (which are tensors) from Hessian evaluations. Our generalization is based on the observation that quasi-Newton updates are least-change updates satisfying the secant equation, with different methods using different norms to measure the size of the change. We present a full characterization for least-change updates in weighted Frobenius norms (satisfying an analogue of the secant equation) for derivatives of arbitrary order. Moreover, we establish convergence of the approximations to the true derivative under standard assumptions and explore the quality of the generated approximations in numerical experiments.

Tue, 21 Feb 2023

14:00 - 14:30
Lecture Room 3

Are sketch-and-precondition least squares solvers numerically stable?

Maike Meier
Abstract

Sketch-and-precondition techniques are popular for solving large overdetermined least squares (LS) problems. This is when a right preconditioner is constructed from a randomized 'sketch' of the matrix. In this talk, we will see that the sketch-and-precondition technique is not numerically stable for ill-conditioned LS problems. We propose a modifciation: using an unpreconditioned iterative LS solver on the preconditioned matrix. Provided the condition number of A is smaller than the reciprocal of the unit round-off, we show that this modification ensures that the computed solution has a comparable backward error to the iterative LS solver applied to a well-conditioned matrix. Using smoothed analysis, we model floating-point rounding errors to provide a convincing argument that our modification is expected to compute a backward stable solution even for arbitrarily ill-conditioned LS problems.