Show simple item record

dc.contributor.authorRamanan, Prakash
dc.date.accessioned2019-04-21T04:16:06Z
dc.date.available2019-04-21T04:16:06Z
dc.date.issued2018-06-15
dc.identifier.citationRamanan, 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, 2018en_US
dc.identifier.isbn978-145035703-6
dc.identifier.urihttps://doi.org/10.1145/3206333.3206336
dc.identifier.urihttp://hdl.handle.net/10057/16026
dc.descriptionClick on the DOI link to access the article (may not be free).en_US
dc.description.abstractConsider 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).en_US
dc.language.isoen_USen_US
dc.publisherAssociation for Computing Machinery, Incen_US
dc.relation.ispartofseries5th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond, Beyond;2018
dc.subjectMapReduceen_US
dc.subjectMatrix multiplicationen_US
dc.subjectPerformance boundsen_US
dc.subjectStrassen's algorithmen_US
dc.titleSix pass MapReduce implementation of Strassen's algorithm for matrix multiplicationen_US
dc.typeConference paperen_US
dc.rights.holder© 2019 ACM, Inc.en_US


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record