FRG: Collaborative Research: Randomized Algorithms for Solving Linear Systems

California Institute Of Technology, Pasadena CA

Investigators

Abstract

The objective of this project is to develop faster and more energy-efficient algorithms for one of the most fundamental tasks in computational science: solving large systems of coupled linear equations. Faster algorithms will both accelerate computations that can already be performed, and enable computations that are beyond the reach of existing methods. More energy efficient algorithms will help to reduce the power consumption of data centers, and to extend the battery life of mobile devices such as cell phones and tablet computers. The fundamental innovation behind our approach is to harness mathematical properties of large collections of random numbers to build new stochastic algorithms that dramatically outperform existing deterministic ones. In a nutshell, the idea is to use randomized sampling, and randomized averaging, to reduce the effective dimensionality of the problems to be processed. In addition the project provides research training opportunities for postdoctoral fellows and graduate students. We seek to develop computationally efficient methods for solving linear systems of equations involving large numbers of variables, both in terms of asymptotic complexity, and in terms of practical speed at realistic problem sizes. Such systems of equations arise ubiquitously in science and engineering, and solving them is often the bottleneck in terms of time that decides how large of a problem can be handled. In particular, this is what limits how large of a data set can be analyzed, or how realistic a computational simulation can be when modelling some physical phenomenon. By developing faster and more efficient algorithms, we will accelerate computations that are done today, and enable many others that are outside the reach of currently existing methods. The project is premised on the recent development of new randomized algorithms for solving linear algebraic problems. Such methods have proven to dramatically outperform classical deterministic methods for certain tasks such as computing low rank factorizations to matrices - the crucial computational step in e.g. Principal Component Analysis, the PageRank algorithm by Larry Page and Sergey Brin, numerical coarse graining when modeling complex multiscale systems, and many more. Randomized algorithms have also been used to build faster solvers for linear systems. However, while the theoretical results obtained at this point are extremely encouraging, it remains to develop randomized linear solvers that are decisively faster in practical applications. To achieve this goal, the project will support a research group that brings together four researchers with complementary skills in numerical linear algebra, random matrix theory, computational harmonic analysis, optimization, and high performance computing. 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.