Spectral graph sparsification in nearly-linear time leveraging efficient spectral perturbation analysis

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

27 Scopus citations

Abstract

Spectral graph sparsification aims to find an ultra-sparse subgraph whose Laplacian matrix can well approximate the original Laplacian matrix in terms of its eigenvalues and eigenvectors. The resultant sparsified subgraph can be efficiently leveraged as a proxy in a variety of numerical computation applications and graph-based algorithms. This paper introduces a practically efficient, nearly-linear time spectral graph sparsification algorithm that can immediately lead to the development of nearly-linear time symmetric diagonally-dominant (SDD) matrix solvers. Our spectral graph sparsification algorithm can efficiently build an ultra-sparse subgraph from a spanning tree subgraph by adding a few "spectrally-critical" off-tree edges back to the spanning tree, which is enabled by a novel spectral perturbation approach and allows to approximately preserve key spectral properties of the original graph Laplacian. Extensive experimental results confirm the nearly-linear runtime scalability of an SDD matrix solver for large-scale, real-world problems, such as VLSI, thermal and finite-element analysis problems, etc. For instance, a sparse SDD matrix with 40 million unknowns and 180 million nonzeros can be solved (1E-3 accuracy level) within two minutes using a single CPU core and about 6GB memory.

Original languageEnglish
Title of host publicationProceedings of the 53rd Annual Design Automation Conference, DAC 2016
ISBN (Electronic)9781450342360
DOIs
StatePublished - 5 Jun 2016
Event53rd Annual ACM IEEE Design Automation Conference, DAC 2016 - Austin, United States
Duration: 5 Jun 20169 Jun 2016

Publication series

NameProceedings - Design Automation Conference
Volume05-09-June-2016
ISSN (Print)0738-100X

Conference

Conference53rd Annual ACM IEEE Design Automation Conference, DAC 2016
Country/TerritoryUnited States
CityAustin
Period5/06/169/06/16

Keywords

  • Iterative methods
  • SDD matrix solver
  • Spectral graph sparsification

Fingerprint

Dive into the research topics of 'Spectral graph sparsification in nearly-linear time leveraging efficient spectral perturbation analysis'. Together they form a unique fingerprint.

Cite this