Six pass MapReduce implementation of Strassen's algorithm for matrix multiplication
MetadataShow full item record
Ramanan, Prakash. 2018. Six pass MapReduce implementation of Strassen's algorithm for matrix multiplication. Beyond. MR'18 Proceedings of the 5th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond. Article No. 7. Houston, TX, June 15, 2018
Consider the multiplication of two n x n matrices. A straight-forward sequential algorithm for computing the product takes Θ(n3) time. Strassen  presented an algorithm that takes Θ(nlg 7) time; lg denotes logarithm to the base 2; lg 7 is about 2.81.Now, consider the implementation of these two algorithms (straightforward and Strassen) in the mapReduce framework. Several papers have studied mapReduce implementations of the straight-forward algorithm; this algorithm can be implemented using a constant number (typically, one or two) of mapReduce passes. In this paper, we study the mapReduce implementation of Strassen's algorithm.If we unwind the recursion, Strassen's algorithm consists of three parts, Parts I-III. Direct mapReduce implementations of the three parts take lg n, 1 and lg n passes, respectively; total number of passes is 2 lg n + 1. In a previous paper , we showed that Part I can be implemented in 2 passes, with total work Θ(nlg 7), and reducer size and reducer workload o(n). In this paper, we show that Part III can be implemented in three passes. So, overall, Strassen's algorithm can be implemented in six passes, with total work Θ(nlg 7), and reducer size and reducer workload o(n).
Click on the DOI link to access the article (may not be free).