On 24/12/14 04:33, Robert McGibbon wrote: > Alex Griffing pointed out on github that this feature was recently added > to scipy in https://github.com/scipy/scipy/pull/3144. Sweet!
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: - 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. This is also interesting: https://jakevdp.github.io/blog/2013/08/28/understanding-the-fft/ Sturla _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
