**On the Arithmetic Complexity of Strassen-Like 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 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.

**Category / Keywords: **implementation / Fast matrix multiplication, Strassen-like matrix multiplication, computational complexity, cryptographic computations, computer algebra.

**Date: **received 24 Feb 2013

**Contact author: **mcenk at uwaterloo ca

**Available format(s): **PDF | BibTeX Citation

**Version: **20130227:175453 (All versions of this report)

**Short URL: **ia.cr/2013/107

[ Cryptology ePrint archive ]