Coppersmith–Winograd algorithm: Difference between revisions

Revision as of 19:05, 15 September 2015

Revision as of 23:09, 26 January 2016

Line 1:

{{Use dmy dates|date=July 2013}}

In [[linear algebra]], the '''Coppersmith–Winograd algorithm''', named after [[Don Coppersmith]] and [[Shmuel Winograd]], was the asymptotically fastest known [[algorithm]] for square [[matrix multiplication algorithm]] until 2010. It can multiply two <math>n \times n</math> matrices in <math>O(n^{2.375477})</math> time <ref name="coppersmith">{{Citation|doi=10.1016/S0747-7171(08)80013-2|title=Matrix multiplication via arithmetic progressions|url=http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf|year=1990|last1=Coppersmith|first1=Don|last2=Winograd|first2=Shmuel|journal=Journal of Symbolic Computation|volume=9|issue=3|pages=251}}</ref> (see [[Big O notation]]).

This is an improvement over the naïve <math>O(n^3)</math> time algorithm and the <math>O(n^{2.807355})</math> time [[Strassen algorithm]]. Algorithms with better asymptotic running time than the Strassen algorithm are rarely used in practice, because the large constant factors in their running times make them impractical.<ref>{{citation

| last = Le Gall | first = F.