Evolutionary Search for Matrix Multiplication Algorithms

May 2001

Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2001)

Volume

Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2001)

All Papers

This paper addresses the problem of algorithm discovery, via evolutionary search, in the context of matrix multiplication. The traditional multiplication algorithm requires O(n^3) multiplications for square matrices of order n. Strassen discovered a recursive matrix multiplication algorithm requiring only seven multiplications at each level, resulting in a runtime of O(n^{lg 7}), or O(n^{2.81}). We have been able to replicate this discovery using evolutionary search. The paper presents the representational schema, evaluation criteria, and evolution mechanisms employed during 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 2x2 submatrices to algorithms using 3x3 decompositions is also discussed.