A Combinatorial Cut-Based Algorithm for Solving Laplacian Linear Systems.
Monika Rauch Henzinger, Billy Jin, David P. Williamson · arXiv (Cornell University) · 2020
Over the last two decades, a significant line of work in theoretical algorithms has been progress in solving linear systems of the form $\mathbf{L}\mathbf{p} = \mathbf{b}$, where $\mathbf{L}$ is the Laplacian matrix of a weighted graph with weights $w(i,j)>0$ on the edges. The solution $\mathbf{p}$ of the linear system can be interpreted as the potentials of an electrical flow. Kelner, Orrechia, Sidford, and Zhu \cite{KOSZ13} give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law. Here we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law. We prove that this dual algorithm also runs in a near-linear number of iterations. Each iteration requires updating all potentials on one side of a fundamental cut of a spanning tree by a fixed amount. If this update step can be performed in polylogarithmic time, we can also obtain a near-linear time algorithm to solve $\mathbf{L}\mathbf{p} = \mathbf{b}$. However, if we abstract this update step as a natural data structure problem, we show that we can use the data structure to solve a problem that has been conjectured to be difficult for dynamic algorithms, the online vector-matrix-vector problem \cite{HKNS15}. The conjecture implies that the data structure does not have an $O(n^{1-\epsilon})$ time algorithm for any $\epsilon > 0$. Thus our dual algorithm cannot be near-linear time algorithm for solving $\mathbf{L}\mathbf{p} = \mathbf{b}$ unless we are able to take advantage of the structure of the particular update steps that our algorithm uses.