Publications:Relating FFTW and Split-Radix
From CERES
| Title | Relating FFTW and Split-Radix |
|---|---|
| Author | Oleg Kiselyov and Walid Taha |
| Year | 2004 |
| PublicationType | Conference Paper |
| Journal | |
| HostPublication | |
| DOI | |
| Conference | ICESS'04 International Conference on Embedded Software and Systems |
| Diva url | http://hh.diva-portal.org/smash/record.jsf?searchId=1&pid=diva2:588272 |
| 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. |
