[SciPy-dev] fft benchmarks for new routines

[Charles R Harris]

> > >Then we should bench your algorithms also against FFTW as FFTW is >
> >faster
> > >than FFTPACK.
> >
> > Where are the wrappers for FFTW? They seem to have disappeared from
> > scipy, certainly they didn't come down with the latest CVS update.
>
>FFTW as well as other FFT backends are wrapped by scipy.fftpack.

Ok, I'll do the benchmark.

I've been thinking about the benchmark results for long transforms. The
difference in actual computation times between different algorithms
should be insignificant, as memory access is so dominant. The main
difference should be the the number of passes thru the data:

radix 2 : lg(n) 
radix 4 : lg(n)/2 
radix 8 : lg(n)/3

after I unrolled the loop, the times of fftpack and my routines should
be identical. So why the difference? The accesses are basically the same
for the four varieties of fft -- decimation in time, decimation in
frequency + bit reversed versions of same -- except for the order in
which the coefficients are stored. If they are in linear order the
accesses will be less efficient than if they are in bitreversed order.
I suspect this is the only difference that accounts for the results.
This suggests that some sort of data chunking is the way to go here.
For shorter transforms the algorithm should make a difference, but this
is pretty much buried in the calling overhead. I suspect that a simple
radix 2 with chunking would look much the same to Python as even the
most comlicated algorithm.

Chuck