Title :
A framework for the design and implementation of FFT permutation algorithms
Author :
Seguel, Jaime ; Bollman, Dorothy ; Feo, John
Author_Institution :
Dept. of Math., Puerto Rico Univ., Mayaguez, Puerto Rico
fDate :
7/1/2000 12:00:00 AM
Abstract :
We propose an algebraic framework for the design and implementation of a large class of data-sorting procedures, including all index-digit permutations used in FFTs. We discuss both old and new algorithms in terms of this framework. We show that the algebraic formulation of the new algorithms can be easily encoded using a functional programming language, and that the resulting code introduces no inefficiencies. We present performance results for implementations of three new algorithms for mixed-radix digit-reversal on a Cray C-90 and on a Sun Sparc 5
Keywords :
digital arithmetic; fast Fourier transforms; functional programming; sorting; FFT permutation; data-sorting; data-sorting procedures; functional programming language; index-digit permutation; index-digit permutations; induced permutation; mixed-radix digit-reversal; performance results; tensor sum; Algorithm design and analysis; Application software; Arithmetic; Concurrent computing; Fast Fourier transforms; Flexible printed circuits; Functional programming; Scattering; Sun; Tensile stress;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
