Approaching Optimality For Solving SDD Linear Systems

Abstract—We present an algorithm that on input of an n-vertex m-edge weighted graph G and a value k, produces an incremental sparsifier Ĝ with n-1+m=k edges, such that the condition number of G with Ĝ is bounded above by Õ(k log2 n), with probability 1 - p.