A preconditioned and extrapolation-accelerated GMRES method for pagerank. (English) Zbl 1314.65057
Summary: We propose and analyze GMRES-type methods for the PageRank computation. However, GMRES may converge very slowly or sometimes even diverge or break down when the damping factor is close to 1 and the dimension of the search subspace is low. We propose two strategies: preconditioning and vector extrapolation accelerating, to improve the convergence rate of the GMRES method. Theoretical analysis demonstrate the efficiency of the proposed strategies and numerical experiments show that the performance of the proposed methods is very much better than that of the traditional methods for PageRank problems.
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65F08 | Preconditioners for iterative methods |
| 65F10 | Iterative numerical methods for linear systems |
| 68P10 | Searching and sorting |
References:
| [2] | Sauer, T., Numerical Analysis (2005), Addison Wesley Publication: Addison Wesley Publication USA |
| [3] | Sidi, A., Vector extrapolation methods with applications to solution of large systems of equations and to PageRank computations, Comput. Math. Appl., 56, 1-24 (2008) · Zbl 1145.65312 |
| [4] | Wu, G.; Wei, Y., An Arnoldi-extrapolation algorithm for computing PageRank, J. Comput. Appl. Math., 234, 3196-3212 (2010) · Zbl 1201.65059 |
| [5] | Golub, G. H.; Greif, C., An Arnoldi-type algorithm for computing PageRank, BIT, 46, 759-771 (2006) · Zbl 1105.65034 |
| [6] | Gleich, D.; Gray, A.; Greif, C.; Lau, T., An inner-outer iteration for computing PageRank, SIAM J. Sci. Comput., 32, 349-371 (2010) · Zbl 1209.65043 |
| [7] | Langville, A. N.; Meyer, C. D., Google’s PageRank and Beyond: the Science of Search Engine Rankings (2006), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 1104.68042 |
| [8] | Wu, G.; Wei, Y., Arnoldi versus GMRES for computing pageRank: a theoretical contribution to Google’s pageRank problem, ACM Trans. Inf. Syst., 28, 3 (2010), Article No. 11 |
| [9] | Saad, Y.; Schultz, M. H., GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statistical Comput., 7, 856-869 (1986) · Zbl 0599.65018 |
| [10] | Wu, G.; Wang, Y. C.; Jin, X. Q., A preconditioned and shifted GMRES algorithm for the PageRank problem with multiple damping factors, SIAM J. Sci. Comput., 34, 5, 2558-2575 (2012) · Zbl 1263.65037 |
| [11] | Sidi, A., Review of two vector extrapolation methods of polynomial type with applications to large-scale problems, J. Comput. Sci., 3, 3, 92-101 (2012) |
| [12] | Cabay, S.; Jackson, L. W., A polynomial extrapolation method for finding limits and antilimits of vector sequences, SIAM J. Numer. Anal., 13, 734-752 (1976) · Zbl 0359.65029 |
| [13] | Eddy, P. R., Extrapolating to the limit of a vector sequence, (Wang, P. C.C., Information Linkage Between Applied Mathematics and Industry (1979), Academic Press: Academic Press New York), 387-396 |
| [14] | Mes˘ina, M., Convergence acceleration for the iterative solution of the equations \(X = A X + f\), Comput. Methods Appl. Mech. Engrg., 10, 165-173 (1977) · Zbl 0344.65019 |
| [15] | Brezinski, C., Généralisations de la transformation de Shanks, de la table de Padé, et de \(1, \epsilon \)-algorithme, Calcolo, 11, 317-360 (1975) · Zbl 0329.65006 |
| [16] | Wynn, P., Accelerated techniques for iterated vector and matrix problems, Math. Comp., 16, 301-322 (1962) · Zbl 0105.10302 |
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.
