Upgrading subgroup triple-product-property triples

DOI10.1145/2699877zbMATH Open1348.65076arXiv1107.5973OpenAlexW2044405930MaRDI QIDQ2828201FDOQ2828201

Authors: Ivo Hedtke 

Publication date: 24 October 2016

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

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.

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

Recommendations

• Search and test algorithms for triple product property triples.
• A fast search algorithm for \(\langle m,m,m\rangle\) Triple Product Property triples and an application for \(5\times 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

zbMATH Keywords

fast matrix multiplicationexponent of matrix multiplicationtriple product propertygroup-theoretic matrix multiplication

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

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

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)