Thumbnail
Access Restriction
Subscribed

Author Hedtke, Ivo
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Fast matrix multiplication ♦ Triple Product Property ♦ Exponent of matrix multiplication ♦ Group-theoretic matrix multiplication
Abstract In 2003, Cohn and Umans introduced a group-theoretic approach to fast matrix multiplication. This involves finding large subsets of a group satisfying the Triple Product Property (TPP) as a means to bound the exponent of matrix multiplication. Recently, Hedtke and Murthy discussed several methods to find TPP triples. Because the search space for subset triples is too large, it is only possible to focus on subgroup triples. We present methods to upgrade a given TPP triple to a bigger TPP triple. If no upgrade is possible, we use reduction methods (based on random experiments and heuristics) to create a smaller TPP triple that can be used as input for the upgrade methods. If we apply the upgrade process for subset triples after one step with the upgrade method for subgroup triples for the known maximal subgroup TPP triples in groups of order up to 1,000, we achieve an enlargement of the triple size of 100% in the best case. Further, we test the upgrade process with all examples from the 2003 and 2005 papers from Cohn et al. and are able to increase the triple size by 595% in the best case (in the group $D^{5}_{6}).$
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-03-09
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 20
Page Count 17
Starting Page 1
Ending Page 17


Open content in new tab

   Open content in new tab
Source: ACM Digital Library