Computer Science – Data Structures and Algorithms
Scientific paper
2007-03-29
Computer Science
Data Structures and Algorithms
14 pages
Scientific paper
We describe certain special consequences of certain elementary methods from group theory for studying the algebraic complexity of matrix multiplication, as developed by H. Cohn, C. Umans et. al. in 2003 and 2005. The measure of complexity here is the exponent of matrix multiplication, a real parameter between 2 and 3, which has been conjectured to be 2. More specifically, a finite group may simultaneously "realize" several independent matrix multiplications via its regular algebra if it has a family of triples of "index" subsets which satisfy the so-called simultaneous triple product property (STPP), in which case the complexity of these several multiplications does not exceed the rank (complexity) of the algebra. This leads to bounds for the exponent in terms of the size of the group and the sizes of its STPP triples, as well as the dimensions of its distinct irreducible representations. Wreath products of Abelian with symmetric groups appear especially important, in this regard, and we give an example of such a group which shows that the exponent is less than 2.84, and could be possibly be as small as 2.02 depending on the number of simultaneous matrix multiplications it realizes.
No associations
LandOfFree
The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-711119