论文标题
通过Euler-Poisson-Darboux方程加速八卦算法
Acceleration of Gossip Algorithms through the Euler-Poisson-Darboux Equation
论文作者
论文摘要
八卦算法及其加速版本已在图表上独家研究。在这项工作中，我们采用了不同的方法，并考虑在大图和大量迭代中八卦算法的缩放限制。这些限制导致具有洞察力的众所周知的偏微分方程（PDE）。在晶格上，我们证明了Boyd等人的非加速八卦算法。 [2006]融合到热方程，以及Berthier等人的加速Jacobi多项式迭代。 [2020]收敛到Euler-Poisson-Darboux（EPD）方程 - 阻尼波方程。值得注意的是，使用适当的参数，EPD方程的基本解决方案具有理想的八卦行为：椭圆形的均匀密度，其半径以与T成正比的速率增加 - 局部通信八卦算法的最快速率。这与热方程式相反，该加密方程在$ \ sqrt {t} $的典型比例下扩散。此外，我们提供模拟，证明八卦算法通过其限制PDE可以准确地近似。
Gossip algorithms and their accelerated versions have been studied exclusively in discrete time on graphs. In this work, we take a different approach, and consider the scaling limit of gossip algorithms in both large graphs and large number of iterations. These limits lead to well-known partial differential equations (PDEs) with insightful properties. On lattices, we prove that the non-accelerated gossip algorithm of Boyd et al. [2006] converges to the heat equation, and the accelerated Jacobi polynomial iteration of Berthier et al. [2020] converges to the Euler-Poisson-Darboux (EPD) equation - a damped wave equation. Remarkably, with appropriate parameters, the fundamental solution of the EPD equation has the ideal gossip behaviour: a uniform density over an ellipsoid, whose radius increases at a rate proportional to t - the fastest possible rate for locally communicating gossip algorithms. This is in contrast with the heat equation where the density spreads on a typical scale of $\sqrt{t}$. Additionally, we provide simulations demonstrating that the gossip algorithms are accurately approximated by their limiting PDEs.
