24
$\begingroup$

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)$ ?

$\endgroup$
30
$\begingroup$

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 and Abrahamson will give you more information.

$\endgroup$
  • $\begingroup$ Hi Ryan, Awesome. What about the group-theoretic algorithms by Cohn-Umans [FOCS2003] and Cohn-Kleinberg-Szegedy-Umans [FOCS2005] ? $\endgroup$ – Shiva Kintali Sep 15 '10 at 3:32
  • 1
    $\begingroup$ 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. $\endgroup$ – Ryan Williams Sep 15 '10 at 3:51
  • $\begingroup$ How can one have $poly(logn)$ space when it takes $2n^{2}$ space to store the entries of the matrices? $\endgroup$ – Turbo Oct 23 '10 at 2:10
  • $\begingroup$ 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. $\endgroup$ – Ryan Williams Oct 23 '10 at 5:08
  • 1
    $\begingroup$ 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... $\endgroup$ – Ryan Williams Aug 22 '16 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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