Optimality of the Fast Fourier transform

1979/01/01 by Christos H. Papadimitriou · 4 citations
Computer Science · Engineering · Materials Science · #Digital Filter Design and Implementation #Electromagnetic Simulation and Numerical Methods #Magnetic Properties and Applications

paper · pdf · doi:10.1145/322108.322118

openalex publication_date 1979/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22

Abstract

A graph-theoretic model for a class of linear algorithms computing the discrete Fourier transform of sequences of length a power of 2, the mformat~on flow network, is presented The information flow network correspondmg to the fast Fourier transform IS shown to be umquely optimal in tim class with respect to a naturally defined cost

Citations

• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• An algorithm for the machine calculation of complex Fourier series
• Fast Convolution using fermat number transforms with applications to digital filtering

Cited by

• A Modified Split-Radix FFT With Fewer Arithmetic Operations
• Algorithms meeting the lower bounds on the multiplicative complexity of length-2/sup n/ DFTs and their connection with practical algorithms
• Time Bounds for Streaming Problems
• Fast Fourier transform [wikipedia]