El Algoritmo FFT, un Breve Análisis

Ponente(s): Eder Alexander Trujillo Montaño, Eliseo Sarmiento Rosales, Pedro Vidales Rosales
Un algoritmo de transformación rápida de Fourier (FFT) es un algoritmo que calcula la transformación discreta de Fourier (DFT) en un tiempo acotado por O(nlogn). Se presentan sus propiedades como transformación lineal invertible, y su representación matricial con las raíces enésimas de la unidad para luego mostrar su utilidad en el procesamiento de señales digitales y evaluación de polinomios. Se presenta un algoritmo FFT, se hace un análisis contrastando la complejidad computacional con la definición de la DFT y se muestra una implementación para los dos casos mencionados.