most recent 30 from http://mathoverflow.net 2013-05-25T07:38:36Z http://mathoverflow.net/feeds/question/1743 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/1743/what-is-the-constant-of-the-coppersmith-winograd-matrix-multiplication-algorithm DoubleJay 2009-10-21T21:57:43Z 2010-03-05T23:13:32Z

<p>Or at least it's order of magnitude.</p> <p>I've only ever heard it described as "huge", and a google search turned up nothing.</p> <p>Also, given that the Strassen algorithm has a significantly greater constant than Gaussian Elimination, and that Coppersmith-Winograd is greater still, are there any indications of what constant an O(n^2) matrix multiplication algorithm might have?</p>

http://mathoverflow.net/questions/1743/what-is-the-constant-of-the-coppersmith-winograd-matrix-multiplication-algorithm/1747#1747 Harrison Brown 2009-10-21T22:13:25Z 2009-10-21T22:13:25Z

<p>In answer to the second part of your question, I think the conventional wisdom is that there <em>isn't</em> a O(n^2) algorithm; analogously to the case for integer multiplication, you shouldn't be able to do better than about O(n^2 log n). (Raz has shown that this is a lower bound in the arithmetic circuits with bounded coefficients model.)</p> <p>What's the implied constant there? Probably just "huge." As far as I know, the reason that people believe that we can achieve close to O(n^2) is basically by analogy with integer multiplication, so if you want some grasp on the constants it might be worthwhile to look at the constants in FFT multiplication.</p> <p>Incidentally, has the appropriate volume of Art of Computer Programming been released, or will it be soon? I know Knuth's a stickler for including these kinds of details, so that might be the most obvious reference apart from the original paper...</p>

http://mathoverflow.net/questions/1743/what-is-the-constant-of-the-coppersmith-winograd-matrix-multiplication-algorithm/1749#1749 Stephen Canon 2009-10-21T22:20:42Z 2010-03-05T23:13:32Z

<p>In your second question, I think you mean "naive matrix multiplication", not "Gaussian elimination".</p> <p>Henry Cohn et al had <a href="http://arxiv.org/pdf/math.GR/0307321.pdf" rel="nofollow">a cute paper</a> that relates fast matrix multiply algorithms to certain groups. It doesn't do much for answering your question (unless you want to go and prove the conjectured results =), but it's a fun read.</p> <p>Also, to back up <strong>harrison</strong>, I don't think that anyone really believes that there's an $O(n^2)$ algorithm. A fair number of people believe that there is likely to be an algorithm which is $O(n^{2+\epsilon})$ for any $\epsilon > 0$. An $O(n^2 \log n)$ algorithm would fit the bill.</p> <p><strong>edit:</strong> You can get a back-of-the-envelope feeling for a lower bound on the exponent of Coppersmith-Winograd based on the fact that people don't use it, even for n on the order of 10,000; naive matrix multiplication requires $2n^3 + O(n^2)$ flops, and Coppersmith-Winograd requires $Cn^{2.376} + O(n^2)$. Setting the expressions equal and solving for $C$ gives that the two algorithms would have equal performance for n = 10,000 (ignoring memory access patterns, implementation efficiency, and all sorts of other things) if the constant were about 627. In reality, it's likely much larger.</p>