*** Welcome to piglix ***

Coppersmith–Winograd algorithm


In linear algebra, the Coppersmith–Winograd algorithm, named after Don Coppersmith and Shmuel Winograd, was the asymptotically fastest known matrix multiplication algorithm until 2010. It can multiply two matrices in time (see Big O notation). This is an improvement over the naïve time algorithm and the 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. It is possible to improve the exponent further; however, the exponent must be at least 2 (because an matrix has values, and all of them have to be read at least once to calculate the exact result).


...
Wikipedia

...