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

线性代数算法中的随机化是一个令人兴奋和创新的想法。近年来，大量的工作集中在回归问题的可证明准确的随机算法上，特别强调最小二乘回归。快速算法的这些问题是持续的兴趣，由于其广泛的适用性，在科学计算和统计数据分析，越来越大的输入矩阵出现。PI旨在从理论上和数值上研究可证明准确且实用的随机算法，以解决以下问题：（i）回归问题的约束矩阵是拉普拉斯算子，或（ii）回归问题是欠约束或过约束且稀疏的。因此，PI试图解决Spielman，Teng及其合作者最近突破性的理论结果与其实际适用性之间的惊人差距，以及缺乏有效的算法来处理稀疏输入矩阵的过度或欠约束回归问题。为了弥合理论和应用之间的差距差距，在这条线的研究，一些新的理论成果是必要的，将进行调查。建议的研究的实际用途将使用数据矩阵从科学application.Efficiently解决大型线性方程组的数值分析和线性代数中最基本的问题，可能是数值评估和数值评估，主要是因为这样的系统是无处不在的科学计算应用。拟议的工作旨在将Spielman，Teng及其合作者最近关于求解具有拉普拉斯输入矩阵的线性方程组的理论突破更接近实践。为此，理论和数值结果将得出。这种研究范式随后可以作为一个起点，以激发更广泛的大型线性方程组的系统的进一步研究工作。拟议工作的影响的第二个方面与理论计算机科学和数值线性代数方法之间的相当大的重叠，将进行探讨。随着随机化在线性代数的背景下变得越来越有用，PI预计该领域的下一代研究人员将需要在这两个领域进行扎实的培训，这正是拟议的工作将为研究生提供的。最后，拟议工作影响的第三个方面将通过在备受瞩目的相关会议上通过研讨会、教程和小型研讨会传播我们的成果而显现。

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.