求解PageRank问题的Arnoldi-PIO算法

Arnoldi-PIO algorithm for PageRank

PageRank算法能帮助用户快速、准确地在巨量杂乱无章的信息中检索出有用的信息.两步分裂迭代法是用幂法来修正内外分裂(power-inner-outer,PIO)迭代法以加速PageRank算法.基于两步分裂迭代法,将预处理思想运用于求解PageRank问题,提出了求解PageRank问题的深度重启的Arnoldi算法加速的两步分裂迭代法,然后对此算法的收敛性进行了证明.数值实验结果证明,该算法的计算速度要快于两步分裂迭代法.

The PageRank algorithm plays an important role in determining the impor- tance of Web pages. The power-inner-outer （PIO） method is a two-step splitting itera- tion framework that combines the inner-outer scheme with the classical power method to accelerate the computation of PageRank algorithm. This paper proposes an Arnoldi-PIO algorithm, which is a PIO iteration algorithm modified with the thick restarted Arnoldi method. Description and convergence of the proposed algorithm are discussed in details. Numerical results show efficiency and convergence behaviors of the algorithm.