Simple parallel and distributed algorithms for spectral graph sparsification

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

19 Scopus citations

Abstract

We describe a simple algorithm for spectral graph sparsification, based on iterative computations of weighted spanners and uniform sampling. Leveraging the algorithms of Baswana and Sen for computing spanners, we obtain the first distributed spectral sparsification algorithm. We also obtain a parallel algorithm with improved work and time guarantees. Combining this algorithm with the parallel framework of Peng and Spielman for solving symmetric diagonally dominant linear systems, we get a parallel solver which is much closer to being practical and significantly more efficient in terms of the total work.

Original languageEnglish (US)
Title of host publicationSPAA 2014 - Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages61-66
Number of pages6
ISBN (Print)9781450328210
DOIs
StatePublished - 2014
Externally publishedYes
Event26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2014 - Prague, Czech Republic
Duration: Jun 23 2014Jun 25 2014

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Other

Other26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2014
Country/TerritoryCzech Republic
CityPrague
Period6/23/146/25/14

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Keywords

  • Distributed algorithms
  • Parallel algorithms
  • SDD linear systems
  • Spectral sparsification

Fingerprint

Dive into the research topics of 'Simple parallel and distributed algorithms for spectral graph sparsification'. Together they form a unique fingerprint.

Cite this