Optimality of the Fast Fourier transform

DOI10.1145/322108.322118zbMath0388.68055OpenAlexW1972710063WikidataQ54087140 ScholiaQ54087140MaRDI QIDQ4170248

Christos H. Papadimitriou

Publication date: 1979

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322108.322118

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

Tighter Fourier Transform Lower Bounds ⋮ The complexity of computing (almost) orthogonal matrices with \(\varepsilon\)-copies of the Fourier transform ⋮ Fast Fourier optimization ⋮ Paraunitary matrices, entropy, algebraic condition number and Fourier computation ⋮ An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model

This page was built for publication: Optimality of the Fast Fourier transform