Mathematics – Group Theory
Scientific paper
2003-07-24
Proceedings of the 44th Annual Symposium on Foundations of Computer Science, 11-14 October 2003, Cambridge, MA, IEEE Computer
Mathematics
Group Theory
12 pages, 1 figure, only updates from previous version are page numbers and copyright information
Scientific paper
10.1109/SFCS.2003.1238217
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-by-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.
Cohn Henry
Umans Christopher
No associations
LandOfFree
A group-theoretic approach to fast matrix multiplication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A group-theoretic approach to fast matrix multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A group-theoretic approach to fast matrix multiplication will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-367792