Genetic algorithms for discovery of matrix multiplication methods

A.M. Joó; Aniko Ekárt; Juan P. Neirotti

doi:10.1109/TEVC.2011.2159270

Genetic algorithms for discovery of matrix multiplication methods

Research output: Contribution to journal › Article

Abstract

We present a parallel genetic algorithm for nding matrix multiplication algo-rithms. For 3 x 3 matrices our genetic algorithm successfully discovered algo-rithms requiring 23 multiplications, which are equivalent to the currently best known human-developed algorithms. We also studied the cases with less mul-tiplications and evaluated the suitability of the methods discovered. Although our evolutionary method did not reach the theoretical lower bound it led to an approximate solution for 22 multiplications.

Original language	English
Article number	6151102
Pages (from-to)	749-751
Number of pages	3
Journal	IEEE Transactions on Evolutionary Computation
Volume	16
Issue number	5
Early online date	10 Feb 2012
DOIs	https://doi.org/10.1109/TEVC.2011.2159270
Publication status	Published - Oct 2012

Bibliographical note

© 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Keywords

parallel genetic algorithm
matrix multiplication algo-rithms
theoretical lower bound

Access to Document

10.1109/TEVC.2011.2159270

letter-18-04.pdf
© 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Accepted author manuscript, 527 KB

Cite this

@article{c2e5db54fe714ba19ce83c939e6ae2f5,

title = "Genetic algorithms for discovery of matrix multiplication methods",

abstract = "We present a parallel genetic algorithm for nding matrix multiplication algo-rithms. For 3 x 3 matrices our genetic algorithm successfully discovered algo-rithms requiring 23 multiplications, which are equivalent to the currently best known human-developed algorithms. We also studied the cases with less mul-tiplications and evaluated the suitability of the methods discovered. Although our evolutionary method did not reach the theoretical lower bound it led to an approximate solution for 22 multiplications.",

keywords = "parallel genetic algorithm, matrix multiplication algo-rithms, theoretical lower bound",

author = "A.M. Jo{\'o} and Aniko Ek{\'a}rt and Neirotti, {Juan P.}",

note = "{\textcopyright} 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.",

year = "2012",

month = oct,

doi = "10.1109/TEVC.2011.2159270",

language = "English",

volume = "16",

pages = "749--751",

journal = "IEEE Transactions on Evolutionary Computation",

issn = "1089-778X",

publisher = "IEEE",

number = "5",

}

TY - JOUR

T1 - Genetic algorithms for discovery of matrix multiplication methods

AU - Joó, A.M.

AU - Ekárt, Aniko

AU - Neirotti, Juan P.

N1 - © 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

PY - 2012/10

Y1 - 2012/10

N2 - We present a parallel genetic algorithm for nding matrix multiplication algo-rithms. For 3 x 3 matrices our genetic algorithm successfully discovered algo-rithms requiring 23 multiplications, which are equivalent to the currently best known human-developed algorithms. We also studied the cases with less mul-tiplications and evaluated the suitability of the methods discovered. Although our evolutionary method did not reach the theoretical lower bound it led to an approximate solution for 22 multiplications.

AB - We present a parallel genetic algorithm for nding matrix multiplication algo-rithms. For 3 x 3 matrices our genetic algorithm successfully discovered algo-rithms requiring 23 multiplications, which are equivalent to the currently best known human-developed algorithms. We also studied the cases with less mul-tiplications and evaluated the suitability of the methods discovered. Although our evolutionary method did not reach the theoretical lower bound it led to an approximate solution for 22 multiplications.

KW - parallel genetic algorithm

KW - matrix multiplication algo-rithms

KW - theoretical lower bound

UR - http://www.scopus.com/inward/record.url?scp=84867033790&partnerID=8YFLogxK

UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6151102

U2 - 10.1109/TEVC.2011.2159270

DO - 10.1109/TEVC.2011.2159270

M3 - Article

SN - 1089-778X

VL - 16

SP - 749

EP - 751

JO - IEEE Transactions on Evolutionary Computation

JF - IEEE Transactions on Evolutionary Computation

IS - 5

M1 - 6151102

ER -

Genetic algorithms for discovery of matrix multiplication methods

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this