Publications:Relating FFTW and Split-Radix

Jump to: navigation, search

Do not edit this section

Keep all hand-made modifications below

Title Relating FFTW and Split-Radix
Author Oleg Kiselyov and Walid Taha
Year 2004
PublicationType Conference Paper
Conference ICESS'04 International Conference on Embedded Software and Systems
Diva url
Abstract Recent work showed that staging and abstract interpretation can beused to derive correct families of combinatorial circuits, and illustrated this technique with an in-depth analysis of the Fast Fourier Transform (FFT) for sizes 2n.While the quality of the generated code was promising, it used more floatingpoint operations than the well-known FFTW codelets and split-radix algorithm.This paper shows that staging and abstract interpretation can in fact be used toproduce circuits with the same number of floating-point operations as each ofsplit-radix and FFTW. In addition, choosing between two standard implementations of complex multiplication produces results that match each of the twoalgorithms. Thus, we provide a constructive method for deriving the two distinctalgorithms.