¡Vaya!
Este artículo puede basarse excesivamente en fuentes demasiado relacionadas con el tema , lo que podría impedir que el artículo sea verificable y neutral . ( Abril de 2018 ) |
 El logotipo de FFTW | |
| Desarrollador(es) | Matteo Frigo y Steven G. Johnson |
|---|---|
| Lanzamiento inicial | 24 de marzo de 1997 ( 24 de marzo de 1997 ) |
| Versión estable | 3.3.10 [1] / 15 de septiembre de 2021 ( 15 de septiembre de 2021 ) |
| Repositorio |
|
| Escrito en | C , OCaml |
| Tipo | Software numérico |
| Licencia | GPL , comercial |
| Sitio web | www.fftw.org |
La Transformada de Fourier más rápida de Occidente ( FFTW ) es una biblioteca de software para calcular transformadas de Fourier discretas (DFT) desarrollada por Matteo Frigo y Steven G. Johnson en el Instituto Tecnológico de Massachusetts . [2] [3] [4]
FFTW es una de las implementaciones de software libre más rápidas de la transformada rápida de Fourier (FFT). Implementa el algoritmo FFT para matrices de valores reales y complejos de tamaño y dimensión arbitrarios.
Biblioteca
FFTW transforma rápidamente los datos al admitir una variedad de algoritmos y elegir el que estima o mide (una descomposición particular de la transformación en transformaciones más pequeñas) que es preferible en las circunstancias particulares. Funciona mejor en matrices de tamaños con factores primos pequeños , siendo las potencias de dos óptimas y los primos grandes el peor de los casos (pero aún O ( n log n )). Para descomponer las transformaciones de tamaños compuestos en transformaciones más pequeñas, elige entre varias variantes del algoritmo FFT de Cooley-Tukey (que corresponden a diferentes factorizaciones y/o diferentes patrones de acceso a la memoria), mientras que para tamaños primos utiliza el algoritmo FFT de Rader o de Bluestein . [2] Una vez que la transformación se ha dividido en subtransformaciones de tamaños suficientemente pequeños, FFTW utiliza FFT desenrolladas codificadas de forma rígida para estos tamaños pequeños que se produjeron (en tiempo de compilación , no en tiempo de ejecución ) mediante la generación de código ; Estas rutinas utilizan una variedad de algoritmos que incluyen variantes de Cooley-Tukey, el algoritmo de Rader y algoritmos FFT de factores primos . [2]
Para una cantidad suficientemente grande de transformaciones repetidas, resulta ventajoso medir el rendimiento de algunos o todos los algoritmos admitidos en el tamaño de matriz y la plataforma determinados . Estas mediciones, a las que los autores denominan "sabiduría", se pueden almacenar en un archivo o una cadena para su uso posterior.
FFTW tiene una "interfaz de gurú" que pretende "exponer la mayor flexibilidad posible en la arquitectura FFTW subyacente". Esto permite, entre otras cosas, transformaciones multidimensionales y transformaciones múltiples en una sola llamada (por ejemplo, cuando los datos se intercalan en la memoria).
FFTW tiene un soporte limitado para transformaciones fuera de orden (usando la versión de Interfaz de Paso de Mensajes (MPI)). La reordenación de datos genera una sobrecarga, que para las transformaciones in situ de tamaño y dimensión arbitrarios no es trivial de evitar. No está documentado para qué transformaciones es significativa esta sobrecarga.
FFTW está licenciada bajo la Licencia Pública General de GNU . También está licenciada comercialmente (por un costo de hasta $12,500) por el MIT [5] y se utiliza en el paquete comercial de matrices MATLAB [6] para calcular FFT. FFTW está escrito en lenguaje C , pero existen interfaces Fortran y Ada , así como interfaces para algunos otros lenguajes. Si bien la biblioteca en sí es C, el código en realidad se genera a partir de un programa llamado ' genfft', que está escrito en OCaml . [7]
En 1999, FFTW ganó el Premio JH Wilkinson de Software Numérico .
Véase también
.svg/1280px-Free_and_open-source_software_logo_(2009).svg.png){kind=logo}
Referencias
- ^ "Notas de la versión de FFTW" . Consultado el 16 de septiembre de 2021 .
- ^ abc Frigo M, Johnson SG (febrero de 2005). "El diseño y la implementación de FFTW3" (PDF) . Actas del IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . doi :10.1109/JPROC.2004.840301. S2CID 6644892.
- ^ Frigo M, Johnson SG (1998). "FFTW: Una arquitectura de software adaptativa para la FFT". Actas de la Conferencia Internacional IEEE de 1998 sobre Acústica, Habla y Procesamiento de Señales, ICASSP '98 (Cat. No.98CH36181) . Vol. 3. págs. 1381–1384. CiteSeerX 10.1.1.47.8661 . doi :10.1109/ICASSP.1998.681704. ISBN . 978-0-7803-4428-0.S2CID12560207 .
- ^ Johnson SG, Frigo M (septiembre de 2008). "capítulo 11: Implementación de FFT en la práctica". En CS Burrus (ed.). Transformadas rápidas de Fourier . Houston, TX: Connexions: Rice University.
- ^ "FFTW - La transformada de Fourier más rápida de Occidente | Oficina de licencias de tecnología del MIT". tlo.mit.edu . Consultado el 7 de febrero de 2023 .
- ^ "Transformadas de Fourier finitas más rápidas MATLAB" www.mathworks.com . Consultado el 24 de marzo de 2014 .
- ^ "Preguntas frecuentes sobre FFTW"
Enlaces externos
- Sitio web oficial
