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

Abstract: 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 < 1$. Yet $nu > 1$ for exascale-size problems solved in single precision and also for problems of order $n > 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.

Mathematics

Audience: researchers in the topic

E-NLA - Online seminar series on numerical linear algebra

Series comments: E-NLA is an online seminar series dedicated to topics in Numerical Linear Algebra. Talks take place on Wednesdays at 4pm (Central European Time) via Zoom and are initially scheduled on a weekly basis.

To join the seminar, please complete the sign up form at the bottom of the webpage. Information about how to connect to the conference call will be circulated via email to all registered attendees.