Past Numerical Analysis Group Internal Seminar

Nested commutators of differential operators appear frequently in the numerical solution of equations of quantum mechanics. These are expensive to compute with and a significant effort is typically made to avoid such commutators. In the case of Magnus-Lanczos methods, which remain the standard approach for solving Schrödinger equations featuring time-varying potentials, however, it is not possible to avoid the nested commutators appearing in the Magnus expansion.

We show that, when working directly with the undiscretised differential operators, these commutators can be simplified and are fairly benign, cost-wise. The caveat is that this direct approach compromises structure -- we end up with differential operators that are no longer skew-Hermitian under discretisation. This leads to loss of unitarity as well as resulting in numerical instability when moderate to large time steps are involved. Instead, we resort to working with symmetrised differential operators whose discretisation naturally results in preservation of structure, conservation of unitarity and stability
 

Multi-index methods are a generalization of multilevel methods in high dimensional problem and are based on taking mixed first-order differences along all dimensions. With these methods, we can accurately and efficiently compute a quadrature or construct an interpolation where the integrand requires some form of high dimensional discretization. Multi-index methods are related to Sparse Grid methods and the Combination Technique and have been applied to multiple sampling methods, i.e., Monte Carlo, Stochastic Collocation and, more recently, Quasi Monte Carlo.

In this talk, we describe and analyse the Multi-Index Monte Carlo (MIMC) and Multi-Index Stochastic Collocation (MISC) methods for computing statistics of the solution of a PDE with random data. Provided sufficient mixed regularity, MIMC and MISC achieve better complexity than their corresponding multilevel methods. We propose optimization procedures to select the most effective mixed differences to include in these multi-index methods. We also observe that in the optimal case, the convergence rate of MIMC and MISC is only dictated by the convergence of the deterministic solver applied to a one-dimensional spatial problem. We finally show the effectiveness of MIMC and MISC in some computational tests, including PDEs with random coefficients and Stochastic Particle Systems.
 

I will discuss some of the relationships between ODE IVPs, usually solved by marching, and ODE BVPs, usually solved by global discretizations.

Diffusion processes are commonly used in image processing. In particular, complex diffusion models have been successfully applied in medical imaging denoising. The interpretation of a complex diffusion equation as a cross-diffusion system motivates the introduction of more general models of this type and their study in the context of image processing. In this talk we will discuss the use of nonlinear cross-diffusion systems to perform image restoration. We will analyse the well-posedness, scale-space properties and
long time behaviour of the models along with their performance to treat image filtering problems. Examples of application will be highlighted.

Low-rank compression of matrices and tensors is a huge and growing business.  Closely related is low-rank compression of multivariate functions, a technique used in Chebfun2 and Chebfun3.  Not all functions can be compressed, so the question becomes, which ones?  Here we focus on two kinds of functions for which compression is effective: those with some alignment with the coordinate axes, and those dominated by small regions of localized complexity.

We establish necessary and sufficient conditions for linear convergence of operator splitting methods for a general class of convex optimization problems where the associated fixed-point operator is averaged. We also provide a tight bound on the achievable convergence rate. Most existing results establishing linear convergence in such methods require restrictive assumptions regarding strong convexity and smoothness of the constituent functions in the optimization problem. However, there are several examples in the literature showing that linear convergence is possible even when these properties do not hold. We provide a unifying analysis method for establishing linear convergence based on linear regularity and show that many existing results are special cases of our approach.

We propose several optimal preconditioners for systems defined by some functions $g$ of Toeplitz matrices $T_n$. In this paper we are interested in solving $g(T_n)x=b$ by the preconditioned conjugate method or the preconditioned minimal residual method, namely in the cases when $g(T_n)$ are the analytic functions $e^{T_n}$, $\sin{T_n}$ and $\cos{T_n}$. Numerical results are given to show the effectiveness of the proposed preconditioners.

This talk will be a geophysicist's view on the emerging properties of a numerical model representing the Earth's climate and volcanic activity over the past million years.

The model contains a 2D ice sheet (Glen's Law solved with a semi-implicit scheme), an energy balance for the atmosphere and planet surface (explicit), and an ODE for the time evolution of CO2 (explicit).

The dependencies between these models generate behaviour similar to weakly coupled nonlinear oscillators.

Low-rank compression of matrices and tensors is a huge and growing business.  Closely related is low-rank compression of multivariate functions, a technique used in Chebfun2 and Chebfun3.  Not all functions can be compressed, so the question becomes, which ones?  Here we focus on two kinds of functions for which compression is effective: those with some alignment with the coordinate axes, and those dominated by small regions of localized complexity.

An important observation in compressed sensing is the exact recovery of an l0 minimiser to an underdetermined linear system via the l1 minimiser, given the knowledge that a sparse solution vector exists. Here, we develop a continuous analogue of this observation and show that the best L1 and L0 polynomial approximants of a corrupted function (continuous analogue of sparse vectors) are equivalent. We use this to construct best L1 polynomial approximants of corrupted functions via linear programming. We also present a numerical algorithm for computing best L1 polynomial approximants to general continuous functions, and observe that compared with best L-infinity and L2 polynomial approximants, the best L1 approximants tend to have error functions that are more localized.

Joint work with Alex Townsend (MIT).