On the asymptotic complexity of matrix multiplication

Authors:
  • DCD. Coppersmith
    D. Coppersmith
  • SWS. Winograd
    S. Winograd

Abstract
The main results of this paper have the following flavor: given one algorithm for multiplying matrices, there exists another, better, algorithm. A consequence of these results is that ω, the exponent for matrix multiplication, is a limit point, that is, cannot be realized by any single algorithm. We also use these results to construct a new algorithm which shows that ω ≪ 2.495364.