[SciPy-User] which FFT, convolve functions are the fastest one?

josef.pktd@gmai... josef.pktd@gmai...
Thu Nov 11 08:30:20 CST 2010


On Thu, Nov 11, 2010 at 3:40 AM, braingateway <braingateway@gmail.com> wrote:
> David :
>> 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).
>>
> Yes you are all right about this, that is why I asked "especially those
> convolve() does not based on FFT". I just wanna use to for IIR filters,
> which usually have an order far far less than 200.

How can you use (regular) convolve for IIR filters?
I thought it only works for moving average filters.

Josef


>> 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
>> _______________________________________________
>> SciPy-User mailing list
>> SciPy-User@scipy.org
>> http://mail.scipy.org/mailman/listinfo/scipy-user
>>
> Sincerely,
>
> LittleBigBrain
> _______________________________________________
> SciPy-User mailing list
> SciPy-User@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>


More information about the SciPy-User mailing list