Fall 2013

An Algebraic View of the New Randomized Kaczmarz Linear Solver

Wednesday, October 23rd, 2013 10:30 am11:00 am

Add to Calendar

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", 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.