基于切比雪夫多项式加速求解 PageRank 的类海森伯格算法

Abstract

Abstract:

In order to solve the PageRank problem, a new algorithm Hessenberg-Chebyshev is proposed by combining Hessenberg-type algorithm with Chebyshev acceleration technology. This algorithm improves the Hessenberg-type algorithm based on the acceleration technique of Chebyshev polynomial. The implementation and convergence analysis of the new algorithm are discussed in detail, and the effectiveness of the algorithm is verified by numerical experiments.

Key words: Hessenberg process, Chebyshev polynomials, iterative method, convergence, PageRank

CLC Number:

O241.6

Wang Qiongqiong, Tang Jia. Hessenberg-Type Algorithm for PageRank Acceleration Based on Chebyshev Polynomials[J].Acta mathematica scientia,Series A, 2025, 45(4): 1291-1300.

Trendmd

References

[1]	Page L, Brin S, Motwani R, Winograd T. The Pagerank Citation Ranking: Bringing Order to the Web. Palo Alto: Stanford InfoLab, 1999
[2]	Kamvar S D, Haveliwala T H, Manning C D, Golub G H. Extrapolation methods for accelerating PageRank computations// Proceedings of the 12th International Conference on World Wide Web, 2003: 261-270
[3]	Kamvar S, Haveliwala T, Golub G H. Adaptive methods for the computation of PageRank. Linear Algebra Appl, 2004, 3.6: 51-65
[4]	Langville A N, Meyer C D. Deeper inside pagerank. Internet Mathematics, 2004, 1(3): 335-380
[5]	Zhou T, Martinez-Baez E, Schenter G, et al. PageRank as a collective variable to study complex chemical transformations and their energy landscapes. The Journal of Chemical Physics, 2019, 1.0(13): 134102
[6]	Liu B, Jiang S, Zou Q. HITS-PR-HHblits: protein remote homology detection by combining PageRank and hyperlink-induced topic search. Briefings in Bioinformatics, 2020, 21(1): 298-308
[7]	Zhang M, Li X, Zhang L, et al. Boosting spectrum-based fault localization using pagerank// Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis, 2017: 261-272
[8]	Heyouni M, Sadok H. On a variable smoothing procedure for Krylov subspace methods. Linear Algebra and Its Applications, 1998, 2.8: 131-149
[9]	Golub G H, Greif C. An Arnoldi-type algorithm for computing page rank. BIT Numerical Mathematics, 2006, 46: 759-771
[10]	Wu G, Wei Y. A Power-Arnoldi algorithm for computing PageRank. Numerical Linear Algebra with Applications, 2007, 14(7): 521-546
[11]	Gu C, Wang W. An Arnoldi-Inout algorithm for computing PageRank problems. Journal of Computational and Applied Mathematics, 2017, 3.9: 219-229
[12]	Yin J F, Yin G J, Ng M. On adaptively accelerated Arnoldi method for computing PageRank. Numerical Linear Algebra with Applications, 2012, 19(1): 73-85
[13]	Sadok H. CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm. Numer Algorithms, 1999, 20(4): 303-321
[14]	Gu X M, Lei S L, Zhang K, et al. A Hessenberg-type algorithm for computing PageRank Problems. Numerical Algorithms, 2022, 89(4): 1845-1863
[15]	Hu Q Y, Gu X M, Wen C. Application of an extrapolation method in the Hessenberg algorithm for computing PageRank. J Supercomput, 2024, 80(15): 22836-22859
[16]	Wrigley H E. Accelerating the Jacobi method for solving simultaneous equations by Chebyshev extrapolation when the eigenvalues of the iteration matrix are complex. Comput J, 1963, 6(2): 169-176
[17]	Haveliwala T H, Kamvar S D. The Second Eigenvalue of the Google Matrix. Palo Alto: Stanford InfoLab, 2003
[18]	Miao C Q, Tan X Y. Accelerating the Arnoldi method via Chebyshev polynomials for computing PageRank. J Comput Appl Math, 2020, 3.7: 112891

Hessenberg-Type Algorithm for PageRank Acceleration Based on Chebyshev Polynomials

RichHTML

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0

[1]	Pengjie Liu, Hu Shao, Jiayi Li, Duanduan Dong. An Inertial Three-Term Conjugate Gradient Projection Method Based on BFGS Update [J]. Acta mathematica scientia,Series A, 2025, 45(5): 1698-1710.
[2]	Yu Dongmei, Liu Dayi. The Levenberg-Marquardt Algorithm for Solving the Generalized Complementarity Problems [J]. Acta mathematica scientia,Series A, 2025, 45(4): 1311-1326.
[3]	Wang Wujing, Zhu Meiling, Zhang Yongle. A New Projection Algorithm for Solving Quasimonotone Variational Inequality Problems and Fixed Point Problems [J]. Acta mathematica scientia,Series A, 2025, 45(1): 236-255.
[4]	Ma Changfeng, Xie Yajun, Bu Fan. The Tensor Scheme BCGSTAB Algorithm for Solving Stein Tensor Equations [J]. Acta mathematica scientia,Series A, 2024, 44(6): 1652-1664.
[5]	Wang Junjie. Symplectic Difference Scheme for the Space Fractional KGS Equations [J]. Acta mathematica scientia,Series A, 2024, 44(5): 1319-1334.
[6]	Yu Ting, Dong Ying. The Convergence Rate of the Fast Signal Diffusion Limit for a Three-Dimensional Keller-Segel-Stokes System [J]. Acta mathematica scientia,Series A, 2024, 44(4): 925-945.
[7]	Ma Xiaojun, Chen Fu, Jia Zhifu. Research on a Strong Convergence Theorem for Proximal Split Feasibility Problems with Non-Lipschitz Stepsizes [J]. Acta mathematica scientia,Series A, 2024, 44(4): 1052-1065.
[8]	Jian Jinbao, Dai Yu, Yin Jianghua. An Inertial Conjugate Gradient Projection Method for the Split Feasibility Problem [J]. Acta mathematica scientia,Series A, 2024, 44(4): 1066-1079.
[9]	Nie Jialin, Long Xianjun. A Golden Ratio Primal-Dual Algorithm for a Class of Nonsmooth Saddle Point Problems [J]. Acta mathematica scientia,Series A, 2024, 44(4): 1080-1091.
[10]	Zhang Xiao, Zhang Hongwu. Fractional Tikhonov Regularization Method for an Inverse Boundary Value Problem of the Fractional Elliptic Equation [J]. Acta mathematica scientia,Series A, 2024, 44(4): 978-993.
[11]	Zhang Jie, Sun Yiming, Liu Yongping. EC-tractability of Multivariate $\mathbb{L}_{\infty}$-approximation in Weighted Korobov Spaces [J]. Acta mathematica scientia,Series A, 2024, 44(3): 525-538.
[12]	Liu Hua, Basma Al-Shutnawi. On Convergence Sets of Power Series with Holomorphic Coefficients [J]. Acta mathematica scientia,Series A, 2024, 44(3): 563-574.
[13]	Wang Weimin, Yan Wei. Convergence Problem and Dispersive Blow-up for the Modified Kawahara Equation [J]. Acta mathematica scientia,Series A, 2024, 44(3): 595-608.
[14]	Liu Jinghua, Li Lin. Homeomorphic Solutions of Iterative Functional Equations [J]. Acta mathematica scientia,Series A, 2024, 44(2): 313-325.
[15]	Cai Yu, Zhou Guanghui. Global Convergence of a WYL Type Spectral Conjugate Gradient Method [J]. Acta mathematica scientia,Series A, 2024, 44(1): 173-184.