A group-theoretic approach to fast matrix multiplication

被引:68
作者
Cohn, H [1 ]
Umans, C [1 ]
机构
[1] Microsoft Res, Redmond, WA 98052 USA
来源
44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2003年
关键词
D O I
10.1109/SFCS.2003.1238217
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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(l)) support n x 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.
引用
收藏
页码:438 / 449
页数:12
相关论文
共 15 条
[1]   On the capacity of digraphs [J].
Alon, N .
EUROPEAN JOURNAL OF COMBINATORICS, 1998, 19 (01) :1-5
[2]   ON THE SPERNER CAPACITY OF THE CYCLIC TRIANGLE [J].
BLOKHUIS, A .
JOURNAL OF ALGEBRAIC COMBINATORICS, 1993, 2 (02) :123-124
[3]  
BROWN KS, 1982, GRADUATE TEXTS MATH, V87
[4]  
Burgisser Peter, 1997, GRUNDLEHREN MATH WIS, V315
[5]  
CALDERBANK R, 1993, J ALGEBR COMB, V2, P31
[6]   MATRIX MULTIPLICATION VIA ARITHMETIC PROGRESSIONS [J].
COPPERSMITH, D ;
WINOGRAD, S .
JOURNAL OF SYMBOLIC COMPUTATION, 1990, 9 (03) :251-280
[7]  
*GAP GROUP, 2002, GAP GROUPS ALG PROGR
[8]   QUALITATIVE INDEPENDENCE AND SPERNER PROBLEMS FOR DIRECTED-GRAPHS [J].
GARGANO, L ;
KORNER, J ;
VACCARO, U .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1992, 61 (02) :173-192
[9]  
Green JA., 1955, T AM MATH SOC, V80, P402
[10]  
James G., 2001, REPRESENTATIONS CHAR, DOI 10.1017/CBO9780511814532