基于MapReduce的增量矩阵乘法设计①
2016-10-14张沛然
计算机系统应用 2016年9期
关键词:实验
张沛然, 徐 云
基于MapReduce的增量矩阵乘法设计①
张沛然, 徐 云
(中国科学技术大学计算机科学与技术学院, 合肥 230027)(中国科学技术大学安徽省高性能计算重点实验室, 合肥 230027)
矩阵乘法是许多应用中的核心计算, 在这些应用中只是少量矩阵元素发生改变, 如果全量重新计算则工作量很大, 因此增量计算是解决该问题的有效手段. 本文提出了一种基于MapReudce模型的增量矩阵乘法计算方法, 以及计算矩阵中变化元素的高效识别方法, 通过利用矩阵元素的摘要信息快速计算出变化元素, 然后将矩阵乘法计算过程转换为一系列等价的连接问题, 实现了一种有效的矩阵乘法增量计算. 对于矩阵元素变化率较小的情形, 计算实验表明提出的方法计算时间上明显优于全量重新计算方法.
矩阵乘法; 增量计算; MapReduce
矩阵乘法广泛应用于机器学习、推荐系统、社交网络分析、图挖掘等领域. 在分析社交网络中用户关系时, 对社交网络图的邻接矩阵进行一次矩阵自乘, 可以计算出“朋友的朋友”[1]. 推荐领域中, 通过用户对物品的打分记录进行矩阵分解来预测还没有评分物品的分数, 而矩阵分解是用迭代矩阵乘法来求得的[2]. 许多图计算问题如最短路径、强连通分量、图匹配等, 矩阵乘法都起到了构建基本单元的作用[3].
随着互联网及云计算应用的迅速发展, 一些求解问题需要处理的矩阵规模也越来越大, 传统的并行方法[4]由于扩展性差而不能满足实际需求……
登录APP查看全文
