
[Sponsors] 
March 9, 2005, 11:38 
FFT with no requirement 2^N

#1 
Guest
Posts: n/a

Hello! I am using FFT to solve PDEs and I'm searching for a Fast Fourier Transform which doesn't require the number of grid points to be 2^N. Anybody may provide me such a code (Fortran) or information about it?
thanks for answering. 

March 9, 2005, 11:43 
Re: FFT with no requirement 2^N

#2 
Guest
Posts: n/a

Just pad your data with zeros to have array sizes in 2^N !!
(for example : if the size is 13 then create an array of size 16 =2^4 then pad it with three 0's to index 16) 

March 9, 2005, 11:57 
Re: FFT with no requirement 2^N

#3 
Guest
Posts: n/a

I was also wondering how to do this a while back. I just padded the data with zero's and used a hanning window to sort out the problem with nondiscrete periods or leakage. I used Matlab to do the FFT analysis, but you could do it excel.
Check this web site out. http://www.me.psu.edu/me82/Learning/FFT/FFT.html Regards James 

March 9, 2005, 12:18 
Re: FFT with no requirement 2^N

#4 
Guest
Posts: n/a

Alternatively you can use an FFT library that include fast transform for other than 2^n sample size. See for instance http://www.fftw.org/. Note that it's basically a C library which may sometime be a little tricky to use with fortran.
Regards Lionel 

March 11, 2005, 12:29 
Re: FFT with no requirement 2^N

#5 
Guest
Posts: n/a

Padding with zeros is incorrect!
Padding with zeros is the equivalent of superimposing a step function onto your time series. This corresponds to (1/omega) spectrum superimposed on the actual FFT, so it's quite different from the original spectrum. I have encountered this several times, and is easiest to check in MATLAB. (MATLAB will give different a spectrum for data padded with zeros compared to the original data). There are several FFT libs that work with arbitrary number of data points (see http://www.fftw.org). Else, truncate your data to the right size, but don't add information (zeros) to the time series that does not exist! 

March 11, 2005, 14:14 
Re: FFT with no requirement 2^N

#6 
Guest
Posts: n/a

noName is right, padding with zeros makes it much easier to calculate the FT of a dataset that is very different from yours!
Truncating your dataset also changes things. The length of your dataset winds up being part of the transform in a sense. That is, the FT will have observations of the amplitudes and phases of periodic variability at 0, 1, 2 and so forth, cycles per the length of your dataset, with no information at all about noninteger numbers of cycles per your dataset. Looking at the lowest values in the frequency domain will make this clear. This is somewhat like the problem that most uses of Fourier Transforms are misuses because the Transform is only valid for datasets that are intrinsically cyclic themselves. For example, temperatures measured around the entire length of an iron hoop (Fourier's original example) are intrinsically cyclic. Or if you measured reflectivity of the eye's iris as you sampled it at different locations circling around the center. These are perfectly fine applications. But any Fourier Transform applied to a time series has to be taking at least a little liberty with this  time never truly repeats. Why do you want to use FFT? I mean, why do you want the "fast" algorithm version of a fourier transform? Many problems that required "fast fourier transforms" in the past can be solved on modern powerful computers without the fast algorithm. This eliminates any restriction on the number of observations, or even on whether they are synchronous versus asynchronous. The 2^n requirement is just an issue of the "fast" algorithm, and does not relate directly to Fourier Transforms in general. If you really need the FFT, I think there are modified versions with less restrictive requirements, like ones that can do 1.5*2^n or 1.25*2^n or 1.75*2^n. Also you can apply tapered envelopes as multipliers on your variable, so the amplitudes all go to zero at the ends but 1 everywhere not close to an end. 

March 11, 2005, 15:52 
Re: FFT with no requirement 2^N

#7 
Guest
Posts: n/a

Go on the Cornell University website. There are the Numerical Recipes. Their theoretical presentation of FFT is valuable.


March 14, 2005, 05:51 
Re: FFT with no requirement 2^N

#8 
Guest
Posts: n/a

My guess is that the CFD code that produces the results isn't "fast", so any savings gained by using a "Fast" Fourier transform are going to be minimal.


Thread Tools  
Display Modes  


Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
FFT for Post Simulation Analysis  faisal_durr  CFX  12  March 13, 2012 04:35 
FFT solver for Poisson equation  mranji1  Main CFD Forum  1  November 16, 2009 02:12 
qurey regarding fft.  sunil  Main CFD Forum  0  June 26, 2008 02:11 
PIV: fft crosscorrelation with large searchwindow  Liang  Main CFD Forum  0  April 11, 2005 14:39 
fft of unsteady solution  K S Chang  Main CFD Forum  6  January 15, 2004 07:42 