Re: FFTs in IDL

[Achim Hein <hein(at)maxwell.nv.et-inf.uni-siegen.de>]

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 
 WinogradFourierTransformAlgorithm is shown in OPPENHEIM,SCHÄFER:DISCRETE 
 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 
 information in your 2-d-image?
-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.

Peplies by email please.

Achim Hein
Center of Sensor Systems
Remote Sensing and optimal Signal Processing
University of Siegen