Randomized Algorithms for Matrix Computations

矩阵计算的随机算法

• 批准号: 1620472
• 负责人: Per-Gunnar Martinsson
• 金额: $ 25万
• 依托单位: University of Colorado at Boulder
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2019-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1620472&HistoricalAwards=false
• 关键词: Randomized; Algorithms; Matrix; Computations

This project will develop mathematical techniques for accelerating computational tasks such as simulating electromagnetic scattering, medical imaging, extracting useful information from large datasets, machine learning, and many others. In all these computations, the step that tends to be the most time-consuming, and which therefore limits how large problems can be solved, concerns the manipulation of large square or rectangular arrays of numbers, called "matrices". Many of the matrices that arise in practical applications have redundancies, and can be compressed to enable them to be stored using less space. Using the compressed format, computations involving the matrix can also be greatly accelerated. The problems that will be addressed are deterministic in nature, but the algorithms that will be developed are probabilistic. It turns out that by exploiting certain mathematical properties of large ensembles of independent random numbers, one can build algorithms for compressing matrices that are much faster than traditional deterministic techniques. The new randomized algorithms can in theory fail, but the likelihood of failure can be shown to be lower than 1 time out of 10,000,000,000 runs in typical applications. Randomized algorithms of this type have recently attracted much interest due to the fact that they perform particularly well on emerging computing platforms such as mobile computing (where conserving energy is the key priority), computing using graphical processor units (where the vast numbers of computational cores create challenges), and distributed memory parallel computers. The methods also perform very well when applied to massively large datasets that must be stored on hard drives, or on large server farms. The project will train one doctoral student, and will lead to the release of a publicly available software package that implements the methods that will be developed. From a technical point of view, the objective of the project is to develop efficient algorithms for factorizing matrices and for solving large linear systems of algebraic equations. The algorithms will be based on randomized sampling, and will exploit remarkable mathematical properties of random matrices and random orthogonal projections. Such randomized algorithms require less communication than traditional methods, which makes them particularly attractive for modern applications involving multicore processors, distributed computing, out-of-core computing, etc. Specifically, the project will address the following problems: (1) Computing full matrix factorizations (e.g. the so called "column pivoted QR factorization") which are core building blocks in scientific computing. Preliminary numerical experiments demonstrate speed-ups of close to an order of magnitude compared to state-of-the-art software packages. (2) Solving linear systems involving many unknowns and many equations. We expect to achieve substantial practical acceleration, and are cautiously optimistic about the possibility to develop solvers with substantially better asymptotic complexity than the cubic complexity achieved by standard techniques. (3) Developing randomized methods for accelerating computational simulations of phenomena such as electro-statics, composite materials, biochemical processes, slow fluid flows, Gaussian processes in 2 and 3 dimensions, etc. Technically, this will be achieved by developing randomized methods for compressing so called "data-sparse" or "rank-structured" matrices.

该项目将开发数学技术来加速计算任务，例如模拟电磁散射、医学成像、从大型数据集中提取有用信息、机器学习等。在所有这些计算中，往往是最耗时的步骤，因此限制了可以解决的问题的大小，涉及对大的正方形或矩形数字数组（称为“矩阵”）的操作。实际应用中出现的许多矩阵都具有冗余，可以进行压缩以使用更少的空间来存储它们。使用压缩格式，涉及矩阵的计算也可以大大加速。将要解决的问题本质上是确定性的，但将开发的算法是概率性的。事实证明，通过利用独立随机数的大型集合的某些数学特性，我们可以构建比传统确定性技术快得多的矩阵压缩算法。新的随机算法理论上可能会失败，但在典型应用中，失败的可能性低于 10,000,000,000 次运行中的 1 次。这种类型的随机算法最近引起了人们的极大兴趣，因为它们在新兴计算平台上表现得特别好，例如移动计算（其中节能是关键优先事项）、使用图形处理器单元的计算（其中大量计算核心）创造挑战）和分布式内存并行计算机。当应用于必须存储在硬盘驱动器或大型服务器场上的海量数据集时，这些方法也表现得非常好。该项目将培训一名博士生，并将发布一个公开可用的软件包，该软件包实施将要开发的方法。从技术角度来看，该项目的目标是开发有效的算法来分解矩阵和求解大型线性代数方程组。该算法将基于随机采样，并将利用随机矩阵和随机正交投影的显着数学特性。这种随机算法比传统方法需要更少的通信，这使得它们对于涉及多核处理器、分布式计算、核外计算等的现代应用特别有吸引力。具体来说，该项目将解决以下问题：（1）计算全矩阵因式分解（例如所谓的“列枢转 QR 因式分解”）是科学计算中的核心构建块。初步数值实验表明，与最先进的软件包相比，速度提高了接近一个数量级。 (2)求解涉及许多未知数和许多方程的线性系统。我们期望实现实质性的实际加速，并对开发渐近复杂度远高于标准技术所实现的三次复杂度的求解器的可能性持谨慎乐观态度。 (3) 开发随机方法来加速静电、复合材料、生化过程、慢速流体流动、二维和三维高斯过程等现象的计算模拟。技术上，这将通过开发随机压缩方法来实现所谓的“数据稀疏”或“等级结构”矩阵。