Coppersmith–Winograd algorithm: Difference between revisions

Revision as of 13:31, 3 May 2013

Revision as of 02:59, 3 July 2013

Line 1:

{{Use dmy dates|date=SeptemberJuly 20102013}}

In [[linear algebra]], the '''Coppersmith–Winograd algorithm''', named after [[Don Coppersmith]] and [[Shmuel Winograd]], was the asymptotically fastest known [[algorithm]] for square [[matrix multiplication]] until 2010. It can multiply two <math>n \times n</math> matrices in <math>O(n^{2.375477})</math> time <ref name="coppersmith">Don Coppersmith and Shmuel Winograd. [http://www.cs.umd.edu/~gasarch/ramsey/matrixmult.pdf Matrix Multiplication via Arithmetic Progressions]. J. Symbolic

Computation, 9(3):251–280, 1990, doi:10.1016/S0747-7171(08)80013-2.</ref> (see [[Big O notation]]).

Line 25 ⟶ 26:

{{Numerical linear algebra}}

{{Use dmy dates|date=September 2010}}

{{DEFAULTSORT:Coppersmith-Winograd Algorithm}}