Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses

DOI10.1137/0220028zbMath0729.65115OpenAlexW2049622697MaRDI QIDQ3355210

Ulrich Baum, Michael Clausen

Publication date: 1991

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0220028

zbMATH Keywords

group algebrasFrobenius groupsfast Fourier transforminverse Fourier transformfinite grouplinear complexityWalsh-Hadamard transformsextra- special 2-groupslower and upper complexity boundsSchur relations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Ordinary representations and characters (20C15) Numerical methods for discrete and fast Fourier transforms (65T50) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Complexity and performance of numerical algorithms (65Y20)

Related Items

Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments, Fast Fourier Transforms for Symmetric Groups: Theory and Implementation, Existence and efficient construction of fast Fourier transforms on supersolvable groups, Computing Fourier transforms and convolutions of \(S_{n - 1}\)-invariant signals on \(S_n\) in time linear in \(n\), Linear time Fourier transforms of \(S_{n-k}\)-invariant functions on the symmetric group \(S_n\), Double coset decompositions and computational harmonic analysis on groups, Fourier Inversion for Finite Inverse Semigroups, Improved upper complexity bounds for the discrete Fourier transform