Mapreduce implementation of Strassen's algorithm for matrix multiplication

Loading...
Thumbnail Image
Authors
Deng, Minhao
Advisors
Ramanan, Prakash
Issue Date
2017-05
Type
Thesis
Keywords
Research Projects
Organizational Units
Journal Issue
Citation
Abstract

Consider the multiplication C = A x B of two n x n matrices. A straight-forward sequential algorithm for computing the product takes ?(n 3 ) time. Strassen [17] presented an algorithm that takes ?(n lg 7) time; lg denotes logarithm to the base 2; lg 7 is about 2.81. Now, consider the implementation of these two algorithms (straight-forward 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) mapReduce passes. In this thesis, 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, for a total of 2 lg n + 1 passes. We show that Part I can be implemented in 2 passes, with total work ?(n lg 7), and reducer size and reducer workload o(n). We believe that Part III can also be implemented, with small reducer size and workload, in a constant number of passes (possibly 4 passes); this is future work.

Table of Contents
Description
Thesis (M.S.)--Wichita State University, College of Engineering, Dept. of Electrical Engineering and Computer Science
Publisher
Wichita State University
Journal
Book Title
Series
PubMed ID
DOI
ISSN
EISSN