CaltechAUTHORS
  A Caltech Library Service

Group-theoretic Algorithms for Matrix Multiplication

Cohn, Henry and Kleinberg, Robert and Szegedy, Balázs and Umans, Christopher (2005) Group-theoretic Algorithms for Matrix Multiplication. In: 46th Annual IEEE Symposium on Foundations of Computer Science. Annual IEEE Symposium on Foundations of Computer Science. IEEE , Los Alamitos, CA, pp. 379-388. ISBN 0-7695-2468-0 http://resolver.caltech.edu/CaltechAUTHORS:20110609-141427936

[img] PDF - Published Version
See Usage Policy.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20110609-141427936

Abstract

We further develop the group-theoretic approach to fast matrix multiplication introduced by Cohn and Umans, and for the first time use it to derive algorithms asymptotically faster than the standard algorithm. We describe several families of wreath product groups that achieve matrix multiplication exponent less than 3, the asymptotically fastest of which achieves exponent 2.41. We present two conjectures regarding specific improvements, one combinatorial and the other algebraic. Either one would imply that the exponent of matrix multiplication is 2.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/SFCS.2005.39 DOIArticle
Additional Information:© 2005 IEEE. Date of Current Version: 14 November 2005. We are grateful to Michael Aschbacher, Noam Elkies, William Kantor, Lászlό Lovász, Amin Shokrollahi, Gábor Simonyi, and David Vogan for helpful discussions.
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number8814628
Record Number:CaltechAUTHORS:20110609-141427936
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20110609-141427936
Official Citation:Group-theoretic algorithms for matrix multiplication Cohn, H.; Kleinberg, R.; Szegedy, B.; Umans, C.; Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on Digital Object Identifier: 10.1109/SFCS.2005.39 Publication Year: 2005 , Page(s): 379 - 388
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:23966
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:09 Jun 2011 21:37
Last Modified:29 Mar 2014 03:28

Repository Staff Only: item control page