Abstract:
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.
Published Date: May 2001
Registration: ISBN 978-1-57735-133-7
Copyright: Published by The AAAI Press, Menlo Park, California.