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

[josef.pktd at gmail.com]

On Thu, Nov 11, 2010 at 10:34 AM, braingateway <braingateway at gmail.com> wrote:
> josef.pktd at gmail.com :
>> On Thu, Nov 11, 2010 at 3:40 AM, braingateway <braingateway at gmail.com> wrote:
>>
>>> David :
>>>
>>>> On 11/11/2010 10:10 AM, josef.pktd at gmail.com wrote:
>>>>
>>>>
>>>>> On Wed, Nov 10, 2010 at 7:53 PM, David<david at 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
>>
> FIR is actually a convolution. IIR can use Direct form II, which split
> into a feedback and a FIR. You can do it by maitainning a buffer and a
> convolution.

Do you have an example? I don't know what Direct form II is and how
this would work.

Thanks,

Josef

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