Войти
 Логотип FFTW | |
| Разработчик (и) | Маттео Фриго и Стивен Джонсон |
|---|---|
| Первоначальный выпуск | 24 марта 1997 г. (1997-03-24) |
| Стабильный выпуск | 3.3.8 / 28 мая 2018 г.; 2 года назад (28.05.2018) |
| Репозиторий |  |
| Написано на | C, OCaml |
| Тип | Числовой программное обеспечение |
| Лицензия | GPL, коммерческое |
| Веб-сайт | www.fftw.org |
Самое быстрое преобразование Фурье на Западе (FFTW ) - это программное обеспечение библиотека для вычисления дискретных преобразований Фурье (ДПФ), разработанная Маттео Фриго и Стивеном Дж. Джонсоном в Массачусетский технологический институт.
FFTW известен как самая быстрая бесплатная программа, реализующая быстрое преобразование Фурье (БПФ) (подтверждается стандартными тестами ). Как и многие другие реализации, он может вычислять преобразования реальных и сложных -значных массивов произвольного размера и размерности за O (n log n ) времени.
Это достигается за счет поддержки множества алгоритмов и выбора одного ( конкретное разложение преобразования на более мелкие преобразования) он оценивает или измеряет его как предпочтительный в конкретных обстоятельствах. Он лучше всего работает с массивами размеров с маленькими простыми множителями, причем степени двойки являются оптимальными, а большие простые числа - наихудшим случаем (но все же O (n log п )). Чтобы разложить преобразования составных размеров на более мелкие преобразования, он выбирает один из нескольких вариантов алгоритма БПФ Кули-Тьюки (соответствующий разным факторизациям и / или различным шаблонам доступа к памяти), в то время как для простых размеров используется алгоритм БПФ Рейдера или Блустейна. После того, как преобразование было разбито на частные преобразования достаточно малого размера, FFTW использует жестко закодированные развернутые БПФ для этих небольших размеров, которые были созданы (во время компиляции, а не в время выполнения ) с помощью генерации кода ; в этих подпрограммах используются различные алгоритмы, включая варианты Кули-Тьюки, алгоритм Рейдера и алгоритмы БПФ с простым коэффициентом.
Для достаточно большого количества повторяющихся преобразований полезно измерить производительность некоторых или всех поддерживаемых алгоритмы на заданном размере массива и платформе. Эти измерения, которые авторы называют «мудростью», могут быть сохранены в файле или строке для дальнейшего использования.
FFTW имеет «интерфейс гуру», который предназначен «раскрыть как можно больше гибкости в базовой архитектуре FFTW». Это позволяет, среди прочего, выполнять многомерные преобразования и несколько преобразований за один вызов (например, когда данные чередуются в памяти).
FFTW имеет ограниченную поддержку неупорядоченных преобразований (с использованием версии интерфейса передачи сообщений (MPI)). Переупорядочение данных влечет за собой накладные расходы, которых нетривиально избежать для преобразований на месте произвольного размера и размера. Недокументировано, для каких преобразований значительны эти накладные расходы.
FFTW находится под лицензией Стандартной общественной лицензии GNU. Он также имеет коммерческую лицензию (стоимостью до 12 500 долларов США) от MIT и используется в коммерческом матричном пакете MATLAB для расчета БПФ. FFTW написан на языке C, но существуют интерфейсы Fortran и Ada, а также интерфейсы для нескольких других языков. Хотя сама библиотека написана на языке C, код на самом деле создается из программы под названием 'genfft', которая написана на OCaml.
В 1999 году FFTW выиграла J. Премия Х. Уилкинсона за численное программное обеспечение.
Портал бесплатного программного обеспечения с открытым исходным кодом 