La Transformada de Fourier más rápida en 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 de Tecnología de Massachusetts . [1] [2] [3]
![]() El logo de FFTW | |
Desarrollador (es) | Matteo Frigo y Steven G. Johnson |
---|---|
Versión inicial | 24 de marzo de 1997 |
Lanzamiento estable | 3.3.9 / 13 de diciembre de 2020 |
Repositorio | ![]() |
Escrito en | C , OCaml |
Tipo | Software numérico |
Licencia | GPL , comercial |
Sitio web | www ![]() |
FFTW se conoce como la implementación de software libre más rápida de la transformada rápida de Fourier (FFT) (respaldada por evaluaciones comparativas regulares [4] ). Como muchas otras implementaciones, puede calcular transformaciones de matrices de valores reales y complejos de tamaño y dimensión arbitrarios en tiempo O ( n log n ).
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 estima o mide como preferible en las circunstancias particulares. Funciona mejor en matrices de tamaños con factores primos pequeños , con potencias de dos siendo óptimas y números primos grandes en el peor de los casos (pero aún así O ( n log n )). Para descomponer transformaciones de tamaños compuestos en transformaciones más pequeñas, elige entre varias variantes del algoritmo Cooley-Tukey FFT (correspondientes a diferentes factorizaciones y / o diferentes patrones de acceso a memoria), mientras que para tamaños primos utiliza el algoritmo FFT de Rader o Bluestein . [1] Una vez que la transformada ha sido dividido en subtransforms de suficientemente pequeños tamaños, FFTW utiliza codificadas de forma rígida desenrollados FFT para estos pequeños tamaños que fueron producidos (en tiempo de compilación , no en tiempo de ejecución ) por generación de código ; estas rutinas utilizan una variedad de algoritmos que incluyen variantes de Cooley-Tukey, algoritmo de Rader y algoritmos FFT de factor primo . [1]
Para un número suficientemente grande de transformaciones repetidas, es ventajoso medir el rendimiento de algunos o todos los algoritmos admitidos en la plataforma y el tamaño de matriz dados . Estas medidas, a las que los autores se refieren como "sabiduría", se pueden almacenar en un archivo o cadena para su uso posterior.
FFTW tiene una "interfaz de gurú" que pretende "exponer tanto como sea posible la flexibilidad 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 soporte limitado para transformaciones fuera de orden (usando la versión de Interfaz de paso de mensajes (MPI)). El reordenamiento de los datos genera una sobrecarga, que no es trivial evitar en el caso de transformaciones in situ de tamaño y dimensión arbitrarios. Es indocumentado por lo que transforma esta sobrecarga es significativa.
FFTW tiene la licencia GNU General Public License . También tiene licencia comercial (por un costo de hasta $ 12,500) por MIT [5] y se usa en el paquete de matriz comercial 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 .
Ver también
- FFTPACK
Referencias
- ↑ a b c Frigo M, Johnson SG (febrero de 2005). "El diseño e implementación de FFTW3" (PDF) . Actas del IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . doi : 10.1109 / JPROC.2004.840301 .
- ^ Frigo M, Johnson SG (1998). FFTW: una arquitectura de software adaptativa para FFT . Actas de la Conferencia Internacional IEEE de 1998 sobre acústica, habla y procesamiento de señales . 3 . págs. 1381-1384. CiteSeerX 10.1.1.47.8661 . doi : 10.1109 / ICASSP.1998.681704 . ISBN 978-0-7803-4428-0.
- ^ Johnson SG, Frigo M (septiembre de 2008). "cap.11: Implementación de FFT en la práctica" . En CS Burrus (ed.). Transformadas rápidas de Fourier . Houston TX: Conexiones: Universidad Rice.
- ^ Página de inicio, segundo párrafo [1] y página de comparativas [2]
- ^ "Ver tecnologías | Oficina de licencias de tecnología del MIT" .
- ^ Transformaciones finitas de Fourier más rápidas: MATLAB 6 incorpora FFTW
- ^ "Preguntas frecuentes sobre FFTW"
enlaces externos
- Página web oficial