An Arnoldi-Extrapolation algorithm for computing PageRank

作者：Wu Gang; Wei Yimin^*

来源：Journal of Computational and Applied Mathematics, 2010, 234(11): 3196-3212.

DOI：10.1016/j.cam.2010.02.009

• PageRank
• Gene Rank
• Krylov subspace
• Arnoldi method
• Ritz value

The Arnoldi-type algorithm proposed by Golub and Greif [G. Golub, C. Greif, An Arnoldi-type algorithm for computing PageRank, BIT 46 (2006) 759-771] is a restarted Krylov subspace method for computing PageRank. However, this algorithm may not be efficient when the damping factor is high and the dimension of the search subspace is small. In this paper, we first develop an extrapolation method based on Ritz values. We then consider how to periodically knit this extrapolation method together with the Arnoldi-type algorithm. The resulting algorithm is the Arnoldi-Extrapolation algorithm. The convergence of the new algorithm is analyzed. Numerical experiments demonstrate the numerical behavior of this algorithm.

• 出版日期2010-10-1
• 单位江苏师范大学; 复旦大学