EAGER: Numerical Accuracy of Randomized Algorithms for Matrix Multiplication and Least Squares
EAGER:矩阵乘法和最小二乘随机算法的数值精度
基本信息
- 批准号:1145383
- 负责人:
- 金额:$ 8.5万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2011
- 资助国家:美国
- 起止时间:2011-09-01 至 2014-11-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
The PI proposes to investigate the numerical accuracy and robustness of randomized algorithms for matrix multiplication and overdetermined least squares problems. Existing analyses of randomized algorithms are mostly concerned with asymptotic time and space complexity in exact arithmetic, and very little is known about their numerical behavior in floating point arithmetic. The PI proposes to develop a numerical perturbation and stability theory for randomized algorithms for matrix multiplication and least squares problems. This entails the invention of new approaches and concepts to capture the numerical behavior of randomized algorithms. It is not at all clear what ``numerical stability'' means in this context, let alone how it should be defined. How does one distinguish variability caused by randomization from variability caused by finite precision? Where should parameters like failure probability, choice of probabilities, and amount of sampling be accounted for? Proposed approaches for answering these questions will include matrix perturbation analysis, probability theory, and methods on matrix manifolds. Extensive numerical experiments will be performed to corroborate the analyses.The motivation for randomized algorithms is the need for streaming massive data sets that are too large for traditional deterministic algorithms. Randomized algorithms have been implemented successfully for applications such as pattern recognition, social network analysis, population genetics, circuit testing, and text classification. The proposed research will help to determine for which application domains a randomized algorithm is suitable, and it will also result in practical bounds and recommendations for parameter choices to achieve a user-specified accuracy. The proposed research is highly relevant because randomized algorithms will be indispensable for exascale computing, in applications like high energy physics and astronomy, where peta bytes of data are expected to stream in daily and tasks like rare event detection make it imperative to have a good understanding of numerical accuracy and robustness.
PI建议研究矩阵乘法和超定最小二乘问题的随机算法的数值精度和鲁棒性。现有的随机算法的分析主要关注精确算术中的渐近时间和空间复杂度,而对浮点算术中的数值行为知之甚少。 PI提出为矩阵乘法和最小二乘问题的随机算法开发数值扰动和稳定性理论。 这需要发明新的方法和概念来捕捉随机算法的数值行为。 在这种情况下,根本不清楚“数量稳定”是什么意思,更不用说应该如何定义了。如何区分随机化引起的变异性和有限精度引起的变异性? 应该在哪里考虑失效概率、概率的选择和抽样量等参数? 回答这些问题的方法包括矩阵扰动分析、概率论和矩阵流形方法。 大量的数值实验将进行证实的分析。随机算法的动机是需要流的海量数据集,太大的传统的确定性算法。 随机算法已经成功地应用于模式识别、社会网络分析、群体遗传学、电路测试和文本分类等应用。 建议的研究将有助于确定哪些应用领域的随机算法是合适的,它也将导致实际的界限和建议的参数选择,以达到用户指定的精度。 拟议的研究是高度相关的,因为随机算法将是不可或缺的exascale计算,在高能物理和天文学等应用中,预计每天都会有peta字节的数据流,而稀有事件检测等任务使得必须很好地理解数值精度和鲁棒性。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
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 }}
Ilse C.F. Ipsen其他文献
Ilse C.F. Ipsen的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Ilse C.F. Ipsen', 18)}}的其他基金
NSF-BSF: AF: Collaborative Research: Small: Randomized preconditioning of iterative processes: Theory and practice
NSF-BSF:AF:协作研究:小型:迭代过程的随机预处理:理论与实践
- 批准号:
2209510 - 财政年份:2022
- 资助金额:
$ 8.5万 - 项目类别:
Standard Grant
FRG: Collaborative Research: Randomization as a Resource for Rapid Prototyping
FRG:协作研究:随机化作为快速原型制作的资源
- 批准号:
1760374 - 财政年份:2018
- 资助金额:
$ 8.5万 - 项目类别:
Standard Grant
2015 Gene Golub SIAM Summer School (G2S3): Randomization in Numerical Linear Algebra (RandNLA)
2015 Gene Golub SIAM 暑期学校 (G2S3):数值线性代数随机化 (RandNLA)
- 批准号:
1522231 - 财政年份:2015
- 资助金额:
$ 8.5万 - 项目类别:
Standard Grant
Early-Career and Student Support for the XIX Householder Symposium, June 8-13, 2014
第十九届住户研讨会的早期职业和学生支持,2014 年 6 月 8 日至 13 日
- 批准号:
1415152 - 财政年份:2014
- 资助金额:
$ 8.5万 - 项目类别:
Standard Grant
Early Career and Student Support for the XVIII Householder Symposium
第十八届住户研讨会的早期职业和学生支持
- 批准号:
1125906 - 财政年份:2011
- 资助金额:
$ 8.5万 - 项目类别:
Standard Grant
Scientific Computing Research Environments for the Mathematical Sciences (SCREMS)
数学科学的科学计算研究环境 (SCREMS)
- 批准号:
0209695 - 财政年份:2002
- 资助金额:
$ 8.5万 - 项目类别:
Standard Grant
Mathematical Sciences: Workshop on Krylov Subspace Methods and Applications
数学科学:克雷洛夫子空间方法与应用研讨会
- 批准号:
9415578 - 财政年份:1994
- 资助金额:
$ 8.5万 - 项目类别:
Standard Grant
Relative Perturbation Techniques for Eigenvalue and Singular Value Decompositions
特征值和奇异值分解的相对扰动技术
- 批准号:
9400921 - 财政年份:1994
- 资助金额:
$ 8.5万 - 项目类别:
Continuing Grant
Numerical Control Structures for the Computation of Large Eigenvalue and Singular Value Problems
用于计算大特征值和奇异值问题的数控结构
- 批准号:
9496115 - 财政年份:1993
- 资助金额:
$ 8.5万 - 项目类别:
Continuing Grant
相似海外基金
DMS-EPSRC: Certifying Accuracy of Randomized Algorithms in Numerical Linear Algebra
DMS-EPSRC:验证数值线性代数中随机算法的准确性
- 批准号:
EP/Y030990/1 - 财政年份:2024
- 资助金额:
$ 8.5万 - 项目类别:
Research Grant
High-Accuracy Numerical Simulation of Pathological Vocal Fold Vibrations Considering Individual Differences
考虑个体差异的病理性声带振动的高精度数值模拟
- 批准号:
23K17195 - 财政年份:2023
- 资助金额:
$ 8.5万 - 项目类别:
Grant-in-Aid for Early-Career Scientists
DMS-EPSRC:Certifying Accuracy of Randomized Algorithms in Numerical Linear Algebra
DMS-EPSRC:验证数值线性代数中随机算法的准确性
- 批准号:
2313434 - 财政年份:2023
- 资助金额:
$ 8.5万 - 项目类别:
Standard Grant
MPS-Ascend: Improved Accuracy and Robustness for Numerical Partial Differential Equations and Nonlinear Optimization
MPS-Ascend:提高数值偏微分方程和非线性优化的准确性和鲁棒性
- 批准号:
2213322 - 财政年份:2022
- 资助金额:
$ 8.5万 - 项目类别:
Fellowship Award
Numerical analysis and high-accuracy algorithms for scattering, spectra, and interdisciplinary applications.
适用于散射、光谱和跨学科应用的数值分析和高精度算法。
- 批准号:
RGPIN-2019-06886 - 财政年份:2022
- 资助金额:
$ 8.5万 - 项目类别:
Discovery Grants Program - Individual
The geo-anthrosphere from a perspective of dust: broad-area estimation of dead vegetation amount to improve the accuracy of numerical dust model
尘埃视角下的地球人类圈:大面积估算死亡植被数量以提高数值尘埃模型的准确性
- 批准号:
22H01310 - 财政年份:2022
- 资助金额:
$ 8.5万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
Numerical analysis and high-accuracy algorithms for scattering, spectra, and interdisciplinary applications.
适用于散射、光谱和跨学科应用的数值分析和高精度算法。
- 批准号:
RGPIN-2019-06886 - 财政年份:2021
- 资助金额:
$ 8.5万 - 项目类别:
Discovery Grants Program - Individual
Numerical analysis and high-accuracy algorithms for scattering, spectra, and interdisciplinary applications.
适用于散射、光谱和跨学科应用的数值分析和高精度算法。
- 批准号:
RGPIN-2019-06886 - 财政年份:2020
- 资助金额:
$ 8.5万 - 项目类别:
Discovery Grants Program - Individual
Mechanism of two phase thermo-fluid behavior in porous media and its high accuracy numerical analysis based on multi-scale effect
多孔介质中两相热流体行为机理及其基于多尺度效应的高精度数值分析
- 批准号:
19KK0109 - 财政年份:2019
- 资助金额:
$ 8.5万 - 项目类别:
Fund for the Promotion of Joint International Research (Fostering Joint International Research (B))
Numerical analysis and high-accuracy algorithms for scattering, spectra, and interdisciplinary applications.
适用于散射、光谱和跨学科应用的数值分析和高精度算法。
- 批准号:
RGPIN-2019-06886 - 财政年份:2019
- 资助金额:
$ 8.5万 - 项目类别:
Discovery Grants Program - Individual