Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs

Guy E. Blelloch, Anupam Gupta, Ioannis Koutis, Gary L. Miller, Richard Peng, Kanat Tangwongsan

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

10 Scopus citations

Abstract

This paper presents the design and analysis of a near linear-work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input an SDD n-by-n matrix A with m non-zero entries and a vector b, our algorithm computes a vector x̃ such that ∥x̃ - A+ b∥A ≤ ε · ∥ A+ b∥A in O(m logO(1) n log 1/ε work and O(m1/3+θ log 1/ε depth for any fixed θ > 0. The algorithm relies on a parallel algorithm for generating low-stretch spanning trees or spanning subgraphs. To this end, we first develop a parallel decomposition algorithm that in polylogarithmic depth and Õ(|E|) work, partitions a graph into components with polylogarithmic diameter such that only a small fraction of the original edges are between the components. This can be used to generate low-stretch spanning trees with average stretch O(nα) in O(n 1+α) work and O(nα) depth. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in O(|E|) work and polylogarithmic depth. We apply this subgraph construction to derive our solver. By using the linear system solver in known applications, our results imply improved parallel randomized algorithms for several problems, including single-source shortest paths, maximum flow, min-cost flow, and approximate max-flow.

Original languageEnglish (US)
Title of host publicationSPAA'11 - Proceedings of the 23rd Annual Symposium on Parallelism in Algorithms and Architectures
Pages13-22
Number of pages10
DOIs
StatePublished - 2011
Externally publishedYes
Event23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'11 - San Jose, CA, United States
Duration: Jun 4 2011Jun 6 2011

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Other

Other23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'11
Country/TerritoryUnited States
CitySan Jose, CA
Period6/4/116/6/11

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Keywords

  • linear systems
  • low-diameter decomposition
  • low-stretch spanning trees
  • low-stretch subgraphs
  • parallel algorithms

Fingerprint

Dive into the research topics of 'Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs'. Together they form a unique fingerprint.

Cite this