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 建议为矩阵乘法和最小二乘问题的随机算法开发数值扰动和稳定性理论。 这需要发明新的方法和概念来捕获随机算法的数值行为。 在这种情况下，“数值稳定性”的含义根本不清楚，更不用说如何定义它了。如何区分随机化引起的变异性和有限精度引起的变异性？ 故障概率、概率选择和采样量等参数应该在哪里考虑？ 回答这些问题的建议方法包括矩阵扰动分析、概率论和矩阵流形方法。 将进行广泛的数值实验来证实分析。随机算法的动机是需要流式处理对于传统确定性算法来说太大的海量数据集。 随机算法已成功应用于模式识别、社交网络分析、群体遗传学、电路测试和文本分类等应用。 所提出的研究将有助于确定随机算法适合哪些应用领域，并且还将产生参数选择的实际界限和建议，以实现用户指定的精度。 拟议的研究具有高度相关性，因为随机算法对于高能物理和天文学等应用中的百亿亿级计算是不可或缺的，在这些应用中，预计每天都会有千万亿字节的数据流，而罕见事件检测等任务使得必须有一个良好的理解数值准确性和鲁棒性。