# zbMATH — the first resource for mathematics

A preprocessed multi-step splitting iteration for computing PageRank. (English) Zbl 1427.65046
Summary: The PageRank algorithm plays an important role in determining the importance of Web pages. The multi-step splitting iteration (MSPI) method for calculating the PageRank problem is an iterative framework of combining the multi-step classical power method with the inner-outer method. In this paper, we present a preprocessed MSPI method called the Arnoldi-MSPI iteration, which is the MSPI method modified with the thick restarted Arnoldi algorithm. The implementation and convergence of the new method are discussed in detail. Numerical experiments are given to show that our method has a good computational effect when the damping factor is close to 1.

##### MSC:
 65F15 Numerical computation of eigenvalues and eigenvectors of matrices 65F10 Iterative numerical methods for linear systems 68M11 Internet topics
eigs; IRAM
Full Text:
##### References:
  Arnoldi, W. E., The principle of minimized iterations in the solution of the matrix eigenvalue problem. The principle of minimized iterations in the solution of the matrix eigenvalue problem, Q. Appl. Math., 9, 17-29 (1951) · Zbl 0042.12801  Bai, Z.; Golub, G. H.; Ng, M. K., Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. matrix Anal. Appl., 24, 603-626 (2003) · Zbl 1036.65032  Bai, Z., On convergence of the inner-outer iteration method for computing pagerank. On convergence of the inner-outer iteration method for computing pagerank, Numer. Algebra Control Optim., 2, 4, 855-862 (2013) · Zbl 1264.65041  Gleich, D. F.; Gray, A. P.; Greif, C.; etal., An inner-outer iteration for computing pagerank. An inner-outer iteration for computing pagerank, SIAM J. Sci. Comput., 32, 1, 349-371 (2007) · Zbl 1209.65043  Gleich, D. F., Pagerank beyond the web. Pagerank beyond the web, Comput. Sci., 57, 3 (2014) · Zbl 1336.05122  Gu, C.; Xie, F.; Zhang, K., A two-step matrix splitting iteration for computing pagerank. A two-step matrix splitting iteration for computing pagerank, J. Comput. Appl. Math., 278, 19-28 (2015) · Zbl 1304.65132  Gu, C.; Ma, X., A multiple step power modifying inner-outer iteration for computing pagerank. A multiple step power modifying inner-outer iteration for computing pagerank, Commun. Appl. Math. Comput., 28, 454-460 (2014) · Zbl 1324.65062  Langville, A.; Meyer, C., Google’s PageRank and Beyond: The Science of the Search Engine Rankings (2006), Princeton University Press · Zbl 1104.68042  Morgan, R., On restarting the Arnoldi method for large nonsymmetric eigenvalue problems. On restarting the Arnoldi method for large nonsymmetric eigenvalue problems, Math. Comput. Am. Math. Soc., 65, 215, 1213-1230 (1996) · Zbl 0857.65041  Morgan, R.; Zeng, M., A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity. A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity, Linear Algebra Appl., 415, 1, 96-113 (2006) · Zbl 1088.65033  L. Page, The pagerank citation ranking : bringing order to the web, Stanford Digital Libraries Working Paper 9(1) (1998) 1-14.  Saad, Y., Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems. Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems, Math. Comput., 42, 166, 567-588 (1984) · Zbl 0539.65013  Sorensen, D., Implicit application of polynomial filters in a k-step Arnoldi method[J]. Implicit application of polynomial filters in a k-step Arnoldi method[J], Siam Journal on Matrix Analysis and Applications, 13, 1, 357-385 (1992) · Zbl 0763.65025  Haveliwala, T.; Kamvar, S., The second eigenvalue of the google matrix. The second eigenvalue of the google matrix, Proceedings of the Twelfth International World Wide Web of Conference (2003)  Wu, G.; Wei, Y., A Power-Arnoldi algorithm for computing pagerank. A Power-Arnoldi algorithm for computing pagerank, Numer. Linear Algebra Appl., 14, 7, 521-546 (2010) · Zbl 1199.65125  Wu, G.; Wei, Y., Arnoldi versus GMRES for computing pagerank: A theoretical contribution to google’s pagerank problem[j]. Arnoldi versus GMRES for computing pagerank: A theoretical contribution to google’s pagerank problem[j], ACM Trans. Inf. Syst. (TOIS), 28, 3, 1-28 (2010)  Saad, Y., Numerical Methods for Large Eigenvalue Problems (1992), Manchester University Press · Zbl 0991.65039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.