[SciPy-Dev] Overlap-add convolution implementation

[Andras Deak]

> 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.

If I understand correctly you're looking for an N(M) mapping of
optimal chunk size, where the given formula for the number of
convolutions is minimal. How about generating a (large) range of
reasonable M values, numerically evaluating each optimal N_{opt} for
the given M and plotting this N_{opt}(M) function, then trying to come
up with a reasonable heuristic based on that? If the functions (number
of convolutions vs N on one hand and N_{opt} vs M on the other) behave
reasonably enough (and hopefully they will) you might be able to come
up with a few intervals of M where you can approximate the N_{opt}(M)
function with something nice. Basically hand-rolling a piecewise
interpolating function for N_{opt}(M) to hard-wire in the
implementation.
I've never implemented anything like this so I might be completely
wrong, but my hunch is that having a "good enough" heuristic is better
than risking too much work (in terms of memory and CPU) to find the
strictly optimal chunk size on each call.
Regards,

András

> 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
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at python.org
> https://mail.python.org/mailman/listinfo/scipy-dev