On the arithmetic complexity of Strassen-like matrix multiplications. (May 2017) - Cenk, Murat; Hasan, M. Anwar
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 ( 7 n 2.81 − 6 n 2 ) for n = 2 k . Winograd showed that using seven multiplications for this kind of matrix multiplication is optimal. Therefore, any algorithm for multiplying 2 × 2 matrices with seven multiplications is 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 ( 6 n 2.81 − 5 n 2 ) for n = 2 k and ( 3.73 n 2.81 − 5 n 2 ) for n = 8 ⋅ 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 ( 5 n 2.81 + 0.5 n 2.59 + 2 n 2.32 − 6.5 n 2 ) for n = 2 k . It is also shown that the total arithmetic complexity can be improved to ( 3.55 n 2.81 + 0.148 n 2.59 + 1.02 n 2.32 − 6.5 n 2 ) for n = 8 ⋅ 2 k, which, to the best of our knowledge, improves the best-known bound for a Strassen-like matrix multiplication algorithm.