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

DOI10.1137/0220028zbMATH Open0729.65115OpenAlexW2049622697MaRDI QIDQ3355210FDOQ3355210

Authors: 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

Recommendations

• On the computational complexity of the general discrete Fourier transform
• Improved upper complexity bounds for the discrete Fourier transform
• scientific article; zbMATH DE number 1004938
• \(q\)-generalization of the inverse Fourier transform
• Publication:4724256
• scientific article; zbMATH DE number 847093
• scientific article; zbMATH DE number 1256356
• A Generalized Fourier Transform and Its Applications
• Tighter Fourier transform lower bounds
• Generalized Fourier Transforms, Inverse Problems, and Integrability in 4+2

zbMATH Keywords

fast Fourier transformfinite groupFrobenius groupsgroup algebraslinear complexityinverse Fourier transformWalsh-Hadamard transformsextra- special 2-groupslower and upper complexity boundsSchur relations

Mathematics Subject Classification ID

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

Cited In (11)

• Improved upper complexity bounds for the discrete Fourier transform
• Fast Fourier Transforms for Metabelian Groups
• 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\)
• On the computational complexity of the general discrete Fourier transform
• Fourier inversion for finite inverse semigroups
• Linear time Fourier transforms of \(S_{n-k}\)-invariant functions on the symmetric group \(S_n\)
• Title not available (Why is that?)
• Fast Fourier Transforms for Symmetric Groups: Theory and Implementation
• Fast Fourier Analysis for SL₂over a Finite Field and Related Numerical Experiments
• Double coset decompositions and computational harmonic analysis on groups

This page was built for publication: Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses

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