Welcome to the resource topic for 2013/107
Title:
On the Arithmetic Complexity of Strassen-Like Matrix Multiplications
Authors: Murat Cenk, 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.
ePrint: https://eprint.iacr.org/2013/107
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .