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

数学物理学报 ›› 2025, Vol. 45 ›› Issue (4): 1291-1300.

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

王琼琼,唐嘉^*()

福建师范大学数学与统计学院福州 350007

收稿日期:2024-08-23 修回日期:2025-01-13 出版日期:2025-08-26 发布日期:2025-08-01
通讯作者: *E-mail: tang_jia@126.com
基金资助:
国家自然科学基金(12371378)

Hessenberg-Type Algorithm for PageRank Acceleration Based on Chebyshev Polynomials

Wang Qiongqiong,Tang Jia^*()

School of Mathematics and Statistics, Fujian Normal University, Fuzhou 350007

Received:2024-08-23 Revised:2025-01-13 Online:2025-08-26 Published:2025-08-01
Supported by:
NSFC(12371378)

摘要/Abstract

摘要：

该文通过将类海森伯格算法与 Chebyshev 加速技术相结合, 提出了一种求解 PageRank 问题的海森伯格切比雪夫加速算法. 并详细讨论了新算法的收敛性分析, 数值实验表明该算法在极为宽泛的阻尼系数范围内具有出色的数值结果, 尤其是在高阻尼系数下表现出了相较于其它算法表现出了显著的优势.

关键词: Hessenberg 算法, Chebyshev 加速, 迭代法, 收敛性, PageRank

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

中图分类号:

O241.6

王琼琼, 唐嘉. 基于切比雪夫多项式加速求解 PageRank 的类海森伯格算法[J]. 数学物理学报, 2025, 45(4): 1291-1300.

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.

图/表 6

表1

表2

表3

图1

图2

表4

参考文献 18

[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