在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2024, Vol. 41 ›› Issue (4): 642-658.doi: 10.3969/j.issn.1005-3085.2024.04.004

• • 上一篇    下一篇

求解PageRank向量的一种松弛多步分裂迭代方法

田兆禄1,  王玉栋2,  刘仲云3   

  1. 1. 山西财经大学应用数学学院，太原 030006
    2. 广西科技大学生物与化学工程学院，柳州 545006
    3. 长沙理工大学数学与统计学院，长沙 410076
  • 收稿日期:2021-11-23 接受日期:2023-11-08 出版日期:2024-08-15
  • 基金资助:
    国家自然科学基金 (52263002)；山西省自然科学基金 (20210302123480)；山西省回国留学人员科研资助项目 (2023-117).

A Relaxed Multi-splitting Iteration Method for Computing PageRank Vector

TIAN Zhaolu1,  WANG Yudong2,  LIU Zhongyun3   

  1. 1. School of Applied Mathematics, Shanxi University of Finance and Economics, Taiyuan 030006
    2. College of Biological and Chemical Engineering, Guangxi University of Science and Technology, Liuzhou 545006
    3. School of Mathematics and Statistics, Changsha University of Science and Technology, Changsha 410076
  • Received:2021-11-23 Accepted:2023-11-08 Online:2024-08-15
  • Supported by:
    The National Natural Science Foundation of China (52263002); the Natural Science Foundation of Shanxi Province (20210302123480); the Scholarship Council Research Project of Shanxi Province (2023-117).

摘要：

基于求解PageRank向量的内外迭代格式，引入一个松弛因子得到一种松弛内外迭代方法。结合已有的多步分裂迭代框架，引入两个不同的松弛因子，提出了求解PageRank向量的松弛多步分裂迭代方法并分析了算法的收敛性。更进一步地，利用松弛内外迭代格式构造了加速投影子空间方法的预处理矩阵，理论分析相关谱分布情况，并给出了松弛多步分裂迭代方法及预处理矩阵中参数的选取准则。几个数值例子验证了松弛多步分裂迭代方法和预处理矩阵的有效性，通过选取合适的松弛因子，与多步分裂迭代方法相比具有更高的运算效率。

关键词: PageRank向量, 多步分裂迭代方法, 松弛因子, 迭代矩阵, 最优参数

Abstract:

Based on the inner-outer iteration sequence for solving the PageRank vector, a relaxed inner-outer iteration method is obtained by introducing a relaxed factor. Combining the multi-splitting iteration framework with two different relaxed factors, a relaxed multi-splitting iteration method for solving the PageRank vector is proposed, and its convergence property is analyzed. Furthermore, by using the relaxed inner-outer iteration format, a preconditioned matrix for accelerating the projection subspace methods is constructed, the spectral distribution is theoretically investigated, and choice criteria of the parameters in the relaxed multi-splitting iteration method and preconditioner are provided. Several numerical examples validate the effectiveness of the relaxed multi-splitting iteration method and preconditioner, the relaxed multi-splitting iteration method is more efficient compared to the multi-splitting iteration method with appropriate relaxed factors.

Key words: PageRank vector, multi-splitting iteration method, relaxed factor, iteration matrix, optimal parameter

中图分类号: