<p>Yes, all algorithms which stem from Strassen's original algorithm (this includes most known $n^{3-\varepsilon}$ algorithms for matrix multiplication, but not all -- see the comments) have space complexity $\Theta(n^2)$. If you could find a $n^{3-\varepsilon}$ time algorithm with $poly(\log n)$ space complexity, this would be a great advance. One application would be a $2^{(1-\varepsilon)n}$ time, $poly(n)$ space algorithm for the Subset-Sum problem. </p>

<p>However there are some obstacles to such a result. For some computational models, there are fairly strong lower bounds for the time-space product of matrix multiplication. References like <a href="http://linkinghub.elsevier.com/retrieve/pii/0022000084900291">Yesha</a> and <a href="http://linkinghub.elsevier.com/retrieve/pii/002200009190014V">Abrahamson</a> will give you more information.</p>

CC BY-SA 3.0
2016-08-22T18:56:09.403Z
Is there a relationship between combinatorial algorithms and space efficiency for matrix multiplication?
Michael Wehar
CC BY-SA 3.0
2016-08-22T19:22:08.960Z
I don't know what you have in mind, but there are definitely "combinatorial" (table look-up) algs for Boolean matrix mult which beat n^3 time by log factors and use much less than n^2 space...
Ryan Williams
CC BY-SA 3.0
2016-08-23T02:13:54.260Z
@RyanWilliams This is quite helpful.  Thank you!  I guess I was just wondering if it would be more interesting to find a fast subquadratic space algorithm or to find a fast combinatorial algorithm for BMM?
Michael Wehar
CC BY-SA 2.5
2010-09-15T03:32:07.733Z
Hi Ryan, Awesome. What about the group-theoretic algorithms by Cohn-Umans [FOCS2003] and Cohn-Kleinberg-Szegedy-Umans [FOCS2005] ?
Shiva Kintali
CC BY-SA 2.5
2010-09-15T03:51:54.007Z
Yeah, those too. My understanding is that they are doing a special kind of convolution (an FFT over a special group), but the convolution is over objects of size $\Theta(n^2)$. No small-space algorithms (with time complexity better than the obvious algorithm) are known for convolutions of vectors over integers, and I imagine it's only harder to get small-space convolutions over these groups.
Ryan Williams
CC BY-SA 2.5
2010-10-23T02:10:51.057Z
How can one have $poly(logn)$ space when it takes $2n^{2}$ space to store the entries of the matrices?
Turbo
CC BY-SA 2.5
2010-10-23T05:08:56.293Z
Because in the usual way in which space complexity is measured, the input is not counted towards the space bound. The input is treated as "read only", and we measure how much extra "read-write" memory is needed to compute the function. In this case, only $O(log n)$ extra space is sufficient when the input entries are bounded (e.g., 0 or 1) and you use $O(n^3)$ operations.
Ryan Williams
CC BY-SA 2.5
2010-09-15T03:26:31.243Z
2010-09-15T03:53:01.207Z
2010-09-15T03:53:01.207Z
Ryan Williams
<p>Coppersmith–Winograd algorithm is the asymptotically fastest known algorithm for multiplying two $n \times n$ square matrices. The running time of their algorithm is $O(n^{2.376})$  which is the best known so far. What is the space complexity of this algorithm ? Is it in $\Theta(n^2)$ ?</p>

<ds.algorithms><matrices>
Space complexity of Coppersmith–Winograd algorithm
Shiva Kintali
# Space complexity of Coppersmith–Winograd algorithm

(Asked by: username_0 on 2010-09-15)

Coppersmith–Winograd algorithm is the asymptotically fastest known algorithm for multiplying two $n \times n$ square matrices. The running time of their algorithm is $O(n^{2.376})$ which is the best known so far. What is the space complexity of this algorithm ? Is it in $\Theta(n^2)$ ?

**Tags:** ds.algorithms, matrices


---

## 1 answers

### Answer by username_1 on 2010-09-15. Score: 31 | Accepted answer

Yes, all algorithms which stem from Strassen's original algorithm (this includes most known $n^{3-\varepsilon}$ algorithms for matrix multiplication, but not all -- see the comments) have space complexity $\Theta(n^2)$. If you could find a $n^{3-\varepsilon}$ time algorithm with $poly(\log n)$ space complexity, this would be a great advance. One application would be a $2^{(1-\varepsilon)n}$ time, $poly(n)$ space algorithm for the Subset-Sum problem.

However there are some obstacles to such a result. For some computational models, there are fairly strong lower bounds for the time-space product of matrix multiplication. References like [Yesha](http://linkinghub.elsevier.com/retrieve/pii/0022000084900291) and [Abrahamson](http://linkinghub.elsevier.com/retrieve/pii/002200009190014V) will give you more information.

> **Comments:**
> **username_0**: Hi Ryan, Awesome. What about the group-theoretic algorithms by Cohn-Umans [FOCS2003] and Cohn-Kleinberg-Szegedy-Umans [FOCS2005] ?  
> **username_1**: Yeah, those too. My understanding is that they are doing a special kind of convolution (an FFT over a special group), but the convolution is over objects of size $\Theta(n^2)$. No small-space algorithms (with time complexity better than the obvious algorithm) are known for convolutions of vectors over integers, and I imagine it's only harder to get small-space convolutions over these groups.  
> **username_3**: How can one have $poly(logn)$ space when it takes $2n^{2}$ space to store the entries of the matrices?  
> **username_1**: Because in the usual way in which space complexity is measured, the input is not counted towards the space bound. The input is treated as "read only", and we measure how much extra "read-write" memory is needed to compute the function. In this case, only $O(log n)$ extra space is sufficient when the input entries are bounded (e.g., 0 or 1) and you use $O(n^3)$ operations.  
> **username_2**: Is there a relationship between combinatorial algorithms and space efficiency for matrix multiplication?  
> **username_1**: I don't know what you have in mind, but there are definitely "combinatorial" (table look-up) algs for Boolean matrix mult which beat n^3 time by log factors and use much less than n^2 space...  
> **username_2**: @RyanWilliams This is quite helpful.  Thank you!  I guess I was just wondering if it would be more interesting to find a fast subquadratic space algorithm or to find a fast combinatorial algorithm for BMM?  

---

