Richard Peng: Solving SDD Linear Systems in Nearly mlog1/2n Time

We present the current fastest algorithm for solving linear systems in symmetric diagonally dominant matrices. Solvers for these systems have been studied extensively due to their widespread applications in spectral graph theory, combinatorial optimization, computer vision, and machine learning.

Our result builds upon the random cycle update approach introduced in recent combinatorial solvers. We draw from the connection between electrical flows and voltage problems to analyze large batches of these updates. This leads to improved bounds for randomized preconditioners, which gives a faster solver when combined with improved tree embeddings. Both of these components may be of independent interest, and are available online.

Joint with Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Anup B. Rao, and Shen Chen Xu.