Coppersmith–Winograd algorithm: Difference between revisions

Content deleted Content added
New.
 
top: Retarget redirect with dash to preferred target of redirect with hyphen-minus after manual review
Tags: AWB Removed redirect
 
(168 intermediate revisions by more than 100 users not shown)
Line 1:
#REDIRECT [[Matrix multiplication algorithm]] {{R from merge}}
In the [[mathematics|mathematical]] discipline of [[linear algebra]], the 'Coppersmith-Winograd algorithm' is the fastest currently known algorithm for square [[matrix multiplication]]. It can multiply two <math>n \times n</math> matrices in <math>O(n^{2.376})</math> time. This is an improvement over the trivial <math>O(n^3)</math> time algorithm and the <math>n^{2.807}</math> time [[Strassen algorithm]]. It might be possible to improve the exponent further; however, it has been shown that the exponent must be at least 2. The Coppersmith-Winograd algorithm is frequently used as building block in other algorithms to prove run time bounds, but it appears to be not particularly practical for implementations.
 
== References ==
* [[Don Coppersmith]] and [[Shmuel Winograd]]. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251&ndash;280, 1990.