[SciPy-Dev] PR for overlap-add convolution

[Todd]

On Thu, Sep 26, 2019 at 10:43 PM Nathaniel Smith <njs at pobox.com> wrote:

> On Thu, Sep 26, 2019 at 6:51 PM Todd <toddrjen at gmail.com> wrote:
> > I have submitted a PR [1] for a new function, "oaconvolve", which is an
> implementation of the overlap-add algorithm for convolution.  This
> algorithm is much faster than conventional FFT-based > We previously
> discussed whether this should be its own function or part of fftconvolve.
> The performance and memory characteristics of this function are
> significantly different than those of fftconvolve and would really be used
> in different situations, so the consensus seemed to be that this should be
> its own function.  I would ultimately like "convolve" to be able to use
> oaconvolve when it is the best choice, but that is an issue for later.
> >
> > There is a "method" argument for choosing whether to automatically fall
> back on fftconvolve or raise an error.  Being able to prevent falling back
> on fftconvolve is essentially for testing.  We need to be able to make sure
> that oaconvolve is actually being tested and not the fftconvolve fallback.
> But this may not be the best way to do that.
>
> It seems like there's some contradiction between the idea that it
> needs to be its own function so that users can control which algorithm
> they're using, but then it sometimes silently falls back to
> fftconvolve, so they can't – and then you need an argument to disable
> the fallback because you do need to control the choice of algorithm.
>
> What would be the consequences of removing the fallback entirely?
>
> -n
>

You would get exceptions in specific, very hard-to-predict combinations of
shapes.  Unless you have total control over the shapes of the inputs, the
function couldn't be used safely on its own.  You would need to handle such
cases somehow.

To be clear, the situations where it falls back on fftconvolve are the
situations where oaconvolve reduces to fftconvolve.  It would be possible
to implement oaconvolve in these situations, and it would ultimately be the
same algorithm as fftconvolve, but it would add unnecessary time and memory
overhead compared to just using the fftconvolve fallback.  I didn't see the
point in doing a numerically identical algorithm slower, hence the
fallback.  Further, handling these situations in the oaconvolve function
would slow down the oaconvolve function under all conditions, not just
situations where oaconvolve reduces to fftconvolve.

I need the argument, or something like it, because I want to make sure the
tests don't hit situations where oaconvolve reduces to fftconvolve.  Even
if these situations where handled in oaconvolve itself rather than an
fftconvolve fallback, I would still need to be able to raise an exception
for these situations because I need to make sure the tests are actually
testing the oaconvolve algorithm, not the fftconvolve one.

The reason there are two functions are situations where fftconvolve and
oaconvolve are substantially different in their characteristics.  There is
no fallback in such cases, even if fftconvolve is faster.  Picking the
fastest algorithm for a given set of inputs should be handled by the
"convolve" function, but adding support for oaconvolve to convolve will be
a later pull request.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20190926/1a5ab2d3/attachment-0001.html>