收稿日期: 2016-12-24
网络出版日期: 2017-04-30
基金资助
国家自然科学基金资助项目(11371243); 上海市教委科研创新资助项目(13ZZ068); 上海市重点学科建设资助项目(S30104)
A GMRES-Inout algorithm for computing PageRank problems
Received date: 2016-12-24
Online published: 2017-04-30
顾传青, 邵晨晨 . 求解PageRank问题的GMRES-Inout方法[J]. 上海大学学报(自然科学版), 2017 , 23(2) : 179 -184 . DOI: 10.3969/j.issn.1007-2861.2016.07.010
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
[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.
/
| 〈 |
|
〉 |
