A fast search algorithm for (m,m,m) triple product property triples and an application for 5 × 5 matrix multiplication

We present a new fast search algorithm for (m,m,m) Triple Product Property (TPP) triples as defined by Cohn and Umans in 2003. The new algorithm achieves a speed-up factor of 40 up to 194 in comparison to the best known search algorithm. With a parallelized version of the new algorithm we are able to search for TPP triples in groups up to order 55. As an application we identify a list “C1” of groups that could realize 5×5 matrix multiplication with under 100 resp. 125 scalar multiplications (the best known upper bound by Makarov 1987 resp. the trivial upper bound) if they contain a (5,5,5) TPP triple. With our new algorithm we show that no group in this list can realize 5×5 matrix multiplication better than Makarov’s algorithm. We also show a direction to modified group-theoretic search, not covered by C1 list