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.