Past Numerical Analysis Group Internal Seminar

We propose a randomized algorithm for solving a linear system $Ax = b$ with a highly numerically rank-deficient coefficient matrix $A$ with nearly consistent right-hand side possessing a small-norm solution. Our algorithm finds a small-norm solution with small residual in $O(N_r + nrlogn + r^3 )$ operations, where $r$ is the numerical rank of $A$ and $N_r$ is the cost of multiplying an $n\times r$ matrix to $A$. 

Joint work with Marcus Webb (Manchester). 

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact trefethen@maths.ox.ac.uk.

Often in scattering applications it is advantageous to reformulate the problem as an integral equation, discretize, and then solve the resulting linear system using a fast direct solver. The computational cost of this approach is typically dominated by the work needed to compress the coefficient matrix into a rank-structured format. In this talk, we present a novel technique which exploits the bandlimited-nature of solutions to the Helmholtz equation in order to accelerate this procedure in environments where multiple frequencies are of interest.

This talk is based on joint work with Gunnar Martinsson (UT Austin).

-

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact trefethen@maths.ox.ac.uk.

Motivated by the work of K.R. Rajagopal, the objective of the talk is to discuss the construction and analysis of numerical approximations to a class of models that fall outside the realm of classical Cauchy elasticity. The models under consideration are implicit and nonlinear, and are referred to as strain-limiting, because the linearised strain remains bounded even when the stress is very large, a property that cannot be guaranteed within the framework of classical elastic or nonlinear elastic models. Strain-limiting models can be used to describe, for example, the behavior of brittle materials in the vicinity of fracture tips, or elastic materials in the neighborhood of concentrated loads where there is concentration of stress even though the magnitude of the strain tensor is limited.

We construct a finite element approximation of a strain-limiting elastic model and discuss the theoretical difficulties that arise in proving the convergence of the numerical method. The analytical results are illustrated by numerical experiments.

The talk is based on joint work with Andrea Bonito (Texas A&M University) and Vivette Girault (Sorbonne Université, Paris).

--

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact trefethen@maths.ox.ac.uk.

For high order finite elements (continuous piecewise polynomials) the conditioning of the basis is important. However, so far there seems no generally accepted concept of "a well-conditioned basis”,  or a general strategy for how to obtain such representations. In this presentation, we use the $L^2$ condition number as a measure of the conditioning, and construct representations by frames such that the associated $L^2$ condition number is bounded independently of the polynomial degree. The main tools include the bubble transform, which is a stable decomposition of functions into local modes, and orthogonal polynomials on simplexes.  We also include a brief discussion on potential applications in preconditioning. This is a joint work with Ragnar Winther. 

--

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact trefethen@maths.ox.ac.uk.

That neural networks may be pruned to high sparsities and retain high accuracy is well established. Recent research efforts focus on pruning immediately after initialization so as to allow the computational savings afforded by sparsity to extend to the training process. In this work, we introduce a new `DCT plus Sparse' layer architecture, which maintains information propagation and trainability even with as little as 0.01% trainable kernel parameters remaining. We show that standard training of networks built with these layers, and pruned at initialization, achieves state-of-the-art accuracy for extreme sparsities on a variety of benchmark network architectures and datasets. Moreover, these results are achieved using only simple heuristics to determine the locations of the trainable parameters in the network, and thus without having to initially store or compute with the full, unpruned network, as is required by competing prune-at-initialization algorithms. Switching from standard sparse layers to DCT plus Sparse layers does not increase the storage footprint of a network and incurs only a small additional computational overhead.

--

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact trefethen@maths.ox.ac.uk.

A wide variety of fixed-point iterative methods for the solution of nonlinear operator equations in Hilbert spaces exists. In many cases, such schemes can be interpreted as iterative local linearisation methods, which can be obtained by applying a suitable preconditioning operator to the original (nonlinear) equation. Based on this observation, we will derive a unified abstract framework which recovers some prominent iterative methods. It will be shown that for strongly monotone operators this unified iteration scheme satisfies an energy contraction property. Consequently, the generated sequence converges to a solution of the original problem.

--

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact trefethen@maths.ox.ac.uk.

Point cloud registration is the task of finding the transformation that aligns two data sets. We make the assumption that the data lies on a low-dimensional algebraic variety.  The task is phrased as an optimization problem over the special orthogonal group of rotations. We solve this problem using Riemannian optimization algorithms and show numerical examples that illustrate the efficiency of this approach for point cloud registration. 

--

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact trefethen@maths.ox.ac.uk.

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact trefethen@maths.ox.ac.uk.

Topology optimisation finds the optimal material distribution of a fluid or solid in a domain, subject to PDE, volume, and box constraints. The optimisation problem is normally nonconvex and can support multiple local minima. In recent work [1], the authors developed an algorithm for systematically discovering multiple minima of two-dimensional problems through a combination of barrier methods, active-set strategies, and deflation. The bottleneck of the algorithm is solving the Newton systems that arise. In this talk, we will present preconditioning methods for these linear systems as they occur in the topology optimization of Stokes flow. The strategies involve a mix of block preconditioning and specialized multigrid relaxation schemes that reduce the computational work required and allow the application of the algorithm to three-dimensional problems.

[1] “Computing multiple solutions of topology optimization problems”, I. P. A. Papadopoulos, P. E. Farrell, T. M. Surowiec, 2020, https://arxiv.org/abs/2004.11797

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact trefethen@maths.ox.ac.uk.

Identifying discrete patterns in binary data is an important dimensionality reduction tool in machine learning and data mining. In this paper, we consider the problem of low-rank binary matrix factorisation (BMF) under Boolean arithmetic. Due to the NP-hardness of this problem, most previous attempts rely on heuristic techniques. We formulate the problem as a mixed integer linear program and use a large scale optimisation technique of column generation to solve it without the need of heuristic pattern mining. Our approach focuses on accuracy and on the provision of optimality guarantees. Experimental results on real world datasets demonstrate that our proposed method is effective at producing highly accurate factorisations and improves on the previously available best known results for 16 out of 24 problem instances.

--

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact trefethen@maths.ox.ac.uk.

In this talk, we will present an approach to constrained optimisation when the set of constraints is a smooth manifold. This setting is of particular interest in data science applications, as many interesting sets of matrices have a manifold structure. We will show how we may couple classic ideas from differential geometry with modern methods such as autodifferentiation to simplify optimisation problems from spaces with a difficult topology (e.g. problems with orthogonal or fixed-rank constraints) to problems on ℝⁿ where we can use any classical optimisation methods to solve them. We will also show how to use these methods to automatically compute quantities such as the Riemannian gradient and Hessian. We will present the library GeoTorch that allows for putting these kind of constraints within models written in PyTorch by adding just one line to the model. We will also comment on some convergence results if time allows.

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please contact trefethen@maths.ox.ac.uk.

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please send email to trefethen@maths.ox.ac.uk.

Preconditioning techniques are widely used for speeding up the iterative solution of systems of linear equations, often by transforming the system into one with lower condition number. Even though the condition number also serves as the determining constant in simple bounds for the numerical error of the solution, simple experiments and bounds show that such preconditioning on the matrix level is not guaranteed to reduce this error. Transformations on the operator level, on the other hand, improve both accuracy and speed of iterative methods as predicted by the change of the condition number. We propose to investigate such methods under a common framework, which we call full operator preconditioning, and show practical examples.

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please send an email to trefethen@maths.ox.ac.uk.

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please send email to trefethen@maths.ox.ac.uk.

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please send email to trefethen@maths.ox.ac.uk.

Smectic A liquid crystals are of great interest in physics for their striking defect structures, including curvature walls and focal conics. However, the mathematical modeling of smectic liquid crystals has not been extensively studied. This work takes a step forward in understanding these fascinating topological defects from both mathematical and numerical viewpoints. In this talk, we propose a new (two- and three-dimensional) mathematical continuum model for the transition between the smectic A and nematic phases, based on a real-valued smectic order parameter for the density perturbation and a tensor-valued nematic order parameter for the orientation. Our work expands on an idea mentioned by Ball & Bedford (2015). By doing so, physical head-to-tail symmetry in half charge defects is respected, which is not possible with vector-valued nematic order parameter.

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please send email to trefethen@maths.ox.ac.uk.

Motivated by the advent of machine learning, the last few years saw the return of hardware-supported low-precision computing. Computations with fewer digits are faster and more memory and energy efficient, but can be extremely susceptible to rounding errors. An application that can largely benefit from the advantages of low-precision computing is the numerical solution of partial differential equations (PDEs), but a careful implementation and rounding error analysis are required to ensure that sensible results can still be obtained. In this talk we study the accumulation of rounding errors in the solution of the heat equation, a proxy for parabolic PDEs, via Runge-Kutta finite difference methods using round-to-nearest (RtN) and stochastic rounding (SR). We demonstrate how to implement the numerical scheme to reduce rounding errors and we present \emph{a priori} estimates for local and global rounding errors. Let $u$ be the roundoff unit. While the worst-case local errors are $O(u)$ with respect to the discretization parameters, the RtN and SR error behaviour is substantially different. We show that the RtN solution is discretization, initial condition and precision dependent, and always stagnates for small enough $\Delta t$. Until stagnation, the global error grows like $O(u\Delta t^{-1})$. In contrast, the leading order errors introduced by SR are zero-mean, independent in space and mean-independent in time, making SR resilient to stagnation and rounding error accumulation. In fact, we prove that for SR the global rounding errors are only $O(u\Delta t^{-1/4})$ in 1D and are essentially bounded (up to logarithmic factors) in higher dimensions.

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please send email to trefethen@maths.ox.ac.uk.

Since Weierstrass it has been known that there are functions that are continuous but nowhere differentiable.  A beautiful example (with probability 1) is any Brownian path.  Brownian paths can be constructed either in space, via Brownian bridge, or in Fourier space, via random Fourier series.

What about functions, which we call "smoothies", that are $C^\infty$ but nowhere analytic?  This case is less familiar but analogous, and again one can do the construction either in space or Fourier space.  We present the ideas and illustrate them with the new Chebfun $\tt{smoothie}$ command.  In the complex plane, the same idea gives functions analytic in the open unit disk and $C^\infty$ on the unit circle, which is a natural boundary.

Reconstruction of 3D images from a set of 2D X-ray projections is a standard inverse problem, particularly in medical imaging. Improvements in imaging technologies have enabled the development of a flat-panel X-ray source, comprised of an array of low-power emitters that are fired in quick succession. During a complete firing sequence, there may be shifts in the patient’s resting position which ultimately create artifacts in the final reconstruction. We present a method for correcting images with respect to unknown body motion, focusing on the case of simple rigid body motion. Image reconstructions are obtained by solving a sparse linear inverse problem, with respect to not only the underlying body but also the unknown velocity. Results find that reconstructions of a moving body can be much better than those obtained by measuring a stationary body, as long as the underlying motion is well approximated.

The standard rounding procedure in floating-point computations is round to nearest (RN). In this talk we consider an alternative rounding strategy called stochastic rounding (SR) which has the appealing property of being exact (actually exact!) in expectation. In the first part of the talk we discuss recent developments in probabilistic rounding error analysis and we show how rounding errors grow at an O(\sqrt{n}) rate rather than O(n) when SR is employed. This shows that Wilkinson's rule of thumb provably holds for this type of rounding. In the second part of the talk we consider the application of SR to parabolic PDEs admitting a steady state solution. We show that when the heat equation is solved in half precision RN fails to compute an accurate solution, while SR successfully solves the problem to decent accuracy.
 

We consider the problem of dynamically pricing multiple products on a network of resources, such as that faced by an airline selling tickets on its route network. For computational reasons this inherently stochastic problem is often approximated deterministically, however even the deterministic dynamic pricing problem can be impractical to solve. For this reason we have derived a novel iterative Quadratic Programming approximation to the deterministic dynamic pricing problem that is not only very fast to solve in practice but also exhibits a provably linear rate of convergence. This is joint work with Saksham Jain and Raphael Hauser.
 

Robust principal component analysis and low-rank matrix completion are extensions of PCA that allow for outliers and missing entries, respectively. Solving these problems requires a low coherence between the low-rank matrix and the canonical basis. However, in both problems the well-posedness issue is even more fundamental; in some cases, both Robust PCA and matrix completion can fail to have any solutions due to the fact that the set of low-rank plus sparse matrices is not closed. Another consequence of this fact is that the lower restricted isometry property (RIP) bound cannot be satisfied for some low-rank plus sparse matrices unless further restrictions are imposed on the constituents. By restricting the energy of one of the components, we close the set and are able to derive the RIP over the set of low rank plus sparse matrices and operators satisfying concentration of measure inequalities. We show that the RIP of an operator implies exact recovery of a low-rank plus sparse matrix is possible with computationally tractable algorithms such as convex relaxations or line-search methods. We propose two efficient iterative methods called Normalized Iterative Hard Thresholding (NIHT) and Normalized Alternative Hard Thresholding (NAHT) that provably recover a low-rank plus sparse matrix from subsampled measurements taken by an operator satisfying the RIP.
 

Randomized SVD has become an extremely successful approach for efficiently computing a low-rank approximation of matrices. In particular the paper by Halko, Martinsson (who is speaking twice this week), and Tropp (SIREV 2011) contains extensive analysis, and made it a very popular method. 
The complexity for $m\times n$ matrices is $O(Nr+(m+n)r^2)$ where $N$ is the cost of a (fast) matrix-vector multiplication; which becomes $O(mn\log n+(m+n)r^2)$ for dense matrices. This work uses classical results in numerical linear algebra to reduce the computational cost to $O(Nr)$ without sacrificing numerical stability. The cost is essentially optimal for many classes of matrices, including $O(mn\log n)$ for dense matrices. The method can also be adapted for updating, downdating and perturbing the matrix, and is especially efficient relative to previous algorithms for such purposes.  

We introduce a new and generic approximation to Schur complements arising from inf-sup stable mixed finite element discretizations of self-adjoint multi-physics problems. The approximation exploits the discretization mesh by forming local, or element, Schur complements and projecting them back to the global degrees of freedom. The resulting Schur complement approximation is sparse, has low construction cost (with the same order of operations as a general finite element matrix), and can be solved using off-the-shelf techniques, such as multigrid. Using the Ladyshenskaja-Babu\v{s}ka-Brezzi condition, we show that this approximation has favorable eigenvalue distributions with respect to the global Schur complement. We present several numerical results to demonstrate the viability of this approach on a range of applications. Interestingly, numerical results show that the method gives an effective approximation to the non-symmetric Schur complement from the steady state Navier-Stokes equations.
 

In STFC's Computational Mathematics Group, we work alongside scientists at large-scale National Facilities, such as ISIS Neutron and Muon source, Diamond Light Source, and the Central Laser Facility. For each of these groups, non-linear least squares fitting is a vital part of their scientific workflow. In this talk I will describe FitBenchmarking, a software tool we have developed to benchmark the performance of different non-linear least squares solvers on real-world data. It is designed to be easily extended, so that new data formats and new minimizers can be added. FitBenchmarking will allow (i) scientists to determine objectively which fitting engine is optimal for solving their problem on their computing architecture, (ii) scientific software developers to quickly test state-of-the-art algorithms in their data analysis software, and (iii) mathematicians and numerical software developers to test novel algorithms against realistic datasets, and to highlight characteristics of problems where the current best algorithms are not sufficient.