Improved spectral sparsification and numerical algorithms for SDD matrices

Ioannis Koutis, Alex Levin, Richard Peng

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

31 Scopus citations

Abstract

We present three spectral sparsification algorithms that, on input a graph G with n vertices and m edges, return a graph H with n vertices and O(n log n/e2) edges that provides a strong approximation of G. Namely, for all vectors x and any ε > 0, we have (1 - ε)xT L Gx ≤ x LHx ≤ (1 + ε)xT L Gx, where LG and LH are the Laplacians of the two graphs. The first algorithm is a simple modification of the fastest known algorithm and runs in Õ(mlog2n) time, an O(log n) factor faster than before. The second algorithm runs in Õ(m log n) time and generates a sparsifier with Õ(n log3n) edges. The third algorithm applies to graphs where m > n log5n and runs in Õ(m log m/nlog5 n n) time. In the range where m > n1+r for some constant r this becomes Õ(m). The improved sparsification algorithms are employed to accelerate linear system solvers and algorithms for computing fundamental eigenvectors of dense SDD matrices.

Original languageEnglish (US)
Title of host publication29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012
Pages266-277
Number of pages12
DOIs
StatePublished - 2012
Externally publishedYes
Event29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012 - Paris, France
Duration: Feb 29 2012Mar 3 2012

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume14
ISSN (Print)1868-8969

Other

Other29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012
Country/TerritoryFrance
CityParis
Period2/29/123/3/12

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Linear system solving
  • Spectral sparsification

Fingerprint

Dive into the research topics of 'Improved spectral sparsification and numerical algorithms for SDD matrices'. Together they form a unique fingerprint.

Cite this