ФФТВ

ФФТВ
	Логотип ФФТВ
Разработчик(и)	Маттео Фриго и Стивен Дж. Джонсон
Первоначальный выпуск	24 марта 1997 г.
Стабильная версия	3.3.10 / 15 сентября 2021 г .; 2 года назад
Репозиторий	github .с /FFTW /fftw3 ;
Написано в	C , OCaml
Тип	Числовое программное обеспечение
Лицензия	GPL , коммерческая
Веб-сайт	www .немного .org

Самое быстрое преобразование Фурье на Западе ( FFTW ) — это программная библиотека для вычисления дискретных преобразований Фурье (DFT), разработанная Маттео Фриго и Стивеном Дж. Джонсоном в Массачусетском технологическом институте . ^[2]^[3]^[4]

FFTW — одна из самых быстрых бесплатных программных реализаций быстрого преобразования Фурье (БПФ). Он реализует алгоритм БПФ для вещественных и комплексных массивов произвольного размера и размерности.

Библиотека

FFTW оперативно преобразует данные, поддерживая различные алгоритмы и выбирая тот из них (конкретное разложение преобразования на более мелкие преобразования), который он оценивает или измеряет как предпочтительный в конкретных обстоятельствах. Лучше всего он работает с массивами размеров с небольшими простыми множителями , при этом степени двойки являются оптимальными, а большие простые числа - худшим случаем (но все же O ( n log n )). Чтобы разложить преобразования составных размеров на более мелкие преобразования, он выбирает один из нескольких вариантов алгоритма БПФ Кули-Тьюки (соответствующих различным факторизациям и/или различным шаблонам доступа к памяти), а для простых размеров он использует алгоритм БПФ Рейдера или Блюстейна . ^[2] После того, как преобразование было разбито на подпреобразования достаточно малых размеров, FFTW использует жестко закодированные развернутые БПФ для этих небольших размеров, которые были созданы (во время компиляции , а не во время выполнения ) путем генерации кода ; в этих процедурах используются различные алгоритмы, включая варианты Кули-Тьюки, алгоритм Рейдера и алгоритмы БПФ с простыми коэффициентами . ^[2]

При достаточно большом количестве повторных преобразований полезно измерить производительность некоторых или всех поддерживаемых алгоритмов на заданном размере массива и платформе . Эти измерения, которые авторы называют «мудростью», можно сохранить в файле или строке для дальнейшего использования.

У FFTW есть «интерфейс гуру», цель которого «раскрыть как можно большую гибкость базовой архитектуры FFTW». Это позволяет, среди прочего, выполнять многомерные преобразования и несколько преобразований за один вызов (например, когда данные чередуются в памяти).

FFTW имеет ограниченную поддержку преобразований вне порядка (с использованием версии интерфейса передачи сообщений (MPI)). Переупорядочение данных влечет за собой накладные расходы, избежать которых при преобразовании на месте произвольного размера и размерности нетривиально. Недокументировано, для каких преобразований эти накладные расходы являются значительными.

FFTW распространяется по лицензии GNU General Public License . Он также имеет коммерческую лицензию (по цене до 12 500 долларов США) от MIT . ^[5] и используется в коммерческом MATLAB ^[6] матричный пакет для расчета БПФ. FFTW написан на языке C , но существуют интерфейсы Fortran и Ada , а также интерфейсы для нескольких других языков. Хотя сама библиотека написана на языке C, на самом деле код генерируется из программы под названием ' genfft', который написан на OCaml . ^[7]

В 1999 году FFTW выиграл премию Дж. Х. Уилкинсона в области цифрового программного обеспечения .

См. также

ФФТПАК

Ссылки

^ «Примечания к выпуску FFTW» . Проверено 16 сентября 2021 г.
^ Jump up to: ^а ^б ^с Фриго М., Джонсон С.Г. (февраль 2005 г.). «Проектирование и реализация FFTW3» (PDF) . Труды IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . дои : 10.1109/JPROC.2004.840301 . S2CID 6644892 .
^ Фриго М., Джонсон С.Г. (1998). «FFTW: Адаптивная программная архитектура для БПФ». Материалы Международной конференции IEEE по акустике, речи и обработке сигналов 1998 г., ICASSP '98 (Кат. № 98CH36181) . Том. 3. С. 1381–1384. CiteSeerX 10.1.1.47.8661 . дои : 10.1109/ICASSP.1998.681704 . ISBN 978-0-7803-4428-0 . S2CID 12560207 .
^ Джонсон С.Г., Фриго М. (сентябрь 2008 г.). «гл.11: Реализация БПФ на практике» . В CS Буррус (ред.). Быстрое преобразование Фурье . Хьюстон, Техас: Связи: Университет Райса.
^ «FFTW — самое быстрое преобразование Фурье на Западе | Офис лицензирования технологий Массачусетского технологического института» . tlo.mit.edu . Проверено 7 февраля 2023 г.
^ «Быстрое конечное преобразование Фурье MATLAB» . www.mathworks.com . Проверено 24 марта 2014 г.
^ "Часто задаваемые вопросы по FFTW"

Внешние ссылки

Официальный сайт

[wikidata-856605fcdbf31816200322d6a936e6ceac9a1c0f-v13-1] «Примечания к выпуску FFTW» . Проверено 16 сентября 2021 г.

[Frigo2005-2] Jump up to: ^а ^б ^с Фриго М., Джонсон С.Г. (февраль 2005 г.). «Проектирование и реализация FFTW3» (PDF) . Труды IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . дои : 10.1109/JPROC.2004.840301 . S2CID 6644892 .

[Frigo1998-3] Фриго М., Джонсон С.Г. (1998). «FFTW: Адаптивная программная архитектура для БПФ». Материалы Международной конференции IEEE по акустике, речи и обработке сигналов 1998 г., ICASSP '98 (Кат. № 98CH36181) . Том. 3. С. 1381–1384. CiteSeerX 10.1.1.47.8661 . дои : 10.1109/ICASSP.1998.681704 . ISBN 978-0-7803-4428-0 . S2CID 12560207 .

[Johnson08-4] Джонсон С.Г., Фриго М. (сентябрь 2008 г.). «гл.11: Реализация БПФ на практике» . В CS Буррус (ред.). Быстрое преобразование Фурье . Хьюстон, Техас: Связи: Университет Райса.

[5] «FFTW — самое быстрое преобразование Фурье на Западе | Офис лицензирования технологий Массачусетского технологического института» . tlo.mit.edu . Проверено 7 февраля 2023 г.

[6] «Быстрое конечное преобразование Фурье MATLAB» . www.mathworks.com . Проверено 24 марта 2014 г.

[FFTW_FAQ-7] "Часто задаваемые вопросы по FFTW"

[1]

[2]

[3]

[4]

[5]

[6]

[7]