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