[SciPy-user] SciPy-user Digest, Vol 42, Issue 10

Anne Archibald peridot.faceted@gmail....
Wed Feb 7 11:20:13 CST 2007


On 07/02/07, Paul Ray <paul.ray@nrl.navy.mil> wrote:
>
> On Feb 7, 2007, at 9:04 AM, scipy-user-request@scipy.org wrote:
>
> > I have a problem with fft speed.
>
> The speed of most FFT algorithms depends greatly on the largest prime
> factor of N.
>
> Here are the factors of your example numbers:
>  >factor 186888
> 186888: 2 2 2 3 13 599
>
>  >factor 186890
> 186890: 2 5 11 1699
>
>  >factor 186889
> 186889: 186889
>
> Note that 186889 is prime!  This is the worst case situation!
> Numbers which are powers of 2 can be FFT'ed in order N*Log_2(N) time,
> while prime numbers take order N**2 time.  This is what you are seeing.
> You might do a survey of FFT algorithms to see which ones perform
> best on prime Ns.  Many you will find, work ONLY on power of 2 Ns!
> You should make sure that your SciPy is using FFTW3 for the FFT
> engine for sure, since I think it does about as well as possible on
> prime Ns.  You can read about FFTW at http://fftw.org

There are at least two algorithms to efficiently compute prime-length
FFTs (Rader's conversion and the chirp-z transform).

How does one determine which FFT package one is actually using? (I
normally use the scipy and numpy that are packaged in ubuntu edgy, but
even if you compile it yourself it may not be obvious whether it found
the packages you have installed.)

Anne M. Archibald


More information about the SciPy-user mailing list