Genetic algorithms for discovery of matrix multiplication methods

Research output: Contribution to journalArticle

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 languageEnglish
Article number6151102
Pages (from-to)749-751
Number of pages3
JournalIEEE Transactions on Evolutionary Computation
Volume16
Issue number5
Early online date10 Feb 2012
DOIs
Publication statusPublished - Oct 2012

Fingerprint

Matrix multiplication
Multiplication
Genetic algorithms
Genetic Algorithm
Parallel Genetic Algorithm
Parallel algorithms
Lower bound
Human

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

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 = "{\circledC} 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 = "10",
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",

}

Genetic algorithms for discovery of matrix multiplication methods. / Joó, A.M.; Ekárt, Aniko; Neirotti, Juan P.

In: IEEE Transactions on Evolutionary Computation, Vol. 16, No. 5, 6151102, 10.2012, p. 749-751.

Research output: Contribution to journalArticle

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

VL - 16

SP - 749

EP - 751

JO - IEEE Transactions on Evolutionary Computation

JF - IEEE Transactions on Evolutionary Computation

SN - 1089-778X

IS - 5

M1 - 6151102

ER -