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)$ ?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
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.
answered Sep 15, 2010 at 3:26
-
$\begingroup$ Hi Ryan, Awesome. What about the group-theoretic algorithms by Cohn-Umans [FOCS2003] and Cohn-Kleinberg-Szegedy-Umans [FOCS2005] ? $\endgroup$ Commented Sep 15, 2010 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$ Commented Sep 15, 2010 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$– TurboCommented Oct 23, 2010 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$ Commented Oct 23, 2010 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$ Commented Aug 22, 2016 at 19:22