求解PageRank问题的GMRES-Inout方法

doi:10.3969/j.issn.1007-2861.2016.07.010

Journal of Shanghai University（Natural Science Edition） ›› 2017, Vol. 23 ›› Issue (2): 179-184.doi: 10.3969/j.issn.1007-2861.2016.07.010

Previous Articles Next Articles

A GMRES-Inout algorithm for computing PageRank problems

GU Chuanqing, SHAO Chenchen

College of Sciences, Shanghai University, Shanghai 200444, China

Received:2016-12-24 Online:2017-04-30 Published:2017-04-30

Abstract

Abstract:

The PageRank algorithm for determining the importance of Web pages has become a central technique in Web search. Based on the inout method, a GMRESInout algorithm which modifying the inner-outer method preconditioned with the restarted GMRES algorithm is proposed. Description and convergence analysis of the proposed algorithm are given. Numerical results are reported to demonstrate the efficiency of the proposed algorithm.

Key words: convergence, GMRES algorithm , inner-outer iteration , PageRank

GU Chuanqing, SHAO Chenchen. A GMRES-Inout algorithm for computing PageRank problems[J]. Journal of Shanghai University（Natural Science Edition）, 2017, 23(2): 179-184.

References

[1] Wu G, Wei Y M. A Power-Arnoldi algorithm for computing PageRank [J]. Numerical Linear Algebra with Applications, 2007, 14(7): 521-546.
[2] Page L, Brin S, Motwani R, et al. The PageRank citation ranking: bring order to the web [R/OL]. (2016-12-24)[2017-03-22]. http://homepages.dcc.ufmg.br/vnivio/cursos/rill/sources/pagerank.pdf.
[3] Kamvar S D, Haveliwala T H, Manning C D, et al. Extrapolation methods for accelerating PageRank computations [C]//12th International World Wide Web Conference. 2003: 261-270.
[4] Gleich D F, Gray A P, Greif C, et al. An inner-outer iteration method for computing Page-Rank [J]. SIAM Journal on Scientific Computing, 2010, 32(1): 349-371.
[5] 顾传青, 王磊. 一类修正的幂外推法加速PageRank 计算[J]. 上海大学学报(自然科学版), 2013, 19(2): 150-153.
[6] 顾传青, 马先磊. 求解PageRank 问题的多步幂法修正的内外迭代法[J]. 应用数学与计算数学学报, 2014, 28(4): 454-460.
[7] 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.
[8] Pu B Y, Huang T Z, Wen C. A preconditioned and extrapolation-accelerated GMRES method for PageRank [J]. Applied Mathematics Letters, 2014, 37(11): 95-100.
[9] 蒋尔雄. 矩阵计算[M]. 北京: 科学出版社, 2008.
[10] Haveliwala T H, Kamvar A D. The second eigenvalue of the google matrix [R/OL]. (2016-11-21)[2016-012-20]. http://ilpubs.stanford.edu:8090/582.
[11] Gu C Q, Xie F, Zhang K. A two-step splitting iteration for computing PageRank [J]. Journal of Computational and Applied Mathematics, 2015, 278: 19-28.
[12] Gu C Q, Wang W W. An Arnoldi-Inout algorithm for computing PageRank problems [J]. Journal of Computational and Applied Mathematics, 2017, 309: 219-229.

A GMRES-Inout algorithm for computing PageRank problems

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments