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

AF:小型:用于解决线性方程拉普拉斯系统和稀疏最小二乘问题的快速高效随机算法

基本信息

  • 批准号:
    1016501
  • 负责人:
  • 金额:
    $ 32.27万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2010
  • 资助国家:
    美国
  • 起止时间:
    2010-08-01 至 2015-07-31
  • 项目状态:
    已结题

项目摘要

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.
在线性地球算法的背景下,随机化是一个令人兴奋且创新的想法。近年来,大量工作集中在可证明的回归问题的准确随机算法上,并特别强调了最小二乘的回归。由于其在科学计算和统计数据分析中的广泛适用性,因此对于此类问题的快速算法引起了人们的持续关注,其中出现了越来越大的输入矩阵。当(i)回归问题的约束矩阵是laplacian,或(ii)回归问题在(ii)回归问题不足或稀疏时,PI寻求理论和数值研究这些问题的准确和实际有用的随机算法。因此,PI试图解决Spielman,Teng和合作者最近的突破理论结果与其实际适用性之间的令人震惊的差距,以及缺乏处理稀疏输入矩阵的过度或不受限制回归问题的有效算法。为了弥合这一研究中的理论与应用之间的差距,需要进行许多新颖的理论结果,并将研究。拟议研究的实际实用性将使用科学应用中的数据矩阵进行数值评估。在数值分析和线性代数中,有效地求解大型线性方程系统可能是最基本的问题,主要是因为这种系统在科学计算应用中无处不在。拟议的工作旨在使Spielman,Teng和合作者在求解线性方程式系统方程的最新工作中的理论突破,并以Laplacian输入矩阵更接近实践。为此,将得出理论和数值结果。随后,该研究范式可以用作起点,以激发对更广泛的线性方程组的更广泛类别的研究工作。拟议工作影响的第二个方面与将要探讨的理论计算机科学与数值线性代数方法之间的重叠有关。随着随机化在线性代数的背景下变得越来越有用,PI期望该领域的下一代研究人员将需要在这两个领域进行良好的培训,这正是拟议的工作将为研究生提供的。最后,拟议工作的影响的第三个方面将通过研讨会,教程和迷你群岛在备受瞩目的相关会议中的讲习班,教程和迷你群岛的传播中出现。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

暂无数据

数据更新时间:2024-06-01

Petros Drineas其他文献

A randomized least squares solver for terabyte-sized dense overdetermined systems
  • DOI:
    10.1016/j.jocs.2016.09.007
    10.1016/j.jocs.2016.09.007
  • 发表时间:
    2019-09-01
    2019-09-01
  • 期刊:
  • 影响因子:
  • 作者:
    Chander Iyer;Haim Avron;Georgios Kollias;Yves Ineichen;Christopher Carothers;Petros Drineas
    Chander Iyer;Haim Avron;Georgios Kollias;Yves Ineichen;Christopher Carothers;Petros Drineas
  • 通讯作者:
    Petros Drineas
    Petros Drineas
共 1 条
  • 1
前往

Petros Drineas的其他基金

NSF-BSF: AF: Collaborative Research: Small: Randomized preconditioning of iterative processes: Theory and practice
NSF-BSF:AF:协作研究:小型:迭代过程的随机预处理:理论与实践
  • 批准号:
    2209509
    2209509
  • 财政年份:
    2022
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
Collaborative Research: Randomized Numerical Linear Algebra for Large Scale Inversion, Sparse Principal Component Analysis, and Applications
合作研究:大规模反演的随机数值线性代数、稀疏主成分分析及应用
  • 批准号:
    2152687
    2152687
  • 财政年份:
    2022
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
CCF-BSF: AF: Small: Collaborative Research: Practice-Friendly Theory and Algorithms for Linear Regression Problems
CCF-BSF:AF:小型:协作研究:线性回归问题的实用理论和算法
  • 批准号:
    1814041
    1814041
  • 财政年份:
    2018
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
FRG: Collaborative Research: Randomization as a Resource for Rapid Prototyping
FRG:协作研究:随机化作为快速原型制作的资源
  • 批准号:
    1760353
    1760353
  • 财政年份:
    2018
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
III: Small: Novel Statistical Data Analysis Approaches for Mining Human Genetics Datasets
III:小型:挖掘人类遗传学数据集的新颖统计数据分析方法
  • 批准号:
    1715202
    1715202
  • 财政年份:
    2017
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
BIGDATA: F: DKA: Collaborative Research: Randomized Numerical Linear Algebra (RandNLA) for multi-linear and non-linear data
BIGDATA:F:DKA:协作研究:用于多线性和非线性数据的随机数值线性代数 (RandNLA)
  • 批准号:
    1661760
    1661760
  • 财政年份:
    2016
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
III: Small: Fast and Efficient Algorithms for Matrix Decompositions and Applications to Human Genetics
III:小:快速高效的矩阵分解算法及其在人类遗传学中的应用
  • 批准号:
    1661756
    1661756
  • 财政年份:
    2016
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
BIGDATA: F: DKA: Collaborative Research: Randomized Numerical Linear Algebra (RandNLA) for multi-linear and non-linear data
BIGDATA:F:DKA:协作研究:用于多线性和非线性数据的随机数值线性代数 (RandNLA)
  • 批准号:
    1447283
    1447283
  • 财政年份:
    2014
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
III: Small: Fast and Efficient Algorithms for Matrix Decompositions and Applications to Human Genetics
III:小:快速高效的矩阵分解算法及其在人类遗传学中的应用
  • 批准号:
    1319280
    1319280
  • 财政年份:
    2013
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
Collaborative Research: Randomized Algorithms in Linear Algebra and Numerical Evaluations on Massive Datasets
合作研究:线性代数中的随机算法和海量数据集的数值评估
  • 批准号:
    1008983
    1008983
  • 财政年份:
    2010
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant

相似国自然基金

靶向Treg-FOXP3小分子抑制剂的筛选及其在肺癌免疫治疗中的作用和机制研究
  • 批准号:
    32370966
  • 批准年份:
    2023
  • 资助金额:
    50 万元
  • 项目类别:
    面上项目
化学小分子激活YAP诱导染色质可塑性促进心脏祖细胞重编程的表观遗传机制研究
  • 批准号:
    82304478
  • 批准年份:
    2023
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目
靶向小胶质细胞的仿生甘草酸纳米颗粒构建及作用机制研究:脓毒症相关性脑病的治疗新策略
  • 批准号:
    82302422
  • 批准年份:
    2023
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目
HMGB1/TLR4/Cathepsin B途径介导的小胶质细胞焦亡在新生大鼠缺氧缺血脑病中的作用与机制
  • 批准号:
    82371712
  • 批准年份:
    2023
  • 资助金额:
    49 万元
  • 项目类别:
    面上项目
小分子无半胱氨酸蛋白调控生防真菌杀虫活性的作用与机理
  • 批准号:
    32372613
  • 批准年份:
    2023
  • 资助金额:
    50 万元
  • 项目类别:
    面上项目

相似海外基金

AF : Small : Fast algorithms for LPs, TSP, and Connectivity
AF:小型:LP、TSP 和连接的快速算法
  • 批准号:
    2129816
    2129816
  • 财政年份:
    2022
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
AF:Small: Algorithms for Fast Simulation of Macromolecular Interaction Systems
AF:Small:大分子相互作用系统快速模拟算法
  • 批准号:
    1816314
    1816314
  • 财政年份:
    2018
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
AF: Small: Fast and accurate computational tools for large-scale evolutionary inference: a phylogenetic network approach
AF:小型:用于大规模进化推理的快速准确的计算工具:系统发育网络方法
  • 批准号:
    1714417
    1714417
  • 财政年份:
    2017
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
AF: Small: Collaborative Research: Mathematical Theory and Fast Algorithms for Rayleigh Quotient-type Optimizations
AF:小型:协作研究:瑞利商型优化的数学理论和快速算法
  • 批准号:
    1527091
    1527091
  • 财政年份:
    2015
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant
AF: Small: Collaborative Research: Mathematical Theory and Fast Algorithms for Rayleigh Quotient-type Optimizations
AF:小型:协作研究:瑞利商型优化的数学理论和快速算法
  • 批准号:
    1527104
    1527104
  • 财政年份:
    2015
  • 资助金额:
    $ 32.27万
    $ 32.27万
  • 项目类别:
    Standard Grant
    Standard Grant