Введение

Библиотека программного обеспечения для вычисления дискретных преобразований Фурье.

Самое быстрое преобразование Фурье на Западе (FFTW) — это библиотека программного обеспечения для вычисления дискретных преобразований Фурье (ДПФ), разработанная Маттео Фриго и Стивеном Г. Джонсоном в Массачусетском технологическом институте. FFTW является одной из самых быстрых бесплатных программных реализаций быстрого преобразования Фурье (БПФ). Она реализует алгоритм БПФ для массивов вещественных и комплексных чисел произвольного размера и размерности.

Библиотека

FFTW быстро преобразует данные, поддерживая различные алгоритмы и выбирая тот (особое разложение преобразования на более мелкие преобразования), который, по его оценкам или измерениям, является предпочтительным в данных обстоятельствах. Он наиболее эффективно работает с массивами размеров, имеющими небольшие простые множители, при этом степени двойки являются оптимальными, а большие простые числа – наихудшим случаем (но всё равно со сложностью O(n log n)). Для разложения преобразований составных размеров на более мелкие преобразования он выбирает из нескольких вариантов алгоритма FFT Cooley-Tukey (соответствующих различным факторизациям и/или различным схемам доступа к памяти), а для простых размеров использует алгоритм FFT Rader'а или Bluestein'а. FFTW используется в коммерческом пакете матриц MATLAB для вычисления БПФ. FFTW написана на языке C, но существуют интерфейсы для Fortran и Ada, а также для нескольких других языков. Хотя сама библиотека реализована на C, код фактически генерируется из программы под названием "genfft", написанной на OCaml. В 1999 году FFTW была удостоена премии имени Дж. Х. Уилкинсона за численное программное обеспечение.