On the arithmetic complexity of Strassen-like matrix multiplications. (May 2017)

• Record Type: Journal Article
• Authors: Cenk, Murat; Hasan, M. Anwar
• Is Part Of: Journal of symbolic computation. Volume 80:Part 2(2017)
• Page Start: 484
• Page End: 501
• Publication Date: 2017-05
• Subjects: Fast matrix multiplication -- Strassen-like matrix multiplication -- Computational complexity -- Cryptographic computations -- Computer algebra; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.07.004
• Languages: English
• ISSNs: 0747-7171

Abstract

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.