高度可伸缩的稀疏矩阵乘法

摘要：

矩阵乘法是线性代数和图算法中非常重要的一个基本操作，而大规模数据处理中的矩阵往往是稀疏矩阵。MapReduce编程框架能够有效地支持海量数据的分布式计算。因此，对如何运用MapReduce编程框架实现超大规模稀疏矩阵的乘法进行了研究。传统矩阵乘法并行算法没有针对稀疏矩阵进行专门优化，导致计算过程中出现大量不必要的通信开销。提出了一种新的算法--CRM（column row multiplication）算法，并与传统的矩阵分块算法进行了比较。实验证明，CRM算法运行效率有很大的提高，并且具有高度的可伸缩性，适合在MapReduce平台上运行。

关键词：稀疏矩阵乘法、分布式计算、Hadoop

分类号：TP319(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant No.61070042

在线出版日期：2013-11-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：973-982