[SciPy-Dev] Overlap-add convolution implementation

[Todd]

Hi all,

I am currently working an an implementation of overlap-add convolution
[0].  I have a 1D implementation working and I am going to start expanding
it to ND.  Overlap-add convolution can provide significant performance
benefits over FFT-based convolution.  Does this make sense for scipy?

Assuming it is, I have a couple questions.

First is the name.  We have "convolve" and "fftconvolve" already.  A few
options:

overall_add_conv
oaconvolve
oadconvolve

Second is how to calculate the optimal chunk size for the convolution.  The
equation for the number of complex convolutions, according to wikipedia, is:

(Nx/(N-M+1))*N*(log2(N)+1)

Where Nx is the signal length, M is the filter length, and N is the chunk
size.  I need to find the minimum of that equation.  Nx is a constant
scaling factor so I get rid of that.  But I still can't find a closed-form
solution to the equation.

Assuming there is no closed-form solution, I need another approach.  What I
am doing now is calculating the minimum across all possible power of 2
indices (I calculated the log of the ends, do a linear range, then convert
that back to linear steps to avoid doing logarithms on every step).
However, this means I miss the fast powers of 3 and 5.  I could do the
minimum for all powers, but that would take longer.  What would be a good
trade-off?

[0] https://en.wikipedia.org/wiki/Overlap%E2%80%93add_method
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20190614/21420bc5/attachment.html>