Acceleration of the generalized FOM algorithm for computing PageRank

Yu Jin; Chun Wen; Zhao-Li Shen; Yu Jin; Chun Wen; Zhao-Li Shen

doi:10.3934/era.2022039

Electronic Research Archive

2022, Volume 30, Issue 2: 732-754. doi: 10.3934/era.2022039

Previous Article Next Article

Research article Special Issues

Acceleration of the generalized FOM algorithm for computing PageRank

Yu Jin ¹,
Chun Wen ^{1
,
,},
Zhao-Li Shen ^{2
,
,}

1.
School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, China
2.
College of Science, Sichuan Agricultural University, Ya'an 625000, China

Received: 14 December 2021 Revised: 07 February 2022 Accepted: 13 February 2022 Published: 28 February 2022

In this paper, a generalized full orthogonalization method (GFOM) based on weighted inner products is discussed for computing PageRank. In order to improve convergence performance, the GFOM algorithm is accelerated by two cheap methods respectively, one is the power method and the other is the extrapolation method based on Ritz values. Such that two new algorithms called GFOM-Power and GFOM-Extrapolation are proposed for computing PageRank. Their implementations and convergence analyses are studied in detail. Numerical experiments are used to show the efficiency of our proposed algorithms.
- PageRank,
- FOM,
- generalized FOM,
- power method,
- ritz values,
- extrapolation procedure
Citation: Yu Jin, Chun Wen, Zhao-Li Shen. Acceleration of the generalized FOM algorithm for computing PageRank[J]. Electronic Research Archive, 2022, 30(2): 732-754. doi: 10.3934/era.2022039

Related Papers:

Abstract

In this paper, a generalized full orthogonalization method (GFOM) based on weighted inner products is discussed for computing PageRank. In order to improve convergence performance, the GFOM algorithm is accelerated by two cheap methods respectively, one is the power method and the other is the extrapolation method based on Ritz values. Such that two new algorithms called GFOM-Power and GFOM-Extrapolation are proposed for computing PageRank. Their implementations and convergence analyses are studied in detail. Numerical experiments are used to show the efficiency of our proposed algorithms.

References

[1]	L. Page, S. Brin, R. Motwami, T. Winograd, The PageRank citation ranking: Bringing order to the web, Stanford Digital Library Technol. Proj., 1998. https://doi.org/10.1007/978-3-319-08789-4-10
[2]	I. C. Ipsen, T. M. Selee, PageRank computation, with special attention to dangling nodes, SIAM J. Matrix Anal. Appl., 29 (2008), 1281–1296. https://doi.org/10.1137/060664331 doi: 10.1137/060664331
[3]	A. Langville, C. Meyer, A survey of eigenvector methods for web information retrieval, SIAM Rev., 47 (2005), 135–161. https://doi.org/10.1137/S0036144503424786 doi: 10.1137/S0036144503424786
[4]	A. Langville, C. Meyer, Deeper inside PageRank, Internet Math., 1 (2004), 335–380. https://doi.org/10.1080/15427951.2004.10129091
[5]	G. H. Golub, C. F. Van Loan, Matrix Computations, 3$^{rd}$ edition, The Johns Hopkins University Press, Baltimore, London, 1996. https://doi.org/10.1007/978-1-4612-5118-7-5
[6]	S. Kamvar, T. Haveliwala, C. Manning, G. Golub, Extrapolation methods for accelerating PageRank computations, in Proceedings of the Twelfth Internatinal World Wide Web Conference, ACM Press, New York, (2003), 261–270. https://doi.org/10.1145/775152.775190
[7]	A. Sidi, Vector extrapolation methods with applications to solution of large systems of equations and to PageRank computations, Comput. Appl. Math., 56 (2008), 1–24. https://doi.org/10.1016/j.camwa.2007.11.027 doi: 10.1016/j.camwa.2007.11.027
[8]	X. Y. Tan, A new extrapolation method for PageRank computations, J. Comput. Appl. Math., 313 (2017), 383–392. https://doi.org/10.1016/j.cam.2016.08.034 doi: 10.1016/j.cam.2016.08.034
[9]	S. Cipolla, M. Redivo-Zaglia, F. Tudisco, Extrapolation methods for fixed-point multilinear PageRank computations, Numer. Linear Algebra Appl., 27 (2020), e2280. https://doi.org/10.1002/nla.2280 doi: 10.1002/nla.2280
[10]	D. Gleich, A. Gray, C. Greif, T. Lau, An inner-outer iteration for computing PageRank, SIAM J. Sci. Comput., 32 (2010), 349–371. https://doi.org/10.1137/080727397 doi: 10.1137/080727397
[11]	Z. Z. Bai, On convergence of the inner-outer iteration method for computing PageRank, Numer. Algebra Control Optim., 2 (2012), 855–862. https://doi.org/10.3934/naco.2012.2.855 doi: 10.3934/naco.2012.2.855
[12]	C. Q. Gu, F. Xie, K. Zhang, A two-step matrix splitting iteration for computing PageRank, J. Comput. Appl. Math., 278 (2015), 19–28. https://doi.org/10.1016/j.cam.2014.09.022 doi: 10.1016/j.cam.2014.09.022
[13]	C. Wen, T. Z. Huang, Z. L. Shen, A note on the two-step matrix splitting iteration for computing PageRank, J. Comput. Appl. Math., 315 (2017), 87–97. https://doi.org/10.1016/j.cam.2016.10.020 doi: 10.1016/j.cam.2016.10.020
[14]	Z. L. Tian, Y. Liu, Y. Zhang, Z. Y. Liu, M. Y. Tian, The general inner-outer iteration method based on regular splittings for the PageRank problem, Appl. Math. Comput., 356 (2019), 479–501. https://doi.org/10.1016/j.amc.2019.02.066 doi: 10.1016/j.amc.2019.02.066
[15]	J. F. Yin, G. J. Yin, M. Ng, On adaptively accelerated Arnoldi method for computing PageRank, Numer. Linear Algebra Appl., 19 (2012), 73–85. https://doi.org/10.1002/nla.789 doi: 10.1002/nla.789
[16]	C. Wen, Q. Y. Hu, G. J. Yin, X. M. Gu, Z. L. Shen, An adaptive Power-GArnoldi algorithm for computing PageRank, J. Comput. Appl. Math., 386 (2021), 113209. https://doi.org/10.1016/j.cam.2020.113209 doi: 10.1016/j.cam.2020.113209
[17]	C. Wen, Q. Y. Hu, B. Y. Pu, Y. Y. Huang, Acceleration of an adaptive generalized Arnoldi method for computing PageRank, AIMS Math., 6 (2021), 893–907. https://doi.org/10.3934/math.2021053 doi: 10.3934/math.2021053
[18]	H. D. Sterck, T. A. Manteuffel, S. F. McCormick, Q. Nguyen, J. Ruge, Multilevel adaptive aggregation for Markov chains, with application to web ranking, SIAM J. Sci. Comput., 30 (2008), 2235–2262. https://doi.org/10.1137/070685142 doi: 10.1137/070685142
[19]	Z. L. Shen, T. Z. Huang, B. Carpentieri, C. Wen, X. M. Gu, Block-accelerated aggregation multigrid for Markov chains with application to PageRank problems, Commun. Nonlinear. Sci. Numer. Simulat., 59 (2018), 472–487. https://doi.org/10.1016/j.cnsns.2017.11.031 doi: 10.1016/j.cnsns.2017.11.031
[20]	G. H. Golub, C. Greif, An Arnoldi-type algorithm for computing PageRank, BIT Numer. Math., 46 (2006), 759–771. https://doi.org/10.1007/s10543-006-0091-y doi: 10.1007/s10543-006-0091-y
[21]	Z. X. Jia, Refined iterative algorithms based on Arnoldi's process for large unsymmetric eigenproblems, Linear Algebra Appl., 259 (1997), 1–23. https://doi.org/10.1016/S0024-3795(96)00238-8 doi: 10.1016/S0024-3795(96)00238-8
[22]	G. Wu, Y. M. Wei, A Power-Arnoldi algorithm for computing PageRank, Numer. Linear Algebra Appl., 14 (2007), 521–546. https://doi.org/10.1002/nla.531 doi: 10.1002/nla.531
[23]	R. B. Morgan, M. Zeng, A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity, Linear Algebra Appl., 415 (2006), 96–113. https://doi.org/10.1016/j.laa.2005.07.024 doi: 10.1016/j.laa.2005.07.024
[24]	Q. Y. Hu, C. Wen, T. Z. Huang, Z. L. Shen, X. M. Gu, A variant of the Power-Arnoldi algorithm for computing PageRank, J. Comput. Appl. Math., 381 (2021), 113034. https://doi.org/10.1016/j.cam.2020.113034 doi: 10.1016/j.cam.2020.113034
[25]	G. Wu, Y. M. Wei, An Arnoldi-Extrapolation algorithm for computing PageRank, J. Comput. Appl. Math., 234 (2010), 3196–3212. https://doi.org/10.1016/j.cam.2010.02.009 doi: 10.1016/j.cam.2010.02.009
[26]	H. F. Zhang, T. Z. Huang, C. Wen, Z. L. Shen, FOM accelerated by an extrapolation method for solving PageRank problems, J. Comput. Appl. Math., 296 (2016), 397–409. https://doi.org/10.1016/j.cam.2015.09.027 doi: 10.1016/j.cam.2015.09.027
[27]	C. Q. Gu, X. L. Jiang, C. C. Shao, Z. B. Chen, A GMRES-Power algorithm for computing PageRank problems, J. Comput. Appl. Math., 343 (2018), 113–123. https://doi.org/10.1016/j.cam.2018.03.017 doi: 10.1016/j.cam.2018.03.017
[28]	Y. Saad, M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986), 857–869. https://doi.org/10.1137/0907058 doi: 10.1137/0907058
[29]	Z. L. Shen, T. Z. Huang, B. Carpentieri, X. M. Gu, C. Wen, An efficient elimination strategy for solving PageRank problems, Appl. Math. Comput., 298 (2017), 111–122. https://doi.org/10.1016/j.amc.2016.10.031 doi: 10.1016/j.amc.2016.10.031
[30]	Z. L. Shen, T. Z. Huang, B. Carpentieri, X. M. Gu, C. Wen, X. Y. Tan, Off-diagonal low-rank preconditioner for difficult PageRank problems, J. Comput. Appl. Math., 346 (2019), 456–470. https://doi.org/10.1016/j.cam.2018.07.015 doi: 10.1016/j.cam.2018.07.015
[31]	B. Y. Pu, T. Z. Huang, C. Wen, A preconditioned and extrapolation-accelerated GMRES method for PageRank, Appl. Math. Lett., 37 (2014), 95–100. https://doi.org/10.1016/j.aml.2014.05.017 doi: 10.1016/j.aml.2014.05.017
[32]	C. Q. Miao, X. Y. Tan, Accelerating the Arnoldi method via Chebyshev polynomials for computing PageRank, J. Comput. Appl. Math., 377 (2020), 112891. https://doi.org/10.1016/j.cam.2020.112891 doi: 10.1016/j.cam.2020.112891
[33]	X. M. Gu, S. L. Lei, K. Zhang, Z. L. Shen, C. Wen, B. Carpentieri, A Hessenberg-type algorithm for computing PageRank problems, Numer. Algorithms, 2021. https://doi.org/10.1007/s11075-021-01175-w
[34]	Z. L. Shen, H. Yang, B. Carpentieri, X. M. Gu, C. Wen, A preconditioned variant of the refined Arnoldi method for computing PageRank eigenvectors, Symmetry, 13 (2021), 1327. https://doi.org/10.3390/sym13081327 doi: 10.3390/sym13081327
[35]	Z. L. Tian, Y. Zhang, J. X. Wang, C. Q. Gu, Several relaxed iteration methods for computing PageRank, J. Comput. Appl. Math., 388 (2021), 113295. https://doi.org/10.1016/j.cam.2020.113295 doi: 10.1016/j.cam.2020.113295
[36]	Z. L. Tian, Z. Y. Liu, Y. H. Dong, The coupled iteration algorithms for computing PageRank, Numer. Algor., (2021), 1–15. https://doi.org/10.1007/s11075-021-01166-x
[37]	Y. H. Feng, J. X. You, Y. X. Dong, An extrapolation iteration and its lumped type iteration for computing PageRank, Bull. Iran. Math. Soc., (2021), 1–8. https://doi.org/10.1007/s41980-021-00656-x
[38]	Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, 2003.
[39]	SuiteSparse Matrix Collection, Available from: https://sparse.tamu.edu/.
[40]	T. Haveliwala, S. Kamvar, The second eigenvalue of the Google matrix, in Proceedings of the Twelfth International World Wide Web of Conference, 2003.
[41]	R. Horn, S. Serra-Capizzano, A general setting for the parametric Google matrix, Internet Math., 3 (2008), 385–411. https://doi.org/10.1080/15427951.2006.10129131 doi: 10.1080/15427951.2006.10129131

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)