[Numpy-discussion] strange runtimes of numpy fft

[David Cournapeau]

On Thu, Nov 14, 2013 at 4:45 PM, Charles Waldman <charles at crunch.io> wrote:

> Can you post the raw data?  It seems like there are just a couple of "bad"
> sizes, I'd like to know more precisely what these are.
>

Indeed. Several of the sizes generated by logspace(2, 7, 25) are prime
numbers, where numpy.fft is actually O(N^2) and not the usual O(NLogN).

There is unfortunately no freely (aka BSD-like licensed) available fft
implementation that works for prime (or 'close to prime') numbers, and
implementing one that is precise enough is not trivial (look at Bernstein
transform for more details).

David

>
> It's typical for FFT to perform better at a sample size that is a power of
> 2, and algorithms like FFTW take advantage of factoring the size, and
> "sizes that are products of small factors are transformed most efficiently."
>
>   - Charles
>
> On Thu, Nov 14, 2013 at 10:18 AM, Max Linke <max_linke at gmx.de> wrote:
>
>> Hi
>>
>> I noticed some strange scaling behavior of the fft runtime. For most
>> array-sizes the fft will be calculated in a couple of seconds, even for
>> very large ones. But there are some array sizes in between where it will
>> take about ~20 min (e.g. 400000). This is really odd for me because an
>> array with 10 million entries is transformed in ~2s. Is this typical for
>> numpy?
>>
>> I attached a plot and an ipynb to reproduce and illustrate it.
>>
>> best Max
>>
>> _______________________________________________
>> NumPy-Discussion mailing list
>> NumPy-Discussion at scipy.org
>> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>>
>>
>
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20131114/4ef2c181/attachment.html>