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.

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)

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 non-discrete 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

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

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!

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.

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

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.