Minor Sparsifiers and the Distributed Laplacian Paradigm
Minor Sparsifiers and the Distributed Laplacian Paradigm
复制标题
小稀疏器和分布式拉普拉斯范式
DOI：
10.1109/focs52979.2021.00099
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ye, Mingquan
中科院分区：
文献类型：
--
作者：
Forster, Sebastian;Goranci, Gramoz;Liu, Yang P.;Peng, Richard;Sun, Xiaorui;Ye, Mingquan
我们研究了基于minor的顶点稀疏器的分布式算法，并给出了在CONGEST模型中求解图拉普拉斯矩阵中的线性系统的高精度算法。我们的Laplacian求解器的轮复杂度为，因此几乎与的下界相匹配，其中是网络中的节点数，是网络的直径。我们表明，我们的分布式求解器产生新的次线性轮算法的几个基石问题的组合优化。这是通过在分布式图算法的背景下利用内点方法（IPM）和拉普拉斯范式的强大算法框架来实现的，这需要通过一系列拉普拉斯系统数值求解图上的优化问题。受益于我们的分布式算法范式的问题，包括精确的最小成本流，负权重最短路径，最大流，和稀疏有向图的二分匹配。对于最大流问题，这是第一个适用于有向图的精确分布式算法，而以前的工作[Ghaffari et al. SICOMP'18]考虑了近似设置，仅适用于无向图。对于最小费用流和负权最短路径问题，我们的结果构成了第一个精确的分布式算法运行在一个次线性轮数。考虑到IPM和拉普拉斯范式之间的混合已被证明是有用的，在集中式设置中处理众多的优化问题，我们相信，我们的分布式求解器将找到未来的应用。我们的分布式拉普拉斯求解器的核心是[Li，Schild FOCS'18]的谱子空间稀疏器的概念。我们提出了一个非平凡的分布式实现他们的建设（i）给他们的算法，避免了随机生成树的采样，并使用近似的杠杆分数代替的并行变体，和（ii）表明该算法仍然产生一个高质量的子空间谱稀疏仔细设置和分析矩阵鞅。结合这种顶点减少递归树和消除为基础的预条件导致我们的算法求解拉普拉斯系统。基于消除的预处理器的建设是基于计算短的随机游走，我们引入了一种新的技术，以减少这些行走的模拟加权图所产生的拥塞。
We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrices to high accuracy. Our Laplacian solver has a round complexity of, and thus almost matches the lower bound of, whereis the number of nodes in the network andis its diameter. We show that our distributed solver yields new sublinear round algorithms for several cornerstone problems in combinatorial optimization. This is achieved by leveraging the powerful algorithmic framework of Interior Point Methods (IPMs) and the Laplacian paradigm in the context of distributed graph algorithms, which entails numerically solving optimization problems on graphs via a series of Laplacian systems. Problems that benefit from our distributed algorithmic paradigm include exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on sparse directed graphs. For the maxflow problem, this is the first exact distributed algorithm that applies to directed graphs, while the previous work by [Ghaffari et al. SICOMP'18] considered the approximate setting and works only for undirected graphs. For the mincost flow and the negative weight shortest path problems, our results constitute the first exact distributed algorithms running in a sublinear number of rounds. Given that the hybrid between IPMs and the Laplacian paradigm has proven useful for tackling numerous optimization problems in the centralized setting, we believe that our distributed solver will find future applications. At the heart of our distributed Laplacian solver is the notion of spectral subspace sparsifiers of [Li, Schild FOCS'18]. We present a nontrivial distributed implementation of their construction by (i) giving a parallel variant of their algorithm that avoids the sampling of random spanning trees and uses approximate leverage scores instead, and (ii) showing that the algorithm still produces a high-quality subspace spectral sparsifier by carefully setting up and analyzing matrix martingales. Combining this vertex reduction recursively with both tree and elimination-based preconditioners leads to our algorithm for solving Laplacian systems. The construction of the elimination-based preconditioners is based on computing short random walks, and we introduce a new technique for reducing the congestion incurred by the simulation of these walks on weighted graphs.
登录
查看更多内容
DOI：
10.1137/1.9781611976465.74
发表时间：
2020-07
期刊：
--
影响因子：
--
作者：
Parinya Chalermsook;Syamantak Das;Bundit Laekhanukit;Yunbum Kook;Yang P. Liu;Richard Peng;Mark Sellke-Mark-Sell
通讯作者：
Parinya Chalermsook;Syamantak Das;Bundit Laekhanukit;Yunbum Kook;Yang P. Liu;Richard Peng;Mark Sellke-Mark-Sell
影响因子：
--
作者：
Danupon Nanongkai;Hsin
通讯作者：
Hsin
通过流水线的分布式加权所有对最短路径
DOI：
10.1109/ipdps.2019.00014
发表时间：
2019
期刊：
2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
影响因子：
--
作者：
U. Agarwal;V. Ramachandran
通讯作者：
V. Ramachandran
关于概率对数空间中随机矩阵特征值的逼近
影响因子：
1.4
作者：
Dean Doron;Amir Sarid;A. Ta
通讯作者：
A. Ta
小空间随机游走的高精度估计
DOI：
10.1109/focs46700.2020.00123
发表时间：
2020
期刊：
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Ahmadinejad, AmirMahdi;Kelner, Jonathan;Murtagh, Jack;Peebles, John;Sidford, Aaron;Vadhan, Salil
通讯作者：
Vadhan, Salil