On adaptively accelerated Arnoldi method for computing PageRank. (English) Zbl 1274.65109
The authors present a generalized refined Arnoldi method based on the weighted inner product for computing PageRank. To accelerate the convergence for computing PageRank, they adaptively change the weighted least squares problem according to the component of the residual and then use the generalized Arnoldi method to find the approximate PageRank vector. When the damping factor is close to 1, their numerical results show that their new approach converges faster and better than the known methods.
Reviewer: Yi Min Wei (Shanghai)
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65F50 | Computational methods for sparse matrices |
| 68P10 | Searching and sorting |
Keywords:
PageRank; eigenvalue problem; power method; Arnoldi process; weighted least squares problem; convergence; numerical resultsReferences:
| [1] | Saad, Numerical Methods for Large Eigenvalue Problems (1992) · Zbl 1242.65068 |
| [2] | Kamvar SD Haveliwala TH Manning CD Golub GH Exploiting the block structure of the web for computing PageRank Technical Report, SCCM-03-02 2003 |
| [3] | De Sterck, Multilevel adaptive aggregation for markov chains, with application to web ranking, SIAM Journal on Scientific Computing 30 pp 2235– (2008) · Zbl 1173.65028 · doi:10.1137/070685142 |
| [4] | Langville, A reordering for the PageRank problem, SIAM Journal on Scientific Computing 27 pp 2112– (2006) · Zbl 1103.65048 · doi:10.1137/040607551 |
| [5] | Berkhin, A survey on PageRank computing, Internet Mathematics 2 pp 73– (2005) · Zbl 1100.68504 · doi:10.1080/15427951.2005.10129098 |
| [6] | Langville, Deeper inside PageRank, Internet Mathematics 1 pp 335– (2005) · Zbl 1098.68010 · doi:10.1080/15427951.2004.10129091 |
| [7] | Elden L 2003 A note on the eigenvalues of the Google matrix, Report LiTH-MAT-R-04-01 |
| [8] | Langville AN Meyer CD 2003 Fiddling with PageRank, Technical Report |
| [9] | Kamvar, Proceedings of the Twelfth International World Wide Web Conference (2003) |
| [10] | Kamvar, Adaptive methods for the computation of PageRank, Linear Algebra and its Applications 386 pp 51– (2004) · Zbl 1091.68044 · doi:10.1016/j.laa.2003.12.008 |
| [11] | Golub, An Arnoldi-type algorithm for computing PageRank, BIT Numerical Mathematics 46 pp 759– (2006) · Zbl 1105.65034 · doi:10.1007/s10543-006-0091-y |
| [12] | Gang, A Power-Arnoldi algorithm for computing PageRank, Numerical Linear Algebra with Applications 14 pp 521– (2007) · Zbl 1199.65125 · doi:10.1002/nla.531 |
| [13] | Essai, Weighted FOM and GMRES for solving nonsymmetric linear systems, Numerical Algorithms 18 pp 277– (1998) · Zbl 0926.65036 · doi:10.1023/A:1019177600806 |
| [14] | Saberi Najafi, Weighted restarting method in the weighted Arnoldi algorithm for computing the eigenvalues of a nonsymmetric matrix, Applied Mathematics and Computation 175 pp 1276– (2006) · Zbl 1094.65029 · doi:10.1016/j.amc.2005.08.035 |
| [15] | Arnoldi, The principle of minimized iteration in the solution of the matrix eigenvalue problem, Quarterly of Applied Mathematics 9 pp 17– (1951) · Zbl 0042.12801 · doi:10.1090/qam/42792 |
| [16] | Saad, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific Computing 7 pp 856– (1986) · Zbl 0599.65018 · doi:10.1137/0907058 |
| [17] | Lehoucq, Deflation Techniques for an Implicitly Restarted Arnoldi Iteration, SIAM Journal on Scientific Computing 17 pp 789– (1996) · Zbl 0863.65016 |
| [18] | Sorensen DC 1995 Implicitly restarted Arnoldi/Lanczos Methods for Large Scale Eigenvalue Calculations |
| [19] | Jia, Refined iterative algorithms based on Arnoldi’s process for large unsymmetric eigenproblems, Linear Algebra and its Applications 259 pp 1– (1997) · Zbl 0877.65018 · doi:10.1016/S0024-3795(96)00238-8 |
| [20] | Philippe, Numerical Methods in Markov Chain Modeling, Operations Research 40 pp 1156– (1992) · Zbl 0764.65095 · doi:10.1287/opre.40.6.1156 |
| [21] | De Sterck, Recursively accelerated multilevel aggregation for Markov Chains, SIAM Journal on Scientific Computing 32 pp 1652– (2010) · Zbl 1213.65018 · doi:10.1137/090770114 |
| [22] | Treister, Square and stretch multigrid for stochastic matrix eigenproblems, Numerical Linear Algebra Appl 17 pp 229– (2010) · Zbl 1240.65124 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
