Re: Very large FFT

Rune Allnor wrote:
A 1M FFT is *formally* equivalent to multiplying a 1M x 1M matrix
with
a 1M vector.

That't mathematically true. But it is not the way how FFT works. FFT uses symmetries in this matrix introduced by the prime factors of it's size. Only if the size is a prime number, there is no redundency.

The matrix is known, though, so all the coefficients are
computed on the fly, and you don't actually use more than 2M or maybe
3M elements in memory.

That's true anyway.


Marcel
.