论文标题
在几乎线性的时间内驱散的定向随机步行
Derandomizing Directed Random Walks in Almost-Linear Time
论文作者
论文摘要
在本文中，我们介绍了第一个确定性的定向Laplacian L Systems Solver，该求解器几乎是在L的非零条目数字上运行的。 我们通过引入部分对称性来获得这些结果，这是一种新技术，它使欧拉尔有向图的拉普拉斯在有用的意义上``''simalled offed''可能具有独立的兴趣。该技术的实用性来自两个关键观察：首先，部分对称的拉普拉斯先前条件在Richardson迭代中井井有条的原始Eulerian Laplacian井，使我们能够从求解器中为部分对称的一个求解器构建原始矩阵的求解器。其次，部分对称的拉普拉斯（Laplacian）中的无向结构使得非常粗略地稀疏矩阵，即具有较大的光谱误差，并且仍然表明，当使用稀疏的矩阵作为预处理器时，Richardson迭代会收敛。这使我们能够为部分对称的拉普拉斯人开发确定性的稀疏工具。 加上以前从定向的拉普拉斯人降低到欧拉·拉普拉斯人的降低，我们的技术导致了第一种确定性的几乎线性时间算法，用于求解有向拉普拉斯的线性方程。 To emphasize the generality of our new technique, we show that two prominent existing (randomized) frameworks for solving linear equations in Eulerian Laplacians can be derandomized in this way: the squaring-based framework of Cohen, Kelner, Peebles, Peng, Rao, Sidford and Vladu (STOC 2017) and the sparsified Cholesky-based framework of Peng and Song (STOC 2022).
In this article, we present the first deterministic directed Laplacian L systems solver that runs in time almost-linear in the number of non-zero entries of L. Previous reductions imply the first deterministic almost-linear time algorithms for computing various fundamental quantities on directed graphs including stationary distributions, personalized PageRank, hitting times and escape probabilities. We obtain these results by introducing partial symmetrization, a new technique that makes the Laplacian of an Eulerian directed graph ``less directed'' in a useful sense, which may be of independent interest. The usefulness of this technique comes from two key observations: Firstly, the partially symmetrized Laplacian preconditions the original Eulerian Laplacian well in Richardson iteration, enabling us to construct a solver for the original matrix from a solver for the partially symmetrized one. Secondly, the undirected structure in the partially symmetrized Laplacian makes it possible to sparsify the matrix very crudely, i.e. with large spectral error, and still show that Richardson iterations convergence when using the sparsified matrix as a preconditioner. This allows us to develop deterministic sparsification tools for the partially symmetrized Laplacian. Together with previous reductions from directed Laplacians to Eulerian Laplacians, our technique results in the first deterministic almost-linear time algorithm for solving linear equations in directed Laplacians. To emphasize the generality of our new technique, we show that two prominent existing (randomized) frameworks for solving linear equations in Eulerian Laplacians can be derandomized in this way: the squaring-based framework of Cohen, Kelner, Peebles, Peng, Rao, Sidford and Vladu (STOC 2017) and the sparsified Cholesky-based framework of Peng and Song (STOC 2022).
