Forthcoming events in this series


Tue, 28 May 2019

14:30 - 15:00
L5

Optimisation of 1D Piecewise Smooth Functions

Jonathan Grant-Peters
(Oxford)
Abstract

Optimisation in 1D is far simpler than multidimensional optimisation and this is largely due to the notion of a bracket. A bracket is a trio of points such that the middle point is the one with the smallest objective function value (of the three). The existence of a bracket is sufficient to guarantee that a continuous function has a local minimum within the bracket. The most stable 1D optimisation methods, such as Golden Section or Brent's Method, make use of this fact. The mentality behind these methods is to maintain a bracket at all times, all the while finding smaller brackets until the local minimum can be guaranteed to lie within a sufficiently small range. For smooth functions, Brent's method in particular converges quickly with a minimum of function evaluations required. However, when applied to a piece-wise smooth functions, it achieves its realistic worst case convergence rate. In this presentation, I will present a new method which uses ideas from Brent and Golden Section, while being designed to converge quickly for piece-wise smooth functions.

Tue, 28 May 2019

14:00 - 14:30
L5

On divergence-free methods for double-diffusion equations in porous media

Paul Méndez
(Concepción)
Abstract

A stationary Navier-Stokes-Brinkman model coupled to a system of advection-diffusion equations serves as a model for so-called double-diffusive viscous flow in porous mediain which both heat and a solute within the fluid phase are subject to transport and diffusion. The solvability analysis of these governing equations results as a combination of compactness arguments and fixed-point theory. In addition an H(div)-conforming discretisation is formulated by a modification of existing methods for Brinkman flows. The well-posedness ofthe discrete Galerkin formulation is also discussed, and convergence properties are derived rigorously. Computational tests confirm the predicted rates of error decay and illustrate the applicability of the methods for the simulation of bacterial bioconvection and thermohaline circulation problems.

Tue, 21 May 2019

14:30 - 15:00
L5

A Model-Based Derivative-Free Approach to Black-Box Adversarial Examples in Deep Learning

Giuseppe Ughi
(Oxford)
Abstract

Neural Network algorithms have achieved unprecedented performance in image recognition over the past decade. However, their application in real world use-cases, such as self driving cars, raises the question of whether it is safe to rely on them.

We generally associate the robustness of these algorithms with how easy it is to generate an adversarial example: a tiny perturbation of an image which leads it to be misclassified by the Neural Net (which classifies the original image correctly). Neural Nets are strongly susceptible to such adversarial examples, but when the architecture of the target neural net is unknown to the attacker it becomes more difficult to generate these examples efficiently.

In this Black-Box setting, we frame the generation of an adversarial example as an optimisation problem solvable via derivative free optimisation methods. Thus, we introduce an algorithm based on the BOBYQA model-based method and compare this to the current state of the art algorithm.

Tue, 21 May 2019

14:00 - 14:30
L5

Time-Varying Matrix Problems and Zhang Neural Networks

Frank Uhlig
(Auburn)
Abstract

We adapt convergent look-ahead and backward finite difference formulas to compute future eigenvectors and eigenvalues of piecewise smooth time-varying matrix flows $A(t)$. This is based on the Zhang Neural Network model for time-varying problems and uses the associated error function

$E(t) =A(t)V(t)−V(t)D(t)$

with the Zhang design stipulation

$\dot{E}(t) =−\eta E(t)$.

Here $E(t)$ decreased exponentially over time for $\eta >0$. It leads to a discrete-time differential equation of the form $P(t_k)\dot{z}(t_k) = q(t_k)$ for the eigendata vector $z(t_k)$ of $A(t_k)$. Convergent high order look-ahead difference formulas then allow us to express $z(t_k+1)$ in terms of earlier discrete $A$ and $z$ data. Numerical tests, comparisons and open questions follow.

Tue, 14 May 2019

14:30 - 15:00
L3

Deep artificial neural networks overcome the curse of dimensionality in PDE approximation

Timo Welti
(ETHZ)
Abstract

Numerical simulations indicate that deep artificial neural networks (DNNs) seem to be able to overcome the curse of dimensionality in many computational  problems in the sense that the number of real parameters used to describe the DNN grows at most polynomially in both the reciprocal of the prescribed approximation accuracy and the dimension of the function which the DNN aims to approximate. However, there are only a few special situations where results in the literature can rigorously explain the success of DNNs when approximating high-dimensional functions.

In this talk it is revealed that DNNs do indeed overcome the curse of dimensionality in the numerical approximation of Kolmogorov PDEs with constant diffusion and nonlinear drift coefficients. A crucial ingredient in our proof of this result is the fact that the artificial neural network used to approximate the PDE solution really is a deep artificial neural network with a large number of hidden layers.

Tue, 14 May 2019

14:00 - 14:30
L3

Fast Graph Sampling using Gershgorin Disc Alignment

Gene Cheung
(York University)
Abstract

Graph sampling with noise is a fundamental problem in graph signal processing (GSP). A popular biased scheme using graph Laplacian regularization (GLR) solves a system of linear equations for its reconstruction. Assuming this GLR-based reconstruction scheme, we propose a fast sampling strategy to maximize the numerical stability of the linear system--i.e., minimize the condition number of the coefficient matrix. Specifically, we maximize the eigenvalue lower bounds of the matrix that are left-ends of Gershgorin discs of the coefficient matrix, without eigen-decomposition. We propose an iterative algorithm to traverse the graph nodes via Breadth First Search (BFS) and align the left-ends of all corresponding Gershgorin discs at lower-bound threshold T using two basic operations: disc shifting and scaling. We then perform binary search to maximize T given a sample budget K. Experiments on real graph data show that the proposed algorithm can effectively promote large eigenvalue lower bounds, and the reconstruction MSE is the same or smaller than existing sampling methods for different budget K at much lower complexity.

Tue, 07 May 2019

14:30 - 15:00
L5

Fireshape, a look under the hood

Alberto Paganini
(Oxford)
Abstract

Fireshape is a shape optimization library based on finite elements. In this talk I will describe how Florian Wechsung and I developed Fireshape and will share my reflections on lessons learned through the process.

Tue, 07 May 2019

14:00 - 14:30
L5

Sharp error bounds for Ritz vectors and approximate singular vectors

Yuji Nakatsukasa
(Oxford)
Abstract

We derive sharp bounds for the accuracy of approximate eigenvectors (Ritz vectors) obtained by the Rayleigh-Ritz process for symmetric eigenvalue problems. Using information that is available or easy to estimate, our bounds improve the classical Davis-Kahan sin-theta theorem by a factor that can be arbitrarily large, and can give nontrivial information even when the sin-theta theorem suggests that a Ritz vector might have no accuracy at all. We also present extensions in three directions, deriving error bounds for invariant subspaces, singular vectors and subspaces computed by a (Petrov-Galerkin) projection SVD method, and eigenvectors of self-adjoint operators on a Hilbert space.

Tue, 30 Apr 2019

14:30 - 15:00
L3

Exponential integrators for stiff PDEs

Lloyd Nick Trefethen
(Oxford)
Abstract

Many time-dependent PDEs -- KdV, Burgers, Gray-Scott, Allen-Cahn, Navier-Stokes and many others -- combine a higher-order linear term with a lower-order nonlinear term.  This talk will review the method of exponential integrators for solving such problems with better than 2nd-order accuracy in time.

Tue, 30 Apr 2019

14:00 - 14:30
L3

Computable upper error bounds for Krylov subspace approximations to matrix exponentials

Tobias Jawecki
(TU Wien)
Abstract

A defect-based a posteriori error estimate for Krylov subspace approximations to the matrix exponential is introduced. This error estimate constitutes an upper norm bound on the error and can be computed during the construction of the Krylov subspace with nearly no computational effort. The matrix exponential function itself can be understood as a time propagation with restarts. In practice, we are interested in finding time steps for which the error of the Krylov subspace approximation is smaller than a given tolerance. Finding correct time steps is a simple task with our error estimate. Apart from step size control, the upper error bound can be used on the fly to test if the dimension of the Krylov subspace is already sufficiently large to solve the problem in a single time step with the required accuracy.

Tue, 05 Mar 2019

14:30 - 15:00
L5

MLQMC Methods for Elliptic PDEs Driven by White Noise

Matteo Croci
(Oxford)
Abstract

When solving partial differential equations driven by additive spatial white noise, the efficient sampling of white noise realizations can be challenging. In this talk we focus on the efficient sampling of white noise using quasi-random points in a finite element method and multilevel Quasi Monte Carlo (MLQMC) setting. This work is an extension of previous research on white noise sampling for MLMC.

We express white noise as a wavelet series expansion that we divide in two parts. The first part is sampled using quasi-random points and contains a finite number of terms in order of decaying importance to ensure good QMC convergence. The second part is a correction term which is sampled using standard pseudo-random numbers.

We show how the sampling of both terms can be performed in linear time and memory complexity in the number of mesh cells via a supermesh construction. Furthermore, our technique can be used to enforce the MLQMC coupling even in the case of non-nested mesh hierarchies. We demonstrate the efficacy of our method with numerical experiments.

Tue, 05 Mar 2019

14:00 - 14:30
L5

A VEM discretization for the transmission eigenvalue problem

David Mora
(Universidad del Bio-Bio)
Abstract

In this talk, we analyze a virtual element method (VEM) for solving a non-selfadjoint fourth-order eigenvalue problem derived from the transmission eigenvalue problem. We write a variational formulation and propose a $C^1$-conforming discretization by means of the VEM. We use the classical approximation theory for compact non-selfadjoint operators to obtain optimal order error estimates for the eigenfunctions and a double order for the eigenvalues. Finally, we present some numerical experiments illustrating the behavior of the virtual scheme on different families of meshes.

Tue, 26 Feb 2019

14:30 - 15:00
L3

Multispectral snapshot demosaicing via non-convex matrix completion

Simon Vary
(Oxford)
Abstract

Snapshot mosaic multispectral imagery acquires an undersampled data cube by acquiring a single spectral measurement per spatial pixel. Sensors which acquire p frequencies, therefore, suffer from severe 1/p undersampling of the full data cube.  We show that the missing entries can be accurately imputed using non-convex techniques from sparse approximation and matrix completion initialised with traditional demosaicing algorithms.

Tue, 26 Feb 2019

14:00 - 14:30
L3

New mixed finite element methods for natural convection with phase-change in porous media

Bryan Gómez Vargas
(Conception)
Abstract

This talk is concerned with the mathematical and numerical analysis of a steady phase change problem for non-isothermal incompressible viscous flow. The system is formulated in terms of pseudostress, strain rate and velocity for the Navier-Stokes-Brinkman equation, whereas temperature, normal heat flux on the boundary, and an auxiliary unknown are introduced for the energy conservation equation. In addition, and as one of the novelties of our approach, the symmetry of the pseudostress is imposed in an ultra-weak sense, thanks to which the usual introduction of the vorticity as an additional unknown is no longer needed. Then, for the mathematical analysis two variational formulations are proposed, namely mixed-primal and fully-mixed approaches, and the solvability of the resulting coupled formulations is established by combining fixed-point arguments, Sobolev embedding theorems and certain regularity assumptions. We then construct corresponding Galerkin discretizations based on adequate finite element spaces, and derive optimal a priori error estimates. Finally, numerical experiments in 2D and 3D illustrate the interest of this scheme and validate the theory.

Tue, 19 Feb 2019

14:30 - 15:00
L3

Univariate and Multivariate Polynomials in Numerical Analysis

Lloyd N. Trefethen
(Oxford)
Abstract

We begin by reviewing numerical methods for problems in one variable and find that univariate polynomials are the starting point for most of them.  A similar review in several variables, however, reveals that multivariate polynomials are not so important.  Why?  On the other hand in pure mathematics, the field of algebraic geometry is precisely the study of multivariate polynomials.  Why?

Tue, 19 Feb 2019

14:00 - 14:30
L3

Stochastic Analysis and Correction of Floating Point Errors in Monte Carlo Simulations

Oliver Sheridan-Methven
(Oxford)
Abstract

In this talk we will show how the floating point errors in the simulation of SDEs (stochastic differential equations) can be modelled as stochastic. Furthermore, we will show how these errors can be corrected within a multilevel Monte Carlo approach which performs most calculations with low precision, but a few calculations with higher precision. The same procedure can also be used to correct for errors in converting from uniform random numbers to approximate Normal random numbers. Numerical results will be generated on both CPUs (using single/double precision) and GPUs (using half/single precision).

Tue, 12 Feb 2019

14:30 - 15:00
L5

Optimization Relaxations in Dynamic Pricing

Jaroslav Fowkes
(Oxford)
Abstract

The idea of adjusting prices in order to sell goods at the highest acceptable price, such as haggling in a market, is as old as money itself. We consider the problem of pricing multiple products on a network of resources, such as that faced by an airline selling tickets on its flight network. In this talk I will consider various optimization relaxations to the deterministic dynamic pricing problem on a network. This is joint work with Raphael Hauser.

Tue, 12 Feb 2019

14:00 - 14:30
L5

Direct solvers for the Lippmann-Schwinger equation

Abinand Gopal
(Oxford)
Abstract

In recent years, there has been an increased interest in exploiting rank structure of matrices arising from the discretization of partial differential equations to develop fast direct solvers. In this talk, I will outline the fundamental ideas of this topic in the context of solving the integral equation formulation of the Helmholtz equation, known as the Lippmann-Schwinger equation, and will discuss some plans for future work to develop new, higher-order solvers. This is joint work with Gunnar Martinsson.

Tue, 05 Feb 2019

14:30 - 15:00
L5

An Introduction to Persistent Homology

Vidit Nanda
(Oxford)
Abstract

This talk will feature a brief introduction to persistent homology, the vanguard technique in topological data analysis. Nothing will be required of the audience beyond a willingness to row-reduce enormous matrices (by hand if we can, by machine if we must).

Tue, 05 Feb 2019

14:00 - 14:30
L5

An introduction to classical time-parallelisation methods

Giancarlo Antonucci
(Oxford)
Abstract

For decades, researchers have been studying efficient numerical methods to solve differential equations, most of them optimised for one-core processors. However, we are about to reach the limit in the amount of processing power we can squeeze into a single processor. This explains the trend in today's computing industry to design high-performance processors looking at parallel architectures. As a result, there is a need to develop low-complexity parallel algorithms capable of running efficiently in terms of computational time and electric power.

Parallelisation across time appears to be a promising way to provide more parallelism. In this talk, we will introduce the main algorithms, following (Gander, 2015), with a particular focus on the parareal algorithm.

Tue, 29 Jan 2019

14:30 - 15:00
L3

Nearby preconditioning for multiple realisations of the Helmholtz equation, with application to uncertainty quantification

Owen Pembery
(Bath)
Abstract

The Helmholtz equation models waves propagating with a fixed frequency. Discretising the Helmholtz equation for high frequencies via standard finite-elements results in linear systems that are large, non-Hermitian, and indefinite. Therefore, when solving these linear systems, one uses preconditioned iterative methods. When one considers uncertainty quantification for the Helmholtz equation, one will typically need to solve many (thousands) of linear systems corresponding to different realisations of the coefficients. At face value, this will require the computation of many preconditioners, a potentially expensive task.

Therefore, we investigate how well a preconditioner for one realisation of the Helmholtz equation works as a preconditioner for another realisation. We prove that if the two realisations are 'nearby' (with a precise meaning of 'nearby'), then the preconditioner is robust (that is, preconditioned GMRES converges in a number of iterations that is independent of frequency). We also give some preliminary computational results indicating the speedup one obtains in uncertainty quantification calculations.

Tue, 29 Jan 2019

14:00 - 14:30
L3

Dimensionality reduction for linear least square problems

Zhen Shao
(Oxford)
Abstract

The focus of this talk is how to tackle huge linear least square problems via sketching, a dimensionality reduction technique from randomised numerical linear algebra. The technique allows us to project the huge problem to a smaller dimension that captures essential information of the original problem. We can then solve the projected problem directly to obtain a low accuracy solution or using the projected problem to construct a preconditioner for the original problem to obtain a high accuracy solution. I will survey the existing projection techniques and evaluate the performance of sketching for linear least square problems by comparing it to the state-of-the-art traditional solution methods. More than ten-fold speed-up has been observed in some cases.

Tue, 22 Jan 2019

14:30 - 15:00
L5

Shape optimization with finite elements

Alberto Paganini
(Oxford)
Abstract

A common strategy to solve shape optimization problems is to select an initial domain and to update it iteratively until it satisfies certain optimality crietria. In the presence of PDE-constraints, computing these updates requires solving a boundary value problem on a domain that changes at every iteration. We explain how to use isoparametric finite elements to tackle this issue. We also show how finite elements allow computing these updates without deriving shape derivative formulas by hand.

Tue, 22 Jan 2019

14:00 - 14:30
L5

Halley and Newton are one step apart

Trond Steihaug
(Bergen)
Abstract

In this talk, we consider solving nonlinear systems of equations and the unconstrained minimization problem using Newton’s method methods from the Halley class. The methods in this class have in general local and third order rate of convergence while Newton’s method has quadratic convergence. In the unconstrained optimization case, the Halley methods will require the second and third derivative. Third-order methods will, in most cases, use fewer iterations than a second-order method to reach the same accuracy. However, the number of arithmetic operations per iteration is higher for third-order methods than for a second-order method. We will demonstrate that for a large class of problems, the ratio of the number of arithmetic operations of Halley’s method and Newton’s method is constant per iteration (independent of the number of unknowns).

We say that the sparsity pattern of the third derivative (or tensor) is induced by the sparsity pattern of the Hessian matrix. We will discuss some datastructures for matrices where the indices of nonzero elements of the tensor can be computed. Historical notes will be merged into the talk.

Tue, 15 Jan 2019

14:00 - 15:00
L5

Quantifying the ill-conditioning of analytic continuation

Lloyd N. Trefethen
(Oxford)
Abstract

Analytic continuation is ill-posed, but becomes merely ill-conditioned (though with an infinite condition number) if it is known that the function in question is bounded in a given region of the complex plane.
This classical, seemingly theoretical subject has many connections with numerical practice.  One argument indicates that if one tracks an analytic function from z=1 around a branch point at z=0 and back to z=1 again by a Weierstrass chain of disks, the number of accurate digits is divided by about exp(2 pi e) ~= 26,000,000.