DMS-EPSRC:Certifying Accuracy of Randomized Algorithms in Numerical Linear Algebra

DMS-EPSRC：验证数值线性代数中随机算法的准确性

• 批准号: 2313434
• 负责人: Per-Gunnar Martinsson
• 金额: $ 32.27万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-09-01 至 2026-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2313434&HistoricalAwards=false
• 关键词: DMS; EPSRC; Certifying; Accuracy; Randomized

The project will improve the accuracy and robustness of randomized algorithms for solving some of the most fundamental tasks in computational science. Specifically, the project will focus on algorithms for solving linear algebraic equations involving large arrays of numbers known as matrices, or large connected systems of linear equations, using Numerical Linear Algebra (NLA) techniques. Such equations form a core part of many computations performed on laptops, smartphones, tablets, and supercomputers. With the rise of data science and machine learning leading to massive datasets to process, the need for efficient and reliable methodologies for solving such equations is growing. Within the field of NLA, a key innovation in the past couple of decades has been the development of a new set of algorithms that harness the mathematical properties of extensive collections of random numbers to build new randomized algorithms that outperform existing deterministic ones. This project will develop techniques for certifying the accuracy of an answer computed using a randomized algorithm. The project will further develop algorithms that combine the speed of randomized methods with the robustness of classical algorithms. The project will provide training opportunities for students and early career researchers in STEM.The project aims to develop techniques for assessing the accuracy of a particular instantiation of a randomized algorithm for solving a linear algebraic problem. The project will represent a continuation of a more significant research effort on randomized algorithms in linear algebra that has already impacted the computational sciences and enabled massively large-scale matrix computations. This project will develop a-posteriori error estimates and bounds, which are in contrast to existing apriori estimates and bounds. The investigators will construct bounds that utilize only information available to the user at the time of the computation. The new estimates will be deployed to standard problems such as low-rank approximation, solving linear systems, and approximating data-sparse matrices. The project will develop algorithms that combine the remarkable speed and versatility of randomized algorithms, with the reliability and robustness of existing deterministic methods.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.

该项目将提高随机算法的准确性和鲁棒性，以解决计算科学中一些最基本的任务。具体而言，该项目将专注于使用数值线性代数（NLA）技术的涉及大量数字的线性代数方程或线性方程的大型连接系统的算法。这种方程式构成了在笔记本电脑，智能手机，平板电脑和超级计算机上执行的许多计算的核心部分。随着数据科学和机器学习的兴起，导致大规模数据集进行处理，对解决此类方程的有效和可靠方法的需求正在增长。在NLA领域内，过去几十年来的关键创新是开发了一组新的算法，该算法利用了广泛的随机数集的数学属性，以构建优于现有确定性的新随机算法。该项目将开发技术，以证明使用随机算法计算的答案的准确性。该项目将进一步开发算法，将随机方法的速度与经典算法的鲁棒性结合起来。该项目将为STEM的学生和早期职业研究人员提供培训机会。该项目旨在开发用于评估随机算法的特定实例化的技术，以解决线性代数问题。该项目将代表对已经影响计算科学并实现大规模大规模矩阵计算的线性代数中随机算法进行更重要的研究工作。该项目将开发A-tosteriori误差估计和界限，与现有的APRIORI估计和界限相反。调查人员将构建仅利用用户在计算时可用的信息的界限。新的估计值将部署到标准问题，例如低级别近似值，求解线性系统和近似数据矩阵矩阵。该项目将开发算法，这些算法将随机算法的显着速度和多功能性与现有确定性方法的可靠性和鲁棒性结合在一起。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的审查标准通过评估来获得支持的。