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

[LittleBigBrain]

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?)

As I tested, scipy.fftpack.fft is nearly as twice fast as numpy.fft.fft
But how about scipy.signal package?
I also found several convolve function:
numpy.convolve
scipy.signal.convolve
scipy.signal.fftconvolve
scipy.fftpack.convolve.convolve
Which convolve function is speeded up by LAPACK? especially those
non-FFT based convolution.
>From the source, it looks like fftpack.convolve and signal.fftconvolve
all based on fftpack, then what is the difference between them?

I also wondering scipy.signal.lfilter is based on a convolve function or not?
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.
Should it be much faster to implement a filter function via LAPACK
convolution routine?

Thanks ahead,

LittleBigBrain
_______________________________________________
SciPy-User mailing list
SciPy...@scipy.org
http://mail.scipy.org/mailman/listinfo/scipy-user

[David]

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. Note that it supports types beyond what LAPACK would
support (integers, long double, python objects), but LAPACK has no
convolution function anyway, so I am not sure to understand what you are
refering to ?

cheers,

David

[josef...@gmail.com]

On Wed, Nov 10, 2010 at 7:53 PM, David <da...@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.

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.

I think, there are also differences in performance depending on the
shapes of the arrays for nd.

Josef

[David]

On 11/11/2010 10:10 AM, josef...@gmail.com wrote:
> On Wed, Nov 10, 2010 at 7:53 PM, David<da...@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...

[braingateway]

David :

> 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. Note that it supports types beyond what LAPACK would
> support (integers, long double, python objects), but LAPACK has no
> convolution function anyway, so I am not sure to understand what you are
> refering to ?
>

Oh, sad! Because, MKL seems to have this routine, so I thought usual
LAPACK has it. MATLAB conv() and filter() based on this, making it much
faster.

> cheers,
>
> David
> _______________________________________________
> SciPy-User mailing list
> SciPy...@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>

Thanks a lot!

LittleBigBrain

[braingateway]

David :

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...@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>

Sincerely,

LittleBigBrain

[josef...@gmail.com]

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

Josef

[braingateway]

josef...@gmail.com :

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.

LittleBigBrain

[josef...@gmail.com]

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

Thanks,

Josef