Evolutionary Search for Matrix Multiplication Algorithms

John F. Kolen and Phillip Bruce, University of West Florida, USA

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.