Evolutionary Search for Matrix Multiplication Algorithms
John F. Kolen, Phillip Bruce · 2001
This paper addresses the problem of algorithm discov-ery, via evolutionary search, in the context of matrix multiplication. The traditional multiplication algorithm requires O(n3) multiplications for square matrices of or-der n. Strassen (Strassen 1969) discovered a re, cursive matrix multiplication algorithm requiring only seven multiplications at each level, resulting in a runtime of O(n/x7), or O(n2"81). We have been able to replicate this discovery using evolutionary search (Fogel 1995). The paper presents the representational schema, evalu-ation criteria, and evolution mechanisms employed ur-ing search. The most crucial decision was removing the determination of coefficients used to combine the product terms in the final addition steps from the search space and calculating them directly from the specified multiplications. Extending this methodology from 2 x 2 submatrices to algorithms using 3 × 3 decompositions is also discussed.