file.pdf (213.87 kB)
Download file

Approaching Optimality For Solving SDD Linear Systems

Download (213.87 kB)
journal contribution
posted on 01.01.2003, 00:00 by Ioannis Koutis, Gary Miller, Richard Peng
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.