A unified treatment of compact symmetric FFT code generation

A method for the automatic generation of compact symmetric fast Fourier transforms (FFTs) from high-level specifications is presented. The generated code eliminates all redundant computations induced by the symmetries in the FFT data flow, minimizing storage requirements, input/output and arithmetic operations, and preserves the attractive computational feature of FFT algorithms. The code-generating method can be expressed as a simple and well-structured meta-algorithm whose inputs are the dimension and edge size of the data array and a matrix representation of the data symmetries