CFD Online Logo CFD Online URL
www.cfd-online.com
[Sponsors]
Home > Forums > Main CFD Forum

FFT with no requirement 2^N

Register Blogs Members List Search Today's Posts Mark Forums Read

Reply
 
LinkBack Thread Tools Display Modes
Old   March 9, 2005, 11:38
Default FFT with no requirement 2^N
  #1
Annie
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.
  Reply With Quote

Old   March 9, 2005, 11:43
Default Re: FFT with no requirement 2^N
  #2
ulysses
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)
  Reply With Quote

Old   March 9, 2005, 11:57
Default Re: FFT with no requirement 2^N
  #3
James Date
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 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
  Reply With Quote

Old   March 9, 2005, 12:18
Default Re: FFT with no requirement 2^N
  #4
Lionel Larcheveque
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
  Reply With Quote

Old   March 11, 2005, 12:29
Default Re: FFT with no requirement 2^N
  #5
noName
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!
  Reply With Quote

Old   March 11, 2005, 14:14
Default Re: FFT with no requirement 2^N
  #6
Chris Bailey
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.
  Reply With Quote

Old   March 11, 2005, 15:52
Default Re: FFT with no requirement 2^N
  #7
Guillaume
Guest
 
Posts: n/a
Go on the Cornell University website. There are the Numerical Recipes. Their theoretical presentation of FFT is valuable.
  Reply With Quote

Old   March 14, 2005, 05:51
Default Re: FFT with no requirement 2^N
  #8
Steve
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.
  Reply With Quote

Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


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 cross-correlation 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


All times are GMT -4. The time now is 16:55.