Revision as of 10:42, 30 January 2007 edit Jitse Niesen (talk \| contribs) Extended confirmed users 17,194 edits m Reverted edits by 210.212.253.76 (talk) to last version by Mellum ← Previous edit		Revision as of 22:49, 30 January 2007 edit undo Hmonroe (talk \| contribs) 240 edits Expanded description of Cohn et al Next edit →
Line 3: The Coppersmith–Winograd algorithm is frequently used as building block in other algorithms to prove theoretical time bounds. However, unlike the Strassen algorithm, it is not used in practice due to huge constants hidden in the [[Big O notation]]. [[Henry Cohn]], [[Robert Kleinberg]], [[Balázs Szegedy]] and [[Christopher Umans]] have rederived the Coppersmith–Winograd algorithm using a [[group theory\|group-theoretic]] construction. They also show that either of two different conjectures would imply that the exponent of matrix multiplication is 2, as has long been suspected. It has also been conjectured that no fastest algorithm for matrix multiplication exists, in light of the nearly 20 successive improvements leading to the [[Coppersmith-Winograd algorithm]]. ==References==

Coppersmith–Winograd algorithm: Difference between revisions