FFT in MATLAB
A.E lover
do yo know what algorithm MATLAB's fft function based on? I read from
MATLAB's help, it is something called FFTW. Is it a radix 2 or radix 4
or anything else?
Thank you.
Georgios Kokovidis
Steven G. Johnson
FFTW uses a variety of fixed radices, from 2 to 64, as well as
arbitrary radices of size ~sqrt(N) for very large lengths N, to prime
radices for large prime factors (handled by O(N log N) algorithms).
Also, its implementation style is radically different from the
"radix-2" and "radix-4" examples that you are likely to find in
textbooks.
For more information, see the "Documentation" section of the FFTW home
page (www.fftw.org), and in particular the paper:
Matteo Frigo and Steven G. Johnson, "The Design and Implementation of
FFTW3," Proceedings of the IEEE 93 (2), 216-231 (2005).
http://fftw.org/fftw-paper-ieee.pdf
I would suggest reading sections I and II of the paper if you are
curious, especially section II, since these give a general overview of
FFTW and FFT algorithms in 2.5 pages.
Regards,
Steven G. Johnson