Tight bounds on one- and two-pass MapReduce algorithms for matrix multiplication
Prakash V. Ramanan, Ashita Nagar · 2016
We study one- and two-pass mapReduce algorithms for multiplying two matrices. First, consider one-pass algorithms. In the literature, there is a tight bound for the tradeoff between communication cost and parallelism. It measures communication cost using the replication rate r, and measures parallelism by reducer size q. It gives a tight bound on qr for multiplying dense square matrices. We extend it in two different ways: First, to sparse rectangular matrices; second, to a different measure of parallelism, namely, reducer workload w. We present tight bounds on qr and wr2, for multiplying sparse rectangular matrices. We also show that the lower bound on qr follows from the lower bound on wr2; so, the lower bound on wr2 is stronger.