12
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
16
$\begingroup$

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

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Aug 14, 2016 at 17:45
  • 1
    $\begingroup$ ...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$. $\endgroup$
    – Joshua Grochow
    Aug 14, 2016 at 17:45
  • $\begingroup$ @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)}$. $\endgroup$
    – David Harris
    Aug 15, 2016 at 12:52
  • $\begingroup$ @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... $\endgroup$
    – Joshua Grochow
    Aug 15, 2016 at 18:23
  • $\begingroup$ @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. $\endgroup$
    – David Harris
    Aug 15, 2016 at 20:40
4
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.