×

A queueing network-based distributed Laplacian solver for directed graphs. (English) Zbl 1506.68073

Summary: We present a distributed algorithm for solving Laplacian systems on strongly connected directed graphs, the first that can be analyzed in terms of the underlying graph’s parameters. Our distributed solver works for a large and important class of Laplacian systems that we call “one-sink” Laplacian systems, which includes the important electrical flow computation problem. Specifically, given \(D_{\text{out}}\) as the diagonal out-degree matrix and \(\overrightarrow{A}\) as the adjacency matrix of the directed graph with \(L=D_{\text{out}}-\overrightarrow{A}\), our solver can produce solutions for systems of the form \(\boldsymbol{x}^T L = \boldsymbol{b}^T\), where exactly one of the coordinates of b is negative. Our solver takes \(\widetilde{O}(t_{\text{hit}} d_{\max}^{\text{in}})\) 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 \(d_{\max}^{\text{in}}\) is the maximum in-degree of the graph.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C20 Directed graphs (digraphs), tournaments
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
68W15 Distributed algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Spielman, D. A.; Teng, S.-H., Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, (Proc. of the 36th Annual ACM Symp. on Theory of Computing, STOC’04 (2004), ACM) · Zbl 1192.65048
[2] Cohen, M. B.; Kelner, J.; Peebles, J.; Peng, R.; Sidford, A.; Vladu, A., Faster algorithms for computing the stationary distribution, simulating random walks, and more, (Proc. of the 57th Annual Symp. on Foundations of Computer Science, FOCS’16 (2016), IEEE)
[3] Cohen, M. B.; Kelner, J.; Kyng, R.; Peebles, J.; Peng, R.; Rao, A. B.; Sidford, A., Solving directed Laplacian systems in nearly-linear time through sparse LU factorizations, (Proc. of the 59th Annual Symp. on Foundations of Computer Science, FOCS’18 (2018), IEEE)
[4] Tang, Y.; Mei, J., Distributed algorithms for solving a linear equation under a directed graph, (Proc. of the 37th Chinese Control Conf., CCC’18 (2018), IEEE)
[5] 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, (Proc. of the 43rd Annual ACM Symp. on Theory of Computing, STOC’11 (2011), ACM), 273-282 · Zbl 1288.94127
[6] Mądry, A.; Straszak, D.; Tarnawski, J., Fast generation of random spanning trees and the effective resistance metric, (Proc. of the 26th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA’15 (2015)) · Zbl 1372.68213
[7] Spielman, D. A.; Srivastava, N., Graph sparsification by effective resistances, SIAM J. Comput., 40, 6, 1913-1926 (2011) · Zbl 1237.05129
[8] Li, H.; Peng, R.; Shan, L.; Yi, Y.; Zhang, Z., Current flow group closeness centrality for complex networks, (Proc. of the World Wide Web Conf., WWW’19 (2019), ACM), 961-971
[9] Gillani, I. A.; Bagchi, A.; Vyavahare, P., A stochastic process on a network with connections to Laplacian systems of equations (2017)
[10] Cohen, M. B.; Kelner, J.; Peebles, J.; Peng, R.; Rao, A. B.; Sidford, A.; Vladu, A., Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs, (Proc. of the 49th Annual ACM Symp. on Theory of Computing, STOC’17 (2017)), 410-419 · Zbl 1370.60115
[11] Fox, A.; Manteuffel, T., Algebraic multigrid for directed graph Laplacian linear systems (NS-LAMG), Numer. Linear Algebra Appl., 25, 3, Article e2152 pp. (2018) · Zbl 1513.65069
[12] Peleg, D., Distributed computing: a locality-sensitive approach, (Monographs in Discrete Mathematics and Applications (2000)) · Zbl 0959.68042
[13] Boyd, S.; Ghosh, A.; Prabhakar, B.; Shah, D., Randomized gossip algorithms, IEEE/ACM Trans. Netw., 14, SI, 2508-2530 (2006) · Zbl 1283.94005
[14] Gillani, I. A.; Bagchi, A., A queueing network-based distributed Laplacian solver, (Proc. of the 32nd ACM Symp. on Parallelism in Algorithms and Architectures, SPAA’20 (2020)), 535-537, Full version:
[15] Sternberg, S., Dynamical Systems (2010), Courier Corporation · Zbl 1215.37002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.