Genetic Algorithms for Discovery of Matrix Multiplication Methods
- 10 February 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 16 (5) , 749-751
Abstract
We present a parallel genetic algorithm for finding matrix multiplication algorithms. For 3 3 matrices our genetic algorithm successfully discovered algorithms requiring 23 multiplications, which are equivalent to the currently best known human-developed algorithms. We also studied cases with fewer multiplications and found an approximate solution for 22 multiplications.Keywords
This publication has 6 references indexed in Scilit:
- Automatic Reproduction of a Genius Algorithm: Strassen's Algorithm Revisited by Genetic SearchIEEE Transactions on Evolutionary Computation, 2009
- Migration Policies, Selection Pressure, and Parallel Evolutionary AlgorithmsJournal of Heuristics, 2001
- A 5/2n 2-Lower Bound for the Multiplicative Complexity of n × n-Matrix Multiplication2001
- Noncommutative Bilinear Algorithms for $3 \times 3$ Matrix MultiplicationSIAM Journal on Computing, 1986
- A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplicationsBulletin of the American Mathematical Society, 1976
- Gaussian elimination is not optimalNumerische Mathematik, 1969