<p>Classical work of Coppersmith shows that for some $\alpha &gt; 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.</p>

<p>François le Gall recently improved on Coppersmith's work, and his <a href="http://arxiv.org/abs/1204.1111">paper</a> 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 <a href="http://rads.stackoverflow.com/amzn/click/3642082289">Algebraic Complexity Theory</a>, the book.</p>

<p>A different strand of work concentrates on multiplying matrices <em>approximately</em>. You can check <a href="http://arxiv.org/abs/1005.2724">this work</a> 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$.</p>

<p>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.</p>

CC BY-SA 3.0
2012-11-21T19:44:14.620Z
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.)
Ryan Williams
CC BY-SA 4.0
2022-05-03T17:22:15.963Z
@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?
Turbo
CC BY-SA 4.0
2022-05-03T17:37:25.603Z
I am looking for $2\times k$ and $k\times 2$ multiplication in general.
Turbo
CC BY-SA 4.0
2022-05-03T19:07:01.250Z
Not on the top of my head.
Yuval Filmus
CC BY-SA 3.0
2012-07-01T16:59:35.637Z
2012-07-01T16:59:35.637Z
Yuval Filmus
<p>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).</p>

<p>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.</p>

<p>Any ideas?</p>

<p>Thanks.</p>

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

CC BY-SA 3.0
2012-06-30T11:17:59.010Z
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?
Colin McQuillan
CC BY-SA 3.0
2012-07-03T04:44:25.193Z
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
<cc.complexity-theory><time-complexity><linear-algebra><matrix-product>
The computational complexity of matrix multiplication
inquirer
# The computational complexity of matrix multiplication

(Asked by: username_0 on 2012-06-30)

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

**Tags:** cc.complexity-theory, time-complexity, linear-algebra, matrix-product
> **Comments:**
> **username_1**: 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?  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2012-07-01. Score: 13

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](http://arxiv.org/abs/1204.1111) 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](http://rads.stackoverflow.com/amzn/click/3642082289), the book.

A different strand of work concentrates on multiplying matrices *approximately*. You can check [this work](http://arxiv.org/abs/1005.2724) 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.

> **Comments:**
> **username_4**: 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.)  
> **username_5**: @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?  
> **username_5**: I am looking for $2\times k$ and $k\times 2$ multiplication in general.  
> **username_3**: Not on the top of my head.  

---

