Paper 2013/107

On the Arithmetic Complexity of Strassen-Like Matrix Multiplications

Murat Cenk and M. Anwar Hasan

Abstract

The Strassen algorithm for multiplying 2×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 (7n2.816n2) for n=2k. Winograd showed that using seven multiplications for this kind of multiplications is optimal, so any algorithm for multiplying 2×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 (6n2.815n2) for n=2k and (3.73n2.815n2) for n=82k, which is the best-known bound for Strassen-like multiplications. This paper proposes a method that reduces the complexity of Winograd's variant to (5n2.81+0.5n2.59+2n2.326.5n2) for n=2k. It is also shown that the total arithmetic complexity can be improved to for , which, to the best of our knowledge, improves the best-known bound for a Strassen-like matrix multiplication algorithm.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Fast matrix multiplicationStrassen-like matrix multiplicationcomputational complexitycryptographic computationscomputer algebra.
Contact author(s)
mcenk @ uwaterloo ca
History
2013-02-27: received
Short URL
https://ia.cr/2013/107
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/107,
      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},
      url = {https://eprint.iacr.org/2013/107}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.