Python SciPy convolve vs fftconvolve

Question

In genere so che FFT and multiplication è in genere più veloce dell'operazione diretta convolve, quando l'array è relativamente grande. Tuttavia, sto convocando un segnale molto lungo (diciamo 10 milioni di punti) con una risposta molto breve (diciamo 1000 punti). In questo caso, il fftconvolve non sembra avere molto senso, dal momento che impone un FFT del secondo array alla stessa dimensione del primo array. È più veloce fare solo convolve diretta in questo caso?

Answer 1

La convoluzione rapida FFT tramite gli algoritmi di sovrapposizione o sovrapposizione può essere eseguita in memoria limitata utilizzando una FFT che è solo un piccolo multiplo (ad esempio 2X) più grande della risposta all'impulso. Rompe il lungo FFT in FFT più corti ma a zero sovrapposti correttamente sovrapposti.

Anche con l'overhead di sovrapposizione, O (N log N) batterà M * N in termini di efficienza per i grandi abbastanza N e M.

Answer 2

Date un'occhiata al confronto che ho fatto qui:

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

Il tuo caso potrebbe essere vicino alla transizione tra l'uso di una semplice convoluzione e l'utilizzo della convoluzione basata su FFT, quindi la soluzione migliore (come suggerito da @Dougal in un commento) è quella di cronometrarti.

(Si noti che non ho fatto sovrapposizione-aggiungere o sovrapporsi-save in quel confronto.)

Answer 3

grazie per il vostro aiuto. Ora ho fatto il test me stesso, ho fatto convoluzione con 2 array, dimensione di 2^20 e 2^4, e questo è il risultato:

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

Così abbiamo un vincitore, Convolve NumPy è è molto più veloce gli altri. Non so ancora perché.

---

Ora ho provato 2 array più lunghi, dimensioni di 2^22 e 2^10. Il risultato è:

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

La differenza aumenta.