A Queueing Network-Based Distributed Laplacian Solver
2021
We use queueing networks to present a new approach to solving Laplacian systems. This marks a significant departure from the existing techniques, mostly based on graph-theoretic constructions and sampling. Our distributed solver works for a large and important class of Laplacian systems that we call “one-sink” Laplacian systems. Specifically, our solver can produce solutions for systems of the form $$L\varvec{x} = \varvec{b}$$
where exactly one of the coordinates of $$\varvec{b}$$
is negative. Our solver is a distributed algorithm that takes $${\widetilde{O}}(t_{\text{ hit }}\hat{d}_{\max })$$
time (where $${\widetilde{O}}$$
hides $${\text {poly}}\log n$$
factors) to produce an approximate solution where $$t_{\text{ hit }}$$
is the worst-case hitting time of the random walk on the graph, which is $$\Theta (n)$$
for a large set of important graphs, and $$\hat{d}_{\max }$$
is the maximum degree of the graph. The class of one-sink Laplacians includes the important voltage computation problem and allows us to compute the effective resistance between nodes in a distributed setting. As a result, our Laplacian solver can be used to adapt the approach by Kelner and Mądry (2009) to give the first distributed algorithm to compute approximate random spanning trees efficiently.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
53
References
0
Citations
NaN
KQI