求解PageRank问题的Arnoldi-PMSI迭代算法

谢亚君; 马昌凤; 罗慧

工程数学学报 ›› 2026, Vol. 43 ›› Issue (4) : 671 -685.

谢亚君, 马昌凤, 罗慧

作者信息 +

Author information +

文章历史 +

摘要

针对大规模稀疏网络分析中PageRank问题在高阻尼因子情形下的计算瓶颈，提出了一种融合深度重启Arnoldi算法与PMSI(Power-Minus-Splitting Iteration)技术的混合求解策略，即Arnoldi-PMSI迭代法。为克服传统幂法在阻尼因子趋近于1时收敛速度显著下降的缺陷，该研究设计了一种基于参数控制的交替迭代框架。在方法实现上，算法首先利用深度重启Arnoldi过程在Krylov子空间中快速生成高质量的近似解；当残差精度未达标时，自动切换至PMSI迭代阶段以进一步压缩误差，并将迭代结果作为新的初始向量反馈至Arnoldi过程，从而实现两种加速机制的优势互补。首先在合理的数学假设下严格证明了该混合算法的收敛性。又通过在多个真实网络链接矩阵上的数值实验验证，结果表明相较于经典幂法、深度重启Arnoldi-幂法及深度重启Arnoldi-MSI法，Arnoldi-PMSI方法在迭代步数、矩阵向量乘法次数以及CPU计算时间等关键指标上均表现出显著优势。该研究不仅有效提升了大规模PageRank问题的求解效率，也为复杂网络分析提供了稳健的数值计算工具。