Exploiting inter-operation parallelism for matrix chain multiplication using MapReduce

Information

Title Exploiting inter-operation parallelism for matrix chain multiplication using MapReduce
Authors Jaeseok Myung, Sang-goo Lee
Year 2013 / 10
Keywords Matrix Chain Multiplication, Multi-way Join, MapReduce, Hadoop
Acknowledgement NRF
Publication Type International Journal
Publication Journal of Supercomputing, Volume 66, Issue 1, pp. 594-609
Index SCI
Link doi

Abstract

In this paper, we address the matrix chain multiplication problem, i.e., the multiplication of several matrices. Although several studies have investigated the problem, our approach has some different points. First, we propose MapReduce algorithms that allow us to provide scalable computation for large matrices. Second, we transform the matrix chain multiplication problem from sequential multiplications of two matrices into a single multiplication among several matrices. Since matrix multiplication is associative, this approach helps to improve the performance of the algorithms. To implement the idea, we adopt multi-way join algorithms in MapReduce that have been studied in recent years. In our experiments, we show that the proposed algorithms are fast and scalable, compared to several baseline algorithms.