Comparison of Krylov subspace methods on the PageRank problem

[摘要] 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 alpha 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 alpha. We see that stationary methods are very reliable and more competitive when the problem is well conditioned, that is for small values of alpha. However, for large values of the parameter alpha 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. (C) 2006 Elsevier B.V. All rights reserved.

[发布日期] 2007-12-31

[效力级别]  Proceedings Paper

[关键词] search engines;Krylov subspace methods;Large and sparse linear systems