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

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

• 批准号: EP/Y030990/1
• 负责人: Yuji Nakatsukasa
• 金额: $ 38.14万
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FY030990%2F1
• 关键词: DMS; EPSRC; Certifying; Accuracy; Randomized

Among the most exciting developments over the last two decades is the rapid advances in randomized numerical linear algebra (RNLA). This has caused a paradigmatic shift in the computational sciences, and has enabled matrix computations of unprecedented scale. In addition to speed, RNLA often provides solutions with exceptional accuracy and robustness. Success stories in RNLA include low-rank approximation, least-squares problems, and trace estimation. In addition, the field has witnessed recent progress in linear systems, eigenvalue problems, and tensor approximation. Despite these success stories, there is often a wide gap between theory and practice. To illustrate, consider the task of "subspace sketching", which is a key idea in RNLA. There is theory to support a claim that structured embeddings (aka "fast Johnson-Lindenstrauss transforms") based on FFTs provide a geometry preserving subspace embedding if O(dlogd) samples are used for a d-dimensional subspace. However, this is usually a pessimistic estimate, and O(d), say 2d samples, is known to suffice in most problems that arise in practice. A similar story holds for sparse sketches, for which beautiful theory is available, but in practice they often perform much better for a particular instance. The same is true even of deterministic algorithms, such as the column-pivoted QR factorization, specifically whether it gives a rank-revealing QR factorization. While the worst-case analysis suggests the algorithm can be exponentially unstable, decades of practical computation has shown that such examples are vanishingly rare. Clearly, in any of these problems, it would be highly useful to have a methodology to assess the correctness of a solution computed for the particular problem at hand.The objective of this proposal is to develop techniques for computing upper bounds on the error incurred by a particular instantiation of a randomized algorithm for solving a linear algebraic problem. Such bounds would allow users to combine the computational speed of randomized algorithms with the reliability of classical deterministic methods. It would also help users in safely balancing the needs of speed and precision. The approach we propose to follow here is close in spirit to the notion of "responsibly reckless" algorithms, recently coined by Jack Dongarra, the latest Turing Award laureate. The idea is to try a fast, but potentially unstable, algorithm, to obtain a potential solution. Then we assess the quality of the solution in a reliable fashion. Specifically, the purpose of this proposal is to develop fast and robust algorithms for this assessment, thereby certifying the correctness of the solution, or otherwise output a warning that the solution may be inaccurate. We will design algorithms, develop theory, and implement them in open-source software optimised for modern computing platforms.The historical development of finite element methods would help put our project in context. A priori analysis came first, and error bounds that were invaluable in guiding the design of finite element spaces were proven. However, these bounds were too pessimistic to usefully assess the error incurred in any particular instantiation, since the bound had to cover the most adversarial input. A posteriori analysis then emerged in response, as it applies specifically to a problem at hand and can, by drawing on quantities available post-computation, provide accurate estimates or bounds on the error. In this project we aim to achieve the same in the RNLA context.Specific directions we will pursue include: Subspace embedding, low-rank approximation, column-pivoted QR factorization, linear systems, eigenvalue problems and SVD, least-squares problems, and building Krylov subspaces efficiently.

在过去的二十年中，最令人兴奋的发展是随机数值线性代数（RNLA）的快速进步。这引起了计算科学的范式转移，并实现了前所未有的量表的矩阵计算。除了速度外，RNLA通常还提供具有出色精度和鲁棒性的解决方案。 RNLA中的成功案例包括低级近似，最小二乘问题和痕量估计。此外，该领域目睹了线性系统，特征值问题和张量近似的最新进展。尽管有这些成功的故事，理论和实践之间通常存在很大差异。为了说明，请考虑“子空间草图”的任务，这是RNLA中的关键思想。有理论可以支持一种主张，即基于FFT的结构化嵌入（又称“快速约翰逊·林斯特劳斯变换”），如果使用O（DLOGD）样品用于D-Dimensional子空间，则可以提供几何形状保留子空间的嵌入。但是，这通常是一个悲观的估计，而O（d）（例如2D样本）在实践中出现的大多数问题中都足够。一个类似的故事也适用于稀疏草图，为此可获得美丽的理论，但实际上它们在特定实例中的表现通常要好得多。即使是确定性算法，例如列旋转QR分解也是如此，特别是它是否给出了重新浏览QR分解。尽管最坏的案例分析表明该算法可能是指数不稳定的，但数十年的实际计算表明，此类示例消失了罕见。显然，在这些问题中的任何一个中，都有一种方法来评估针对当前特定问题计算的解决方案的正确性。该提案的目的是开发用于计算上界限的技术，该技术是通过通过求解线性代数问题的随机算法引起的误差的上限。这样的界限将允许用户将随机算法的计算速度与经典确定性方法的可靠性相结合。它还将帮助用户安全地平衡速度和精度的需求。我们建议在这里遵循的方法与最新的图灵奖获得者Jack Dongarra最近创造的“负责任的鲁ck”算法的概念紧密相关。这个想法是尝试快速但潜在的不稳定算法，以获得潜在的解决方案。然后，我们以可靠的方式评估解决方案的质量。具体而言，该提案的目的是为此评估开发快速，可靠的算法，从而证明解决方案的正确性，或者以其他方式发出警告，警告解决方案可能不准确。我们将在为现代计算平台优化的开源软件中设计算法，开发理论并实施它们。有限元方法的历史发展将有助于将我们的项目置于上下文中。先验分析是先进的，并且证明了指导有限元空间设计的错误界限。但是，这些界限太悲观了，无法在任何特定的实例化中有效评估误差，因为边界必须涵盖最对抗性的输入。然后出现后验分析，因为它专门适用于手头的问题，并且可以通过利用可用数量后的计算后，对误差提供准确的估计或界限。在这个项目中，我们旨在在RNLA上下文中实现相同的方向。我们将追求的特定方向包括：子空间嵌入，低级别近似，列列的QR QR分解，线性系统，线性问题，特征值问题和SVD，最小二乘问题，以及最小二乘问题以及构建Krylov的Krylov子空间。