Average running time of the fast Fourier transform

DOI10.1016/0196-6774(80)90022-XzbMath0445.68029OpenAlexW2040878416MaRDI QIDQ3890108

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

fast Fourier transformdiscrete Fourier transformCooley-Tukey algorithmnumber of operationsaverage running timechirp-z transformGood's algorithmmixed-radix algorithm

Mathematics Subject Classification ID

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

Related Items

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