CaltechAUTHORS
  A Caltech Library Service

Group-theoretic algorithms for matrix multiplication

Umans, Christopher (2006) Group-theoretic algorithms for matrix multiplication. In: ISSAC '06 Proceedings of the 2006 international symposium on Symbolic and algebraic computation. ACM , New York, NY, p. 5. ISBN 1-59593-276-3. https://resolver.caltech.edu/CaltechAUTHORS:20170103-170341500

[img] PDF - Published Version
See Usage Policy.

42Kb

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

Abstract

The exponent of matrix multiplication is the smallest real number ω such that for all ε>0, O(n^(ω+ε)) arithmetic operations suffice to multiply two n×n matrices. The standard algorithm for matrix multiplication shows that ω≤3. Strassen's remarkable result [5] shows that ω≤2.81, and a sequence of further works culminating in the work of Coppersmith and Winograd [4] have improved this upper bound to ω≤2.376 (see [1] for a full history). Most researchers believe that in fact ω=2, but there have been no further improvements in the known upper bounds for the past fifteen years. It is known that several central linear algebra problems (for example, computing determinants, solving systems of equations, inverting matrices, computing LUP decompositions) have the same exponent as matrix multiplication, which makes ω a fundamental number for understanding algorithmic linear algebra. In addition, there are non-algebraic algorithms whose complexity is expressed in terms of ω. In this talk I will describe a new "group-theoretic" approach, proposed in [3], to devising algorithms for fast matrix multiplication. The basic idea is to reduce matrix multiplication to group algebra multiplication with respect to a suitable non-abelian group. The group algebra multiplication is performed in the Fourier domain, and then using this scheme recursively yields upper bounds on ω. This general framework produces nontrivial matrix multiplication algorithms if one can construct finite groups with certain properties. In particular, a very natural embedding of matrix multiplication into C[G]-multiplication is possible when group G has three subgroups H1, H2, H3 that satisfy the triple product property. I'll define this property and describe a construction that satisfies the triple product property with parameters that are necessary (but not yet sufficient) to achieve ω=2. In the next part of the talk I'll describe demands on the representation theory of the groups in order for the overall approach to yield non-trivial bounds on ω, namely, that the character degrees must be "small." Constructing families of groups together with subgroups satisfying the triple product property and for which the character degrees are sufficiently small has turned out to be quite challenging. In [2], we succeed in constructing groups meeting both requirements, resulting in non-trivial algorithms for matrix multiplication in this framework. I'll outline the basic construction, together with more sophisticated variants that achieve the bounds ω<2.48 and ω<2.41. In the final part of the talk I'll present two appealing conjectures, one combinatorial and the other algebraic. Either one would imply that the exponent of matrix multiplication is 2.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/1145768.1145772DOIAbstract
http://dl.acm.org/citation.cfm?doid=1145768.1145772PublisherAbstract
Additional Information:Copyright is held by the author/owner(s).
Subject Keywords:Algorithms, matrix multiplication, finite groups, representation theory
Classification Code:I.1.2 [ Symbolic and Algebraic Manipulation ]: Algo- rithms
Record Number:CaltechAUTHORS:20170103-170341500
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170103-170341500
Official Citation:Christopher Umans. 2006. Group-theoretic algorithms for matrix multiplication. In Proceedings of the 2006 international symposium on Symbolic and algebraic computation (ISSAC '06). ACM, New York, NY, USA, 5-5. DOI=http://dx.doi.org/10.1145/1145768.1145772
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73192
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:04 Jan 2017 16:44
Last Modified:03 Oct 2019 16:25

Repository Staff Only: item control page