fftconvolve speedup / non powers of two
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:
11.02.2012 11:52, Nicolas Rougier kirjoitti:
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 ?
The underlying library is not FFTW, so the FFTW documentation does not apply. However, IIRC, FFTPACK had factorizations for 2^a*3^b*5^c, so there might be room for similar improvement. However, one would need to check if there are some additional restrictions. -- Pauli Virtanen
Hi, 11.02.2012 11:52, Nicolas Rougier kirjoitti: [clip]
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).
Rescued from oblivion to here: http://projects.scipy.org/scipy/ticket/1621 I think your code can be easily adapted for whatever FFTPACK happens to support. I think the bases for it were 2,3,5, but this needs a double-check. Thanks, -- Pauli Virtanen
participants (2)
-
Nicolas Rougier
-
Pauli Virtanen