Relating FFTW and split-radix

Oleg Kiselyov; Walid Taha

doi:10.1007/11535409_71

Relating FFTW and split-radix

Oleg Kiselyov, Walid Taha

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

18 Citations (Scopus)

Abstract

Recent work showed that staging and abstract interpretation can be used to derive correct families of combinatorial circuits, and illustrated this technique with an in-depth analysis of the Fast Fourier Transform (FFT) for sizes 2ⁿ. While the quality of the generated code was promising, it used more floating-point operations than the well-known FFTW codelets and split-radix algorithm. This paper shows that staging and abstract interpretation can in fact be used to produce circuits with the same number of floating-point operations as each of split-radix and FFTW. In addition, choosing between two standard implementations of complex multiplication produces results that match each of the two algorithms. Thus, we provide a constructive method for deriving the two distinct algorithms.

Original language	English
Title of host publication	Embedded Software and Systems - First International Conference, ICESS 2004, Revised Selected Papers
Publisher	Springer Verlag
Pages	488-493
Number of pages	6
ISBN (Print)	3540281282, 9783540281283
DOIs	https://doi.org/10.1007/11535409_71
Publication status	Published - 2005 Jan 1
Externally published	Yes
Event	First International Conference on Embedded Software and Systems, ICESS 2004 - Hangzhou, China Duration: 2004 Dec 9 → 2004 Dec 10

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3605 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	First International Conference on Embedded Software and Systems, ICESS 2004
Country/Territory	China
City	Hangzhou
Period	04/12/9 → 04/12/10

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/11535409_71

Cite this

Kiselyov, O., & Taha, W. (2005). Relating FFTW and split-radix. In Embedded Software and Systems - First International Conference, ICESS 2004, Revised Selected Papers (pp. 488-493). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3605 LNCS). Springer Verlag. https://doi.org/10.1007/11535409_71

Relating FFTW and split-radix. / Kiselyov, Oleg; Taha, Walid.

Embedded Software and Systems - First International Conference, ICESS 2004, Revised Selected Papers. Springer Verlag, 2005. p. 488-493 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3605 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kiselyov, O & Taha, W 2005, Relating FFTW and split-radix. in Embedded Software and Systems - First International Conference, ICESS 2004, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3605 LNCS, Springer Verlag, pp. 488-493, First International Conference on Embedded Software and Systems, ICESS 2004, Hangzhou, China, 04/12/9. https://doi.org/10.1007/11535409_71

@inproceedings{0e693a7958444cee824f65f4294bb52e,

title = "Relating FFTW and split-radix",

abstract = "Recent work showed that staging and abstract interpretation can be used 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 floating-point operations than the well-known FFTW codelets and split-radix algorithm. This paper shows that staging and abstract interpretation can in fact be used to produce circuits with the same number of floating-point operations as each of split-radix and FFTW. In addition, choosing between two standard implementations of complex multiplication produces results that match each of the two algorithms. Thus, we provide a constructive method for deriving the two distinct algorithms.",

author = "Oleg Kiselyov and Walid Taha",

year = "2005",

month = jan,

day = "1",

doi = "10.1007/11535409_71",

language = "English",

isbn = "3540281282",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "488--493",

booktitle = "Embedded Software and Systems - First International Conference, ICESS 2004, Revised Selected Papers",

note = "First International Conference on Embedded Software and Systems, ICESS 2004 ; Conference date: 09-12-2004 Through 10-12-2004",

}

TY - GEN

T1 - Relating FFTW and split-radix

AU - Kiselyov, Oleg

AU - Taha, Walid

PY - 2005/1/1

Y1 - 2005/1/1

N2 - Recent work showed that staging and abstract interpretation can be used 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 floating-point operations than the well-known FFTW codelets and split-radix algorithm. This paper shows that staging and abstract interpretation can in fact be used to produce circuits with the same number of floating-point operations as each of split-radix and FFTW. In addition, choosing between two standard implementations of complex multiplication produces results that match each of the two algorithms. Thus, we provide a constructive method for deriving the two distinct algorithms.

AB - Recent work showed that staging and abstract interpretation can be used 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 floating-point operations than the well-known FFTW codelets and split-radix algorithm. This paper shows that staging and abstract interpretation can in fact be used to produce circuits with the same number of floating-point operations as each of split-radix and FFTW. In addition, choosing between two standard implementations of complex multiplication produces results that match each of the two algorithms. Thus, we provide a constructive method for deriving the two distinct algorithms.

UR - http://www.scopus.com/inward/record.url?scp=33645970683&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33645970683&partnerID=8YFLogxK

U2 - 10.1007/11535409_71

DO - 10.1007/11535409_71

M3 - Conference contribution

AN - SCOPUS:33645970683

SN - 3540281282

SN - 9783540281283

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 488

EP - 493

BT - Embedded Software and Systems - First International Conference, ICESS 2004, Revised Selected Papers

PB - Springer Verlag

T2 - First International Conference on Embedded Software and Systems, ICESS 2004

Y2 - 9 December 2004 through 10 December 2004

ER -

Relating FFTW and split-radix

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this