Mapreduce implementation of Strassen's algorithm for matrix multiplication
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.
Description
Thesis (M.S.)--Wichita State University, College of Engineering, Dept. of Electrical Engineering and Computer Science