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

Volume

11

Issue

7

fYear

2000

fDate

7/1/2000 12:00:00 AM

Firstpage

625

Lastpage

635

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;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.877731

Filename

877731