loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03)
A Group-Theoretic Approach to Fast Matrix Multiplication
Cambridge, Massachusettes
October 11-October 14
ISBN: 0-7695-2040-5
Henry Cohn, Microsoft Research
Christopher Umans, California Institute of Technology
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 \mathbb{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 + 0(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.
Citation:
Henry Cohn, Christopher Umans, "A Group-Theoretic Approach to Fast Matrix Multiplication," focs, pp.438, 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.