CaltechAUTHORS
  A Caltech Library Service

The prime factor non-binary discrete Fourier transform and use of Crystal_Router as a general purpose communication routine

Kim, J. S. and Fox, G. C. and Aloisio, G. and Veneziani, M. (1988) The prime factor non-binary discrete Fourier transform and use of Crystal_Router as a general purpose communication routine. In: Proceedings of the third conference on Hypercube concurrent computers and applications (C^3P). Vol.2. ACM , New York, NY, pp. 1322-1327. ISBN 0-89791-278-0. http://resolver.caltech.edu/CaltechAUTHORS:20160415-104349160

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160415-104349160

Abstract

We have implemented one of the Fast Fourier Transform algorithms, the Prime Factor algorithm (PFA), on the hypercube. On sequential computers, the PFA and other discrete Fourier transforms (DFT) such as the Winograd algorithm (WFA) are known to be very efficient. However, both algorithms require full data shuffling and are thus challenging to any distributed memory parallel computers. We use a concurrent communication algorithm, called the Crystal_Router for communicating shuffled data. We will show that the speed gained in reduced arithmetic compared to binary FFT is sufficient to overcome the extra communication requirement up to a certain number of processors. Beyond this point the standard Cooley-Tukey FFT algorithm has the best performance. We comment briefly on the application of the DFT to signal processing in synthetic aperture radar (SAR).


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/63047.63087DOIPaper
http://dl.acm.org/citation.cfm?doid=63047.63087PublisherPaper
Additional Information:© 1988 ACM. This work was supported in part by DOE grant DE-FG-03-85ER25009, Parsons and System Development Foundations, the office of the program manager of the Joint Tactical Fusion Office, and by the Italian National Space Plan grant PSN-87-04/AF-04.
Funders:
Funding AgencyGrant Number
Department of Energy (DOE)DE-FG-03-85ER25009
Ralph M. Parsons FoundationUNSPECIFIED
Joint Tactical Fusion OfficeUNSPECIFIED
Agenzia Spaziale Italiana (ASI)PSN-87-04/AF-04
System Development FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20160415-104349160
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20160415-104349160
Official Citation:G. Aloisio, N. Veneziani, J. S. Kim, and G. C. Fox. 1989. The prime factor non-binary discrete Fourier transform and use of Crystal_Router as a general purpose communication routine. In Proceedings of the third conference on Hypercube concurrent computers and applications - Volume 2 (C3P), Geoffrey Fox (Ed.), Vol. 2. ACM, New York, NY, USA, 1322-1327. DOI=http://dx.doi.org/10.1145/63047.63087
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:66219
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:15 Apr 2016 18:13
Last Modified:15 Apr 2016 18:13

Repository Staff Only: item control page