[Numpy-discussion] Fast sizes for FFT

[Sturla Molden]

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