A queueing network-based distributed Laplacian solver

DOI10.1007/s00453-021-00845-4OpenAlexW3176747354MaRDI QIDQ1979459

Iqra Altaf Gillani, Amitabha Bagchi

Publication date: 2 September 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00845-4

zbMATH Keywords

random walksqueueing networksdistributed algorithmrandom spanning treesLaplacian solver

Mathematics Subject Classification ID

Distributed algorithms (68W15) Random walks on graphs (05C81) Flows in graphs (05C21)

Related Items (1)

A stochastic process on a network with connections to Laplacian systems of equations

Uses Software

• LAMG
• GitHub
• Laplacians.jl

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• Stability of token passing rings
• A queueing network-based distributed Laplacian solver for directed graphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Distributed Computing: A Locality-Sensitive Approach
• A New Approach to Laplacian Solvers and Flow Problems
• Geometric Convergence Rates for Stochastically Ordered Markov Chains
• Sampling random spanning trees faster than matrix multiplication
• Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• Faster Generation of Random Spanning Trees
• An almost-linear time algorithm for uniform random spanning tree generation
• An Empirical Comparison of Graph Laplacian Solvers
• An efficient parallel solver for SDD linear systems
• Solving SDD linear systems in nearly m log ^1/2 n time
• Probability Inequalities for Sums of Bounded Random Variables
• Fast Generation of Random Spanning Trees and the Effective Resistance Metric
• An Efficient Multigrid Method for Graph Laplacian Systems II: Robust Aggregation
• Lx = b
• Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
• A Nearly-m log n Time Solver for SDD Linear Systems
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• Graph Sparsification by Effective Resistances

This page was built for publication: A queueing network-based distributed Laplacian solver