基于提前收敛重复平方的限定域矩阵乘法距离积计算方法

摘要

本发明提出一种基于矩阵乘法的大规模图全节点对最短路径计算方法，属于图计算领域和机器学习领域。该方法在预处理阶段，通过指数变换方法对图的邻接矩阵进行预处理，接着利用计算机体系架构中缓存分层设计，来加速矩阵乘法运算，最后对结果矩阵进行取对数处理，得到一轮结果。在加速训练阶段，考虑到矩阵乘法结合律性质，避免了将所得结果矩阵反复与邻接矩阵相乘的矩阵乘法计算，采用重复平方的矩阵乘法技术，对结果矩阵进行自乘计算，从而对计算过程加速。在判定阶段，利用矩阵乘法的中间矩阵收敛至结果矩阵的比例，确定则计算完毕；或者根据计算轮数达到图直径对数，确定则计算完毕；未计算完毕则进入预处理阶段继续计算。该发明基于矩阵乘法方法，能够根据图直径或收敛判定矩阵收敛比例调整计算次数，节省资源使用开销。