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

No Thumbnail Available
Authors
Ramanan, Prakash
Advisors
Issue Date
2018-06-15
Type
Conference paper
Keywords
MapReduce , Matrix multiplication , Performance bounds , Strassen's algorithm
Research Projects
Organizational Units
Journal Issue
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
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).

Table of Contents
Description
Click on the DOI link to access the article (may not be free).
Publisher
Association for Computing Machinery, Inc
Journal
Book Title
Series
5th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond, Beyond;2018
PubMed ID
DOI
ISSN
EISSN