Algoritmo FFT de Bailey

Algoritmo de alto rendimiento

Algoritmo de Bailey (versión de 4 pasos) para una FFT de 16 puntos

La FFT de Bailey (también conocida como FFT de 4 pasos ) es un algoritmo de alto rendimiento para calcular la transformada rápida de Fourier (FFT). Esta variación del algoritmo FFT de Cooley-Tukey fue diseñada originalmente para sistemas con memoria jerárquica común en las computadoras modernas (y fue el primer algoritmo FFT en esta clase denominada "fuera del núcleo"). El algoritmo trata las muestras como una matriz bidimensional (de ahí otro nombre, un algoritmo FFT matricial ^[1] ) y ejecuta operaciones FFT cortas en las columnas y filas de la matriz, con una multiplicación de corrección por " factores twiddle " en el medio. ^[2]

El algoritmo recibió su nombre después de un artículo de David H. Bailey , FFTs in external or hierarchical memory , publicado en 1989. En este artículo, Bailey atribuye el algoritmo a WM Gentleman y G. Sande, quienes publicaron su artículo, Fast Fourier Transforms: for fun and profit , ^[3] unos veinte años antes en 1966. ^[4] El algoritmo puede considerarse una descomposición FFT de radix. ^[5] ${\displaystyle {\sqrt {n}}}$

A continuación se presenta una breve descripción general de cómo funciona la versión de "4 pasos" del algoritmo FFT de Bailey:

1. Los datos (en orden natural) se organizan primero en una matriz.
2. Luego, cada columna de una matriz se procesa independientemente utilizando un algoritmo FFT estándar.
3. Cada elemento de una matriz se multiplica por un coeficiente de corrección.
4. Luego, cada fila de una matriz se procesa independientemente utilizando un algoritmo FFT estándar.

El resultado (en orden natural) se lee columna por columna. Dado que las operaciones se realizan columna por columna y fila por fila, los pasos 2 y 4 (y la lectura del resultado) pueden incluir una transposición de matriz para reorganizar los elementos de una manera conveniente para el procesamiento. El algoritmo se asemeja a una FFT bidimensional , una FFT tridimensional (y más allá) se conocen como FFT de 5 pasos , FFT de 6 pasos , etc. ^{[2] [6]}

La FFT de Bailey se utiliza normalmente para calcular FFT de grandes conjuntos de datos, como los que se utilizan en aplicaciones científicas y de ingeniería. La FFT de Bailey es un algoritmo muy eficiente y se ha utilizado para calcular FFT de conjuntos de datos con miles de millones de elementos (cuando se aplicó a la transformación de teoría de números , los conjuntos de datos del orden de 10 ¹² elementos se procesaron a mediados de la década de 2000 ^[7] ).

Véase también

• Algoritmo FFT de fila-columna
• Algoritmo FFT de base vectorial

Referencias

1. Arndt 2010, pág. 438.
2. Hart, Tornaría y Watkins 2010, p. 191.
3. Gentleman, WM; Sande, G. (1966). "Transformadas rápidas de Fourier: por diversión y beneficio" (PDF) . Actas de la conferencia AFIPS, volumen 29. Conferencia conjunta de informática de otoño, 7-10 de noviembre de 1966. San Francisco, California. págs. 563–578.
4. Bailey 1989, pág. 2.
5. Frigo & Johnson 2005, pág. 2.
6. Al Na'mneh y Pan 2007, págs. 191-192.
7. Al Na'mneh y Pan 2007.

Fuentes

• Bailey, DH (marzo de 1989). "FFTS en la memoria externa de la jerarquía" (PDF) . Actas de la conferencia ACM/IEEE de 1989 sobre supercomputación - Supercomputing '89 . Vol. 4. ACM Press. págs. 23–35. doi :10.1145/76263.76288. ISBN 0897913418.S2CID 52809390  .
• Frigo, M.; Johnson, SG (febrero de 2005). "El diseño y la implementación de FFTW3". Actas del IEEE . 93 (2): 216–231. Bibcode :2005IEEEP..93..216F. CiteSeerX  10.1.1.66.3097 . doi :10.1109/JPROC.2004.840301. ISSN  0018-9219. S2CID  6644892.
• Hart, William B.; Tornaría, Gonzalo; Watkins, Mark (2010). "Coeficientes theta de números congruentes con 1012" (PDF) . Teoría de números algorítmicos . Apuntes de clase en informática. Vol. 6197. Springer Berlin Heidelberg. págs. 186–200. doi :10.1007/978-3-642-14518-6_17. eISSN  1611-3349. ISBN 978-3-642-14517-9. ISSN  0302-9743.
• Al Na'mneh, Rami; Pan, W. David (marzo de 2007). "Algoritmo FFT de cinco pasos con complejidad computacional reducida". Information Processing Letters . 101 (6): 262–267. doi :10.1016/j.ipl.2006.10.009. ISSN  0020-0190.
• Arndt, Jörg (1 de octubre de 2010). "El algoritmo de matriz de Fourier (MFA)". Matters Computational: Ideas, Algorithms, Source Code . Springer Science & Business Media. págs. 438–439. ISBN 978-3-642-14764-7.OCLC 1005788763  .