A Deterministic Linear Program Solver in Current Matrix Multiplication Time
A Deterministic Linear Program Solver in Current Matrix Multiplication Time
复制标题
当前矩阵乘法时间的确定性线性规划求解器
DOI：
10.1137/1.9781611975994.16
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Jan van den Brand
中科院分区：
文献类型：
--
作者：
Jan van den Brand
求解线性规划的内点算法已经被广泛研究了很长一段时间[例如Karmarkar 1984; Lee，Sidford FOCS'14; Cohen，Lee，Song STOC'19]。对于形式为$\min_{Ax=B，x \ge 0} c^\top x$的具有$n$变量和$d$约束的线性规划，一般情况$d = \Omega（n）$最近由Cohen，Lee和Song [STOC'19]解决。他们的算法可以在$\tilde O（n^\omega \log（n/\delta））$预期时间内解决线性规划，其中$\delta$是相对精度。这基本上是最优的，因为所有已知的线性系统求解器需要高达$O（n^{\omega}）$时间来求解$Ax = B$。然而，对于确定性求解器的情况，最好的上限是Vaidya 30年前的$O（n^{2.5} \log（n/\delta））$界[FOCS'89]。在本文中，我们表明，人们也可以解决确定性的设置通过去随机化科恩等人。的$\tilde{O}（n^\omega \log（n/\delta））$时间算法。这允许严格的$\tilde{O}（n^\omega \log（n/\delta））$时间界限，而不是预期的时间界限，以及简化的分析，将他们的中心路径方法的证明长度减少了大约一半。去随机化这个算法也是Song博士论文中提出的一个开放性问题。
实现这一结果的主要工具是一种新的数据结构，它可以在次二次时间内保持线性系统的解。更准确地说，我们能够在对角矩阵U$和向量v$的乘法变化下，在次二次时间内保持$\sqrt {U}A^\top（AUA^\top）^{-1}A\sqrt{U}\：v$。这种类型的更改对于内点算法很常见。以前的算法[例如Vaidya STOC'89; Lee，Sidford FOCS'15; Cohen，Lee，Song STOC'19]需要$\Omega（n^2）$时间来完成这个任务。[...]
Interior point algorithms for solving linear programs have been studied extensively for a long time [e.g. Karmarkar 1984; Lee, Sidford FOCS'14; Cohen, Lee, Song STOC'19]. For linear programs of the form $\min_{Ax=b, x \ge 0} c^\top x$ with $n$ variables and $d$ constraints, the generic case $d = \Omega(n)$ has recently been settled by Cohen, Lee and Song [STOC'19]. Their algorithm can solve linear programs in $\tilde O(n^\omega \log(n/\delta))$ expected time, where $\delta$ is the relative accuracy. This is essentially optimal as all known linear system solvers require up to $O(n^{\omega})$ time for solving $Ax = b$. However, for the case of deterministic solvers, the best upper bound is Vaidya's 30 years old $O(n^{2.5} \log(n/\delta))$ bound [FOCS'89]. In this paper we show that one can also settle the deterministic setting by derandomizing Cohen et al.'s $\tilde{O}(n^\omega \log(n/\delta))$ time algorithm. This allows for a strict $\tilde{O}(n^\omega \log(n/\delta))$ time bound, instead of an expected one, and a simplified analysis, reducing the length of their proof of their central path method by roughly half. Derandomizing this algorithm was also an open question asked in Song's PhD Thesis.
The main tool to achieve our result is a new data-structure that can maintain the solution to a linear system in subquadratic time. More accurately we are able to maintain $\sqrt{U}A^\top(AUA^\top)^{-1}A\sqrt{U}\:v$ in subquadratic time under $\ell_2$ multiplicative changes to the diagonal matrix $U$ and the vector $v$. This type of change is common for interior point algorithms. Previous algorithms [e.g. Vaidya STOC'89; Lee, Sidford FOCS'15; Cohen, Lee, Song STOC'19] required $\Omega(n^2)$ time for this task. [...]
DOI：
10.4230/lipics.itcs.2018.25
发表时间：
2018
期刊：
9th Innovations in Theoretical Computer Science Conference (ITCS 2018
影响因子：
--
作者：
Alman, J.;Vassilevska Williams, V.
通讯作者：
Vassilevska Williams, V.