@inproceedings{81aa68f115b84171867ce985bf5eb35a,

title = "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 {\~O}(k log2 n), with probability 1 - p. The algorithm runs in time {\~O}((mlog n + n log2 n) log(1=p)): As a result, we obtain an algorithm that on input of an n x n symmetric diagonally dominant matrix A with m non-zero entries and a vector b, computes a vector x satisfying ||x - A+b||A < ε||A+b||A, in expected time {\~O}(m log2 n log(1/ε)): The solver is based on repeated applications of the incremental sparsifier that produces a chain of graphs which is then used as input to a recursive preconditioned Chebyshev iteration.",

keywords = "Algorithms, Combinatorial preconditioning, Linear systems, Spectral graph theory",

author = "Ioannis Koutis and Miller, {Gary L.} and Richard Peng",

year = "2010",

doi = "10.1109/FOCS.2010.29",

language = "English (US)",

isbn = "9780769542447",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "235--244",

booktitle = "Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010",

address = "United States",

note = "2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 ; Conference date: 23-10-2010 Through 26-10-2010",

}