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