L3

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).

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?

For a polynomial $h(x)$ in $F[x]$, where $F$ is any field, let $A$ be the
$F$-algebra given by generators $x$ and $y$ and relation $[y, x]=h$.
This family of algebras include the Weyl algebra, enveloping algebras of
$2$-dimensional Lie algebras, the Jordan plane and several other
interesting subalgebras of the Weyl algebra.

In a joint work in progress with Samuel Lopes, we computed the Hochschild
cohomology $HH^*(A)$ of $A$ and determined explicitly the Gerstenhaber
structure of $HH^*(A)$, as a Lie module over the Lie algebra $HH^1(A)$.
In case $F$ has characteristic $0$, this study has revealed that $HH^*(A)$
has finite length as a Lie module over $HH^1(A)$ with pairwise
non-isomorphic composition factors and the latter can be naturally
extended into irreducible representations of the Virasoro algebra.
Moreover, the whole action can be understood in terms of the partition
formed by the multiplicities of the irreducible factors of the polynomial
$h$.
 

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.