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 [email protected] http://mail.scipy.org/mailman/listinfo/numpy-discussion
