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?


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).

  • 8
    $\begingroup$ 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? $\endgroup$ Jun 30, 2012 at 11:17
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Jul 3, 2012 at 4:44

1 Answer 1


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.

François le Gall recently improved on Coppersmith's work, and his paper has just been accepted to FOCS 2012. In order to understand this work, you will need some knowledge of algebraic complexity theory. Virginia Williams's paper contains some relevant pointers. In particular, Coppersmith's work is completely described in Algebraic Complexity Theory, the book.

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$.

The basic approach is to sample the matrices (this corresponds to a randomized dimensionality reduction), and multiplying the much smaller sampled matrices. The trick is to find out when and in what sense this gives a good approximation. In contrast to the previous strand of work which is completely impractical, sampling algorithms are practical and even necessary for handling large amounts of data.

  • 1
    $\begingroup$ Just a note: it is known (as of November 2010) that rectangular matrix multiplication isn't necessary for solving ACC SAT. (Which is good, because rectangular matrix mult is "galactic" and complex.) $\endgroup$ Nov 21, 2012 at 19:44
  • $\begingroup$ @yuvalfilmus do you know the minimum number of multiplications needed for multiplying $2\times3$ and $3\times2$ matrices resulting in $2\times2$ matrix? Is there a reference? $\endgroup$
    – Turbo
    May 3, 2022 at 17:22
  • $\begingroup$ I am looking for $2\times k$ and $k\times 2$ multiplication in general. $\endgroup$
    – Turbo
    May 3, 2022 at 17:37
  • $\begingroup$ Not on the top of my head. $\endgroup$ May 3, 2022 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.