Skip to main content
Springer Nature Link
Log in

A Queueing Network-Based Distributed Laplacian Solver

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Notes

  1. In the following we use bold letters, e.g., \(\varvec{x}\) for column vectors and denote row vectors as the transpose of column vectors, e.g., \(\varvec{x}^T\).

References

  1. Aldous, D., Fill, J.: Reversible markov chains and random walks on graphs (2002). (Monograph)

  2. Aldous, D.J.: The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J. Discret. Math. 3(4), 450–465 (1990)

    Article  MathSciNet  Google Scholar 

  3. Aleliunas, R., Karp, R.M., Lipton, R.J., Lovász, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: Proceedings of the 20th Annual Symposium on Foundations of Computer Science, SFCS ’79, pp. 218–223. IEEE Computer Society (1979)

  4. Anari, N., Liu, K., Gharan, S.O., Vinzant, C.: Log-concave polynomials IV: Exchange properties, tight mixing times, and faster sampling of spanning trees (2020). ArXiv:2004.07220 [cs.DS]

  5. Andoni, A., Krauthgamer, R., Pogrow, Y.: On Solving Linear Systems in Sublinear Time. In: 10th Innovations in Theoretical Computer Science Conference, ITCS ’19, vol. 124, pp. 3:1–3:19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2019). https://doi.org/10.4230/LIPIcs.ITCS.2019.3

  6. Awerbuch, B., Gallager, R.G.: Distributed BFS algorithms. In: Proceedings of the 26th Annual Symp. on Foundations of Computer Science, SFCS ’85, pp. 250–256. IEEE (1985)

  7. Becchetti, L., Bonifaci, V., Natale, E.: Pooling or sampling: Collective dynamics for electrical flow estimation. In: Proceedings of the 17th Intl. Conf. on Autonomous Agents and MultiAgent Systems, AAMAS ’18, pp. 1576–1584 (2018)

  8. Blelloch, G.E., Gupta, A., Koutis, I., Miller, G.L., Peng, R., Tangwongsan, K.: Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs. Theory Comput. Syst. 55(3), 521–554 (2014)

    Article  MathSciNet  Google Scholar 

  9. Boman, E.G., Deweese, K., Gilbert, J.R.: An empirical comparison of graph Laplacian solvers. In: Proceedings of the 18th Workshop on Algorithm Engg. and Experiments, ALENEX ’16, pp. 174–188. SIAM (2016)

  10. Boman, E.G., Deweese, K., Gilbert, J.R.: Evaluating the dual randomized Kaczmarz Laplacian linear solver. Informatica 40(1), 95–107 (2016)

    MathSciNet  Google Scholar 

  11. Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Randomized gossip algorithms. IEEE/ACM Trans. Netw. 14, 2508–2530 (2006)

    MathSciNet  MATH  Google Scholar 

  12. Broder, A.: Generating random spanning trees. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, SFCS ’89, pp. 442–447. IEEE Computer Society (1989)

  13. Christiano, P., Kelner, J.A., Mądry, A., Spielman, D.A., Teng, S.H.: Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In: Proceedings of the 43rd annual ACM Symposium on Theory of computing, STOC ’11, pp. 273–282. ACM (2011)

  14. Chung, F., Simpson, O.: Solving local linear systems with boundary conditions using heat kernel pagerank. Internet Math. 11(4–5), 449–471 (2015)

    Article  MathSciNet  Google Scholar 

  15. Cohen, M.B., Kyng, R., Miller, G.L., Pachocki, J.W., Peng, R., Rao, A.B., Xu, S.C.: Solving SDD linear systems in nearly \(m~log^{1/2}n\) time. In: Proceedings of the 46th annual ACM Symposium on Theory of Computing, STOC ’14, pp. 343–352. ACM (2014)

  16. Durfee, D., Kyng, R., Peebles, J., Rao, A.B., Sachdeva, S.: Sampling random spanning trees faster than matrix multiplication. In: Proceedings of the 49th Annual ACM Symposium on Theory of Computing, STOC ’17, pp. 730–742. ACM (2017)

  17. Georgiadis, L., Szpankowski, W.: Stability of token passing rings. Queue. Syst. 11(1–2), 7–33 (1992)

    Article  MathSciNet  Google Scholar 

  18. Ghaffari, M., Haeupler, B.: Brief announcement: Near-optimal BFS-tree construction in radio networks. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC ’14 (2014)

  19. Gillani, I.A., Bagchi, A.: A queueing network-based distributed Laplacian solver. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’20, p. 535–537. ACM (2020)

  20. Gillani, I.A., Bagchi, A.: A queueing network-based distributed Laplacian solver for directed graphs. Inf. Proc. Lett. 166, 106040 (2021)

    Article  MathSciNet  Google Scholar 

  21. Gillani, I.A., Bagchi, A., Ranu, S.: A group-to-group version of random walk betweenness centrality. In: Proceedings of ACM India Joint International Conference on Data Science and Management of Data, CODS-COMAD ’21, pp. 127–135 (2021)

  22. Gillani, I.A., Bagchi, A., Vyavahare, P.: A stochastic process on a network with connections to Laplacian systems of equations. Adv. Appl. Probab. (to appear) (2021). Full version: arXiv:1701.05296 [cs.NI]

  23. Gross, D.: Fundamentals of Queueing Theory. John Wiley and Sons, New York (2008)

    Book  Google Scholar 

  24. Hoeffding, W.: Probability Inequalities for Sums of Bounded Random Variables. In: Journal of the American Statistical Association, vol. 58, pp. 13–30. Taylor and Francis, (1963)

  25. Hoske, D., Lukarski, D., Meyerhenke, H., Wegner, M.: Is nearly-linear the same in theory and practice? a case study with a combinatorial Laplacian solver. In: Proceedings of International Symposium on Experimental Algorithms, SEA ’15, pp. 205–218. Springer (2015)

  26. Kelner, J.A., Mądry, A.: Faster generation of random spanning trees. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’09, pp. 13–21. IEEE (2009)

  27. Kelner, J.A., Orecchia, L., Sidford, A., Zhu, Z.A.: A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. In: Proceedings of the 45th annual ACM Symposium on Theory of Computing, STOC ’13, pp. 911–920. ACM (2013)

  28. Konolige, T., Brown, J.: A parallel solver for graph Laplacians. In: Proceedings of the Platform for Advanced Scientific Computing Conf., PASC ’18, p. 3. ACM (2018)

  29. Koutis, I., Miller, G.L.: A linear work, \({O}(n^{1/6})\) time, parallel algorithm for solving planar Laplacians. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’07, pp. 1002–1011. SIAM (2007)

  30. Koutis, I., Miller, G.L., Peng, R.: A nearly-\(m~ \log n\) time solver for SDD linear systems. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, FOCS ’11, pp. 590–598. IEEE (2011)

  31. Koutis, I., Miller, G.L., Tolliver, D.: Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing. Comput. Vision Image Underst. 115(12), 1638–1646 (2011)

    Article  Google Scholar 

  32. Kyng, R., Sachdeva, S.: Approximate gaussian elimination for Laplacians-fast, sparse, and simple. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’16, pp. 573–582. IEEE (2016)

  33. Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787–832 (1999)

    Article  MathSciNet  Google Scholar 

  34. Levin, D.A., Peres, Y., Wilmer, E.L.: Markov chains and mixing times. American Mathematical Soc. (2009)

  35. Li, H., Peng, R., Shan, L., Yi, Y., Zhang, Z.: Current flow group closeness centrality for complex networks. In: The World Wide Web Conference, WWW ’19, pp. 961–971. ACM (2019)

  36. Livne, O.E., Brandt, A.: Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver. SIAM J. Sci. Comput. 34(4), B499–B522 (2012)

    Article  MathSciNet  Google Scholar 

  37. Lund, R.B., Tweedie, R.L.: Geometric convergence rates for stochastically ordered markov chains. Math. Op. Res. 21(1), 182–194 (1996)

    Article  MathSciNet  Google Scholar 

  38. Miller, G.L., Peng, R., Xu, S.C.: Parallel graph decompositions using random shifts. In: Proceedings of the 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’13, pp. 196–203. ACM (2013)

  39. Mądry, A.: Computing maximum flow with augmenting electrical flows. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’16, pp. 593–602. IEEE (2016)

  40. Mądry, A., Straszak, D., Tarnawski, J.: Fast generation of random spanning trees and the effective resistance metric. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’15, pp. 2019–2036 (2015)

  41. Napov, A., Notay, Y.: An efficient multigrid method for graph Laplacian systems II: robust aggregation. SIAM J. Sci. Comput. 39(5) (2017)

  42. Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)

    Book  Google Scholar 

  43. Peng, R., Spielman, D.A.: An efficient parallel solver for SDD linear systems. In: Proceedings of the 46th annual ACM Symposium on Theory of computing, STOC ’14, pp. 333–342. ACM (2014)

  44. Rebeschini, P., Tatikonda, S.: A new approach to Laplacian solvers and flow problems. J. Mach. Learn. Res. 20(36), 1–37 (2019)

    MathSciNet  MATH  Google Scholar 

  45. Schild, A.: An almost-linear time algorithm for uniform random spanning tree generation. In: Proceedings of the 50th Annual ACM Symposium on Theory of Computing, STOC ’18, pp. 214–227. ACM (2018)

  46. Spielman, D.A.: Laplacians.jl. https://github.com/danspielman/ Laplacians.jl (2017)

  47. Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. SIAM J. Comput. 40(6), 1913–1926 (2011)

    Article  MathSciNet  Google Scholar 

  48. Spielman, D.A., Teng, S.H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, STOC ’04. ACM (2004)

  49. Tutunov, R.: Fully distributed and mixed symmetric diagonal dominant solvers for large scale optimization (2017). Publicly Accessible Penn. Dissertations

  50. Tutunov, R., Ammar, H.B., Jadbabaie, A.: A fast distributed solver for symmetric diagonally dominant linear equations (2015). ArXiv:1502.03158 [cs.DC]

  51. Tutunov, R., El-Zini, J., Bou-Ammar, H., Jadbabaie, A.: Distributed lifelong reinforcement learning with sub-linear regret. In: Proceedings of 56th Annual IEEE Conference on Decision and Control, CDC ’17, pp. 2254–2259. IEEE (2017)

  52. Vishnoi, N.K.: Lx\(=\) b Laplacian solvers and their algorithmic applications. Found. Trends Theor. Comput. Sci. 8(1–2), 1–141 (2013)

    Article  MathSciNet  Google Scholar 

  53. Zouzias, A., Freris, N.M.: Randomized gossip algorithms for solving Laplacian systems. In: European Control Conference, ECC ’15, pp. 1920–1925. IEEE (2015)

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, IIT Delhi, New Delhi, 110016, India

    Iqra Altaf Gillani & Amitabha Bagchi

Authors
  1. Iqra Altaf Gillani
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Amitabha Bagchi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Iqra Altaf Gillani.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A Brief Announcement of this work appeared in SPAA’20 [19].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gillani, I.A., Bagchi, A. A Queueing Network-Based Distributed Laplacian Solver. Algorithmica 83, 2859–2894 (2021). https://doi.org/10.1007/s00453-021-00845-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-021-00845-4

Keywords

Mathematics Subject Classification

Search

Navigation