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

[braingateway]

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.
> 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