A Modified Multi-Splitting Iterative Method With the Restarted GMRES to Solve the PageRank Problem

XIAO Wenke; CHEN Xingding

doi:10.21656/1000-0887.420210

Volume 43 Issue 3

Mar. 2022

Turn off MathJax

Article Contents

Article Navigation > Applied Mathematics and Mechanics > 2022 > 43(3): 330-340

XIAO Wenke, CHEN Xingding. A Modified Multi-Splitting Iterative Method With the Restarted GMRES to Solve the PageRank Problem[J]. Applied Mathematics and Mechanics, 2022, 43(3): 330-340. doi: 10.21656/1000-0887.420210

Citation:

PDF( 5463 KB)

A Modified Multi-Splitting Iterative Method With the Restarted GMRES to Solve the PageRank Problem

doi: 10.21656/1000-0887.420210

XIAO Wenke,
CHEN Xingding^,

School of Mathematics and Statistics, Beijing Technology and Business University, Beijing 100048, P.R.China

Received Date: 2021-07-26
Accepted Date: 2021-07-26
Rev Recd Date: 2021-11-05

Available Online: 2022-02-11

Publish Date: 2022-03-08

Abstract

Abstract

The PageRank algorithm has become the core technology for web search engines. For the linear equations derived from the PageRank problem, firstly, the restarted GMRES (generalized minimal residual) method of the Krylov subspace methods was combined with the multi-splitting iterative method, and a modified multi-splitting iterative method with the restarted GMRES was proposed. Then, the detailed calculating process and the convergence analysis of this new algorithm were given. Finally, the effectiveness of the algorithm was demonstrated through some numerical experiments.
- PageRank,
- restarted GMRES,
- multi-splitting iterative method,
- convergence

FullText(HTML)

References(16)

References

[1]	BRIN S, PAGE L. The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks and ISDN Systems, 1998, 30: 107-117. doi: 10.1016/S0169-7552(98)00110-X
[2]	KAMVAR S D, HAVELIWALA T H, MANNING C D, et al. Extrapolation methods for accelerating PageRank computations[C]//Proceedings of the 12th International Conference on World Wide Web. New York: Association for Computing Machinery, 2003: 261-270.
[3]	BRIN S, PAGE L, MOTWANI R, et al. The PageRank citation ranking: bringing order to the web[R]. Stanford InfoLab, 1998.
[4]	顾传青, 王磊. 一类修正的幂外推法加速PageRank计算[J]. 上海大学学报(自然科学版), 2013, 19(2): 150-153. (GU Chuanqing, WANG Lei. A class of modified power-extrapolation methods for speeding up PageRank computation[J]. Journal of Shanghai University (Natural Science), 2013, 19(2): 150-153.(in Chinese)
[5]	GLEICH D F, GRAY A P, GREIF C, et al. An inner-outer iteration for computing PageRank[J]. SIAM Journal on Scientific Computing, 2010, 32(1): 349-371. doi: 10.1137/080727397
[6]	GU C, XIE F, ZHANG K. A two-step matrix splitting iteration for computing PageRank[J]. Journal of Computational and Applied Mathematics, 2015, 278: 19-28. doi: 10.1016/j.cam.2014.09.022
[7]	潘春平. 关于PageRank的广义二级分裂迭代方法[J]. 计算数学, 2014, 36(4): 95-104. (PAN Chunping. On generalized two-stage iterative method for computing PageRank[J]. Mathematica Numerica Sinica, 2014, 36(4): 95-104.(in Chinese)
[8]	陈星玎, 李思雨. 求解PageRank的多步幂法修正的广义二级分裂迭代法[J]. 数值计算与计算机应用, 2018, 39(4): 243-252. (CHEN Xingding, LI Siyu. A generalized two-step splitting iterative method modified with the multi-step power method for computing PageRank[J]. Journal on Numerical Methods and Computer Applications, 2018, 39(4): 243-252.(in Chinese) doi: 10.12288/szjs.2018.4.243
[9]	GU C, WANG L. On the multi-splitting iteration method for computing PageRank[J]. Journal of Applied Mathematics and Computing, 2013, 42: 479-490. doi: 10.1007/s12190-013-0645-5
[10]	顾传青, 邵晨晨. 求解PageRank问题的GMRES-Inout方法[J]. 上海大学学报(自然科学版), 2017, 23(2): 179-184. (GU Chuanqing, SHAO Chenchen. A GMRES-Inout algorithm for computing PageRank problems[J]. Journal of Shanghai University (Natural Science), 2017, 23(2): 179-184.(in Chinese)
[11]	邱志红, 顾传青. 求解PageRank问题的GMRES重启的松弛两步分裂法[J]. 高等学校计算数学学报, 2018, 40(4): 331-345. (QIU Zhihong, GU Chuanqing. A GMRES-RPIO algorithm for computing PageRank problem[J]. Numerical Mathematics a Journal of Chinese Universities, 2018, 40(4): 331-345.(in Chinese)
[12]	顾传青, 付友花, 王金波. 求解PageRank问题的Arnoldi松弛两步分裂算法[J]. 上海大学学报(自然科学版), 2019, 25(4): 484-492. (GU Chuanqing, FU Youhua, WANG Jinbo. Arnoldi-RPIO algorithm for computing PageRank problems[J]. Journal of Shanghai University (Natural Science), 2019, 25(4): 484-492.(in Chinese)
[13]	SAAD Y, SCHULTZ M H. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems[J]. SIAM Journal on Scientific and Statistical Computing, 1986, 7(3): 856-869. doi: 10.1137/0907058
[14]	HAVELIWALA T H, KAMVAR S D. The second eigenvalue of the Google matrix[R]. Stanford: Stanford University, 2003.
[15]	LANGVILLE A N, MEYER C D. Deeper inside PageRank[J]. Internet Mathematics, 2004, 1(3): 335-380. doi: 10.1080/15427951.2004.10129091
[16]	SAAD Y. Iterative Methods for Sparse Linear Systems[M]. 2nd ed. Society for Industrial and Applied Mathematics, 2003.