×

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
Software:
eigs; IRAM
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] 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
[3] 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
[4] 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
[5] Gleich, D. F., Pagerank beyond the web. Pagerank beyond the web, Comput. Sci., 57, 3 (2014) · Zbl 1336.05122
[6] 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
[7] 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
[8] Langville, A.; Meyer, C., Google’s PageRank and Beyond: The Science of the Search Engine Rankings (2006), Princeton University Press · Zbl 1104.68042
[9] 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
[10] 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
[11] L. Page, The pagerank citation ranking : bringing order to the web, Stanford Digital Libraries Working Paper 9(1) (1998) 1-14.
[12] 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
[13] 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
[14] 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)
[15] 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
[16] 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)
[17] 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.