3 years ago

A local search based restart evolutionary algorithm for finding triple product property triples

Yi Xiang, Yuren Zhou, Zefeng Chen

Abstract

As a mean to bound the exponent ω 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 ω of the matrix multiplication.

Publisher URL: https://link.springer.com/article/10.1007/s10489-017-1118-6

DOI: 10.1007/s10489-017-1118-6

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.