Approaching optimality for solving SDD linear systems

Ioannis Koutis, Gary L. Miller, Richard Peng

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

110 Scopus citations

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 Õ(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.

Original languageEnglish (US)
Title of host publicationProceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
PublisherIEEE Computer Society
Pages235-244
Number of pages10
ISBN (Print)9780769542447
DOIs
StatePublished - 2010
Externally publishedYes
Event2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 - Las Vegas, United States
Duration: Oct 23 2010Oct 26 2010

Publication series

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

Conference

Conference2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Country/TerritoryUnited States
CityLas Vegas
Period10/23/1010/26/10

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 'Approaching optimality for solving SDD linear systems'. Together they form a unique fingerprint.

Cite this