Past Numerical Analysis Group Internal Seminar

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.

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.

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.

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.

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.

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.

When approximating PDEs with the finite element method, large sparse linear systems must be solved. The ideal preconditioner yields convergence that is  algorithmically optimal and parameter robust, i.e. the number of Krylov iterations required to solve the linear system to a given accuracy does not grow substantially as the mesh or problem parameters are changed.

Achieving this for the stationary Navier-Stokes has proven challenging: LU factorisation is Reynolds-robust but scales poorly with degree of freedom count, while Schur complement approximations such as PCD and LSC degrade as the Reynolds number is increased.

Building on the work of Schöberl, Olshanskii and Benzi, in this talk we present the first preconditioner for the Newton linearisation of the stationary Navier--Stokes equations in three dimensions that achieves both optimal complexity and Reynolds-robustness. The scheme combines a novel tailored finite element discretisation, discrete augmented Lagrangian stabilisation, a custom prolongation operator involving local solves on coarse cells, and an additive patchwise relaxation on each
level. We present 3D simulations with over one billion degrees of freedom with robust performance from Reynolds number 10 to 5000.

Employing the usual multilevel Monte Carlo estimator, we introduce a framework for estimating the solutions of SDEs by an Euler-Maruyama scheme. By considering the expected value of such solutions, we produce simulations using approximately normal random variables, and recover the estimate from the exact normal distribution by use of a multilevel correction, leading to faster simulations without loss of accuracy. We will also highlight this concept in the framework of reduced precision and vectorised computations.

In this talk I will introduce a new mathematical model for the computational modelling of the active contraction of cardiac tissue using stress-assisted conductivity as the main mechanism for mechanoelectrical feedback. The coupling variable is the Kirchhoff stress and so the equations of hyperelasticity are written in mixed form and a suitable finite element formulation is proposed. Next I will introduce a simplified version of the coupled system, focusing on its analysis in terms of solvability and stability of continuous and discrete mixed-primal formulations, and the convergence of these methods will be illustrated through two numerical tests.

In petroleum reservoir simulation, the standard preconditioner is a two-stage process which involves solving a restricted pressure system with AMG. Initially designed for isothermal models, this approach is often used in the thermal case. However, it does not incorporate heat diffusion or the effects of temperature changes on fluid flow through viscosity and density. We seek to develop preconditioners which consider this cross-coupling between pressure and temperature. In order to study the effects of both pressure and temperature on fluid and heat flow, we first consider a model of non-isothermal single phase flow through porous media. For this model, we develop a block preconditioner with an efficient Schur complement approximation. Then, we extend this method for multiphase flow as a two-stage preconditioner.

This work determines an aim point selection strategy for players in order to improve their chances of winning at the classic darts game of 501. Although many previous studies have considered the problem of aim point selection in order to maximise the expected score a player can achieve, few have considered the more general strategical question of minimising the expected number of turns required for a player to finish. By casting the problem as a Markov decision process, a framework is derived for the identification of the optimal aim point for a player in an arbitrary game scenario.

The talk introduces the problem of completing a partially observed matrix whose columns obey a nonlinear structure. This is an extension of classical low-rank matrix completion where the structure is linear. Such matrices are in general full rank, but it is often possible to exhibit a low rank structure when the data is lifted to a higher dimensional space of features. The presence of a nonlinear lifting makes it impossible to write the problem using common low-rank matrix completion formulations. We investigate formulations as a nonconvex optimisation problem and optimisation on Riemannian manifolds.

Matrix completion is an area of great mathematical interest and has numerous applications, including recommender systems for e-commerce. The recommender problem can be viewed as follows: given a database where rows are users and and columns are products, with entries indicating user preferences, fill in the entries so as to be able to recommend new products based on the preferences of other users. Viewing the interactions between user and product instead as interactions between potential drug chemicals and disease-causing target proteins, the problem is that faced within the realm of drug discovery. We propose a divide and conquer algorithm inspired by the work of [1], who use recursive rank-1 approximation. We make the case for using an LP rank-1 approximation, similar to that of [2] by a showing that it guarantees a 2-approximation to the optimal, even in the case of missing data. We explore our algorithm's performance for different test cases.

[1]  Shen, B.H., Ji, S. and Ye, J., 2009, June. Mining discrete patterns via binary matrix factorization. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 757-766). ACM.

[2] Koyutürk, M. and Grama, A., 2003, August. PROXIMUS: a framework for analyzing very high dimensional discrete-attributed datasets. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 147-156). ACM.

There is no more classical problem of numerical PDE than the Laplace equation in a polygon, but Abi Gopal and I think we are on to a big step forward. The traditional approaches would be finite elements, giving a 2D representation of the solution, or integral equations, giving a 1D representation. The new approach, inspired by an approximation theory result of Donald Newman in 1964, leads to a "0D representation" -- the solution is the real part of a rational function with poles clustered exponentially near the corners of the polygon. The speed and accuracy of this approach are remarkable. For typical polygons of up to 8 vertices, we can solve the problem in less than a second on a laptop and evaluate the result in a few microseconds per point, with 6-digit accuracy all the way up to the corner singularities. We don't think existing methods come close to such performance. Next step: Helmholtz?
 

In the first part of this talk, I will present an extension of Chebfun, called Ballfun, for computing with functions and vectors in the unit ball. I will then describe an algorithm for solving the incompressible Navier-Stokes equations in the ball. Contrary to projection methods, we use the poloidal-toroidal decomposition to decouple the PDEs and solve scalars equations. The solver has an optimal complexity (up to polylogarithmic terms) in terms of the degrees of freedom required to represent the solution.

This talk features a self-contained introduction to persistent homology, which is the main ingredient of topological data analysis. 

In the classical theory of fluid mechanics, a linear relationship between the stress and rate of strain is often assumed. Even when this relationship is non-linear, it is typically formulated in terms of an explicit relation. Implicit constitutive theories provide a theoretical framework that generalises this, allowing a, possibly multi-valued, implicit constitutive relation. Since it is not possible to solve explicitly for the stress in the constitutive relation, a more natural approach would be to include the stress as a fundamental unknown in the formulation of the problem. In this talk I will present a formulation with this feature and a proof of convergence of the finite element approximations to a solution of the original problem.

A fundamental task in numerical computation is the solution of large linear systems. The conjugate gradient method is an iterative method which offers rapid convergence to the solution, particularly when an effective preconditioner is employed. However, for more challenging systems a substantial error can be present even after many iterations have been performed. The estimates obtained in this case are of little value unless further information can be provided about the numerical error. In this paper we propose a novel statistical model for this numerical error set in a Bayesian framework. Our approach is a strict generalisation of the conjugate gradient method, which is recovered as the posterior mean for a particular choice of prior. The estimates obtained are analysed with Krylov subspace methods and a contraction result for the posterior is presented. The method is then analysed in a simulation study as well as being applied to a challenging problem in medical imaging.

This work deals with exploiting the low-dimensional hierarchical structure of speech signals towards the  goal  of  improving  acoustic  modelling using deep neural networks (DNN).  To this aim the work employ tools from sparsity aware signal processing under novel frameworks to enrich  the  acoustic  information  present  in  DNN posterior features. 

Convex and in particular semidefinite relaxations (SDP) for non-convex continuous quadratic optimisation can provide tighter bounds than traditional linear relaxations. However, using SDP relaxations directly in Branch&Cut is impeded by lack of warm starting and inefficiency when combined with other cut classes, i.e. the reformulation-linearization technique. We present a general framework based on machine learning for a strong linear outer-approximation that can retain most tightness of such SDP relaxations, in the form of few strong low dimensional linear cuts selected offline. The cut selection complexity is taken offline by using a neural network estimator (trained before installing solver software) as a selection device for the strongest cuts. Lastly, we present results of our method on QP/QCQP problem instances.

The next generation emissive displays including quantum dot LED(QLED) and organic LED(OLED) could be efficiently manufactured by inkjet printing, where nano-scale droplets are injected in banked substrate and after evaporation they leave layers of thin film that forms pixels of a display. This novel manufacturing method would greatly reduce cost and improve reliability. However, it is observed in practice that the deposit becomes much thicker near the bank edge and emission is faint there. This motivated the project and in this talk, we will mathematically model the phenomeno, understand its origin and investigate ways of making more uniform deposit by means of simulation.

When solving stochastic partial differential equations (SPDEs) driven by additive spatial white noise the efficient sampling of white noise realizations can be challenging. In this talk we present a novel sampling technique that can be used to efficiently compute white noise samples in a finite element and multilevel Monte Carlo (MLMC) setting.
After discretization, the action of white noise on a test function yields a Gaussian vector with the FEM mass matrix as covariance. Sampling such a vector requires an expensive Cholesky factorization and for this reason P0 representations, for which the mass matrix is diagonal, are generally preferred in the literature. This however has other disadvantages. In this talk we introduce an alternative factorization that is naturally parallelizable and has linear cost and memory complexity (in the number of mesh elements).
Moreover, in a MLMC framework the white noise samples must be coupled between subsequent levels so as to respect the telescoping sum. We show how our technique can be used to enforce this coupling even in the case in which the hierarchy is non-nested via a supermesh construction. We conclude the talk with numerical experiments that demonstrate the efficacy of our method. We observe optimal convergence rates for the finite element solution of the elliptic SPDEs of interest. In a MLMC setting, a good coupling is enforced and the telescoping sum is respected.
 

(Joint work with Coralia Cartis) The problem of finding the most extreme value of a function, also known as global optimization, is a challenging task. The difficulty is associated with the exponential increase in the computational time for a linear increase in the dimension. This is known as the ``curse of dimensionality''. In this talk, we demonstrate that such challenges can be overcome for functions with low effective dimensionality --- functions which are constant along certain linear subspaces. Such functions can often be found in applications, for example, in hyper-parameter optimization for neural networks, heuristic algorithms for combinatorial optimization problems and complex engineering simulations.
We propose the use of random subspace embeddings within a(ny) global minimisation algorithm, extending the approach in Wang et al. (2013). We introduce a new framework, called REGO (Random Embeddings for GO), which transforms the high-dimensional optimization problem into a low-dimensional one. In REGO, a new low-dimensional problem is formulated with bound constraints in the reduced space and solved with any GO solver. Using random matrix theory, we provide probabilistic bounds for the success of REGO, which indicate that this is dependent upon the dimension of the embedded subspace and the intrinsic dimension of the function, but independent of the ambient dimension. Numerical results demonstrate that high success rates can be achieved with only one embedding and that rates are for the most part invariant with respect to the ambient dimension of the problem.
 

In this talk, first we  address the convergence issues of a standard finite volume element method (FVEM) applied to simple elliptic problems. Then, we discuss discontinuous finite volume element methods (DFVEM) for elliptic problems  with emphasis on  computational and theoretical  advantages over the standard FVEM. Further, we present a natural extension of DFVEM employed for the elliptic problem to the Stokes problems. We also discuss suitability of these methods for the approximation of incompressible miscible displacement problems.
 

The vast majority of the world's electricity is generated by converting thermal energy into electric energy by use of a steam turbine. Siemens are one of the worlds leading manufacturers of such
turbines, and aim to design theirs to be as efficient as possible. Using an internally built software, Siemens can estimate the efficiency which would result from a turbine design. In this presentation, we present the approaches that have been taken to improve turbine design using mathematical optimisation software. In particular, we focus on the failings of the approach currently taken, the obstacles in place which make solving this problem difficult, and the approach we intend to take to find a locally optimal solution.