AF: Small: Fast and Efficient Randomized Algorithms for Solving Laplacian Systems of Linear Equations and Sparse Least Squares Problems

Rensselaer Polytechnic Institute, Troy NY

Investigators

Abstract

Randomization in the context of linear-algebraic algorithms is an exciting and innovative idea. In recent years, a large body of work has focused on provably accurate randomized algorithms for regression problems, with a particular emphasis on least-squares regression. Fast algorithms for such problems are of continuous interest due to their broad applicability in scientific computing and statistical data analysis, where increasingly larger input matrices appear. The PI seeks to theoretically and numerically investigate provably accurate and practically useful randomized algorithms for such problems when (i) the constraint matrix of the regression problem is Laplacian, or (ii) the regression problem is under- or over-constrained and sparse. Thus, the PI seeks to address the alarming gap between recent breakthrough theoretical results of Spielman, Teng, and collaborators and their practical applicability, as well as the lack of efficient algorithms dealing with over- or under-constrained regression problems with sparse input matrices. In order to bridge the gap between theory and applications in this line of research, a number of novel theoretical results are necessary and will be investigated. The practical usefulness of the proposed research will be numerically evaluated using data matrices from scientific applications. Efficiently solving large systems of linear equations is perhaps the most fundamental question in numerical analysis and linear algebra, mainly because such systems are ubiquitous in scientific computing applications. The proposed work seeks to bring the theoretical breakthroughs of the recent work of Spielman, Teng, and collaborators on solving systems of linear equations with Laplacian input matrices closer to practice. Towards that end, both theoretical as well as numerical results will be derived. This research paradigm can subsequently be used as a starting point in order to spark further research efforts on broader classes of massive systems of linear equations. A second aspect of the impact of the proposed work has to do with the considerable overlap between Theoretical Computer Science and Numerical Linear Algebra approaches that will be explored. As randomization becomes increasingly useful in the context of linear algebra, the PI expects that the next generation of researchers in this domain will need solid training in both areas, which is exactly what the proposed work will provide to graduate students. Finally, a third aspect of the impact of the proposed work will emerge from the dissemination of our results via workshops, tutorials, and mini-symposia in high-profile relevant conferences.