Research On The Iteration Methods For Computing PageRank

With the booming development of the internet,the way people obtain information is gradually changing to the web search.Google search engine is one of the most popular search engines in recent years,due to its convenience and comprehensiveness for obtaining information.A key technique,called PageRank,is used to determine the importance of web pages in Google search engine.Many great interesting researches focus on developing efficient numerical methods to compute PageRank problems.In this paper,the Krylov subspace method is used as the point to study the iterative methods to improve the speed of computing PageRank,which is mainly divided into the following two parts:On the one hand,we propose the SGMRES-Chebyshev algorithm.The SGMRES algorithm has gained great theoretical development and practical applications in solving asymmetric systems,but it is seldom used to calculate PageRank problems.The main characteristic of SGMRES algorithm is that there is no need to factor the upper Hessenberg matrix,and the residual vector can be easily obtained in each iteration.Therefore,this paper attempts to study the SGMRES algorithm to compute PageRank.To speed up the computation of PageRank problems,an accelerated technique based on Chebyshev polynomials is applied to improve the SGMRES algorithm,such that a new algorithm named SGMRES-Chebyshev is proposed here.The implementation and the convergence analysis of the SGMRES-Chebyshev algorithm are discussed in detail.Numerical experiments are used to illustrate the efficiency of the SGMRES-Chebyshev algorithm.On the other hand,we discuss a generalized full orthogonalization method(GFOM)based on weighted inner products for computing PageRank.In order to improve convergence performance,the GFOM algorithm is accelerated by two cheap methods respectively,one is the power method and the other is the extrapolation method based on Ritz values.Such that two new algorithms called GFOM-Power and GFOM-Extrapolation are proposed for computing PageRank.Their implementations and convergence analyses are studied in detail.Numerical experiments are used to show the efficiency of our proposed algorithms.