पाइथन SciPy convolve बनाम fftconvolve

Question

मुझे आमतौर पर FFT and multiplication बोलने के बारे में पता है, आमतौर पर convolve ऑपरेशन से तेज़ होता है, जब सरणी अपेक्षाकृत बड़ी होती है। हालांकि, मैं बहुत कम प्रतिक्रिया के साथ एक बहुत लंबा सिग्नल (10 मिलियन अंक कहता हूं) को संकुचित कर रहा हूं (1 हजार अंक कहें)। इस मामले में fftconvolve अधिक समझ में नहीं आता है, क्योंकि यह दूसरी सरणी के एक एफएफटी को पहले सरणी के समान आकार में मजबूर करता है। क्या इस मामले में सीधे विश्वास करने के लिए तेज़ी से तेज है?

Answer 1

ओवरलैप-एड या ओवरलैप एल्गोरिदम के माध्यम से एफएफटी फास्ट कन्वोल्यूशन एक एफएफटी का उपयोग करके सीमित मेमोरी में किया जा सकता है जो आवेग प्रतिक्रिया से केवल एक छोटा सा (जैसे 2 एक्स) बड़ा होता है। यह लंबे एफएफटी को ठीक से ओवरलैप्ड छोटे लेकिन शून्य-गद्देदार एफएफटी में तोड़ देता है।

भी ओवरलैप भूमि के ऊपर, हे (NlogN) बड़ा पर्याप्त एन और एम

Answer 2

के लिए दक्षता में हरा एम * एन जाएगा तुलना मैं यहाँ किया था पर एक नजर डालें साथ:

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

आपका मामला एक सादे रूपांतरण का उपयोग करने और एफएफटी-आधारित संकल्प का उपयोग करने के बीच संक्रमण के निकट हो सकता है, इसलिए आपकी सबसे अच्छी शर्त (जैसा कि टिप्पणी में @ डौगल द्वारा सुझाया गया है) समय है।

(ध्यान दें कि मैं नहीं किया ओवरलैप जोड़ दें या कि तुलना में ओवरलैप-बचाने के।)

Answer 3

आपकी मदद के लिए धन्यवाद। अब मैं अपने आप को परीक्षण किया था, मैं 2 सरणियों, 2^20 और 2^4 के आकार के साथ घुमाव किया था, और यह परिणाम है:

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

तो हम है एक विजेता, numpy convolve है बहुत तेजी से है दूसरे। मैं अभी भी क्यों नहीं जानता कि क्यों।

---

अब मैंने 2 लंबे सरणी, 2^22 और 2^10 के आकार की कोशिश की। नतीजा यह है:

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

अंतर केवल बड़ा हो जाता है।