FOM accelerated by an extrapolation method for solving PageRank problems

摘要

This paper formulates the PageRank problem Ax=x into a consistent singular linear system (I−A)x=0, and applies the full orthogonalization method (FOM) to solve it. This singular system is characterized by index one, namely index(I−A)=1. We analyze the breakdown performance of FOM on a general singular linear system, and conclude that FOM can determine a solution if it converges, without any unfortunate breakdowns for our target problem. Then we propose to use a vector extrapolation method to speed up the convergence performance of FOM. This extrapolation procedure is based on Ritz values, which directly stems from the Arnoldi-Extrapolation algorithm (Wu and Wei, 2010). Eventually numerical experiments are presented to illustrate the effectiveness of our approaches.