[plt-scheme] fft

On Thu, 2006-03-16 at 18:09 -0500, Will Farr wrote:
   . . .
> Doesn't FFTW already do this?  I seem to recall them having some sort
> of analyize step before running an FFT in which they optimize for the
> current hardware.

I believe you're right, it does, at least to some degree.  The question
is, are the optimizations provided by FFTW the best you can get in
software.  If better can be done, then more advanced techniques are
likely to be necessary.  Corey didn't specify whether the FFT was to be
1-dimensional, 2-dimensional, or higher, nor whether the FFT was to be
windowed (sliding), nor (if windowed) whether the window had to be
noise-filtered.  Nor did he mention what the point size had to be --
32-point, 128 point, 1024 point, non-power-of-2, ... .  Depending on the
answers to these questions, pretty sophisticated techniques will be
needed.  I don't know where FFTW is these days -- maybe all this stuff
is built in.  If so, great; if not, there is work that will have to be
done.

For example, if the data set is two-dimensional or higher, the standard
technique involves composing 1D FFTs over the tows, columns, etc. and
combining the results.  This involves multiple runs of the 1D FFT (see
_Numerical Recipes_, chap.12).  The Johnsons' work involves a
transformation of the data into a set of 1D points, applying a specially
constructed 1D FFT over that, and then inverting (in a certain sense)
the result to get the FFT of the higher-dimensioned data.

Does FFTW do this?  I don't know.

 -- Bill Wood