Design of Fast Algorithms using Continuous Methods

使用连续方法设计快速算法

• 批准号: RGPIN-2018-06398
• 负责人: Sachdeva, Sushant
• 金额: $ 2.4万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=713146
• 关键词: Design; Fast; Algorithms; using; Continuous

In this proposal, we aim to develop fast algorithms for several classic graph problems and numerical linear algebra problems using methods from continuous optimization and random matrix analysis. The use of tools from continuous optimization has been a major success story in the design of fast algorithms over the past few years. Combining tools such as near-linear time solvers for linear systems in Laplacian matrices from the seminal work of Spielman and Teng with methods from optimization such as gradient descent and interior point methods, has led to the development of the current fastest algorithms for classic combinatorial problems such as maximum flow, graph partitioning, bipartite matching, sampling random spanning trees etc. Over the past year, my co-authors and I have built on tools from random matrix theory for better analyzing randomized processes on graphs, resulting in an algorithmic tool we refer to as randomized elimination [Kyng et al 16, Kyng-Sachdeva '16]. This has already led to a number of advances, including the simplest Laplacian solver [Kyng-Sachdeva '16], nearly-linear time solver for linear systems in block diagonally dominant (bDD) matrices [Kyng et al '16] (these systems arise when analyzing cryo-electron microscopy data), faster algorithms for sampling random spanning trees in graphs [Durfee et al '17a], and approximating determinants of Laplacians [Durfee et al '17b]. The key objective of this proposal is to develop these programs further and seek to design faster and improved algorithms for several fundamental problems. The first project under this proposal will be to develop randomized elimination based constructions for special trees. Specifically, we seek fast algorithms for low-stretch spanning trees, which are a fundamental component of several fast Laplacian solvers; and to incorporate random walk based ideas to design nearly-linear time algorithms for sampling random spanning trees. The second project under this proposal will be to develop faster and simpler algorithms for several fundamental flow problems on graphs, including maximum-flow, bipartite matching, and multi-commodity flow. These are classic problems in theoretical computer science, where decades-old running time barriers have been broken with the help of continuous methods. The third project under this proposal will be to build solvers for more classes of linear systems such as those arising from analyzing truss structures and RLC circuits. A particularly ambitious goal here is to design faster algorithms for solving systems of linear equations in all positive-semidefinite matrices, which would have immediate applications for basically all problems in numerical linear algebra.

在这个方案中，我们的目标是利用连续优化和随机矩阵分析的方法，为几个经典的图问题和数值线性代数问题开发快速算法。在过去的几年里，持续优化工具的使用在快速算法的设计方面取得了重大的成功。将Spielman和Teng的开创性工作中的拉普拉斯矩阵中的线性系统的近线性时间求解器等工具与最优化方法(如梯度下降法和内点法)相结合，导致了最大流、图划分、二部匹配、采样随机生成树等经典组合问题的当前最快算法的发展。 在过去的一年里，我和我的合著者利用随机矩阵理论的工具来更好地分析图形上的随机过程，产生了一种我们称为随机消除的算法工具[Kyng等人16，Kyng-Sachdeva‘16]。这已经带来了许多进展，包括最简单的拉普拉斯求解器[Kyng-Sachdeva‘16]，块对角占优(BDD)矩阵中线性系统的近线性时间求解器[Kyng等人’16](这些系统出现在分析冷冻电子显微镜数据时)，用于对图中的随机生成树进行采样的更快算法[Durfee等人‘17a]，以及近似拉普拉斯人的行列式[Durfee等人’17b]。 这项提议的关键目标是进一步开发这些程序，并寻求为几个基本问题设计更快和更好的算法。根据这项提议，第一个项目将是开发基于随机淘汰的特殊树木结构。具体地说，我们寻求低伸展生成树的快速算法，这是几个快速拉普拉斯求解器的基本组成部分；并结合基于随机游走的思想来设计用于采样随机生成树的近线性时间算法。 这项提议下的第二个项目将是开发更快、更简单的算法来解决图上的几个基本流问题，包括最大流、二部匹配和多商品流。这些都是理论计算机科学中的经典问题，在连续方法的帮助下，几十年的运行时间障碍已经被打破。 根据这项提议，第三个项目将是为更多类别的线性系统建立求解器，例如那些由分析桁架结构和RLC电路而产生的系统。这里一个特别雄心勃勃的目标是设计更快的算法来求解所有正半定矩阵中的线性方程组，这将直接应用于数值线性代数中的几乎所有问题。