Python SciPy convolve vs fftconvolve

Ich weiß im Allgemeinen FFT and multiplication ist in der Regel schneller als direkte convolve Betrieb, wenn das Array relativ groß ist. Allerdings falte ich ein sehr langes Signal (sagen wir 10 Millionen Punkte) mit einer sehr kurzen Antwort (sagen wir 1 tausend Punkte). In diesem Fall scheint die fftconvolve nicht viel Sinn zu machen, da sie eine FFT des zweiten Arrays auf die gleiche Größe des ersten Arrays erzwingt. Ist es in diesem Fall schneller, direkt zu falten?Python SciPy convolve vs fftconvolve

Quelle

2013-02-22 LWZ

Gibt es einen Grund, warum man beide Ansätze nicht einfach zeitlich aufeinander abstimmen kann, zB mit 'timeit'? – Dougal

Ich kannte diese Funktion nicht. Ich werde es versuchen. Ich möchte aber auch die zugrundeliegende Theorie kennen. – LWZ

FFT schnelle Faltung über die Overlap-Add- oder Overlap-Save-Algorithmen kann in begrenztem Speicher erfolgen, indem eine FFT verwendet wird, die nur ein kleines Vielfaches (wie 2X) größer als die Impulsantwort ist. Es bricht die lange FFT in richtig überlagerte kürzere, aber nicht gepolsterte FFTs auf.

Auch mit der Überlappung Kopf, O (NlogN) für groß genug, um N und M. Effizienz M * N schlagen

Quelle

2013-02-22 08:46:40 hotpaw2

Danke für deine Antwort! Meinst du, selbst mit der 'fftconvolve'-Funktion wird es automatisch lange FFT in kurze FFTs zerlegen und ich brauche mich nicht darum zu kümmern? – LWZ

@LWZ: scipy's fftconvolve macht das nicht, nein. Hotpaw, haben Sie eine Referenz/Implementierung für diese Methode? – endolith

einen Blick auf den Vergleich nehmen ich hier tat:

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

Ihr Fall könnte sich in der Nähe des Übergangs zwischen der Verwendung einer einfachen Faltung und der Verwendung der FFT-basierten Faltung befinden. Daher ist Ihre beste Wette (wie von @Dougal in einem Kommentar vorgeschlagen), die Zeit selbst zu bestimmen.

(Beachten Sie, dass ich nicht in diesem Vergleich Overlap-Add oder Überlappungen speichern tat.)

Quelle

2013-02-22 17:06:05

der Link scheint nicht zu zeigen, was du meintest (obwohl ich es trotzdem auf der Seite finden konnte) – luca

@luca Danke. Diese Seite war ursprünglich auf dem alten Scipy-Wiki, das jetzt verschwunden ist. Ich habe den Link aktualisiert. –

Dank für Ihre Hilfe danken. Jetzt habe ich den Test selbst tat, tat ich Faltung mit 2 Arrays, Größe von 2^20 und 2^4 und das ist das Ergebnis:

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

So haben wir einen Gewinner, numpy convolve sind viel schneller als die Anderen. Ich weiß immer noch nicht warum.

Jetzt habe ich 2 längere Arrays, Größe von 2^22 und 2^10 versucht. Das Ergebnis ist:

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

Der Unterschied wird nur größer.

Quelle

2013-03-05 06:36:10 LWZ

Antwort

Verwandte Themen