[Numpy-discussion] strange runtimes of numpy fft

[David Cournapeau]

On Fri, Nov 15, 2013 at 10:47 PM, Max Linke <max_linke at gmx.de> wrote:

> On Thu, 2013-11-14 at 17:19 +0000, David Cournapeau wrote:
> > 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).
> Ok I thought the fft is always O(N log N). But it makes sense that this
> only works if the input-size factorizes well. Thanks for clearing this
> up.
>

To be exact, there *are* FFT-like algorithms for prime number size, but
that's not implemented in numpy or scipy (see here:
http://numpy-discussion.10968.n7.nabble.com/Prime-size-FFT-bluestein-transform-vs-general-chirp-z-transform-td3171.htmlfor
an old discussion on that topic).

cheers,

David



>
> best Max
> >
> > 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
> > >
> > >
> > _______________________________________________
> > 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/20131115/5ded929b/attachment.html>