[SciPy-Dev] Overlap-add convolution implementation

[Todd]

On Fri, Jun 14, 2019 at 7:29 PM Andras Deak <deak.andris at gmail.com> wrote:

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

I tried that but couldn't figure out anything.  I will look again.
Strictly speaking it is keeping the number of multiplications minimal,
rather than the number of convolutions (no convolutions are actually being
done).

Keep in mind, though, that if I stick to only powers of two, there are only
32 values between, say, 128 and 1 trillion.  The problem with that approach
is that we lose powers of 3 and 5, which would more than double the number
of values needed.    But I am skeptical whether a heuristic would have much
advantage in either performance or accuracy compared to simply calculating
powers of 2.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20190617/7846f4b8/attachment-0001.html>