DMS-EPSRC:Certifying Accuracy of Randomized Algorithms in Numerical Linear Algebra

University Of Texas At Austin, Austin TX

Investigators

Abstract

The project will improve the accuracy and robustness of randomized algorithms for solving some of the most fundamental tasks in computational science. Specifically, the project will focus on algorithms for solving linear algebraic equations involving large arrays of numbers known as matrices, or large connected systems of linear equations, using Numerical Linear Algebra (NLA) techniques. Such equations form a core part of many computations performed on laptops, smartphones, tablets, and supercomputers. With the rise of data science and machine learning leading to massive datasets to process, the need for efficient and reliable methodologies for solving such equations is growing. Within the field of NLA, a key innovation in the past couple of decades has been the development of a new set of algorithms that harness the mathematical properties of extensive collections of random numbers to build new randomized algorithms that outperform existing deterministic ones. This project will develop techniques for certifying the accuracy of an answer computed using a randomized algorithm. The project will further develop algorithms that combine the speed of randomized methods with the robustness of classical algorithms. The project will provide training opportunities for students and early career researchers in STEM. The project aims to develop techniques for assessing the accuracy of a particular instantiation of a randomized algorithm for solving a linear algebraic problem. The project will represent a continuation of a more significant research effort on randomized algorithms in linear algebra that has already impacted the computational sciences and enabled massively large-scale matrix computations. This project will develop a-posteriori error estimates and bounds, which are in contrast to existing apriori estimates and bounds. The investigators will construct bounds that utilize only information available to the user at the time of the computation. The new estimates will be deployed to standard problems such as low-rank approximation, solving linear systems, and approximating data-sparse matrices. The project will develop algorithms that combine the remarkable speed and versatility of randomized algorithms, with the reliability and robustness of existing deterministic methods. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.