A Rank 23 Algorithm for Multiplying 3 x 3 Matrices with an Arithmetic Complexity of 59
In 1969 Strassen showed surprisingly that it is possible to multiply two 2 x 2 matrices using seven multiplications and 18 additions, instead of the naive eight multiplications and four additions. The number of additions was later reduced to 15. Karstadt and Schwartz further reduced the number of additions to 12 using a change-of-basis method. Both the number of multiplications and the number of additions have been shown to be optimal for the 2 x 2 case. For multiplying 3 x 3 matrices, the lowest number of multiplications found so far is 23. Using 23 multiplications, Schwart et al. showed how to reduce the number of additions to 61 using a change-of-basis method. Mårtensson and Stankovski Wagner showed how to achieve 62 additions, without changing basis. Using the optimization method by Mårtensson and Stankovski Wagner, Stapleton found an algorithm requiring only 60 additions. In this work we continue to combine the methods of Mårtensson, Stankovski Wagner and Stapleton, finding an algorithm requiring only 59 additions, still without a basis change. Technical details on the method and tools used for finding this scheme, and a discussion on the impact of this discovery, will come in an upcoming publication.