[SciPy-User] which FFT, convolve functions are the fastest one?
David
david@silveregg.co...
Wed Nov 10 19:38:07 CST 2010
On 11/11/2010 10:10 AM, josef.pktd@gmail.com wrote:
> On Wed, Nov 10, 2010 at 7:53 PM, David<david@silveregg.co.jp> wrote:
>> On 11/11/2010 08:41 AM, LittleBigBrain wrote:
>>> Hi everyone,
>>>
>>> I found lots of implement of FFT and convolve
>>> numpy.fft
>>> scipy.fftpack
>>> scipy.signal.fft (from the source, it seems all import from scipy.fftpack?)
>>
>> scipy.fftpack is faster than numpy.fft, scipy.signal.fft is the same as
>> scipy.fftpack as you noticed.
>>
>>>> From the source, it looks like fftpack.convolve and signal.fftconvolve
>>> all based on fftpack, then what is the difference between them?
>>
>> Different APIs (mostly for historical reasons AFAIK)
>>
>>> I take a glance at the lfilter.c, surprisingly it is a completely
>>> naive implement via polynomial function. I hope I am wrong about this.
>>
>> No, you're right, it is a straightforward implementation of time-domain
>> convolution.
>
> Signal.lfilter is an IIR filter and does convolution only as a special
> case, and only with "same" mode. I'm very happy with it, and wish we
> had a real nd version.
By convolution, I meant the broad, signal processing kind of definition
(with multiple boundary effects modes), not the mathematical definition
which ignores boundary effects.
> One difference in the speed I found in references and using it,
> without real timing:
> fftconvolve is only faster if you have two long arrays to convolve,
> not if a long array is convolved with a short array.
Yes, that's exactly right: convolution of 1d signals of size M and N is
roughly O(MxN), whereas fft-based will be O(P log (P)) - which one is
"best" depends on the ration M/N. There is also an issue with naive
fft-based convolution: it uses a lot of memory (the whole fft has to be
in memory).
Certainly, one could think about implementing smarter strategies, like
short-time fourier kind of techniques (OLA or OLS), which avoid taking
the whole signal FFT, and as such avoid most usual issues associated
with FFT-based convolution. I had such an implementation somwhere in the
talkbox scikits, but I am not sure I ever committed something, and I
don't really have time to work on it anymore...
cheers,
David
More information about the SciPy-User
mailing list