@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",
}