Rectangular Matrix Multiplication in the Low-Bandwidth Model

Abstract

We study rectangular matrix multiplication in the low-bandwidth model of distributed computing. There are $n$ computers; initially the input matrices are distributed evenly between computers, and in each communication round every computer can send and receive an $O(\log n)$-bit message. Eventually each computer must output its designated part of the product matrix.

While prior work has focused primarily on square $n\times n$ multiplication under various sparsity assumptions, we study rectangular instances with no sparsity assumption. We denote by $⟨a,b,c⟩$ the task of multiplying an $a\times b$ matrix by a $b\times c$ matrix in this model. We concentrate on two natural aspect ratios, $⟨n,d,n⟩$ and $⟨d,n,d⟩$, for $d\le n$, and we study how the round complexity depends on $n$ and $d$.

When $d\to n$, both $⟨n,d,n⟩$ and $⟨d,n,d⟩$ approach $⟨n,n,n⟩$, which is the usual task of multiplying square matrices. If we consider multiplication over semirings, the current best upper bound in that case is $O(n^{4/3})$ rounds, and there is a trivial unconditional lower bound of $\Omega (n)$.

We show that for $⟨d,n,d⟩$, we can achieve the complexity of $\tilde{O}(d^{4/3})$, which seems like a natural generalization of the upper bound $\tilde{O}(n^{4/3})$ when $d=n$. However, the case of $⟨n,d,n⟩$ is fundamentally different, and also exhibits a phase transition. We show that for $d\le \sqrt{n}$, the complexity of $⟨n,d,n⟩$ is $\Theta (d\sqrt{n})$; we have matching upper and lower bounds. However, the behavior is genuinely different in the region $d\ge \sqrt{n}$, where the upper bound is $O(d^{2/3}{n}^{2/3})$.