I am not sure what cases you use, but as you can see, there is almost no reason to use Overlap & Save. In the diagonal and lower triangle we have which method was faster: So the upper triangle of the matrix, in Dark Blue isn’t relevant. I only did the case the signal isn’t shorter than the kernel. In the past, using MATLAB, my testing showed you need very long signals and kernels to justify using methods using DFT (Overlap and Save, etc…). Also its implementation isn’t as optimal as it should be. I’m not sure how up to date this package is: GitHub - aamini/FastConv.jl: Fast Convolutions in Julia but as you can see it was faster. I’d bet that direct method with proper vectorization and efficient code will beat overlap and save. I usually expect the convolution of a length- N array and a length- M array to be length N+M-1, but that should be documented. Seems like conv could be smart enough to always do the right thing, but someone needs to add that check. The conv implementation currently selects between those two algorithms depending on the size of the input, but it would be good for it to also select the direct method when one of the inputs is small enough.īasically it’s a matter of perspective - some folks say “FFT convolution is only useful for really big inputs” and other say “direct convolution is only useful for really small inputs”. As you mention, for similarly-sized inputs the FFT approach is generally better, and when they are very differently-sized you want to use overlap-save convolution, which uses FFTs in a block-wise fashion. For instance I’m generally not convolving with filters that are small enough for the direct implementation to be efficient. I think this is one of those things that’s pretty field-specific. This is the reason, for instance, that MATLAB chose direct implementation for conv() while for cross correlation, which usually deals with signals with similar length, it uses fft() based method. Well, it is only faster for really large cases and where the kernel and the signal have similar size.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |