Randomized Methods for Very Large-Scale Linear Algebra

At the core of many computational simulations of physical systems lies a linear algebraic problem, such as a system of linear equations to be solved or an eigenvalue problem. Similar problems also arise throughout computational statistics and data science. Because such computations are often the most computationally expensive part of a simulation, they frequently determine both the simulation’s feasibility and the level of physical detail it can achieve.

In this Presidential Lecture, Per-Gunnar Martinsson will describe how ideas from random matrix theory and high-dimensional probability have, in recent years, enabled a new generation of algorithms that are far faster than traditional deterministic methods and have enabled simulations of problems once considered intractable. One of the most important features of these randomized methods is that they require very little data movement, making them especially well-suited to modern computing hardware. The lecture will present methods for low-rank approximation, for solving linear systems, and for constructing highly accurate compressed representations of continuum operators, including solution operators for elliptic partial differential equations, Dirichlet-to-Neumann maps and time-evolution operators.