 | Эта статья может чрезмерно полагаться на источники, слишком тесно связанные с предметом , что потенциально может помешать проверке и нейтральности статьи . ( Апрель 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
 Логотип FFTW | |
| Разработчики) | Маттео Фриго и Стивен Джонсон |
|---|---|
| Первый выпуск | 24 марта 1997 г. |
| Стабильный выпуск | 3.3.9 / 13 декабря 2020 г . |
| Репозиторий |  |
| Написано в | C , OCaml |
| Тип | Числовое программное обеспечение |
| Лицензия | GPL , коммерческая |
| Веб-сайт | www |
Самое быстрое преобразование Фурье на Западе ( FFTW ) - это программная библиотека для вычисления дискретных преобразований Фурье (ДПФ), разработанная Маттео Фриго и Стивеном Джонсоном из Массачусетского технологического института . [1] [2] [3]
FFTW известен как самая быстрая бесплатная программная реализация быстрого преобразования Фурье (FFT) (подтвержденная регулярными тестами [4] ). Как и многие другие реализации, он может вычислять преобразования реальных и комплексных массивов произвольного размера и размерности за время O ( n log n ).
Библиотека [ править ]
FFTW быстро преобразует данные, поддерживая множество алгоритмов и выбирая тот (конкретное разложение преобразования на более мелкие преобразования), который он оценивает или измеряет, как предпочтительный в конкретных обстоятельствах. Он лучше всего работает с массивами размеров с небольшими простыми множителями , причем степени двойки являются оптимальными, а большие простые числа - наихудшим случаем (но все же O ( n log n )). Чтобы разложить преобразования составных размеров на более мелкие преобразования, он выбирает один из нескольких вариантов алгоритма БПФ Кули-Тьюки(соответствует разным факторизациям и / или различным шаблонам доступа к памяти), а для простых размеров он использует алгоритм БПФ Рейдера или Блустейна . [1] После того, как преобразование было разбито на частичные преобразования достаточно малых размеров, FFTW использует жестко закодированные развернутые БПФ для этих небольших размеров, которые были созданы (во время компиляции , а не во время выполнения ) генерацией кода ; эти процедуры используют множество алгоритмов, включая варианты Кули – Тьюки, алгоритм Рейдера и алгоритмы БПФ с простым множителем . [1]
Для достаточно большого количества повторяющихся преобразований полезно измерить производительность некоторых или всех поддерживаемых алгоритмов на заданном размере массива и платформе . Эти измерения, которые авторы называют «мудростью», могут быть сохранены в файле или строке для дальнейшего использования.
У FFTW есть «интерфейс гуру», который намеревается «максимально раскрыть гибкость базовой архитектуры FFTW». Это позволяет, среди прочего, выполнять многомерные преобразования и множественные преобразования в одном вызове (например, когда данные чередуются в памяти).
FFTW имеет ограниченную поддержку неупорядоченных преобразований (с использованием версии интерфейса передачи сообщений (MPI)). Данные изменения порядка несет накладные расходы, которые для в месте преобразований произвольного размера и размерности является нетривиальным , чтобы избежать. Недокументировано, для каких преобразований значительны эти накладные расходы.
FFTW находится под лицензией GNU General Public License . Он также имеет коммерческую лицензию (по цене до 12 500 долларов США) MIT [5] и используется в коммерческом пакете матриц MATLAB [6] для вычисления БПФ. FFTW написан на языке C , но существуют интерфейсы Fortran и Ada , а также интерфейсы для нескольких других языков. Хотя сама библиотека genfftнаписана на языке C, код на самом деле создается из программы с именем ' ', написанной на OCaml . [7]
В 1999 г. FFTW выиграла премию Дж. Х. Уилкинсона в области программного обеспечения для числовых вычислений .
См. Также [ править ]
- FFTPACK
Ссылки [ править ]
- ^ a b c Фриго М., Джонсон С.Г. (февраль 2005 г.). «Дизайн и реализация FFTW3» (PDF) . Труды IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . DOI : 10.1109 / JPROC.2004.840301 .
- ^ Frigo M, Johnson SG (1998). FFTW: адаптивная программная архитектура для БПФ . Труды Международной конференции IEEE 1998 г. по акустике, речи и обработке сигналов . 3 . С. 1381–1384. CiteSeerX 10.1.1.47.8661 . DOI : 10.1109 / ICASSP.1998.681704 . ISBN 978-0-7803-4428-0.
- ^ Johnson SG, Frigo M (сентябрь 2008). «Глава 11: Реализация БПФ на практике» . В CS Burrus (ред.). Быстрые преобразования Фурье . Хьюстон, Техас: Связи: Университет Райса.
- ^ Домашняя страница, второй абзац [1] и страница тестов [2]
- ^ "View Technologies | MIT Technology Licensing Office" .
- ^ Более быстрые конечные преобразования Фурье: MATLAB 6 включает FFTW
- ^ "Часто задаваемые вопросы о FFTW"
Внешние ссылки [ править ]
- Официальный веб-сайт
