Solving SDD linear systems in nearly m log 1/2 n time
Michael B. Cohen, Rasmus Kyng, Gary Lee Miller, Jakub Pachocki, Richard Peng, Anup B. Rao, Shen Xu · 2014
We show an algorithm for solving symmetric diagonally dominant (SDD) linear systems with m non-zero entries to a relative error of ε in O(m log1/2 n logc n log(1/ε)) time. Our approach follows the recursive preconditioning framework, which aims to reduce graphs to trees using iterative methods. We improve two key components of this framework: random sampling and tree embeddings. Both of these components are used in a variety of other algorithms, and our approach also extends to the dual problem of computing electrical flows.