Fast matrix multiplication using coherent configurations

Abstract

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.