Randomized Algorithms for Matrix Computations

矩阵计算的随机算法

• 批准号: 1929568
• 负责人: Per-Gunnar Martinsson
• 金额: $ 12.07万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1929568&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)开发随机方法加速计算模拟的现象，如静电，复合材料，生物化学过程，缓慢的流体流动，高斯过程中的2和3维等技术上，这将通过开发随机方法压缩所谓的“数据稀疏”或“秩结构”矩阵。