A new parallel algorithm for the multidimensional Fourier transform processing

Author

Shamash, M. ; Gertner, I.

Author_Institution

Dept. of Electr. Eng., Technion Israel Inst. of Technol., Haifa, Israel

fYear

1990

fDate

3-6 Apr 1990

Firstpage

1993

Abstract

Tools are presented for the extension of the Cooley-Tukey (1965) and Pease (1968) fast Fourier transform algorithms to arbitrary dimensions in a compact Kroenecker product formulation. Several variations of the vector radix algorithm (VRA) are presented using this formulation, and an algorithm suitable for spatial concurrency is derived. The tools presented are the multidimensional stride and partitioning permutations together with the multidimensional lower-ordered transforms. The concepts of partitioning permutation and multidimensional perfect shuffle permutations are studied. The first enables one to apply a divide-and-conquer strategy used in Cooley-Tukey algorithms to multidimensions and the second defines algorithm data flow in a lattice

Keywords

fast Fourier transforms; multiprocessor interconnection networks; parallel algorithms; signal processing; Cooley-Tukey algorithms; Kroenecker product formulation; divide-and-conquer strategy; fast Fourier transform algorithms; multidimensional Fourier transform processing; multidimensional lower-ordered transforms; multidimensional perfect shuffle permutations; parallel algorithm; partitioning permutation; signal processing; vector radix algorithm; Concurrent computing; Data flow computing; Fast Fourier transforms; Fourier transforms; Frequency; Lattices; Multidimensional systems; Parallel algorithms; Parallel processing; Partitioning algorithms; Polynomials; Sorting;

fLanguage

English

Publisher

ieee

Conference_Titel

Acoustics, Speech, and Signal Processing, 1990. ICASSP-90., 1990 International Conference on

Conference_Location

Albuquerque, NM

ISSN

1520-6149

Type

conf

DOI

10.1109/ICASSP.1990.115906

Filename

115906