Description
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
Fast algorithms for Laplacian linear systems have found broad applications across both the theory and practice of computer science, playing a foundational role in scientific computing, machine learning, random processes, image processing, network analysis, and computational biology, among others. More recently, they have emerged as a powerful tool in the design of graph algorithms, enabling researchers to break longstanding algorithmic barriers for a wide range of fundamental graph problems, including finding maximum single and multi-commodity flows, generating random spanning trees, sparsifying graphs, routing in distributed systems, and finding sparse cuts and balanced separators.
Designing fast solvers for these systems has been an active area of research, culminating with algorithms that solve them in nearly-linear time. These algorithms are quite complex, as they rely on an intricate recursive construction of preconditioners, whose development required multiple fundamental innovations in spectral and combinatorial graph theory, graph algorithms, and computational linear algebra.
In this talk, I will present a very simple combinatorial algorithm that solves Laplacian systems in nearly-linear time. It uses very little of the machinery that previously appeared to be necessary for a such an algorithm. It does not require recursive preconditioning, or even the Chebyshev Method or Conjugate Gradient. After constructing a "nice" spanning tree of a graph associated to the linear system, the entire algorithm consists of the repeated application of a simple (non-recursive) update rule, which it implements using a lightweight data structure. The algorithm is numerically stable and can be implemented without the increased bit-precision required by previous solvers. As such, the algorithm presented has the fastest known running time under the standard unit-cost RAM model.
While I plan to first introduce the algorithm in the context of computing electrical flow, I will also present an optimization interpretation based on coordinate descent. This will allow me to place our algorithm in context and to discuss its relation with previous solvers from a more principled standpoint.
This is joint work with Jonathan Kelner, Aaron Sidford and Zeyuan Zhu.
All scheduled dates:
Upcoming
No Upcoming activities yet