# FFT with no requirement 2^N

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

 March 9, 2005, 11:38 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.

 March 9, 2005, 11:43 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)

 March 9, 2005, 11:57 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

 March 9, 2005, 12:18 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

 March 11, 2005, 12:29 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!

 March 11, 2005, 14:14 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.

 March 11, 2005, 15:52 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.

 March 14, 2005, 05:51 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.

 Thread Tools Display Modes Linear Mode

 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 OffTrackbacks are On Pingbacks are On Refbacks are On Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post faisal_durr CFX 12 March 13, 2012 04:35 mranji1 Main CFD Forum 1 November 16, 2009 02:12 sunil Main CFD Forum 0 June 26, 2008 02:11 Liang Main CFD Forum 0 April 11, 2005 14:39 K S Chang Main CFD Forum 6 January 15, 2004 07:42

All times are GMT -4. The time now is 14:57.