2006/12/19 by Steven G. Johnson, Matteo Frigo · 2 citations
Computer Science · Mathematics · #Algorithm #Arithmetic #Computer science #Digital Filter Design and Implementation #Discrete Fourier transform (general) #Discrete Hartley transform #Fast Fourier transform #Fourier analysis #Fourier transform #Fractional Fourier transform #Matching (statistics) #Mathematics #Numerical Methods and Algorithms #Parallel Computing and Optimization Techniques #Prime-factor FFT algorithm #Radix (gastropod) #Set (abstract data type) #Simple (philosophy) #Split-radix FFT algorithm #Statistics
paper · doi:10.1109/tsp.2006.882087
openalex publication_date 2006/12/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
Recent results by Van Buskirk have broken the record set by Yavne in 1968 for the lowest exact count of real additions and multiplications to compute a power-of-two discrete Fourier transform (DFT). Here, we present a simple recursive modification of the split-radix algorithm that computes the DFT with asymptotically about 6% fewer operations than Yavne, matching the count achieved by Van Buskirk's program-generation framework. We also discuss the application of our algorithm to real-data and real-symmetric (discrete cosine) transforms, where we are again able to achieve lower arithmetic counts than previously published algorithms