A new algorithm for fast generalized DFTs

DOI10.1145/3301313MaRDI QIDQ4973053zbMATH OpenOpenAlexWikidataFDO

Authors Chloe Ching-Yun Hsu, Chris Umans

Publication date 2 December 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

discrete Fourier transformfinite groups of Lie type

Mathematics Subject Classification ID

Computational methods for problems pertaining to group theory (20-08) Simple groups: alternating groups and groups of Lie type (20D06) Numerical methods for discrete and fast Fourier transforms (65T50) Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40)

Abstract: We give an new arithmetic algorithm to compute the generalized Discrete Fourier Transform (DFT) over finite groups $G$. The new algorithm uses $O(|G{|}^{omega/2+o(1)})$ operations to compute the generalized DFT over finite groups of Lie type, including the linear, orthogonal, and symplectic families and their variants, as well as all finite simple groups of Lie type. Here $omega$ is the exponent of matrix multiplication, so the exponent $omega/2$ is optimal if $omega=2$. Previously, "exponent one" algorithms were known for supersolvable groups and the symmetric and alternating groups. No exponent one algorithms were known (even under the assumption $omega=2$) for families of linear groups of fixed dimension, and indeed the previous best-known algorithm for $S{L}_2(F_q)$ had exponent $4/3$ despite being the focus of significant effort. We unconditionally achieve exponent at most $1.19$ for this group, and exponent one if $omega=2$. Our algorithm also yields an improved exponent for computing the generalized DFT over general finite groups $G$, which beats the longstanding previous best upper bound, for any $omega$. In particular, assuming $omega=2$, we achieve exponent $sqrt2$, while the previous best was $3/2$.

Recommendations

• A fast generalized DFT for finite groups of Lie type
• On the computational complexity of the general discrete Fourier transform
• Fast Fourier Transforms for Metabelian Groups
• Publication:4502609
• Separation of variables and the computation of Fourier transforms on finite groups, I

Cited in

(7)

• On the computational complexity of the general discrete Fourier transform
• A reduced-complexity fast algorithm for software implementation of the IFFT/FFT in DMT systems
• The design of optimal DFT algorithms using dynamic programming
• scientific article; zbMATH DE number 4072331 (Why is no real title available?)
• Unscrambling for fast DFT algorithms
• A fast generalized DFT for finite groups of Lie type
• Fast generalized DFTs for all finite groups

This page was built for publication: A new algorithm for fast generalized DFTs

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