FRG: Collaborative Research: Randomized Algorithms for Solving Linear Systems

FRG：协作研究：求解线性系统的随机算法

基本信息

批准号：
1952735
负责人：
Per-Gunnar Martinsson
金额：
$ 67.7万
依托单位：
University of Texas at Austin
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-08-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1952735&HistoricalAwards=false
关键词：
FRG Collaborative Research Randomized Algorithms

项目摘要

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.

该项目的目的是为计算科学中最基本的任务之一开发更快，更节能的算法：解决大型耦合线性方程的系统。更快的算法都将加速可以执行的计算，并启用无法实现现有方法的计算。更节能的算法将有助于减少数据中心的功耗，并延长移动设备（例如手机和平板电脑）的电池寿命。我们方法背后的基本创新是利用大量随机数的数学属性来构建新的随机算法，从而极大地表现出现有的确定性。简而言之，这个想法是使用随机抽样和随机平均，以减少要处理的问题的有效维度。此外，该项目为博士后研究员和研究生提供了研究培训机会。我们试图开发有效的计算方法，以解决涉及大量变量的方程式的线性系统，无论是在渐近复杂性方面，都在现实问题上的实际速度而言尺寸。这样的方程式在科学和工程中普遍存在，并且解决它们通常是时间的瓶颈，可以决定解决问题的大小。特别是，这就是限制了可以分析数据集的大小，或者在建模某些物理现象时的计算模拟如何现实。通过开发更快，更有效的算法，我们将加速今天完成的计算，并使许多其他方法都超出了当前现有方法的范围。该项目的前提是最近开发了用于解决线性代数问题的新随机算法的发展。事实证明，此类方法对某些任务（例如计算矩阵的低等级因素化）的表现非常优于经典的确定性方法 - 例如，重要的计算步骤，例如主成分分析，Larry Page和Sergey Brin的Pagerank算法，对复杂的多尺度系统进行建模时的数值粗晶粒等等。随机算法也已用于为线性系统构建更快的求解器。但是，尽管此时获得的理论结果极为令人鼓舞，但仍在开发在实际应用中果断更快的随机线性求解器。为了实现这一目标，该项目将支持一个研究小组，该研究小组汇集了四个具有数值线性代数互补技能的研究人员，随机矩阵理论，计算谐波分析，优化和高性能计算。这一奖项反映了NSF的法定任务，并被视为值得通过基金会的智力优点和更广泛的影响审查标准来通过评估来支持。