Comparison of Krylov subspace methods on the PageRank problem
- 作者：Gianna M. Del Corso ; Antonio Gullí ; ; Francesco Romani
- 关键词：Search engines ; Krylov subspace methods ; Large and sparse linear systems
- 刊名：Journal of Computational and Applied Mathematics
- 出版年：2007
- 期刊代码：72_03770427
- 类别：cp
- 出版时间：31 December 2007
- 卷：210
- 期：1-2
- 页码：159-166
- 文件大小：289 K
摘要
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 method=retrieve&_udi=B6TYH-4MGVJ40-8&_mathId=mml67&_user=10&_cdi=5619&_rdoc=18&_acct=C000050221&_version=1&_userid=10&md5=399b0a34fac753a202bb750ea061cd7d" title="Click to view the MathML source">α 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 method=retrieve&_udi=B6TYH-4MGVJ40-8&_mathId=mml68&_user=10&_cdi=5619&_rdoc=18&_acct=C000050221&_version=1&_userid=10&md5=c8b1ff76996ba5d3868d80056f844ac1" title="Click to view the MathML source">α. We see that stationary methods are very reliable and more competitive when the problem is well conditioned, that is for small values of method=retrieve&_udi=B6TYH-4MGVJ40-8&_mathId=mml69&_user=10&_cdi=5619&_rdoc=18&_acct=C000050221&_version=1&_userid=10&md5=8e526009134b90d03ed9948ad7485557" title="Click to view the MathML source">α. However, for large values of the parameter method=retrieve&_udi=B6TYH-4MGVJ40-8&_mathId=mml70&_user=10&_cdi=5619&_rdoc=18&_acct=C000050221&_version=1&_userid=10&md5=ef3e40a024847e1a4df4f861d627c623" title="Click to view the MathML source">α 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.