Design of Fast Algorithms using Continuous Methods

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