FRG: Collaborative Research: Randomized Algorithms for Solving Linear Systems

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

基本信息

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

项目摘要

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.
该项目的目标是为计算科学中最基本的任务之一开发更快、更节能的算法:求解大型耦合线性方程组。更快的算法既可以加速已经执行的计算,又可以实现现有方法无法实现的计算。更节能的算法将有助于减少数据中心的电力消耗,并延长手机和平板电脑等移动设备的电池寿命。我们的方法背后的根本创新是利用大量随机数集合的数学特性来构建新的随机算法,这些算法大大优于现有的确定性算法。简而言之,其思想是使用随机抽样和随机平均来降低待处理问题的有效维数。此外,该项目还为博士后和研究生提供研究培训机会。我们寻求开发计算效率的方法来解决线性方程组涉及大量变量,无论是在渐进的复杂性方面,在实际问题规模的实际速度方面。这样的方程组在科学和工程中无处不在,解决它们往往是时间上的瓶颈,决定了一个问题能处理多大。特别是,这限制了可以分析的数据集的大小,或者在模拟某些物理现象时计算模拟的逼真程度。通过开发更快、更高效的算法,我们将加速目前已经完成的计算,并使许多其他目前现有方法无法实现的计算成为可能。该项目以解决线性代数问题的新随机算法的最新发展为前提。事实证明,这些方法在某些任务上的表现明显优于经典的确定性方法,比如计算矩阵的低秩分解——这是主成分分析、拉里·佩奇和谢尔盖·布林的PageRank算法、复杂多尺度系统建模时的数值粗粒度等关键计算步骤。随机算法也被用来为线性系统建立更快的求解器。然而,尽管在这一点上获得的理论结果非常令人鼓舞,但仍需要开发在实际应用中更快的随机线性求解器。为了实现这一目标,该项目将支持一个由四名在数值线性代数、随机矩阵理论、计算谐波分析、优化和高性能计算方面具有互补技能的研究人员组成的研究小组。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(7)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates
  • DOI:
  • 发表时间:
    2021-02
  • 期刊:
  • 影响因子:
    0
  • 作者:
    De Huang;Jonathan Niles-Weed;Rachel A. Ward
  • 通讯作者:
    De Huang;Jonathan Niles-Weed;Rachel A. Ward
Computing rank‐revealing factorizations of matrices stored out‐of‐core
计算排名——揭示存储在核心之外的矩阵的因式分解
Zeta correction: a new approach to constructing corrected trapezoidal quadrature rules for singular integral operators
Zeta 校正:构建奇异积分算子校正梯形求积规则的新方法
  • DOI:
    10.1007/s10444-021-09872-9
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    1.7
  • 作者:
    Wu, Bowei;Martinsson, Per-Gunnar
  • 通讯作者:
    Martinsson, Per-Gunnar
Bootstrapping the Error of Oja's Algorithm
  • DOI:
  • 发表时间:
    2021-06
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Robert Lunde;Purnamrita Sarkar;Rachel A. Ward
  • 通讯作者:
    Robert Lunde;Purnamrita Sarkar;Rachel A. Ward
Randomized numerical linear algebra: Foundations and algorithms
  • DOI:
    10.1017/s0962492920000021
  • 发表时间:
    2020-05-01
  • 期刊:
  • 影响因子:
    14.2
  • 作者:
    Martinsson, Per-Gunnar;Tropp, Joel A.
  • 通讯作者:
    Tropp, Joel A.
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Per-Gunnar Martinsson其他文献

SlabLU: a two-level sparse direct solver for elliptic PDEs
  • DOI:
    10.1007/s10444-024-10176-x
  • 发表时间:
    2024-08-09
  • 期刊:
  • 影响因子:
    2.100
  • 作者:
    Anna Yesypenko;Per-Gunnar Martinsson
  • 通讯作者:
    Per-Gunnar Martinsson
Mechanics of Materials with Periodic Truss or Frame Micro-Structures
A simplified fast multipole method based on strong recursive skeletonization
一种基于强递归骨架化的简化快速多极子方法
  • DOI:
    10.1016/j.jcp.2024.113707
  • 发表时间:
    2025-03-01
  • 期刊:
  • 影响因子:
    3.800
  • 作者:
    Anna Yesypenko;Chao Chen;Per-Gunnar Martinsson
  • 通讯作者:
    Per-Gunnar Martinsson

Per-Gunnar Martinsson的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Per-Gunnar Martinsson', 18)}}的其他基金

DMS-EPSRC:Certifying Accuracy of Randomized Algorithms in Numerical Linear Algebra
DMS-EPSRC:验证数值线性代数中随机算法的准确性
  • 批准号:
    2313434
  • 财政年份:
    2023
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Standard Grant
Collaborative Research: Nonoscillatory Phase Methods for the Variable Coefficient Helmholtz Equation in the High-Frequency Regime
合作研究:高频域下变系数亥姆霍兹方程的非振荡相法
  • 批准号:
    2012606
  • 财政年份:
    2020
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Standard Grant
Randomized Algorithms for Matrix Computations
矩阵计算的随机算法
  • 批准号:
    1929568
  • 财政年份:
    2018
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Standard Grant
Randomized Algorithms for Matrix Computations
矩阵计算的随机算法
  • 批准号:
    1620472
  • 财政年份:
    2016
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Standard Grant
Collaborative Research: Scalable and accurate direct solvers for integral equations on surfaces
协作研究:可扩展且精确的曲面积分方程直接求解器
  • 批准号:
    1320652
  • 财政年份:
    2013
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Standard Grant
CAREER: Fast Direct Solvers for Differential and Integral Equations
职业:微分方程和积分方程的快速直接求解器
  • 批准号:
    0748488
  • 财政年份:
    2008
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Continuing Grant
Fast Direct Solvers for Boundary Integral Equations
边界积分方程的快速直接求解器
  • 批准号:
    0610097
  • 财政年份:
    2006
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Standard Grant

相似海外基金

FRG: Collaborative Research: New birational invariants
FRG:协作研究:新的双有理不变量
  • 批准号:
    2244978
  • 财政年份:
    2023
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Continuing Grant
FRG: Collaborative Research: Singularities in Incompressible Flows: Computer Assisted Proofs and Physics-Informed Neural Networks
FRG:协作研究:不可压缩流中的奇异性:计算机辅助证明和物理信息神经网络
  • 批准号:
    2245017
  • 财政年份:
    2023
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Standard Grant
FRG: Collaborative Research: Variationally Stable Neural Networks for Simulation, Learning, and Experimental Design of Complex Physical Systems
FRG:协作研究:用于复杂物理系统仿真、学习和实验设计的变稳定神经网络
  • 批准号:
    2245111
  • 财政年份:
    2023
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Continuing Grant
FRG: Collaborative Research: Variationally Stable Neural Networks for Simulation, Learning, and Experimental Design of Complex Physical Systems
FRG:协作研究:用于复杂物理系统仿真、学习和实验设计的变稳定神经网络
  • 批准号:
    2245077
  • 财政年份:
    2023
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Continuing Grant
FRG: Collaborative Research: Singularities in Incompressible Flows: Computer Assisted Proofs and Physics-Informed Neural Networks
FRG:协作研究:不可压缩流中的奇异性:计算机辅助证明和物理信息神经网络
  • 批准号:
    2244879
  • 财政年份:
    2023
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Standard Grant
FRG: Collaborative Research: New Birational Invariants
FRG:合作研究:新的双理性不变量
  • 批准号:
    2245171
  • 财政年份:
    2023
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Continuing Grant
FRG: Collaborative Research: Singularities in Incompressible Flows: Computer Assisted Proofs and Physics-Informed Neural Networks
FRG:协作研究:不可压缩流中的奇异性:计算机辅助证明和物理信息神经网络
  • 批准号:
    2403764
  • 财政年份:
    2023
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Standard Grant
FRG: Collaborative Research: Singularities in Incompressible Flows: Computer Assisted Proofs and Physics-Informed Neural Networks
FRG:协作研究:不可压缩流中的奇异性:计算机辅助证明和物理信息神经网络
  • 批准号:
    2245021
  • 财政年份:
    2023
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Standard Grant
FRG: Collaborative Research: Variationally Stable Neural Networks for Simulation, Learning, and Experimental Design of Complex Physical Systems
FRG:协作研究:用于复杂物理系统仿真、学习和实验设计的变稳定神经网络
  • 批准号:
    2245097
  • 财政年份:
    2023
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Continuing Grant
FRG: Collaborative Research: Variationally Stable Neural Networks for Simulation, Learning, and Experimental Design of Complex Physical Systems
FRG:协作研究:用于复杂物理系统仿真、学习和实验设计的变稳定神经网络
  • 批准号:
    2245147
  • 财政年份:
    2023
  • 资助金额:
    $ 67.7万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了