A Preconditioned and Shifted GMRES Algorithm for the PageRank Problem with Multiple Damping Factors
Gang Wu, Yanchun Wang, Xiaoqing Jin · SIAM Journal on Scientific Computing · 2012
Google has become one of the most popular and successful search engines in recent years. Google's success can be attributed to its simple and elegant algorithm: PageRank. In practice, one often needs to solve the PageRank problem with multiple damping factors or with multiple damping factors and multiple personalization vectors. The conventional PageRank algorithm has to solve these problems one by one. The shifted GMRES$(m)$ algorithm can be used to solve them in the same search subspace. However, there are two disadvantages to this algorithm. The first is “near singularity,” and the second is “stagnation.” In this paper, we first present a modified and shifted GMRES$(m)$ algorithm to deal with the problem of near singularity. In order to overcome the drawback of stagnation and to improve convergence, we propose a polynomial preconditioner for the modified algorithm. We show that the resulting algorithm can circumvent the drawbacks of near singularity and stagnation that occur in its original counterpart. Finally, we consider how to solve the PageRank problem with multiple damping factors and multiple personalization vectors using a preconditioned and shifted block GMRES$(m)$ algorithm. Numerical experiments illustrate the efficiency of our new algorithms, as well as their theoretical properties.