Could a randomized least squares solver become the default in your favorite programming language?

In recent years, researchers have developed a number of fast, randomized algorithms for linear algebra problems. But for widespread deployment of these methods, speed is not enough. To safely incorporate randomized algorithms into general-purpose linear algebra software, we need algorithms which are accurate, stable, and robust. This talk presents new results on the accuracy and stability of randomized least-squares solvers. These results present both good news and bad news concerning the stability of current randomized methods. On the positive side, several current randomized least-squares solvers are forward stable, quickly producing a least-squares solution with comparable error to standard direct solvers. Unfortunately, existing fast randomized least-squares methods are not backward stable, preventing them from being used as drop-in replacements for standard direct methods in some use cases. The talk concludes by discussing ongoing research to develop backward stable randomized least-square methods.