On Wed, Dec 24, 2014 at 7:56 AM, Sturla Molden <sturla.mol...@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@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.
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion