[Numpy-discussion] Fast sizes for FFT
luke.pfister at gmail.com
Wed Dec 24 11:51:53 EST 2014
On Wed, Dec 24, 2014 at 7:56 AM, Sturla Molden <sturla.molden at gmail.com>
> 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
> - 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.
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
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...
More information about the NumPy-Discussion