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

Ioannis Koutis, Gary L. Miller, Richard Peng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

119 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
Pages590-598
Number of pages9
DOIs
StatePublished - 2011
Externally publishedYes
Event2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 - Palm Springs, CA, United States
Duration: Oct 22 2011Oct 25 2011

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
CountryUnited States
CityPalm Springs, CA
Period10/22/1110/25/11

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • algorithms
  • combinatorial preconditioning
  • linear systems
  • spectral graph theory

Fingerprint Dive into the research topics of 'A nearly-m log n time solver for SDD linear systems'. Together they form a unique fingerprint.

Cite this