FFTW - FFTW

FFTW
Логотип FFTW
Логотип FFTW
Разработчики)Маттео Фриго и Стивен Дж. Джонсон
изначальный выпуск24 марта 1997 г. (1997-03-24)
Стабильный выпуск
3.3.8 / 28 мая 2018; 2 года назад (2018-05-28)
Репозиторий
Отредактируйте это в Викиданных
Написано вC, OCaml
ТипЧисловое программное обеспечение
ЛицензияGPL, коммерческий
Интернет сайтwww.fftw.org Отредактируйте это в Викиданных

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

FFTW известен как самый быстрый бесплатно программное обеспечение реализация быстрое преобразование Фурье (БПФ) (поддерживается обычным ориентиры[4]). Как и многие другие реализации, он может вычислять преобразования реальных и сложный -значные массивы произвольного размера и размерности в О (п бревноп ) время.

Библиотека

Для этого он поддерживает множество алгоритмов и выбирает тот (конкретное разложение преобразования на более мелкие преобразования). оценки или меры, которые будут предпочтительнее в конкретных обстоятельствах. Лучше всего работает с массивами с небольшими главные факторы, с силы двух быть оптимальным и большим простые числа худший случай (но все же О (п войти п )). Чтобы разложить преобразования составной размеры в более мелкие преобразования, он выбирает один из нескольких вариантов Алгоритм Кули – Тьюки БПФ (соответствует разным факторизациям и / или различным шаблонам доступа к памяти), а для простых размеров он использует либо Рейдера или же Алгоритм БПФ Блюстейна.[1] После того, как преобразование было разбито на частные преобразования достаточно малого размера, FFTW использует жестко запрограммированный развернутый БПФ для этих малых размеров, которые были произведены (при время компиляции, а не на время выполнения ) к генерация кода; эти процедуры используют множество алгоритмов, включая варианты Кули – Тьюки, алгоритм Рейдера и алгоритмы БПФ с простым фактором.[1]

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

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

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

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

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

Смотрите также

Рекомендации

  1. ^ а б c Фриго М., Джонсон С.Г. (февраль 2005 г.). «Дизайн и реализация FFTW3» (PDF). Труды IEEE. 93 (2): 216–231. CiteSeerX  10.1.1.66.3097. Дои:10.1109 / JPROC.2004.840301.
  2. ^ Фриго М, Джонсон С.Г. (1998). FFTW: адаптивная программная архитектура для БПФ. Труды Международной конференции IEEE 1998 г. по акустике, речи и обработке сигналов. 3. С. 1381–1384. CiteSeerX  10.1.1.47.8661. Дои:10.1109 / ICASSP.1998.681704. ISBN  978-0-7803-4428-0.
  3. ^ Джонсон С.Г., Фриго М. (сентябрь 2008 г.). «Глава 11: Реализация БПФ на практике». В C. S. Burrus (ред.). Быстрые преобразования Фурье. Хьюстон, Техас: Связи: Университет Райса.
  4. ^ Домашняя страница, второй абзац [1], и страница тестов [2]
  5. ^ "View Technologies | MIT Technology Licensing Office".
  6. ^ Более быстрые конечные преобразования Фурье: MATLAB 6 включает FFTW
  7. ^ «FFTW FAQ»

внешняя ссылка