Fast matrix multiplication using coherent configurations
Fast matrix multiplication using coherent configurations
复制标题
DOI：
10.1137/1.9781611973105.77
复制
发表时间：
2012-07
期刊：
影响因子：
--
通讯作者：
Henry Cohn;C. Umans
中科院分区：
文献类型：
--
作者：
Henry Cohn;C. Umans
我们介绍了一个放松张量秩的概念，称为S-秩，并表明上界的S-秩的矩阵乘法张量意味着上界的普通秩。特别地，如果“矩阵乘法的s秩指数”等于2，则ω = 2。s-秩指数和普通指数之间的这种联系使我们能够将Cohn和Umans的群论方法从群代数推广到一般代数。将矩阵乘法嵌入到一般代数乘法中会产生s-秩（不是普通秩）的界，在本文之前，这一直是处理一般代数的障碍。我们确定的邻接代数的相干配置作为一个有前途的家庭代数的广义框架。凝聚构形是推广群和群作用的组合对象;邻接代数是群代数的类似物，并保留了它们的许多重要特征。与群一样，当满足自然组合条件时，相干配置支持矩阵乘法，涉及其底层几何中的点的三角形。最后，我们证明了一个涉及邻接代数的对称幂的闭包性质，这使得我们能够使用交换相干配置证明ω的非平凡界，并表明交换相干配置可能足以证明ω = 2。总之，我们的结果表明，ω的界可以通过嵌入大型矩阵乘法的情况下，到小的交换相干配置。
We introduce a relaxation of the notion of tensor rank, called s-rank, and show that upper bounds on the s-rank of the matrix multiplication tensor imply upper bounds on the ordinary rank. In particular, if the "s-rank exponent of matrix multiplication" equals 2, then ω = 2. This connection between the s-rank exponent and the ordinary exponent enables us to significantly generalize the group-theoretic approach of Cohn and Umans, from group algebras to general algebras. Embedding matrix multiplication into general algebra multiplication yields bounds on s-rank (not ordinary rank) and, prior to this paper, that had been a barrier to working with general algebras. We identify adjacency algebras of coherent configurations as a promising family of algebras in the generalized framework. Coherent configurations are combinatorial objects that generalize groups and group actions; adjacency algebras are the analogue of group algebras and retain many of their important features. As with groups, coherent configurations support matrix multiplication when a natural combinatorial condition is satisfied, involving triangles of points in their underlying geometry. Finally, we prove a closure property involving symmetric powers of adjacency algebras, which enables us to prove nontrivial bounds on ω using commutative coherent configurations and suggests that commutative coherent configurations may be sufficient to prove ω = 2. Altogether, our results show that bounds on ω can be established by embedding large matrix multiplication instances into small commutative coherent configurations.