(1) the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result
Genetic algorithms for discovery of matrix multiplication methods
(2) the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper
Andras Joo, Aston University, Aston Triangle, Birmingham B4 7ET, UK, Email: jooam@aston.ac.uk, Phone: 00 44 781 076 5295
Aniko Ekart, Aston University, Aston Triangle, Birmingham B4 7ET, UK, Email: a.ekart@aston.ac.uk, Phone: 00 44 121 204 3456
Juan P. Neirotti, Aston University, Aston Triangle, Birmingham B4 7ET, UK, Email: j.p.neirotti@aston.ac.uk, Phone:, 00 44 121 204 3657
(3) the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition)
Aniko Ekart
(4) the abstract of the paper(s)
We present a parallel genetic algorithm for finding matrix multiplication algorithms. For 3 x 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.
(5) a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies
B, D, F,G
(6) a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission),
In 1976, J. D. Laderman published his article “A noncommutative algorithm for multiplying 3 x 3 matrices using 23 multiplications” in the Bulletin of the American Mathematical Society. Since then others published equivalent algorithms for multiplication of 3 x 3 matrices using 23 multiplications. The theoretically proven lower bound is 19 multiplications, but no exact algorithm with less than 23 multiplications is known to date.
Our genetic algorithm based approach could reproduce matrix multiplication algorithms using 23 multiplications and also led to an approximate algorithm requiring 22 multiplications.
Therefore we believe that our submission satisfies the criteria:
B: The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal.
D: The result is publishable in its own right as a new scientific result ??independent of the fact that the result was mechanically created.
F: The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered.
G: The result solves a problem of indisputable difficulty in its field.
(7) a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable);
A. Joo, A. Ekart and J.P. Neirotti: Genetic algorithms for discovery of matrix multiplication methods, IEEE Transactions on Evolutionary Computation, accepted for publication, in "Initial production stage with IEEE Publishing Operations"
(8) a statement either that “any prize money, if any, is to be divided equally among the co-authors” OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors; and
Any prize money, if any, is to be given to the first author, Andras Joo
(9) a statement stating why the judges should consider the entry as “best” in comparison to other entries that may also be “human-competitive.”
Current matrix multiplication algorithms for large matrices are based on recursively using Strassen's algorithm published in 1969 that requires n to the power log 7 multiplications for multiplying square matrices of size n (the exponent is approximately equal to 2.807). Therefore, a recursive algorithm with an exponent lower than 2.807 would be of practical significance. A matrix multiplication algorithm requiring 23 multiplications for square matrices of size 3 leads to an exponent of 2.854 and an algorithm requiring 22 multiplications leads to an exponent of 2.813. This is one step toward practical improvement: obtaining a matrix multiplication algorithm requiring 21 multiplications for square matrices of size 3 would mean a reduction of the exponent from 2.807 to 2.771. This would certainly improve the speed of large matrix multiplication of today. Due to the size and nature of the search space it is highly unlikely that such an algorithm can be discovered by a human or a traditional computer program.
For completeness, we must note that an algorithm based on arithmetic progressions requiring an exponent of 2.376 was found in 1990 by Coppersmith and Winograd; however, this is not practically used due to the fact that it would only be advantageous for matrices so large that cannot be processed by current hardware. At the same time, Strassen/Laderman type recursive algorithms show benefits for tractable size large matrices.