Solving Symmetric Diagonally Dominant Linear Systems in O(m log n) expected time
Feb 23, 2011
ABSTRACT: Solving linear systems of the form Ax=b is a classical problem that has been well-studied. The problem where A is symmetric diagonally dominant (SDD) occurs ubiquitously in combinatorial optimization, computer vision, computer graphics and machine learning.

In this talk I will present an algorithm for solving SDD linear systems that's faster than our previous result by a factor of logn. If the number of non-zeros in a n-by-n matrix is m and the desired error is epsilon, the algorithm runs in O(m log n log(1/ epsilon)) expected time. The speedup comes from improving the construction of the preconditioner chain in a global manner, as well as reducing the running time of finding low stretch spanning trees.

This is joint work in progress with Yiannis Koutis and Gary Miller.