关键词: 稀疏矩阵乘法, 分布式计算, Hadoop

Abstract: Matrix multiplication is an important fundamental operation in algebra and graph algorithms. And matrixes are usually highly sparse when coming to massive data processing. MapReduce is a programming model which can process large data sets effectively. This paper focuses on how to deal with massive sparse matrix multiplication on top of MapReduce programming model. Block based matrix multiplication algorithms aren’t optimized for sparse matrix and produce large amount of redundant communication. This paper proposes a new algorithm named CRM (column row multiplication), and compares it with traditional block based matrix algorithms. The experimental results demonstrate that CRM has higher efficiency and scalability, is suitable for operating on MapReduce and outperforms traditional ways considerably.

Key words: sparse matrix multiplication, distributed computing, Hadoop