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

DOI10.1007/S00224-013-9444-5MaRDI QIDQ487267zbMATH OpenOpenAlexFDO

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

Publication date 19 January 2015

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.1750

zbMATH Keywords

linear systemsparallel algorithmslow-diameter decompositionlow-stretch spanning treeslow-stretch subgraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Linear equations (linear algebraic aspects) (15A06) Parallel algorithms in computer science (68W10)

Abstract: We present the design and analysis of a near linear-work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input of a SDD $n$-by-$n$ matrix $A$ with $m$ non-zero entries and a vector $b$, our algorithm computes a vector $ildex$ such that $orm[A]ildex-A^{+}bleqvarepscdotorm[A]A^{+}b$ in $O(mlo{g}^{O(1)}nlogfrac1epsilon)$ work and $O(m^{1/3+heta}logfrac1epsilon)$ depth for any fixed $heta>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 $otilde(|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^{alpha})$ in $O(n^{1+alpha})$ work and $O(n^{alpha})$ depth. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in $otilde(|E|)$ work and polylogarithmic depth. We apply this subgraph construction to derive a parallel linear system solver. By using this solver in known applications, our results imply improved parallel randomized algorithms for several problems, including single-source shortest paths, maximum flow, minimum-cost flow, and approximate maximum flow.

Recommendations

• An efficient parallel solver for SDD linear systems
• Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
• Lower-stretch spanning trees
• Lower-Stretch Spanning Trees
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time

Cites work

• scientific article; zbMATH DE number 5485557 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1131479 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 5485569 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A Nearly-m log n Time Solver for SDD Linear Systems
• A Randomized Parallel Algorithm for Single-Source Shortest Paths
• A linear work, \(O(n^{1/6})\) time, parallel algorithm for solving planar Laplacians
• A mathematical view of interior-point methods in convex optimization
• Complexity of network synchronization
• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• Fast and Efficient Parallel Solution of Sparse Linear Systems
• High-Probability Parallel Transitive-Closure Algorithms
• Lower-stretch spanning trees
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• Probability Inequalities for Sums of Bounded Random Variables
• Spectral sparsification in the semi-streaming setting
• The Laplacian paradigm: emerging algorithms for massive graphs
• The tail of the hypergeometric distribution

Cited in

(14)

• Near-optimal distributed maximum flow
• Lower-Stretch Spanning Trees
• scientific article; zbMATH DE number 7650073 (Why is no real title available?)
• Faster distributed shortest path approximations via shortcuts
• Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
• A linear work, \(O(n^{1/6})\) time, parallel algorithm for solving planar Laplacians
• Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
• Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
• Distributed strong diameter network decomposition
• Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis
• Solving local linear systems with boundary conditions using heat kernel pagerank
• Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
• An efficient parallel solver for SDD linear systems
• A queueing network-based distributed Laplacian solver

This page was built for publication: Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q487267)