Zero padding in FFTW

Dear All,

I want to do zero padding of of the data and than do fft by
FFTW(www.fftw.org).

The dummiest way is to make an array which has more elements than the
data set size. However, it takes more  memory space and more
computation time. I'm wondering if there is a way to tell FFTW do zero
padding automatical and compute the fft.

Best wishes,
Peng

Real data or complex data?
How many points of data, how many points of zeropadding?

Dirk

Complex data.

Say I have n complex numbers, I want to pad it with at least 10n
complex numbers (this is for 1D array). For 2D array, that's 100n^2
padding for n^2 complex numbers.

Thanks,
Peng

On 5 Mar 2005 07:51:11 -0800, dbell@niitek.com wrote:

>Real data or complex data?
>How many points of data, how many points of zeropadding?
>
>Dirk

Peng Yu wrote:
> I want to do zero padding of of the data and than do fft by
> FFTW(www.fftw.org).
>
> The dummiest way is to make an array which has more elements than the
> data set size. However, it takes more  memory space and more
> computation time. I'm wondering if there is a way to tell FFTW do
zero
> padding automatical and compute the fft.

FFTW only computes the ordinary DFT; for anything beyond that you are
on your own (although you can use FFTW as a part of your algorithm, of
course).

There are a couple of approaches to what you seem to want, if I
understand you correctly.

First, if you want *all* of the DFT outputs from zero-padded inputs,
then you can't really save any memory--you still need storage for the
outputs, after all.  However, you can save some (but not too much) time
compared to a full FFT, using what is known as a "pruned" FFT.  There
is some description of this at fftw.org/pruned.html, including code
snippets for the inverse case (computing a few *outputs* from *all* of
the inputs); in your case you reverse the steps.

Second, if the reason you are zero-padding is to get a smoother
spectrum (i.e. to interpolate the spectrum to a higher resolution,
although resolution of spectral features is not really improved), then
you might look instead at the "chirp-z" algorithm instead; see:
http://en.wikipedia.org/wiki/Bluestein%27s_FFT_algorithm

Cordially,
Steven G. Johnson

Hi,

I think what I need is to get a smoother spectrum and only compute the
low frequency amplitude. Is there any implementation of the following
alogrithm? Or can I use FFTW to achieve my goal? Thanks!

Best wishes,
Peng

>Second, if the reason you are zero-padding is to get a smoother
>spectrum (i.e. to interpolate the spectrum to a higher resolution,
>although resolution of spectral features is not really improved), then
>you might look instead at the "chirp-z" algorithm instead; see:
>http://en.wikipedia.org/wiki/Bluestein%27s_FFT_algorithm

Hi,

I think what I need is to get a smoother spectrum and only compute the
low frequency amplitude. Is there any implementation of the following
alogrithm? Or can I use FFTW to achieve my goal? Thanks!

Best wishes,
Peng

>Second, if the reason you are zero-padding is to get a smoother
>spectrum (i.e. to interpolate the spectrum to a higher resolution,
>although resolution of spectral features is not really improved), then
>you might look instead at the "chirp-z" algorithm instead; see:
>http://en.wikipedia.org/wiki/Bluestein%27s_FFT_algorithm