Алгоритм БПФ Бейли

Алгоритм Бейли (4-шаговая версия) для 16-точечного БПФ

БПФ Бейли (также известное как 4-шаговое БПФ ) — это высокопроизводительный алгоритм вычисления быстрого преобразования Фурье (БПФ). Этот вариант алгоритма БПФ Кули-Тьюки изначально был разработан для систем с иерархической памятью, распространенной в современных компьютерах (и был первым алгоритмом БПФ в этом так называемом классе «вне ядра»). Алгоритм рассматривает выборки как двумерную матрицу (отсюда еще одно название — матричный алгоритм БПФ). ) и выполняет короткие операции БПФ над столбцами и строками матрицы с корректирующим умножением на « коэффициенты поворота » между ними.

Алгоритм получил свое название в честь статьи Дэвида Х. Бэйли « БПФ во внешней или иерархической памяти» , опубликованной в 1989 году. В этой статье Бэйли отдает должное алгоритму У.М. Джентльмену и Дж. Санде, которые опубликовали свою статью « Быстрые преобразования Фурье: для развлечения». и прибыль , примерно двадцатью годами ранее, в 1966 году. Алгоритм можно считать поразрядным. ${\sqrt {n}}$ БПФ-разложение.

Вот краткий обзор того, как работает «4-шаговая» версия алгоритма Бейли БПФ:

1. Данные (в естественном порядке) сначала упорядочиваются в матрицу.
2. Затем каждый столбец матрицы обрабатывается независимо с использованием стандартного алгоритма БПФ.
3. Каждый элемент матрицы умножается на поправочный коэффициент.
4. Затем каждая строка матрицы обрабатывается независимо с использованием стандартного алгоритма БПФ.

Результат (в естественном порядке) читается столбец за столбцом. Поскольку операции выполняются по столбцам и по строкам, шаги 2 и 4 (и чтение результата) могут включать в себя транспонирование матрицы для переупорядочения элементов удобным для обработки способом. Алгоритм напоминает 2-мерное БПФ , трехмерные (и не только) расширения известны как 5-шаговое БПФ , 6-шаговое БПФ и т. д.

БПФ Бейли обычно используется для вычисления ДПФ больших наборов данных, например, используемых в научных и инженерных приложениях. БПФ Бейли — очень эффективный алгоритм, который использовался для вычисления БПФ наборов данных с миллиардами элементов (применительно к теоретико-числовому преобразованию наборы данных порядка 10 ¹² элементы обработаны в середине 2000-х годов ).

См. также

• Алгоритм БПФ строк-столбцов
• Алгоритм векторного БПФ

Источники

• Бейли, Д.Х. (март 1989 г.). «FFTS во внешней иерархической памяти» (PDF) . Материалы конференции ACM/IEEE 1989 года по суперкомпьютерам — Supercomputing '89 . Том. 4. АСМ Пресс. стр. 23–35. дои : 10.1145/76263.76288 . ISBN  0897913418 . S2CID   52809390 .
• Фриго, М.; Джонсон, С.Г. (февраль 2005 г.). «Проектирование и реализация FFTW3». Труды IEEE . 93 (2): 216–231. Бибкод : 2005IEEP..93..216F . CiteSeerX   10.1.1.66.3097 . дои : 10.1109/JPROC.2004.840301 . ISSN   0018-9219 . S2CID   6644892 .
• Харт, Уильям Б.; Торнария, Гонсало; Уоткинс, Марк (2010). «Соответствующие числа Тета-коэффициенты 10» ¹² doi (PDF) . Алгоритмическая теория чисел . Конспекты лекций по информатике. Том 6197. Springer Berlin Heidelberg. стр. 186–200. : 10.1007 /978-3-642-14518-6_17 . eISSN   1611-3349 . ISBN  978-3-642-14517-9 . ISSN   0302-9743 .
• Аль Намне, Рами; Пан, В. Дэвид (март 2007 г.). «Пятишаговый алгоритм БПФ с пониженной вычислительной сложностью». Письма об обработке информации . 101 (6): 262–267. дои : 10.1016/j.ipl.2006.10.009 . ISSN   0020-0190 .
• Арндт, Йорг (1 октября 2010 г.). «Матричный алгоритм Фурье (MFA)» . Вопросы вычислений: идеи, алгоритмы, исходный код . Springer Science & Business Media. стр. 438–439. ISBN  978-3-642-14764-7 . OCLC   1005788763 .