03/01/1990 09:00 AM
Computer Science
The Fourier transform is an operator which maps functions from the temporal or spatial domain to the frequency domain. The *discrete* Fourier transform (DFT) is the digital analogue of the Fourier transform; it maps the discrete representation of a function to the frequency domain. The *fast* Fourier transform (FFT) is a method---in actuality, any one of a number of methods---for rapid calculation of the DFT. This report describes an investigation into the parallelization properties of the FFT. The first phase (1) of the investigation was a brief look at the mathematical basis of the FFT. The second phase (2) consisted of coding a non- parallel test program using a particular FFT algorithm. The third phase (3) consisted of experiments with a particular parallelizing FORTRAN compiler to test its ability to parallelize, vectorize, optimize, and reorganize FFT code.