Patent ID: 6532484
Filing Date: 2003-03-11
Classification: G06F

Abstract:
A method for computing the fast Fourier transform (FFT) of a real-valued input vector of length n, the method comprising:(a) storing the real-valued input vector as an n1Ã—n2 complex source array partitioned among P processes, wherein the product of n1 and n2 equals n/2; (b) said P processes operating on the n1Ã—n2 complex source array in a parallel fashion to compute an n1Ã—n2 complex intermediate array which represents the FFT of the n1Ã—n2 complex source array; (c) said P processes operating on the n1Ã—n2 complex intermediate array in a parallel fashion to compute an output vector representing the FFT of the real-valued input vector.