# Memory requirement for fast matrix multiplication

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

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

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

• 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 Aug 14 '16 at 17:45
• ...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 Aug 14 '16 at 17:45
• @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 Aug 15 '16 at 12:52
• @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 Aug 15 '16 at 18:23
• @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 Aug 15 '16 at 20:40

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