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.

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