Re: FFTs in IDL

```tom@quake.Stanford.EDU (Thomas Berger) wrote:

>Does anyone know which algorithm the FFT.PRO routine uses? The manual
>implies that it is the Cooley-Tukey with "convert-to-complex" algorithm.
>This should be very much slower than the algorithms tailored for real
>data (especially for large 2-D images like the ones I'm trying to filter).
>
>Numerical Recipes lists some but they are the old "N = factor of 2 or die"
>variety and zero padding a 1300x1024 array to 2048x1200 just seems like
>a really stupid thing to do. The Winograd algorithms would be ideal here.

There is definitly a problem and i don't know the solution but i can give
you some informations.
-We have to distinguish one/two dimensional FFT's and real/complex data.
For the onedimensional FFT the Cooley-Tukey algorithm is one of the best
i know (the reasons why this algorithm is better than the
TIME SIGNAL PROCESSING) but only in the one-dimensional domain.
Transforming two-dimensional arrays with the Cooley-Tukey algorithm slows
down the machine immensely. I think there have to be some radix- or
prime-factorizing algorithms.
-I'm a little bit surprised because it is WAVE that use the Cooley-Tukey
algorithm not IDL. In IDL there is used an algorithm using prime factors
(i don't know the exact way of transformation).
-It is very important to know that there is a little mistake in the
WAVE-Algorithm not in the IDL-Algorithm, try to plot test=findgen(4097)
and oplot,fft(fft(test,-1),1) you will see what I mean.
-The Cooley-Tukey is really slower than any other tailored algorithm for
real data because he works for complex data. Don't you have complex
-In my opinion zero padding is definitly not a stupid thing to do. For
example, the running time of a 263 point FFT is approximately 10 times
longer than that of a 264 point FFT (in IDL, i don't know in WAVE).
And the most important reason for zero padding is the better resolution
in the frequency-domain. Sometimes you have to pad because the resolution
in the frequency-domain depends directly on the sampling frequency and
the sampling frequency grows up by using zero-padding.

-I have the same problem, slow FFT's. My arrays are complex arrays of
dimension 28000x6300 (virtual page counts more than 2 GByte)and you see i
am very interested in new algorithms  for efficient Fourier-Transforms.
I'm very thankful for any experience.