论文标题
用于求解拉普拉斯线性系统的组合切割算法
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems
论文作者
论文摘要
在过去的二十年中，理论算法中的重要作品在求解线性系统方面取得了进展，其系数矩阵是加权图的拉普拉斯矩阵。线性系统的解可以解释为电流的电势。 Kelner，Orrechia，Sidford和Zhu（STOC 2013）提供了一种组合，接近线性的时间算法，以维护Kirchoff现行法律，并通过更新周围的自行车（周期切换）来逐渐实施Kirchoff的潜在法律。在本文中，我们考虑了维持Kirchoff潜在法律的算法的双重版本，并通过切断切换来逐渐执行Kirchoff现行法律：每次迭代更新一侧的一侧的所有潜在剪裁的一侧剪裁基本剪裁的一侧都相同数量。我们证明，该双重算法也以接近线性的迭代次数运行。 但是，我们表明，如果我们抽象切换作为自然数据结构问题，则可以将此问题降低到在线矢量 - 马trix-vector问题上，这已经猜想了Henzinger，Krinninger，Nanongkai和Saranurak难以动态算法的动态算法（Stoc 2015）。猜想意味着，切割算法的直接实现基本上是迭代中的线性时间。为了避免下限，我们批量更新步骤，并同时执行它们，而不是顺序执行。批处理的适当选择会导致$ \ tilde {o}（m^{1.5}）$用于求解拉普拉斯系统的时间切割算法。此外，如果我们泄露图形并将我们的算法递归地在批处理和稀疏中隐含的laplacian系统上调用，则可以将运行时间缩短为$ O（M^{1+ε}）$的任何$ε> 0 $。因此，双重刺耳算法可以（几乎）与原始周期循环相同的运行时间（几乎）实现（几乎）运行时间。
Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems whose coefficient matrix is the Laplacian matrix of a weighted graph. The solution of the linear system can be interpreted as the potentials of an electrical flow. Kelner, Orrechia, Sidford, and Zhu (STOC 2013) give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a near-linear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vector-matrix-vector problem, which has been conjectured to be difficult for dynamic algorithms by Henzinger, Krinninger, Nanongkai, and Saranurak (STOC 2015). The conjecture implies that a straightforward implementation of the cut-toggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an $\tilde{O}(m^{1.5})$ time cut-toggling algorithm for solving Laplacian systems. Furthermore, if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, the running time can be reduced to $O(m^{1+ε})$ for any $ε> 0$. Thus, the dual cut-toggling algorithm can achieve (almost) the same running time as its primal cycle-toggling counterpart.
