Winograd's Algorithm

A matrix multiplication algorithm which replaces one recursive matrix multiplication with 15 matrix additions (compared to Strassen's 18), yielding O(n^2.81) asymptotic performance. It's used by D'Alberto and Nicolau in their hybrid-daptive matrix multiplication library, and Craig Douglas in his GIMMW.

See Also

• The Coppersmith-Winograd Algorithm for matrix multiplication
• "GEMMW: A Portable Level 3 Blas Winograd Variant Of Strassen's Matrix-Matrix Multiply Algorithm" from the January 1994 Journal of Computational Physics.