Six pass MapReduce implementation of Strassen's algorithm for matrix multiplication

No Thumbnail Available
Authors
Ramanan, Prakash
Issue Date
2018-06-15
Type
Conference paper
Language
en_US
Keywords
MapReduce , Matrix multiplication , Performance bounds , Strassen's algorithm
Research Projects
Organizational Units
Journal Issue
Alternative Title
Abstract

Consider the multiplication of two n x n matrices. A straight-forward sequential algorithm for computing the product takes Θ(n3) time. Strassen [21] 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 [7], 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).

Description
Click on the DOI link to access the article (may not be free).
Citation
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
Publisher
Association for Computing Machinery, Inc
License
Journal
Volume
Issue
PubMed ID
DOI
ISSN
EISSN