A New Approach to Laplacian Solvers and Flow Problems

zbMath1489.90008arXiv1611.07138MaRDI QIDQ4633047

Sekhar Tatikonda, Patrick Rebeschini

Publication date: 2 May 2019

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

zbMATH Keywords

decentralized algorithmsnetwork flowsmessage passingLaplacian solverMin-Sum

Mathematics Subject Classification ID

Applications of graph theory (05C90) Deterministic network models in operations research (90B10)

Related Items

A queueing network-based distributed Laplacian solver

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gibbs measures and phase transitions.
• Belief Propagation for Min-Cost Network Flow: Convergence and Correctness
• Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• Consensus Propagation
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• The capacity of low-density parity-check codes under message-passing decoding
• An analysis of belief propagation on the turbo decoding graph with Gaussian densities
• Convergence of Min-Sum Message Passing for Quadratic Optimization
• Optimal errors and phase transitions in high-dimensional generalized linear models
• An efficient parallel solver for SDD linear systems
• Solving SDD linear systems in nearly m log ^1/2 n time
• Convergence of Min-Sum Message-Passing for Convex Optimization
• Survey propagation: An algorithm for satisfiability
• Lx = b
• A Nearly-m log n Time Solver for SDD Linear Systems
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time