Comparison of Krylov subspace methods on the PageRank problem
Comparison of Krylov subspace methods on the PageRank problem
复制标题
DOI：
10.1016/j.cam.2006.10.080
复制
发表时间：
2007-12
影响因子：
2.4
通讯作者：
G. D. Corso;Antonio Gullì;F. Romani
中科院分区：
文献类型：
--
作者：
G. D. Corso;Antonio Gullì;F. Romani
PageRank算法在搜索引擎技术中起着非常重要的作用，它涉及到一个矩阵的特征向量的计算，该特征向量对应于一个矩阵的特征值，该矩阵的大小目前已达到数十亿。该问题包含一个参数α，该参数确定问题的难度。本文比较了在不同的α选择下，平稳和非平稳方法在部分真实网络矩阵上的有效性。我们看到，当问题的条件很好时，即对于较小的α值，平稳方法是非常可靠和更具竞争力的。然而，对于较大的参数α，问题变得更加困难，并且在Mflop计数以及达到收敛所需的迭代次数方面，诸如预条件BiCGStag或重新启动的预条件GMRES等方法变得与静态方法竞争。
PageRank algorithm plays a very important role in search engine technology and consists in the computation of the eigenvector corresponding to the eigenvalue one of a matrix whose size is now in the billions. The problem incorporates a parameter α that determines the difficulty of the problem. In this paper, the effectiveness of stationary and nonstationary methods are compared on some portion of real web matrices for different choices of α. We see that stationary methods are very reliable and more competitive when the problem is well conditioned, that is for small values of α. However, for large values of the parameter α the problem becomes more difficult and methods such as preconditioned BiCGStab or restarted preconditioned GMRES become competitive with stationary methods in terms of Mflops count as well as in number of iterations necessary to reach convergence.