Shifted power-GMRES method accelerated by extrapolation for solving PageRank with multiple damping factors

Highlights：

• It derives the efficient implementation of the Power method such that the number of matrix-vector products required keeps constant with the increase of the number of damping factors. We call this method as the shifted Power method. This method can solve the PageRank problem with multiple damping factors much faster than the ordinary Power method, and the advantage of the shifted Power method over the ordinary one will be enlarged when computations with more damping factors and larger damping factors are needed. As far as we know, this is the first time such an efficient implementation of the Power method is presented for this problem class or for general shifted linear systems.

• It demonstrates the collinearity of the residual vectors of all the linear systems corresponding to the case of using the shifted Power method to solve this problem class. This is an important result as it is the basis of constructing hybrid method that combines the shifted Power method with shifted Krylov subspace methods for solving this problem class.

• It studies the possibility of constructing efficient implementations of other stationary iterative methods such that they can outperform the shifted Power method for this problem class. The result is that: the shifted Power method seems to be the best stationary solver for this problem class.

• It combines the shifted Power method with the shifted GMRES method, and presents a simple but effective seed system choosing strategy for solving this problem class. It studies the parameter-settings of the resulting shifted-Power-GMRES method, and gives an advisable suggestion. This method performs much better than the shifted-Power method and the shifted-GMRES method. This is also the first time that a hybrid method formed by stationary methods and non-stationary methods is proposed for solving the considered problem class.

• It proposes a Anderson-type extrapolation technique. The theoretical analysis shows the good potential of this technique for further accelerating the shifted-Power-GMRES method, and this is verified by numerical experiments.