Paper 2013/107
On the Arithmetic Complexity of StrassenLike Matrix Multiplications
Murat Cenk and M. Anwar Hasan
Abstract
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 Strassenlike algorithm. Winograd also discovered an additively optimal Strassenlike 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 bestknown bound for Strassenlike 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 bestknown bound for a Strassenlike matrix multiplication algorithm.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 Fast matrix multiplicationStrassenlike matrix multiplicationcomputational complexitycryptographic computationscomputer algebra.
 Contact author(s)
 mcenk @ uwaterloo ca
 History
 20130227: received
 Short URL
 https://ia.cr/2013/107
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/107, author = {Murat Cenk and M. Anwar Hasan}, title = {On the Arithmetic Complexity of StrassenLike Matrix Multiplications}, howpublished = {Cryptology {ePrint} Archive, Paper 2013/107}, year = {2013}, url = {https://eprint.iacr.org/2013/107} }