CaltechAUTHORS
  A Caltech Library Service

A Group-theoretic Approach to Fast Matrix Multiplication

Cohn, Henry and Umans, Christopher (2003) A Group-theoretic Approach to Fast Matrix Multiplication. In: 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE , Los Alamitos, CA, pp. 438-449. ISBN 0-7695-2040-5 http://resolver.caltech.edu/CaltechAUTHORS:20111026-095124253

Full text is not posted in this repository. Consult Related URLs below.

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

Abstract

We develop a new, group-theoretic approach to bounding the exponent of matrix multiplication. There are two components to this approach: (1) identifying groups G that admit a certain type of embedding of matrix multiplication into the group algebra C[G], and (2) controlling the dimensions of the irreducible representations of such groups. We present machinery and examples to support (1), including a proof that certain families of groups of order n^(2+o(1)) support n × n matrix multiplication, a necessary condition for the approach to yield exponent 2. Although we cannot yet completely achieve both (1) and (2), we hope that it may be possible, and we suggest potential routes to that result using the constructions in this paper.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/SFCS.2003.1238217DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1238217PublisherUNSPECIFIED
Additional Information:© 2003 IEEE. Date of Current Version: 20 October 2003. We are grateful to Michael Aschbacher, Noam Elkies, Bobby Kleinberg, Lászlό Lovász, Amin Shokrollahi, David Vogan, and Avi Wigderson for helpful discussions.
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number7847069
Record Number:CaltechAUTHORS:20111026-095124253
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20111026-095124253
Official Citation:Cohn, H.; Umans, C.; , "A group-theoretic approach to fast matrix multiplication," Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on , vol., no., pp. 438- 449, 11-14 Oct. 2003 doi: 10.1109/SFCS.2003.1238217 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1238217&isnumber=27770
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27435
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:26 Oct 2011 17:21
Last Modified:26 Oct 2011 17:21

Repository Staff Only: item control page