The success of Google’s search engine for retrieving Web information can be attributed to its simple and elegant PageRank algorithm [L. Page, S. Brin, R. Motwami, and T. Winograd, The PageRank Citation Ranking: Bring Order to the Web, Technical report, Computer Science Department, Stanford University, (1998)]. Since the Web can be viewed as a directed graph based on the hyperlink structure, which can be represented with an \( n\times n \) matrix \( P \) whose element \( p_{ij} \) is the probability of moving from page \( i \) to page \( j \) in one step, the PageRank problem can be reformulated as a large sparse linear system of the form \[ (I-\alpha P^T)\mathbf{x} = \mathbf{b}, \] where \( I \) is the \( n\times n \) identity matrix, \( \alpha\in(0,1) \) is called the “damping factor”, and \( \mathbf{b} \) is called the “personalization vector”. In applications like e.g. the design of anti-spam mechanisms [H. Zhang et al., “Making Eigenvector-Based Reputation System Robust to Collusion”, http://www.stanford.edu/group/reputation/WAW-adapt.ps (2004)] and deterministic PageRank problems [P. G. Constantine and D. F. Gleich, Internet Math. 6, No. 2, 189–236 (2009; Zbl 1210.68135)], one may have to deal with the PageRank problem with multiple damping factors or with the PageRank problem with multiple damping factors and multiple personalization vectors.
The first part of the paper deals with the PageRank problem with multiple damping factors: \[ (I-\alpha_i P^T)\mathbf{x}_i = \mathbf{b}, \quad i=1,2,\ldots,k, \] where the first linear system (\( i=1 \)) is called the “seed system” and the others (\( i=2,\ldots,k \)) are called the “additional systems”. In this respect, the shifted GMRES(m) algorithm, proposed by A. Frommer and U. Glässner [SIAM J. Sci. Comput. 19, No. 1, 15–26 (1998; Zbl 0912.65023)], can be applied to solve the linear systems in the same search subspace. The key idea is to run the standard GMRES(m) algorithm on the seed system, and then to generate approximate solutions to the additional systems imposing collinearity with the computed seed residual.
There are, however, two disadvantages to this shifted GMRES(m) algorithm. The first problem is that the projected linear systems involved in the solution of the additional systems will become more and more ill-conditioned as the seed system converges. As a result, the shifted GMRES(m) algorithm may suffer from “near singularity” when solving the additional systems. For this reason, a small modification of the shifted GMRES(m) is presented, leading to projected linear systems which are mathematically equivalent with the ones from the original shifted GMRES(m) algorithm, but for which the condition number can be expected to be much smaller.
The second problem is that the standard GMRES(m) algorithm, to solve the seed system, may suffer from “stagnation”. For this reason, certain polynomial preconditioners \( \mathcal{M}_i=p_{\ell}(\alpha_iP^T) \) of fixed degree \(\ell\) are proposed, leading to the preconditioned linear systems: \[ (I-\alpha_i P^T)\mathcal{M}_i\mathbf{u}_i = \mathbf{b}, \quad i=1,2,\ldots,k, \] with \( \mathbf{x}_i=\mathcal{M}_i\mathbf{u}_i \). It is then shown that the difficulty of stagnation that occurs in the original algorithm can be circumvented whenever the degree \( \ell \) is sufficiently large.
By means of a block generalization of the GMRES algorithm [Y. Saad, Iterative methods for sparse linear systems. 2nd ed. Philadelphia, PA: SIAM Society for Industrial and Applied Mathematics (2003; Zbl 1031.65046)], the results for the case of the PageRank problem with multiple damping factors are generalized in the second part of the paper to the case of the PageRank problem with multiple damping factors and multiple personalization vectors: \[ (I-\alpha_i P^T)X_i = B, \quad i=1,2,\ldots,k, \] where \( B = [\mathbf{b}_1,\mathbf{b}_2,\ldots,\mathbf{b}_p] \) and \( X_i = [\mathbf{x}_1^i,\mathbf{x}_2^i,\ldots,\mathbf{x}_p^i] \).
The paper concludes with several numerical experiments to illustrate the efficiency and theoretical properties of the new algorithms.