fft is unusable of moderately large arrays with a size which is a prime number (Trac #506) #1104
Comments
|
Attachment added by @cournape on 2007-04-27: interruptible_fft.patch |
|
@cournape wrote on 2007-04-27 I attached a patch which solves the interruptible part. |
|
@alberts wrote on 2007-05-12 Looks like the interruptible patch at least can be applied for 1.0.3. After that the milestone should probably be updated to address the rest of the issue in a next release. |
|
Milestone changed to |
|
@charris wrote on 2007-05-12 As far as I know, there is no fast algorithm for the prime numbers other than fast convolution, i.e., http://en.wikipedia.org/wiki/Bluestein's_FFT_algorithm. As Bluestein's algorithm also works for the chirp-z transform we might prefer to implement the latter, or maybe put it in scipy. |
|
@charris wrote on 2007-05-13 Davids patch works for me, so I am going to commit the patch and close the bug. Making a fast transform for a prime number of elements is an enhancement. We probably need a chirp-z transform, either in numpy or in scipy, but its current lack is not a bug. |
|
@stefanv wrote on 2007-05-13 According to http://www.fftw.org/fftw-paper-ieee.pdf FFTW implements Bluestein's algorithm. A python implementation is available at http://www.mail-archive.com/numpy-discussion@scipy.org/msg01812.html |
Original ticket http://projects.scipy.org/numpy/ticket/506 on 2007-04-27 by @cournape, assigned to unknown.
Currently, using fft on arrays of size which has a prime number is extremely slow (up to 15 minutes for eg an array of size 100003). The major problem though is that the code being uninterruptible, this effectively kills the current python session. My understanding is that the fft in numpy is using fftpack converted in C, which uses a O(N^2) algorithm for prime numbers ? Would it be possible at least to make the code interruptible ?
{{
!python
import numpy as N
from scipy import fftpack
prime is a prime number
prime = 100003
a = N.random.randn(prime)
print 'scipy computing...'
fftpack.fft(a)
print 'numpy computing...'
N.fft.fft(a)
}}
The text was updated successfully, but these errors were encountered: