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
- https://doi.org/10.1109/tevc.2011.2159270
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
- A 5/2n 2-Lower Bound for the Multiplicative Complexity of n × n-Matrix MultiplicationLecture Notes in Computer Science, 2001
- Migration Policies, Selection Pressure, and Parallel Evolutionary AlgorithmsJournal of Heuristics, 2001
- 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