Computational Mathematics and Scientific Computing Seminar
A Simple, Combinatorial Algorithm for Solving Laplacian Systems in Nearly-Linear Time Without Recursive Preconditioning **CS Colloquium at 11:30am**
Speaker: Jonathan Kelner, MIT
Location: Warren Weaver Hall 1302
Date: Dec. 7, 2012, 11:30 a.m.
Synopsis:
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 flows and multicommodity flows, generating random spanning trees, sparsifying graphs, routing in distributed systems, and finding sparse cuts and balanced separators.
Finding fast solvers for these systems has been an active area of research, culminating in algorithms that solve them in nearly-linear time. These solvers are quite complex, and developing them required multiple fundamental innovations in spectral and combinatorial graph theory, graph algorithms, and computational linear algebra, which were used to construct and analyze an intricate recursively preconditioned iterative solver.
In this talk, I will give 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.
This is joint work with Aaron Sidford, Zeyuan Zhu, and Lorenzo Orecchia.