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

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

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.