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

DOI10.1007/S00224-013-9444-5zbMATH Open1314.68361arXiv1111.1750OpenAlexW1991838331MaRDI QIDQ487267FDOQ487267

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

Publication date: 19 January 2015

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Probability Inequalities for Sums of Bounded Random Variables
• A mathematical view of interior-point methods in convex optimization
• Title not available (Why is that?)
• Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• Title not available (Why is that?)
• A Nearly-m log n Time Solver for SDD Linear Systems
• Complexity of network synchronization
• Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• The tail of the hypergeometric distribution
• Title not available (Why is that?)
• Title not available (Why is that?)
• High-Probability Parallel Transitive-Closure Algorithms
• Fast and Efficient Parallel Solution of Sparse Linear Systems
• Title not available (Why is that?)
• The Laplacian Paradigm: Emerging Algorithms for Massive Graphs
• Lower-stretch spanning trees
• A Randomized Parallel Algorithm for Single-Source Shortest Paths
• Polylog-time and near-linear work approximation scheme for undirected shortest paths

Cited In (11)

• Lower-Stretch Spanning Trees
• Title not available (Why is that?)
• Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
• Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
• Near-Optimal Distributed Maximum Flow
• Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis
• Distributed strong diameter network decomposition
• Parallel breadth-first search and exact shortest paths and stronger notions for approximate distances
• Title not available (Why is that?)
• 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)