Talk by Nicholas J. Higham (University of Manchester)

Are Numerical Linear Algebra Algorithms Accurate at Extreme Scale and at Low Precisions?

The advent of exascale computing will bring the capability to solve dense linear systems of order $10^8$. At the same time, computer hardware is increasingly supporting low precision floating-point arithmetics, such as the IEEE half precision and bfloat16 arithmetics. The standard rounding error bound for the inner product of two $n$-vectors $x$ and $y$ is $|fl(x^Ty) - x^Ty| \le n u |x|^T|y|$, where $u$ is the unit roundoff, and the bound is approximately attainable. This bound provides useful information only if $nu$ less than 1. Yet $nu$ larger than 1 for exascale-size problems solved in single precision and also for problems of order $n$ larger than 2048 solved in half precision. Standard error bounds for matrix multiplication, LU factorization, and so on, are equally uninformative in these situations. Yet the supercomputers in the TOP500 are there by virtue of having successfully solved linear systems of orders up to $10^7$, and deep learning implementations routinely use half precision with apparent success.

Have we reached the point where our techniques for analyzing rounding errors, honed over 70 years of digital computation, are unable to predict the accuracy of numerical linear algebra computations that are now routine? I will show that the answer is "no": we can understand the behaviour of extreme-scale and low accuracy computations. The explanation lies in algorithmic design techniques (both new and old) that help to reduce error growth along with a new probabilistic approach to rounding error analysis.