<p>More generally, fast matrix multiplication can be done on $p$ processors in $O(n^2/p)$ memory per processor. However, the communication between processors is then suboptimal. Optimal communication can be achieved by using more memory. As far as I know, it is not known whether optimal communication and optimal memory can be achieved simultaneously. Details are in <a href="http://dx.doi.org/10.1007/PL00008264" rel="noreferrer">http://dx.doi.org/10.1007/PL00008264</a></p>

CC BY-SA 3.0
2016-11-23T11:29:15.027Z
2016-11-23T11:29:15.027Z
Alexander Tiskin
<p>The space usage is at most $O(n^2)$ for all Strassen-like algorithms (i.e. those based on upper bounding the rank of matrix multiplication algebraically). See <a href="https://cstheory.stackexchange.com/questions/1313/space-complexity-of-coppersmith-winograd-algorithm/1318#1318">Space complexity of Coppersmith–Winograd algorithm</a></p>

<p>However, I realized in my previous answer that I did not explain why the space usage is $O(n^2)$... so here goes something hand-wavy. Consider what a Strassen-like algorithm does. It starts from a fixed algorithm for $K \times K$ matrix multiplication that uses $K^c$ multiplications for some constant $c &lt; 3$. In particular, this algorithm (whatever it is) can WLOG be written so that:</p>

<ol>
<li><p>It computes $K^c$ different matrices $L_1,\ldots,L_{K^c}$ which multiply entries of the first matrix $A$ by various scalars and $K^c$ matrices $R_1,\ldots,R_{K^c}$ from the second matrix $B$ of a similar form, </p></li>
<li><p>It multiplies those linear combinations $L_i \cdot R_i$, then</p></li>
<li><p>It multiplies entries of $L_i \cdot R_i$ by various scalars, then adds all these matrices up entrywise to obtain $A \cdot B$. </p></li>
</ol>

<p>(This is a so-called "bilinear" algorithm, but it turns out that every "algebraic" matrix multiplication algorithm can be written in this way.) For each $i=1,\ldots,K^c$, this algorithm only has to store the current product $L_i \cdot R_i$ and the current value of $A \cdot B$ (initially set to all-zeroes) in memory at any given point, so the space usage is $O(K^2)$.</p>

<p>Given this finite algorithm, it is then extended to arbitrary $K^{\ell} \times K^{\ell}$ matrices, by breaking the large matrices into $K \times K$ blocks of dimensions $K^{\ell-1}\times K^{\ell-1}$, applying the finite $K \times K$ algorithm to the block matrices, and recursively calling the algorithm whenever it needs to multiply two blocks. At each level of recursion, we need to keep only $O(K^{2\ell})$ field elements in memory (storing $O(1)$ different $K^{\ell} \times K^{\ell}$ matrices). Assuming the space usage for $K^{\ell-1}\times K^{\ell-1}$ matrix multiplication is $S(\ell-1)$, the space usage of this recursive algorithm is $S(\ell) \leq S(\ell-1) + O(K^{2\ell})$, which for $S(1) = 2K^2$ solves to $S(\ell) \leq O(K^{2\ell})$. </p>

CC BY-SA 3.0
2016-12-02T03:09:02.757Z
@RyanWilliams: It seems like you can do the Levin-style search even without fixing the field to constant size. For example, over the rationals, in your Levin-style search consider the description length to include the bit-size of the constants used.
Joshua Grochow
CC BY-SA 3.0
2016-08-14T17:45:01.327Z
For any one Strassen-style algorithm, this seems right to me. But Coppersmith-Winograd also proved that to get down to $n^\omega$ actually requires an infinite sequence of Strassen-style algorithms, each of which gets closer and closer to the true exponent. Indeed, both the CW-style algorithms and the CU-style algorithms provide such sequences (albeit not approaching $\omega$, as far as we know). Over the rationals, it's possible that the constants used in such a sequence would grow very quickly, so that "the" $n^\omega$ algorithm could end up using $\omega(n^2)$ space.
Joshua Grochow
CC BY-SA 3.0
2016-08-14T17:45:27.013Z
...But by your argument, one can always get an algorithm in time $O(n^{\omega + \delta})$ and space $O(n^2)$ for any $\delta > 0$.
Joshua Grochow
CC BY-SA 3.0
2016-08-15T12:52:29.440Z
@Joshua, the memory requirement of these Strassen-type algorithms is like $f(i) * n^2$, where i is the index number of the algorithm and f is computable. So, if you search over these algorithms from $i = 0, ..., k $ and k is a slowly-growing function of n, then the work becomes $n^{\omega+o(1)}$ and the memory is $n^{2+o(1)}$.
David Harris
CC BY-SA 3.0
2016-08-15T18:23:25.777Z
@DavidHarris: Well, sure, as long as $k$ is slowly-growing enough compared to $f$, namely, $k$ has to grow at most as quickly as $f^{-1}$. The question is, for any given family, what is $f$ and how quickly does $k$ grow. But there is no guarantee that $k$ will grow slowly enough to get overall $n^{2+o(1)}$ memory usage...
Joshua Grochow
CC BY-SA 3.0
2016-08-15T20:40:24.913Z
@Joshua. The idea is that on inputs of length $n$, we search over the first $k$ putative Strassen-type algorithms, verify if they are valid, and choose the one that is fastest. Just choose $k$ as a function of $n$ so that $f(k(n)) = n^{o(1)}$. Since $k(n) \rightarrow \infty$, this implies that any Strassen-type algorithm will be selected $n$ sufficiently large. So the time goes to $n^{\omega+o(1)}$ as well.
David Harris
CC BY-SA 3.0
2016-08-15T20:44:24.887Z
@Joshua, con'd. I think $f$ is actually fairly slow growing. The $i$th Strassen type algorithm can be described using $\log i$ bits, so it only has $O(\log i)$ terms in it. So I believe $f(i) \leq (\log i)^{O(1)}$. So just take $k(i) = i$.  (Although this has running time $n^{\omega+o(1)}$, the hidden $n^{o(1)}$ term is probably huge)
David Harris
CC BY-SA 3.0
2016-08-16T19:00:18.183Z
@DavidHarris: This is a nice general idea (I'm not sure your specific thing about "the i-th Strassen-style algorithm" really makes sense, as there are potentially infinitely many such algorithms for each input size...also, enumerating over them is in general hard. However, for any *given* family of Strassen-style algorithms, like CW, or the CKSU constructions, your interleaving construction seems to make sense and work).
Joshua Grochow
CC BY-SA 3.0
2016-08-16T21:03:04.393Z
You may need to set the field to be a fixed size, e.g. GF(p) for a fixed p, so that enumeration over all algs is possible... Moreover, note you don't have to spend much time verifying, you could just use Freivalds' $O(n^2)$-time checker for matrix multiplication. Then we could do a Levin-style enumeration over all finite matrix multiplication algorithms up to a given description length, and have a "universal" randomized matrix multiplication algorithm which always achieves the optimal running time (to within $n^{o(1)}$ factors) as well as having small space :)
Ryan Williams
CC BY-SA 3.0
2016-08-13T06:09:56.190Z
2016-08-13T06:09:56.190Z
2017-04-13T12:32:28.080Z
Ryan Williams
<p>Suppose we want to multiply $n \times n$ matrices. The slow matrix multiplication algorithm runs in time $O(n^3)$ and uses $O(n^2)$ memory. The fastest matrix multiplication runs in time $n^{\omega + o(1)}$, where $\omega$ is the linear algebra constant, but what is known about its memory complexity? </p>

<p>It seems that it may be possible a priori that fast matrix multiplication consumes $n^{\omega}$ memory. Is there are any guarantee that it can be done in $O(n^2)$ memory? Is it the case that the currently-known matrix multiplication algorithms use $O(n^2)$ memory?</p>

<p>(I am actually interested in rectangular matrix multiplication, but I assume that the answer would be the same in that case as for the square case, and the square case is better studied.)</p>

<ds.algorithms><linear-algebra>
Memory requirement for fast matrix multiplication
David Harris
# Memory requirement for fast matrix multiplication

(Asked by: username_0 on 2016-08-12)

Suppose we want to multiply $n \times n$ matrices. The slow matrix multiplication algorithm runs in time $O(n^3)$ and uses $O(n^2)$ memory. The fastest matrix multiplication runs in time $n^{\omega + o(1)}$, where $\omega$ is the linear algebra constant, but what is known about its memory complexity?

It seems that it may be possible a priori that fast matrix multiplication consumes $n^{\omega}$ memory. Is there are any guarantee that it can be done in $O(n^2)$ memory? Is it the case that the currently-known matrix multiplication algorithms use $O(n^2)$ memory?

(I am actually interested in rectangular matrix multiplication, but I assume that the answer would be the same in that case as for the square case, and the square case is better studied.)

**Tags:** ds.algorithms, linear-algebra


---

## 2 answers

### Answer by username_2 on 2016-08-13. Score: 16 | Accepted answer

The space usage is at most $O(n^2)$ for all Strassen-like algorithms (i.e. those based on upper bounding the rank of matrix multiplication algebraically). See [Space complexity of Coppersmith–Winograd algorithm](https://cstheory.stackexchange.com/questions/1313/space-complexity-of-coppersmith-winograd-algorithm/1318#1318)

However, I realized in my previous answer that I did not explain why the space usage is $O(n^2)$... so here goes something hand-wavy. Consider what a Strassen-like algorithm does. It starts from a fixed algorithm for $K \times K$ matrix multiplication that uses $K^c$ multiplications for some constant $c < 3$. In particular, this algorithm (whatever it is) can WLOG be written so that:

1. It computes $K^c$ different matrices $L\_1,\ldots,L\_{K^c}$ which multiply entries of the first matrix $A$ by various scalars and $K^c$ matrices $R\_1,\ldots,R\_{K^c}$ from the second matrix $B$ of a similar form,
2. It multiplies those linear combinations $L\_i \cdot R\_i$, then
3. It multiplies entries of $L\_i \cdot R\_i$ by various scalars, then adds all these matrices up entrywise to obtain $A \cdot B$.

(This is a so-called "bilinear" algorithm, but it turns out that every "algebraic" matrix multiplication algorithm can be written in this way.) For each $i=1,\ldots,K^c$, this algorithm only has to store the current product $L\_i \cdot R\_i$ and the current value of $A \cdot B$ (initially set to all-zeroes) in memory at any given point, so the space usage is $O(K^2)$.

Given this finite algorithm, it is then extended to arbitrary $K^{\ell} \times K^{\ell}$ matrices, by breaking the large matrices into $K \times K$ blocks of dimensions $K^{\ell-1}\times K^{\ell-1}$, applying the finite $K \times K$ algorithm to the block matrices, and recursively calling the algorithm whenever it needs to multiply two blocks. At each level of recursion, we need to keep only $O(K^{2\ell})$ field elements in memory (storing $O(1)$ different $K^{\ell} \times K^{\ell}$ matrices). Assuming the space usage for $K^{\ell-1}\times K^{\ell-1}$ matrix multiplication is $S(\ell-1)$, the space usage of this recursive algorithm is $S(\ell) \leq S(\ell-1) + O(K^{2\ell})$, which for $S(1) = 2K^2$ solves to $S(\ell) \leq O(K^{2\ell})$.

> **Comments:**
> **username_3**: For any one Strassen-style algorithm, this seems right to me. But Coppersmith-Winograd also proved that to get down to $n^\omega$ actually requires an infinite sequence of Strassen-style algorithms, each of which gets closer and closer to the true exponent. Indeed, both the CW-style algorithms and the CU-style algorithms provide such sequences (albeit not approaching $\omega$, as far as we know). Over the rationals, it's possible that the constants used in such a sequence would grow very quickly, so that "the" $n^\omega$ algorithm could end up using $\omega(n^2)$ space.  
> **username_3**: ...But by your argument, one can always get an algorithm in time $O(n^{\omega + \delta})$ and space $O(n^2)$ for any $\delta > 0$.  
> **username_0**: @Joshua, the memory requirement of these Strassen-type algorithms is like $f(i) * n^2$, where i is the index number of the algorithm and f is computable. So, if you search over these algorithms from $i = 0, ..., k $ and k is a slowly-growing function of n, then the work becomes $n^{\omega+o(1)}$ and the memory is $n^{2+o(1)}$.  
> **username_3**: @DavidHarris: Well, sure, as long as $k$ is slowly-growing enough compared to $f$, namely, $k$ has to grow at most as quickly as $f^{-1}$. The question is, for any given family, what is $f$ and how quickly does $k$ grow. But there is no guarantee that $k$ will grow slowly enough to get overall $n^{2+o(1)}$ memory usage...  
> **username_0**: @Joshua. The idea is that on inputs of length $n$, we search over the first $k$ putative Strassen-type algorithms, verify if they are valid, and choose the one that is fastest. Just choose $k$ as a function of $n$ so that $f(k(n)) = n^{o(1)}$. Since $k(n) \rightarrow \infty$, this implies that any Strassen-type algorithm will be selected $n$ sufficiently large. So the time goes to $n^{\omega+o(1)}$ as well.  
> **username_0**: @Joshua, con'd. I think $f$ is actually fairly slow growing. The $i$th Strassen type algorithm can be described using $\log i$ bits, so it only has $O(\log i)$ terms in it. So I believe $f(i) \leq (\log i)^{O(1)}$. So just take $k(i) = i$.  (Although this has running time $n^{\omega+o(1)}$, the hidden $n^{o(1)}$ term is probably huge)  
> **username_3**: @DavidHarris: This is a nice general idea (I'm not sure your specific thing about "the i-th Strassen-style algorithm" really makes sense, as there are potentially infinitely many such algorithms for each input size...also, enumerating over them is in general hard. However, for any *given* family of Strassen-style algorithms, like CW, or the CKSU constructions, your interleaving construction seems to make sense and work).  
> **username_2**: You may need to set the field to be a fixed size, e.g. GF(p) for a fixed p, so that enumeration over all algs is possible... Moreover, note you don't have to spend much time verifying, you could just use Freivalds' $O(n^2)$-time checker for matrix multiplication. Then we could do a Levin-style enumeration over all finite matrix multiplication algorithms up to a given description length, and have a "universal" randomized matrix multiplication algorithm which always achieves the optimal running time (to within $n^{o(1)}$ factors) as well as having small space :)  
> **username_3**: @RyanWilliams: It seems like you can do the Levin-style search even without fixing the field to constant size. For example, over the rationals, in your Levin-style search consider the description length to include the bit-size of the constants used.  

---

### Answer by username_1 on 2016-11-23. Score: 4

More generally, fast matrix multiplication can be done on $p$ processors in $O(n^2/p)$ memory per processor. However, the communication between processors is then suboptimal. Optimal communication can be achieved by using more memory. As far as I know, it is not known whether optimal communication and optimal memory can be achieved simultaneously. Details are in <http://dx.doi.org/10.1007/PL00008264>


---

