Design of Fast Algorithms using Continuous Methods

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

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.