EAGER: Numerical Accuracy of Randomized Algorithms for Matrix Multiplication and Least Squares

EAGER：矩阵乘法和最小二乘随机算法的数值精度

• 批准号: 1145383
• 负责人: Ilse C.F. Ipsen
• 金额: $ 8.5万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2014-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1145383&HistoricalAwards=false
• 关键词: EAGER; Numerical; Accuracy; Randomized; Algorithms

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字节有望在每日中流式传输，并且诸如罕见事件检测之类的任务必须使人们必须充分了解数值准确性和鲁棒性。