Average running time of the fast Fourier transform

DOI10.1016/0196-6774(80)90022-XMaRDI QIDQ3890108zbMATH OpenOpenAlexFDO

Authors Persi Diaconis

Publication date 1980

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(80)90022-x

zbMATH Keywords

average running timechirp-z transformCooley-Tukey algorithmdiscrete Fourier transformfast Fourier transformGood's algorithmmixed-radix algorithmnumber of operations

Mathematics Subject Classification ID

Numerical methods for trigonometric approximation and interpolation (65T40) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cited in

(10)

• Matrix identities of the fast Fourier transform
• Double coset decompositions and computational harmonic analysis on groups
• Separation of variables and the computation of Fourier transforms on finite groups. II
• The efficient computation of Fourier transforms on semisimple algebras
• Size biased sampling from the Dickman subordinator
• Efficient Computation of the Fourier Transform on Finite Groups
• A generalised Dickman distribution and the number of species in a negative binomial process model
• Separation of variables and the computation of Fourier transforms on finite groups. II
• Generalized iterated wreath products of cyclic groups and rooted trees correspondence
• Fast Fourier analysis for abelian group extensions

This page was built for publication: Average running time of the fast Fourier transform

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