Matrix Multiplication in the MPC Model

In this paper, we present algorithms to solve matrix multiplication problems in the MPC model. In particular, we consider the problem under various processor/memory constraints in the MPC model and prove the following results. 1. Multiplication of two rectangular matrices of size $d\times n$ and $n\times d$ ( where $d\le n$) respectively can be done in, i) $O(\sqrt{d}+{\log }_{d}n)$ rounds with $n$ processors and $\mathrm{\Theta }(d)$ memory per processor ii) $O(\frac{d}{\sqrt{n}})$ rounds with $d$ processors and $\mathrm{\Theta }(n)$ memory per processor. 2. Multiplication of two rectangular matrices of size $n\times d$ and $d\times n$ (where $d\le n$) respectively, with $n$ processors of $\mathrm{\Theta }(n)$ memory per processor, can be done in $O(\frac{d}{\sqrt{n}})$ rounds. 3.The multiplication of two $d$-sparse matrices (matrices that contain at most $d$-nonzero elements in each row and in each column) with $n$ processors and $\mathrm{\Theta }(d)$ memory per processor can be done in $O(d^{0.9})$ rounds.