Python SciPy convolve vs fftconvolve

Wiem, że ogólnie rzecz biorąc, FFT and multiplication jest zwykle szybszy niż operacja bezpośrednia convolve, gdy macierz jest stosunkowo duża. Jednak zawieram bardzo długi sygnał (powiedzmy 10 milionów punktów) z bardzo krótką odpowiedzią (powiedzmy 1 tysiąc punktów). W tym przypadku fftconvolve nie wydaje się mieć większego sensu, ponieważ zmusza FFT drugiej macierzy do tego samego rozmiaru pierwszej macierzy. Czy w tym przypadku jest to szybsze po prostu wykonać bezpośrednie convolve?Python SciPy convolve vs fftconvolve

Źródło

2013-02-22 LWZ

Czy istnieje powód, dla którego nie można po prostu zmierzyć obu podejść, np. Za pomocą 'timeit'? – Dougal

Nie znałem tej funkcji. Spróbuję. Chciałbym jednak także poznać podstawową teorię. – LWZ

FFT szybkie splotowanie za pomocą algorytmów dodawania zakładek lub nakładania można wykonać w ograniczonej pamięci za pomocą FFT, która jest tylko małą wielokrotnością (np. 2X) większą niż odpowiedź impulsowa. Przerywa długi FFT w odpowiednio zachodzące na siebie krótsze, ale wyściełane FFT.

Nawet przy obciążeniu stropów, O (NlogN) pobije M * N wydajności dla wystarczająco dużej N i M.

Źródło

2013-02-22 08:46:40 hotpaw2

Dzięki za odpowiedź! Czy masz na myśli, że nawet z funkcją 'fftconvolve', automatycznie rozbija długą FFT na krótkie FFT i nie muszę się tym martwić? – LWZ

@LWZ: scipy's fftconvolve tego nie robi, nie. hotpaw, czy masz referencję/implementację dla tej metody? – endolith

Spójrz na porównanie zrobiłem tutaj:

http://scipy-cookbook.readthedocs.io/items/ApplyFIRFilter.html

Twoja sprawa może znajdować się w pobliżu przejścia pomiędzy zwykłym splotem a użyciem splotu opartego na FFT, więc najlepszym wyjściem (zgodnie z sugestią @Dougala w komentarzu) jest samodzielne zrobienie tego.

(Zauważ, że nie pokrywają dodaj lub pokrywają zapisywanie w tym porównaniu.)

Źródło

2013-02-22 17:06:05

link wydaje się nie wskazywać, co masz na myśli (mimo że I tak go znaleźć na stronie) – luca

@luca Dzięki. Ta strona była oryginalnie na starej wiki scipy, której już nie ma. Zaktualizowałem link. –

dziękuję za pomoc. Teraz zrobiłem sprawdzić się, zrobiłem splot z 2 tablic, wielkość 2^20 a 2^4, a jest to wynik:

numpy.convolve: 110 ms 
scipy.signal.convolve: 1.0 s 
scipy.signal.fftconvolve: 2.5 s

Więc mamy zwycięzcę, numpy convolve jest to znacznie szybciej niż inni. Wciąż nie wiem dlaczego.

Teraz wypróbowałem 2 dłuższe tablice o rozmiarze 2^22 i 2^10. Wynik:

numpy.convolve: 6.7 s 
scipy.signal.convolve: 221 s 
scipy.signal.fftconvolve: MemoryError

Różnica staje się większa.

Źródło

2013-03-05 06:36:10 LWZ

Python SciPy convolve vs fftconvolve

Odpowiedz

Powiązane problemy