[SciPy-user] FFT speed ?

[Anne Archibald]

On 07/02/07, Scott Ransom <sransom at nrao.edu> wrote:
> On Wed, Feb 07, 2007 at 12:13:12PM -0500, Anne Archibald wrote:

> > Can FFTW (or any of the FFT packages numpy/scipy can use) compute an
> > FFT of size 186889 in a reasonable time? I know there are algorithms
> > for large prime factors, and for small prime factors, and that you can
> > combine the two (though perhaps primes of moderate size are a
> > problem).
>
> I know that FFTW uses O(NlogN) algorithms for any N, even large
> prime factors.  It is quite likely that for large prime N, FFTPACK
> (which is what numpy uses) goes to a standard DFT algorithm
> (O(N^2)).

Indeed, for numbers in the vicinity of 10000, some take 500 times as
long as others (on my machine), so I suspect that it is falling back
to a DFT.

> One important thing to remember is that the constant in front of
> the NlogN is highly dependent on the algorithm.  That is why even
> though FFTW v3 uses NlogN algorithms for all N, some N (like
> powers of 2 and those composed of only small prime factors) are
> _much_ faster than those for other N.  But the bottom line is that
> no matter what the constant, for large N, O(NlogN) is _much_ faster
> than O(N^2).

Of course. But when you say the constant varies, do you mean by a
factor of ten? a hundred? a thousand?

On my machine, scipy.show_config reports that it can find FFTW2 but
not FFTW3; does that mean it is actually *using* FFTW2? How does one
tell?

Does scipy provide any access to the special features of FFTW's
interface? (wisdom, for efficiently computing many FFTs on the same
array, for example)

Anne M. Archibald