Search Algorithm For The Problem Of Matrix Multiplication Based On Group Theory

For decades, matrix multiplication has been an important issue in the field of computer science, which limits the efficiency of the computer in a certain range. In 2003, Cohn and Umans put forward a group-theoretic approach to achieve matrix multiplication, which required to find out three subsets or subgroups of a given group satisfying the so-called Triple Product Property(TPP). It effectively utilizes the knowledge of algebraic group theory, and is a new method which can reduce the complexity of matrix multiplication. In the recent year, although some scholars have worked on such subject, some of the algorithms are too simple and brute-force. Subject to the prevailing conditions, they only found out the TPP triples which is able to solve matrix multiplication problem of the groups within order 24.In this paper, with respect to the existence of TPP triples within finite groups, a fast search algorithm, a random search algorithm and a evolutionary algorithm have been designed and realized successively to search for a given type of TPP triples and its maximum product b(G) of their sizes. Fast search algorithm for effective integration of the restrictive conditions favorable, the search space is reduced greatly, so that the search efficiency of algorithm of 6-24 group b(G) compared to the current best deterministic algorithm for improved 4-188 times. On the basis of study of stochastic search algorithm, the experimental results found in group TPP triples apart of a lower density is better than fast search algorithm. Another way of evolutionary algorithms, focusing on the correlation between the TPP triples, making the based TPP triples(1,1,1) transform into(n, p,m) step by step, experimental results shows that the efficiency of evolutionary algorithm is relatively stable, and performance well in the group of high order, so finally use evolutionary algorithms to search for b(G) of group of order within 94.