python - Python SciPy convolve と fftconvolve

Question

一般的に言えば、配列が比較的大きい場合、FFT and multiplication通常は直接操作よりも高速です。convolveただし、非常に長い信号 (1000 万ポイントなど) と非常に短い応答 (1000 ポイントなど) を畳み込みます。この場合、fftconvolve2 番目の配列の FFT を最初の配列と同じサイズに強制するため、あまり意味がないようです。この場合、直接畳み込みを行う方が速いですか?

Answer 1

ここで行った比較を見てください。

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

あなたのケースは、単純な畳み込みの使用と FFT ベースの畳み込みの使用との間の移行に近い可能性があるため、(@Dougal がコメントで示唆しているように) 自分で時間を計ることが最善の策です。

(その比較では、重複追加または重複保存を行っていないことに注意してください。)

Answer 2

ご協力ありがとうございました。今、私は自分でテストを行い、サイズが 2^20 と 2^4 の 2 つの配列で畳み込みを行いました。結果は次のとおりです。

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

したがって、勝者がいます。numpy convolve は、他のものよりもはるかに高速です。なぜだかはまだわかりませんが。

---

ここで、サイズが 2^22 と 2^10 の 2 つの長い配列を試しました。結果は次のとおりです。

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

その差は大きくなるばかりです。

Answer 3

オーバーラップ加算アルゴリズムまたはオーバーラップ保存アルゴリズムによる FFT 高速畳み込みは、インパルス応答よりも小さい倍数 (2X など) だけの FFT を使用することで、限られたメモリで実行できます。長い FFT を、適切にオーバーラップされた短いがゼロ パディングされた FFT に分割します。

オーバーラップ オーバーヘッドがあっても、O(NlogN) は N と M が十分に大きい場合、M*N の効率を上回ります。