Python SciPy convolve vs fftconvolve

Question

Tôi biết nói chung FFT and multiplication thường nhanh hơn hoạt động trực tiếp convolve, khi mảng tương đối lớn. Tuy nhiên, tôi đang xoay chuyển một tín hiệu rất dài (nói 10 triệu điểm) với một phản ứng rất ngắn (nói 1 nghìn điểm). Trong trường hợp này, fftconvolve dường như không có ý nghĩa gì nhiều, vì nó buộc FFT của mảng thứ hai có cùng kích thước của mảng đầu tiên. Nó có nhanh hơn để thực hiện trực tiếp convolve trong trường hợp này?

Answer 1

Chuyển đổi nhanh FFT thông qua việc thêm chồng chéo hoặc chồng chéo thuật toán lưu có thể được thực hiện trong bộ nhớ giới hạn bằng cách sử dụng FFT chỉ là bội số nhỏ (như 2X) lớn hơn phản ứng xung. Nó phá vỡ FFT dài lên thành các FFT ngắn hơn nhưng không được chồng lên nhau.

Ngay cả với chi phí chồng chéo, O (NlogN) sẽ đánh bại M * N trong hiệu quả cho N đủ lớn và M.

Answer 2

Hãy nhìn vào sự so sánh tôi đã làm ở đây:

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

Trường hợp của bạn có thể ở gần quá trình chuyển đổi giữa việc sử dụng chuyển đổi đơn giản và sử dụng chuyển đổi dựa trên FFT, do đó, đặt cược tốt nhất của bạn (theo gợi ý của @Dougal trong nhận xét) là tự mình định thời gian.

(Lưu ý rằng tôi không thực hiện chồng chéo thêm hoặc trùng lặp-lưu trong so sánh đó.)

Answer 3

cảm ơn sự giúp đỡ của bạn. Bây giờ tôi đã thử nghiệm bản thân mình, tôi đã làm chập với 2 mảng, kích thước của 2^20 và 2^4, và đây là kết quả:

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

Vì vậy, chúng ta có một người chiến thắng, dây leo NumPy là nhanh hơn nhiều những người khác. Tôi vẫn không biết tại sao.

---

Bây giờ tôi đã thử 2 mảng dài hơn, kích thước 2^22 và 2^10. Kết quả là:

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

Sự khác biệt chỉ lớn hơn.