An Arnoldi-Extrapolation algorithm for computing PageRank |
| |
Authors: | Gang Wu Yimin Wei |
| |
Institution: | a School of Mathematical Sciences, Xuzhou Normal University, Xuzhou, 221116, Jiangsu, PR China b School of Mathematical Sciences, Fudan University, Shanghai, 200433, PR China c Shanghai Key Laboratory of Contemporary Applied Mathematics, PR China |
| |
Abstract: | 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. |
| |
Keywords: | 65F15 65F10 65C40 60J22 |
本文献已被 ScienceDirect 等数据库收录! |
|