[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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
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
-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.
Center of Sensor Systems
Remote Sensing and optimal Signal Processing
University of Siegen