Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications
复制标题
DOI：
10.1137/1.9781611975482.85
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
AmirMahdi Ahmadinejad;A. Jambulapati;A. Saberi;Aaron Sidford
中科院分区：
文献类型：
--
作者：
AmirMahdi Ahmadinejad;A. Jambulapati;A. Saberi;Aaron Sidford
在本文中，我们提供了几个问题的近似线性时间算法密切相关的经典Perron-Frobenius定理，包括计算Perron向量，即非负矩阵的入口非负特征向量，并解决线性系统的非对称M-矩阵，Laplacian系统的推广。我们的算法的运行时间几乎线性依赖于输入的大小和polynomically所需的精度和问题的条件数。利用这些结果，我们还为更广泛的问题提供了更好的运行时间，包括计算基于随机行走的图内核，计算Katz中心性等。我们的算法的运行时间改善以前已知的结果，要么多项式依赖于问题的条件数，所需的二次时间，或仅适用于特殊情况。我们通过提供新的迭代方法将这些问题简化为求解行列对角占优（RCDD）矩阵中的线性系统来获得这些结果。我们的方法与用于特征向量计算的经典移位和反转预处理技术相关，并且构成了Cohen等人（2016）结果的第一种替代方案，用于减少平稳分布计算和求解有向拉普拉斯系统以求解RCDD系统。
In this paper we provide nearly linear time algorithms for several problems closely associated with the classic Perron-Frobenius theorem, including computing Perron vectors, i.e. entrywise non-negative eigenvectors of non-negative matrices, and solving linear systems in asymmetric M-matrices, a generalization of Laplacian systems. The running times of our algorithms depend nearly linearly on the input size and polylogarithmically on the desired accuracy and problem condition number. Leveraging these results we also provide improved running times for a broader range of problems including computing random walk-based graph kernels, computing Katz centrality, and more. The running times of our algorithms improve upon previously known results which either depended polynomially on the condition number of the problem, required quadratic time, or only applied to special cases. We obtain these results by providing new iterative methods for reducing these problems to solving linear systems in Row-Column Diagonally Dominant (RCDD) matrices. Our methods are related to the classic shift-and-invert preconditioning technique for eigenvector computation and constitute the first alternative to the result in Cohen et al. (2016) for reducing stationary distribution computation and solving directed Laplacian systems to solving RCDD systems.