In this paper, a generalized full orthogonalization method (GFOM) based on weighted inner products is discussed for computing PageRank. In order to improve convergence performance, the GFOM algorithm is accelerated by two cheap methods respectively, one is the power method and the other is the extrapolation method based on Ritz values. Such that two new algorithms called GFOM-Power and GFOM-Extrapolation are proposed for computing PageRank. Their implementations and convergence analyses are studied in detail. Numerical experiments are used to show the efficiency of our proposed algorithms.

Several Krylov subspace methods are based on the Arnoldi process, such as the full orthogonalization method (FOM), GMRES, and in general all the Arnoldi-type methods. In fact, the Arnoldi process is an algorithm for building an orthogonal basis of the Krylov subspace. Once the inner products are performed inexactly, which cannot be avoided due to round-off errors, the orthogonality of Arnoldi vectors is lost. In this paper, we presented a new analysis framework to show how the inexact inner products influence the Krylov subspace methods that are based on the Arnoldi process. A new metric was developed to quantify the inexactness of the Arnoldi process with inexact inner products. In addition, the proposed metric can be used to approximately estimate the loss of orthogonality in the practical use of the Arnoldi process. The discrepancy in residual gaps between Krylov subspace methods employing inexact inner products and their corresponding exact counterparts was discussed. Numerical experiments on several examples were reported to illustrate our theoretical findings and final observations were presented.

The PageRank model is widely utilized for analyzing a variety of scientific issues beyond its original application in modeling web search engines. In recent years, considerable research effort has focused on developing high-performance iterative methods to solve this model, particularly when the dimension is exceedingly large. However, due to the ever-increasing extent and size of data networks in various applications, the computational requirements of the PageRank model continue to grow. This has led to the development of new techniques that aim to reduce the computational complexity required for the solution. In this paper, we present a recursive 5-type lumping algorithm combined with a two-stage elimination strategy that leverage characteristics about the nonzero structure of the underlying network and the nonzero values of the PageRank coefficient matrix. This method reduces the initial PageRank problem to the solution of a remarkably smaller and sparser linear system. As a result, it leads to significant cost reductions for computing PageRank solutions, particularly in scenarios involving large and/or multiple damping factors. Numerical experiments conducted on over 50 real-world networks demonstrate that the proposed methods can effectively exploit characteristics of PageRank problems for efficient computations.