Home
Reading
Searching
Subscribe
Sponsors
Statistics
Posting
Contact
Spam
Lists
Links
About
Hosting
Filtering
Features Download
Marketing
Archives
FAQ
Blog
 
Gmane
From: Nicolas Rougier <Nicolas.Rougier <at> inria.fr>
Subject: fftconvolve speedup / non powers of two
Newsgroups: gmane.comp.python.scientific.devel
Date: Saturday 11th February 2012 10:52:21 UTC (over 4 years ago)
Hi,


FFTW documentation (http://www.fftw.org/fftw2_doc/fftw_3.html)
states that:

"FFTW is best at handling sizes of the form 2^a*3^b*5^c*7^d*11^e*13^f,
where e+f is either 0 or 1."

But the code from fftconvolve is only using (internally) sizes that are
power of two, is there a specific reason ?


I tried a naive implementation handling size of the above form and it seems
to speedup things a bit:

In [1]: from fftconvolve import *

In [2]: %timeit fftconvolve(Z,K,'full')
10 loops, best of 3: 57.3 ms per loop

In [3]: %timeit fftconvolve2(Z,K,'full')
100 loops, best of 3: 13.2 ms per loop


This is for the worst case where the internal size is 257. fftconvolve uses
a size of 512 while fftconvolve2 uses 260. For powers of two, it should not
change performances (only the time to compute best fft shape that may be
probably improved).




Nicolas



Here is the code:
 
CD: 4ms