Research On GMRES-type Algorithms For PageRank Problem

In the field of information retrieval,fast approaches of web ranking are very important to web search engines.Google is one of the search engines with the largest number of users and the highest user evaluation in recent years,and its success can be attributed to its simple and elegant PageRank algorithm.PageRank problem can be described as a large sparse linear system,while PageRank problem with multiple damping factors is essentially one kind of shifted linear system.Based on Krylov subspace method,thesis attempts to research some effective acceleration strategies,in order to improve the solution speed of PageRank problem and promote the development of search engines and even the Internet.Focusing on the PageRank problem with single or multiple damping factors,thesis carries out the following two aspects of algorithm research.On the one hand,thesis propose the PGMRES-DR algorithm for the PageRank problem with a single damping factor.First,thesis apply the GMRES-DR method for solving linear system to solve the PageRank problem with a single damping factor.In view of the bad situation in the solution process of GMRES-DR,according to the mathematical background of PageRank,thesis select the appropriate polynomial preconditioner,and improve the spectral distribution of coefficient matrix by means of preconditioning strategy,then propose a preconditioned version of GMRES-DR,i.e.,PGMRES-DR,which can effectively accelerate the convergence of GMRES-DR and reduce the number of matrix-vector products and CPU time,finally demonstrate the numerical benefits of PGMRES-DR algorithm in numerical experiments.On the other hand,thesis propose the PMGMRES-DR-SH algorithm for the PageRank problem with multiple damping factors.First,thesis apply the GMRES-DR-SH method for solving shifted linear systems to solve the PageRank problem with multiple damping factors,and adopt polynomial preconditioning technology and modification strategy to eliminate the phenomenon of “stagnation” and “near singularity” in the solution process of GMRES-DR-SH,and then propose the preconditioned and modified GMRESDR-SH algorithm,i.e.,PMGMRES-DR-SH,which can effectively accelerate the convergence of GMRES-DR-SH and reduce the number of matrix-vector products and CPU time,finally demonstrate the numerical benefits of PMGMRES-DR-SH algorithm in numerical experiments.PMGMRES-DR-SH can also be seen as the deflated version of PMGMRES-SH,which is used to solve the PageRank problem with multiple damping factors.PMGMRES-DR-SH recycles the spectral information of the preconditioned seed system by means of the deflated restarting strategy,so as to effectively improve the convergence of PMGMRES-SH method to solve the PageRank problem,especially when solving large-scale problems.