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 the past decade, a multitude of specialized solvers have been developed to tackle this problem using preconditioned iterative methods. Most of the recent work focuses on algorithms that efficiently find ultra-sparse 'equivalents' of graphs, where equivalence is defined through spectral condition numbers.
We present an algorithm that takes a graph G with n vertices, n-1+m edges and a value k, produces an incremental sparsifier with n-1 + m/k edges such that the condition number is bounded by klog^2n (ignoring loglog factors). This in turn gives an algorithm that solves SDD linear systems at a cost of roughly O(mlog^2n) per bit.
This talk aims to give an overview of the main parts of the solver. This is joint work in progress with Yiannis Koutis and Gary Miller.