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. https://resolver.caltech.edu/CaltechAUTHORS:20110609-141427936
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
PDF
- Published Version
See Usage Policy. 345kB |
Use this Persistent URL to link to this item: https://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: |
| ||||||
| 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: |
| ||||||
| Series Name: | Annual IEEE Symposium on Foundations of Computer Science | ||||||
| DOI: | 10.1109/SFCS.2005.39 | ||||||
| Record Number: | CaltechAUTHORS:20110609-141427936 | ||||||
| Persistent URL: | https://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: | 09 Nov 2021 16:19 |
Repository Staff Only: item control page
