Difference between revisions of "Publications:Relating FFTW and Split-Radix"
From CERES
(Created page with "<div style='display: none'> == Do not edit this section == </div> {{PublicationSetupTemplate|Author=Oleg Kiselyov, Walid Taha |PID=588272 |Name=Kiselyov, Oleg (Monterey, CA 93...") |
(No difference)
|
Latest revision as of 04:44, 26 June 2014
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. |