Coppersmith–Winograd algorithm: Difference between revisions

Revision as of 00:49, 11 November 2020

Revision as of 17:24, 23 November 2020

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 [[matrix multiplication algorithm]] from 1990 until 2010. It can multiply two <math>n \times n</math> matrices in <math>\mathcal{O}(n^{2.375477})</math> time <ref name="coppersmith">{{Citation

|doi=10.1016/S0747-7171(08)80013-2

|title=Matrix multiplication via arithmetic progressions