Search and test algorithms for Triple Product Property triples

Abstract

In 2003 COHN and UMANS introduced a group-theoretic approach to fast matrix multiplication. This involves finding large subsets of a group $G$ satisfying the Triple Product Property (TPP) as a means to bound the exponent $\omega$ of matrix multiplication. We present two new characterizations of the TPP, which are useful for theoretical considerations and for TPP test algorithms. With this we describe all known TPP tests and implement them in GAP algorithms. We also compare their runtime. Furthermore we show that the search for subgroup TPP triples of nontrivial size in a nonabelian group can be restricted to the set of all nonnormal subgroups of that group. Finally we describe brute-force search algorithms for maximal subgroup and subset TPP triples. In addition we present the results of the subset brute-force search for all groups of order less than 25 and selected results of the subgroup brute-force search for 2-groups, $SL(n,q)$ and $PSL(2,q)$.

14 pages, 2 figures, 4 tables; ISSN (Online) 1869-6104, ISSN (Print) 1867-1144

References in corpus (2)

• Group-theoretic algorithms for matrix multiplication
• A Note on the Group-theoretic Approach to Fast Matrix Multiplication

Cited by in corpus (4)

• The tensor rank of 5x5 matrices multiplication is bounded by 98 and its border rank by 89
• A Fast Search Algorithm for <m,m,m> Triple Product Property Triples and an Application for 5x5 Matrix Multiplication
• A note on the Triple Product Property subgroup capacity of finite groups
• Upgrading Subgroup Triple Product Property Triples