Abstract
Kelner, Orecchia, Sidford, and Zhu recently introduced a novel almost-linear-time solver for Laplacian linear systems ("A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time", http://arxiv.org/abs/1301.6628). Their exposition of the algorithm is based on electrical flows. In the talk, I will present an algebraic view of the algorithm. This viewpoint clarifies the relationship between the new algorithm and older combinatorial Laplacian solvers and between the new algorithm and the Kaczmarz iterative solver. I will also explain the challenges that need to be addressed before the algorithm can be used on parallel machines to solve large-scale problems.