[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: tom(at)quake.stanford.edu*Subject*: Re: FFTs in IDL*From*: Achim Hein <hein(at)maxwell.nv.et-inf.uni-siegen.de>*Date*: 15 Feb 1996 16:34:45 GMT*Newsgroups*: comp.lang.idl-pvwave*Organization*: Computer Center, University of Siegen, Germany*References*: <4fug1n$9br@morrow.stanford.edu>

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

- Prev by Date:
**Re: IDL wish list (continued)** - Next by Date:
**Re: FFTs in IDL** - Prev by thread:
**Re: IDL wish list (continued)** - Next by thread:
**Re: FFTs in IDL** - Index(es):