[Numpy-discussion] Fast sizes for FFT

[Sturla Molden]

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