Upgrading subgroup triple-product-property triples

DOI10.1145/2699877MaRDI QIDQ2828201zbMATH OpenOpenAlexFDO

Authors Ivo Hedtke

Publication date 24 October 2016

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.5973

zbMATH Keywords

exponent of matrix multiplicationfast matrix multiplicationgroup-theoretic matrix multiplicationtriple product property

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Arithmetic and combinatorial problems involving abstract finite groups (20D60)

Abstract: In 2003 COHN and UMANS introduced a group-theoretic approach to fast matrix multiplication. This involves finding large subsets of a group $G$ satisfying the Triple Product Property (TPP) as a means to bound the exponent $omega$ 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 we achieve an enlargement of the triple size of 100 % in the best case.

Recommendations

• Search and test algorithms for triple product property triples.
• A fast search algorithm for m,m,m Triple Product Property triples and an application for 5 5 matrix multiplication
• A note on the triple product property for subsets of finite groups.
• On cap sets and the group-theoretic approach to matrix multiplication
• Matrix multiplication via arithmetic progressions

Cites work

• A note on the triple product property for subsets of finite groups.
• Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)
• Gaussian elimination is not optimal
• Group-theoretic lower bounds for the complexity of matrix multiplication
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• Matrix multiplication via arithmetic progressions
• Multiplying matrices faster than coppersmith-winograd
• Powers of tensors and fast matrix multiplication
• Representations and characters of groups.
• Search and test algorithms for triple product property triples.
• Strassen's matrix multiplication algorithm for matrices of arbitrary order

Cited in

(3)

• A fast search algorithm for m,m,m Triple Product Property triples and an application for 5 5 matrix multiplication
• Search and test algorithms for triple product property triples.
• A note on the triple product property for subsets of finite groups.

This page was built for publication: Upgrading subgroup triple-product-property triples

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828201)