科研之友
微信
新浪微博
Facebook
分享链接
摘要
As a mean to bound the exponent omega of the matrix multiplication, the group-theoretic approach to fast matrix multiplication was first introduced by Cohn and Umans in 2003. This involves a knotty problem, i.e., finding three subsets of a given group satisfying the so-called triple product property such that the product of their sizes is as large as possible. For this challenge problem, exact or randomized heuristic algorithms have been proposed, which are either time-consuming or ineffective on groups with large order. This paper proposes to use an evolutionary algorithm to solve the above problem. In the proposed algorithm, a local search and a restart strategy are employed to enhance the exploitation and exploration ability of the algorithm, respectively. The proposed approach is tested on a large number of nonabelian groups with order from 6 to 100. Experimental results show that the new algorithm can obtain a good tradeoff among effectiveness, robustness and efficiency. Especially, this approach is effective for nonabelian groups with order larger than 36, and obtains three subsets for each of these groups, which satisfy the triple product property and the product of whose sizes reaches the best found so for. Most importantly, we find by using the proposed algorithm 12 groups which would be promising to prove a nontrivial upper bound on the exponent omega of the matrix multiplication.
- 出版日期2018-9
- 单位中山大学
