[SciPy-user] FFT speed ?

Scott Ransom sransom@nrao....
Wed Feb 7 11:35:43 CST 2007


On Wed, Feb 07, 2007 at 12:13:12PM -0500, Anne Archibald wrote:
> On 07/02/07, Samuel GARCIA <sgarcia@olfac.univ-lyon1.fr> wrote:
> >
> >  Yes I know this.
> >  But 186888 186889 and 186890 are not power of 2 and the computation time is
> > very very different just for a difference of size of only one point.
> >  What is the reason ?
> >  And how to deal with that ? (I realy need to compute fft with a random
> > nomber of point)
> 
> Many problems can be solved by padding. But once in a while one comes
> up which needs a particular number of points, and it's not always a
> power of two.
> 
> 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)).  

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).

Scott

-- 
Scott M. Ransom            Address:  NRAO
Phone:  (434) 296-0320               520 Edgemont Rd.
email:  sransom@nrao.edu             Charlottesville, VA 22903 USA
GPG Fingerprint: 06A9 9553 78BE 16DB 407B  FFCA 9BFA B6FF FFD3 2989


More information about the SciPy-user mailing list