GSL fft benchmarks

["Steven G. Johnson" <stevenj at ab-initio dot mit dot edu>]

Hello GSL folks,

I thought you might be interested to here that we've recently updated our
FFT benchmarks for a variety of CPUs, now including both speed and
accuracy benchmarks:

	http://www.fftw.org/benchfft

They include benchmarks of the GSL fft routines (from versions 1.1.1-1.3,
depending on what was installed on each machine...though I don't think
your FFTs have changed much, right?).

As I think you are aware, your mixed-radix routines are usually faster
than your radix-2 routines on all the platforms we tested.  (Our plots
only show the faster of the two, the mixed-radix routines, but the raw
data for both can be downloaded as a text file from our site).

However, you may want to observe that your radix-2 routines are also less
accurate.  The reason for this, as described in our commentary

	http://www.fftw.org/accuracy/comments.html

is almost certainly the fact that you generate your trig. factors with a
recurrence that is less accurate than the FFT itself.  Realizing that you
want to keep it from needing extra storage for the trig. factors, there
are a couple of possible solutions:

1) In single precision, perform the recurrence in double precision (this
should be quite accurate).  In double precision on x86, use long-double
precision (this doesn't help on non-x86, though).

2) Use a more accurate recurrence scheme.  See e.g.
	O. Buneman, "Stable online creation of sines or cosines of
successive angles," Proc. IEEE 75 (10), 1434-1435 (1987).
	Manfred Tasche and Hansmartin Zeuner, "Improved roundoff error
analysis for precomputed twiddle factors," J. Computational Analysis and
Applications 4 (1), 1-18 (2002).

3) Punt, and just warn the user that they will lose an extra decimal place
(or more) of accuracy for large N (the additional error goes as
sqrt(N)) if they use the radix-2 routines.

I hope this is helpful.

Cordially,
Steven G. Johnson