# The computational complexity of matrix multiplication

I am looking for information about the computational complexity of matrix multiplication of rectangular matrices. Wikipedia states that the complexity of multiplying $A \in \mathbb{R}^{m \times n}$ by $B \in \mathbb{R}^{n \times p}$ is $O(mnp)$ (schoolbook multiplication).

I have a case where $m$ and $n$ are much smaller than $p$, and I was hoping to get better complexity than linear in $p$, on the expense of making the dependence on $m$ and $n$ worse than linear.

Any ideas?

Thanks.

Note: the reason I am hoping for it to be possible is because of the well known result of less than cubic dependence in $p$ if $m=n=p$ (when matrices are all squares).

• A (sequential) algorithm's complexity cannot be smaller than the size of its output. For your problem can you represent the input and output using space that is sublinear in p? Jun 30 '12 at 11:17
• are the elements mostly nonzero or often zero? ie sparse? that certainly leads to various optimizations. also it seems like the SVD [singular value decomposition] might be relevant based on the current response referring to approximations.
– vzn
Jul 3 '12 at 4:44

Classical work of Coppersmith shows that for some $\alpha > 0$, one can multiply an $n \times n^\alpha$ matrix with an $n^\alpha \times n$ matrix in $\tilde{O}(n^2)$ arithmetic operations. This is a crucial ingredient of Ryan Williams's recent celebrated result.
A different strand of work concentrates on multiplying matrices approximately. You can check this work by Magen and Zouzias. This is useful for handling really large matrices, say multiplying an $n \times N$ matrix and an $N \times n$ matrix, where $N \gg n$.