An Arnoldi-Extrapolation algorithm for computing PageRank

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:234

Article

Wu, Gang²  Wei, Yimin^1,3 

[1] Fudan Univ, Sch Math Sci, Shanghai 200433, Peoples R China

[2] Xuzhou Normal Univ, Sch Math Sci, Xuzhou 221116, Jiangsu, Peoples R China

[3] Shanghai Key Lab Contemporary Appl Math, Shanghai, Peoples R China

关键词: PageRank;    Gene Rank;    Krylov subspace;    Arnoldi method;    Ritz value;   

DOI  :  10.1016/j.cam.2010.02.009

来源: Elsevier

【 摘 要 】

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. (C) 2010 Elsevier B.V. All rights reserved.

【 授权许可】

Free