Tight bounds on one-pass map-reduce algorithms for matrix multiplication

Abstract

MapReduce is an effi t parallel computation model introduced by Google, for performing many large-scale computations, including matrix multiplication. Matrix multiplication can be done using either an one-pass or a two-pass MapReduce algorithm; these algorithms have been extensively studied. In this thesis, we studied the tradeoff between communication cost and parallelism, for one-pass algorithms for matrix multiplication. We measured communication cost using the replication rate r, as in the literature. We measured parallelism either by reducer size q as in the literature, or by a new parameter, namely, reducer workload w. First, we provided matching upper and lower bounds on qr, for the multi- plication of sparse rectangular matrices; this extends a previously-known result for dense square matrices. Then, we provided matching upper and lower bounds on wr2, for the multiplication of sparse rectangular matrices.