CaltechAUTHORS
  A Caltech Library Service

Fast matrix multiplication using coherent configurations

Cohn, Henry and Umans, Christopher (2013) Fast matrix multiplication using coherent configurations. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM , Philadelphia, PA, pp. 1074-1087. ISBN 978-1-61197-251-1. https://resolver.caltech.edu/CaltechAUTHORS:20160913-165513831

[img] PDF - Published Version
See Usage Policy.

249kB
[img] PDF - Submitted Version
See Usage Policy.

287kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160913-165513831

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/1.9781611973105.77DOIArticle
https://arxiv.org/abs/1207.6528arXivDiscussion Paper
Additional Information:© 2013 SIAM. [R]esearch supported by NSF grants CCF-0846991 and CCF-1116111 and BSF grant 2010120.
Funders:
Funding AgencyGrant Number
NSFCCF-0846991
NSFCCF-1116111
Binational Science Foundation (USA-Israel)2010120
DOI:10.1137/1.9781611973105.77
Record Number:CaltechAUTHORS:20160913-165513831
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160913-165513831
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:70326
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:29 Sep 2016 23:51
Last Modified:11 Nov 2021 04:27

Repository Staff Only: item control page