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的QR QR核对QR）核心分解”是核心分解的科学计算中的核心构建块。初步数值实验表明，与最先进的软件包相比，速度接近数量级。 （2）求解涉及许多未知数和许多方程的线性系统。我们期望实现实践加速度，并且对开发具有比标准技术实现的立方复杂性更好的求解器的可能性谨慎乐观。 （3）开发用于加速现象的计算模拟的随机方法，例如电统计，复合材料，生化过程，缓慢的流体流动，在2和3维度中的高斯过程等。从技术上讲，这将通过开发所谓的“ data-Sparse”或“ cantralured”的构造构造的随机方法来实现。