Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2005 | Published
Book Section - Chapter Open

Group-theoretic Algorithms for Matrix Multiplication

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.

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.

Attached Files

Published - COHfocs05.pdf

Files

COHfocs05.pdf
Files (345.2 kB)
Name Size Download all
md5:8356ec5298619dba2422d52e518b387f
345.2 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
January 13, 2024