Generating and Searching Families of FFT Algorithms
Steve Haynal, Heidi Haynal · Journal on Satisfiability Boolean Modeling and Computation · 2011
A fundamental question of longstanding theoretical interest is to prove the lowest exact count of real additions and multiplications required to compute a power-of-two discrete Fourier transform (DFT).For 35 years the split-radix algorithm held the record by requiring just 4n log 2 n -6n + 8 arithmetic operations on real numbers for a size-n DFT, and was widely believed to be the best possible.Recent work by Van Buskirk and Lundy demonstrated improvements to the split-radix operation count by using multiplier coefficients or "twiddle factors" that are not n th roots of unity for a size-n DFT.This paper presents a Boolean Satisfiability-based proof of the lowest operation count for certain classes of DFT algorithms.First, we present a novel way to choose new yet valid twiddle factors for the nodes in flowgraphs generated by common power-of-two fast Fourier transform algorithms, FFTs.With this new technique, we can generate a large family of FFTs realizable by a fixed flowgraph.This solution space of FFTs is cast as a Boolean Satisfiability problem, and a modern Satisfiability Modulo Theory solver is applied to search for FFTs requiring the fewest arithmetic operations.Surprisingly, we find that there are FFTs requiring fewer operations than the split-radix even when all twiddle factors are n th roots of unity.