Randomization for solving difficult linear algebra problems

Randomization is becoming an increasingly popular tool in numerical linear algebra, sometimes leading to surprisingly simple algorithms that frequently outperform existing deterministic algorithms. The poster child of these developments, the randomized singular value decomposition is nowadays one of the state-the-of-art approaches to perform low-rank approximation for large-scale matrices. In this talk, we will discuss numerous further examples for the potential of randomization to facilitate the solution of notoriously difficult linear algebra problems. This includes a simple numerical algorithm for jointly diagonalizing a family of nearly commuting matrices, a topic to which Heydar Radjavi has made seminal contributions. We will also discuss the solution of several other challenging flavors of eigenvalue problems as well as the low-rank approximation of matrix functions and matrix-valued functions. A common theme of all these developments is that randomization turns identities that only hold generically into robust numerical algorithms that come with reliability guarantees.