Свертка БПФ не быстрее, чем вычисление канонической свертки

Пару месяцев назад я узнал, что свертки вычисляются самым быстрым способом с использованием алгоритма FFT (еще больше с библиотекой FFTW)

Используя следующий код, я получил противоречивые результаты.

импорт

from scipy import fftpack
from numba import jit

Свертка с БПФ:

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

Свертка по формуле:

@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

Это важные функции в очень сложном процессе, разница возникает только при использовании одной или другой версии.

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

** test2 вычисляет больше сверток за тест.*

Тест показывает, что код с FFT медленнее, и я не могу понять, почему, так как fftpack явно называет библиотеку FFTW, которая является "самой быстрой на западе"...

Любое руководство приветствуется.

Вывод для меня заключается в том, что компиляция Numba JIT невероятно быстро.

Источник

2 ответа

Решение

Вы возвращаете только одно значение (n:th) свертки, а не полный массив. С FFT вы всегда вычисляете все значения, тогда как в вашей функции conv вы вычисляете только то, что вам нужно. По сложности, FFT - это O(N*log(N)), а ваша реализация conv - это O(N). Если бы вы реализовали наивную функцию извлечения, которая бы возвращала полную свертку, это было бы O(N^2). Так что, если вы хотите получить полный извилистый массив, лучше всего делать это БПФ. Если вам нужно только значение n:th, ваш метод является наилучшим по сложности.

Источник

Вы должны иметь возможность создавать меньше временных массивов, используя этот тип синтаксиса, что должно сделать его быстрее.

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
Источник
Другие вопросы по тегам