Approaching optimality for solving sdd linear systems

Ioannis Koutis, Gary L. Miller, Richard Peng

Research output: Contribution to journalArticlepeer-review

48 Scopus citations


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 relative condition number of G with Ĝ is bounded above by Õ(k log2 n), with probability 1-p (we use the Õ() notation to hide a factor of at most (log log n)4). 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×n symmetric diagonally dominant matrix A with m nonzero entries and a vector b computes a vector x satisfying ||x-A+b||A <ε|A+b||A, in expected time Õ(mlog2 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 the recursive preconditioned Chebyshev iteration.

Original languageEnglish (US)
Pages (from-to)337-354
Number of pages18
JournalSIAM Journal on Computing
Issue number1
StatePublished - 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


  • Combinatorial preconditioning
  • Graph sparsification
  • Iterative solvers
  • Symmetric diagonally dominant linear systems


Dive into the research topics of 'Approaching optimality for solving sdd linear systems'. Together they form a unique fingerprint.

Cite this