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 &lt; 3$. In particular, this algorithm (whatever it is) can WLOG be written so that:


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, 
It multiplies those linear combinations $L_i \cdot R_i$, then
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})$.