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

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

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.