Re: [SciPy-user] SciPy-user Digest, Vol 42, Issue 10
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 I rarely use FFT in SciPy/NumPy since there are many confusing statements in the instructions about FFTW2/FFTW3 support which don't make sense. The API changed from FFTW2 to FFTW3 and it is really important to get this right. I think FFTW2 support should be removed and someone should do a check to make sure the FFTW3 support is implemented correctly. Cheers, -- Paul
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
On Wed, Feb 07, 2007 at 12:20:13PM -0500, Anne Archibald wrote:
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).
Here is a rough implementation (I don't guarantee anything). Cheers Stéfan
participants (3)
-
Anne Archibald -
Paul Ray -
Stefan van der Walt