Automatic Reproduction of a Genius Algorithm: Strassen´s Algorithm Revisited by Genetic Search

In 1968, Volker Strassen, a young German mathematician, announced a clever algorithm to reduce the asymptotic complexity of n??n matrix multiplication from the order of n ³ to n ^2.81. It soon became one of the most famous scientific discoveries in the 20th century and provoked numerous studies by other mathematicians to improve upon it. Although a number of improvements have been made, Strassen´s algorithm is still optimal in his original framework, the bilinear systems of 2 ?? 2 matrix multiplication, and people are still curious how Strassen developed his algorithm. We examined it to see if we could automatically reproduce Strassen´s discovery using a search algorithm and find other algorithms of the same quality. In total, we found 608 algorithms that have the same quality as Strassen´s, including Strassen´s original algorithm. We partitioned the algorithms into nine different groups based on the way they are constructed. This paper was made possible by the combination of genetic search and linear-algebraic techniques. To the best of our knowledge, this is the first work that automatically reproduced Strassen´s algorithm, and furthermore, discovered new algorithms with equivalent asymptotic complexity using a search algorithm.