TY - GEN

T1 - Approaching optimality for solving SDD linear systems

AU - Koutis, Ioannis

AU - Miller, Gary L.

AU - Peng, Richard

N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

PY - 2010

Y1 - 2010

N2 - 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. The algorithm runs in time Õ((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 Õ(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.

AB - 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. The algorithm runs in time Õ((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 Õ(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.

KW - Algorithms

KW - Combinatorial preconditioning

KW - Linear systems

KW - Spectral graph theory

UR - http://www.scopus.com/inward/record.url?scp=78751501372&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78751501372&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2010.29

DO - 10.1109/FOCS.2010.29

M3 - Conference contribution

AN - SCOPUS:78751501372

SN - 9780769542447

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 235

EP - 244

BT - Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010

T2 - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010

Y2 - 23 October 2010 through 26 October 2010

ER -