[Numpy-discussion] Fast sizes for FFT

[Luke Pfister]

On Wed, Dec 24, 2014 at 7:56 AM, Sturla Molden <sturla.molden at gmail.com>
wrote:

> On 24/12/14 14:34, Sturla Molden wrote:
> > I would rather have SciPy implement this with the overlap-and-add method
> > rather than padding the FFT. Overlap-and-add is more memory efficient
> > for large n:
>
> (eh, the list should be)
>
>
> - Overlap-and-add is more memory efficient for large n.
>
> - It scales as O(n) instead of O(n log n).
>
> - For short FIR filters overlap-and-add also allows us to use small
> radix-2 FFTs.
>
> - Small FFT size also means that we can use a small Winograd FFT instead
> of Cooley-Tukey FFT, which reduces the number of floating point
> multiplications.
>
> - A small look-up table is also preferable as it can be kept in cache.
>
> - Overlap-and-add is also trivial to compute in parallel. This comes at
> the expense of using more memory, but it never requires more memory than
> just taking a long FFT.
>
>
>
> Sturla
>
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>

Overlap-add would also be a great addition for convolution.  It gives a
sizeable speedup when convolving a short filter with a long signal.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20141224/40d00e0b/attachment.html>