CODEWITHSUNDEEP
pythonnumba
Santi Peñate-Vera
Santi Peñate-Vera

Reputation: 1186

FFT convolution not being faster than the cannonical convolution computation

A couple of months ago I found out that convolutions are computed in the fastest possible way using the FFT algorithm (even more with the FFTW library)

Using the following code I have controversial results.

Imports

from scipy import fftpack
from numba import jit

Convolution with FFT:

def conv_fft(X, R):
    n = len(X)   
    a = fftpack.fft(X)
    b = fftpack.fft(R)
    c = a * b
    e = fftpack.ifft(c)
    result = e[n]
    return result

Convolution using the formula:

@jit(cache=True)
def conv(X, R):
    n = len(X)      
    result = complex_type(0)
    for i in range(n+1):
        result += X[n-i] * R[i]
    return result

This are critical functions in a much complex process, the difference arises only by using one version or the other.

       no FFT     with FFT   increment
Test1  0.028761   0.034139   0.0053780
Test2  0.098565   0.103180   0.0046150

** the test2 computes more convolutions per test.*

The test show that the code with FFT is slower and I cannot see why since the fftpack apparently call the FFTW library which is "the fastest in the west"...

Any guidance is appreciated.

A conclusion for my is that the numba JIT compilation is unbelievably fast.

Upvotes: 2

Views: 468

Answers (2)

ilmarinen
ilmarinen

Reputation: 5717

You're only returning a single value (the n:th one) of the convolution, not the full array. With FFT you always calculate all values, whereas in your conv function you only calculate the one you're after. Complexity-wise, the FFT is O(N*log(N)), and your implementation of conv is O(N). If you would implement a naive conv function that would return the full convolution, it would be O(N^2). So, if you want the full convoluted array your best bet is the FFT way of doing it. If you only want the n:th value, your method is complexity wise the best.

Upvotes: 2

Benjamin
Benjamin

Reputation: 11860

You should be able to get away with creating fewer temporary arrays, using this type of syntax, which should make it faster.

def conv_fft(X, R):
    fftpack.fft(X, overwrite_x=True)
    b = fftpack.fft(R)
    X *= b
    fftpack.ifft(X, overwrite_x=True)
    return X

Upvotes: 0

Related Questions