Logo image
Back
Finite matrix multiplication algorithms from infinite groups
Preprint   Open access

Finite matrix multiplication algorithms from infinite groups

Jonah Blasiak, Henry Cohn, Joshua A Grochow, Kevin Pratt and Chris Umans
IACAPAP ArXiv (Online)
18 Oct 2024
DOI: https://doi.org/10.48550/arxiv.2410.14905
url
https://arxiv.org/abs/2410.14905View
Preprint (Author's original) Open arXiv.org - Non-exclusive license to distribute

Abstract

Computer Science - Data Structures and Algorithms Mathematics - Group Theory
The Cohn-Umans (FOCS '03) group-theoretic framework for matrix multiplication produces fast matrix multiplication algorithms from three subsets of a finite group $G$ satisfying a simple combinatorial condition (the Triple Product Property). The complexity of such an algorithm then depends on the representation theory of $G$. In this paper we extend the group-theoretic framework to the setting of infinite groups. In particular, this allows us to obtain constructions in Lie groups, with favorable parameters, that are provably impossible in finite groups of Lie type (Blasiak, Cohn, Grochow, Pratt, and Umans, ITCS '23). Previously the Lie group setting was investigated purely as an analogue of the finite group case; a key contribution in this paper is a fully developed framework for obtaining bona fide matrix multiplication algorithms directly from Lie group constructions.

Metrics

9 Record Views

Details

Logo image