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

DOI10.1007/s00224-013-9444-5zbMath1314.68361arXiv1111.1750OpenAlexW1991838331MaRDI QIDQ487267

Kanat Tangwongsan, Anupam Gupta, Richard Peng, Guy E. Blelloch, Ioannis Koutis, Gary Lee 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

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

Related Items

Distributed strong diameter network decomposition, Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts, Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions, Unnamed Item, Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis, A queueing network-based distributed Laplacian solver, Unnamed Item, Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank, Near-Optimal Distributed Maximum Flow

Cites Work

• The tail of the hypergeometric distribution
• A Mathematical View of Interior-Point Methods in Convex Optimization
• Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• High-Probability Parallel Transitive-Closure Algorithms
• The Laplacian Paradigm: Emerging Algorithms for Massive Graphs
• Lower-stretch spanning trees
• Complexity of network synchronization
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Fast and Efficient Parallel Solution of Sparse Linear Systems
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A Randomized Parallel Algorithm for Single-Source Shortest Paths
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• Probability Inequalities for Sums of Bounded Random Variables
• Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
• A Nearly-m log n Time Solver for SDD Linear Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item