TY - GEN

T1 - A nearly-m log n time solver for SDD linear systems

AU - Koutis, Ioannis

AU - Miller, Gary L.

AU - Peng, Richard

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

PY - 2011

Y1 - 2011

N2 - We present an improved algorithm for solving symmetrically diagonally dominant linear systems. On input of an n x n symmetric diagonally dominant matrix A with m non-zero entries and a vector b such that Ax̄ = b for some (unknown) vector x̄, our algorithm computes a vector x such that ∥x-x̄∥ A<ε∥x̄∥ A in time. Õ (m log n log (1/ε)). The solver utilizes in a standard way a 'preconditioning' chain of progressively sparser graphs. To claim the faster running time we make a two-fold improvement in the algorithm for constructing the chain. The new chain exploits previously unknown properties of the graph sparsification algorithm given in [Koutis,Miller,Peng, FOCS 2010], allowing for stronger preconditioning properties.We also present an algorithm of independent interest that constructs nearly-tight low-stretch spanning trees in time Õ(mlog n), a factor of O (log n) faster than the algorithm in [Abraham,Bartal,Neiman, FOCS 2008]. This speedup directly reflects on the construction time of the preconditioning chain.

AB - We present an improved algorithm for solving symmetrically diagonally dominant linear systems. On input of an n x n symmetric diagonally dominant matrix A with m non-zero entries and a vector b such that Ax̄ = b for some (unknown) vector x̄, our algorithm computes a vector x such that ∥x-x̄∥ A<ε∥x̄∥ A in time. Õ (m log n log (1/ε)). The solver utilizes in a standard way a 'preconditioning' chain of progressively sparser graphs. To claim the faster running time we make a two-fold improvement in the algorithm for constructing the chain. The new chain exploits previously unknown properties of the graph sparsification algorithm given in [Koutis,Miller,Peng, FOCS 2010], allowing for stronger preconditioning properties.We also present an algorithm of independent interest that constructs nearly-tight low-stretch spanning trees in time Õ(mlog n), a factor of O (log n) faster than the algorithm in [Abraham,Bartal,Neiman, FOCS 2008]. This speedup directly reflects on the construction time of the preconditioning chain.

KW - algorithms

KW - combinatorial preconditioning

KW - linear systems

KW - spectral graph theory

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

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

U2 - 10.1109/FOCS.2011.85

DO - 10.1109/FOCS.2011.85

M3 - Conference contribution

AN - SCOPUS:84863329239

SN - 9780769545714

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

SP - 590

EP - 598

BT - Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

T2 - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

Y2 - 22 October 2011 through 25 October 2011

ER -