The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2007
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911345129029632 |
|---|---|
| author | Murthy, Sandeep |
| author_facet | Murthy, Sandeep |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_cs_0703145 |
| institution | arXiv |
| publishDate | 2007 |
| record_format | arxiv |
| spellingShingle | The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication Murthy, Sandeep Data Structures and Algorithms Computational Complexity Group Theory F.2.1 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. |
| title | The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication |
| topic | Data Structures and Algorithms Computational Complexity Group Theory F.2.1 |
| url | https://arxiv.org/abs/cs/0703145 |