A Functional Approach to Radix-R FFTs

Main Article Content

Dorothy Bollman
J. Seguel
J. Feo


We show that each member of a well known family of radix-r FFTs can be expressed as the composition of functions chosen from a set of four basic functions. Thus, a complete library of radix-r FFTs can be developed by programming the four basic functions and composing them to obtain various FFTs. We illustrate this by developing implementations in the functional language Sisal. We compare performance of these FFTs on a Cray C-90. Based on observation of these results we develop an implementation of an FFT of size 2k which is seemingly optional for Cray C-90. We discuss the language features of a particular benefit for programming FFTs and suggest some enhancements that would further streamline the programming.

Article Details

Research Reports