On the arithmetic complexity of Strassen-like matrix multiplications

详细信息    查看全文

• 作者：Murat Cenk^a ; ^{mcenk@metu.edu.tr} ; M. Anwar Hasan^b ; ^{ahasan@uwaterloo.ca}
• 关键词：Fast matrix multiplication ; Strassen-like matrix multiplication ; Computational complexity ; Cryptographic computations ; Computer algebra
• 刊名：Journal of Symbolic Computation
• 出版年：2017
• 出版时间：May-June 2017
• 年：2017
• 卷：80
• 期：part_P2
• 页码：484-501
• 全文大小：446 K
• 卷排序：80

文摘

The Strassen algorithm for multiplying 2×22×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.81−6n2)(7n2.81−6n2) for n=2kn=2k. Winograd showed that using seven multiplications for this kind of matrix multiplication is optimal. Therefore, any algorithm for multiplying 2×22×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 (6n2.81−5n2)(6n2.81−5n2) for n=2kn=2k and (3.73n2.81−5n2)(3.73n2.81−5n2) for n=8⋅2kn=8⋅2k, 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.32−6.5n2)(5n2.81+0.5n2.59+2n2.32−6.5n2) for n=2kn=2k. It is also shown that the total arithmetic complexity can be improved to (3.55n2.81+0.148n2.59+1.02n2.32−6.5n2)(3.55n2.81+0.148n2.59+1.02n2.32−6.5n2) for n=8⋅2kn=8⋅2k, which, to the best of our knowledge, improves the best-known bound for a Strassen-like matrix multiplication algorithm.