Paper 2013/107

On the Arithmetic Complexity of Strassen-Like Matrix Multiplications

Murat Cenk and M. Anwar Hasan


The Strassen algorithm for multiplying $2 \times 2$ matrices requires seven multiplications and 18 additions. The recursive use of this algorithm for matrices of dimension $n$ yields a total arithmetic complexity of $(7n^{2.81}-6n^2)$ for $n=2^k$. Winograd showed that using seven multiplications for this kind of multiplications is optimal, so any algorithm for multiplying $2 \times 2$ matrices with seven multiplications is therefore called a Strassen-like algorithm. Winograd also discovered an additively optimal Strassen-like algorithm with 15 additions. This algorithm is called the Winograd's variant, whose arithmetic complexity is $(6n^{2.81}-5n^2)$ for $n=2^k$ and $(3.73n^{2.81}-5n^2)$ for $n=8\cdot 2^k$, which is the best-known bound for Strassen-like multiplications. This paper proposes a method that reduces the complexity of Winograd's variant to $(5n^{2.81}+0.5n^{2.59}+2n^{2.32}-6.5n^2)$ for $n=2^k$. It is also shown that the total arithmetic complexity can be improved to $(3.55n^{2.81}+0.148n^{2.59}+1.02n^{2.32}-6.5n^2)$ for $n=8\cdot 2^k$, which, to the best of our knowledge, improves the best-known bound for a Strassen-like matrix multiplication algorithm.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Fast matrix multiplicationStrassen-like matrix multiplicationcomputational complexitycryptographic computationscomputer algebra.
Contact author(s)
mcenk @ uwaterloo ca
2013-02-27: received
Short URL
Creative Commons Attribution


      author = {Murat Cenk and M.  Anwar Hasan},
      title = {On the Arithmetic Complexity of Strassen-Like Matrix Multiplications},
      howpublished = {Cryptology ePrint Archive, Paper 2013/107},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.