Быстрое преобразование Фурье

Дискретное преобразование Фурье трансформирует последовательность комплексных (либо вещественных) чисел x_n в последовательность комплексных чисел X_n. Прямое и обратное преобразования Фурье определяются, как:

Приведенные выше формулы имеют сложность O(N²), однако широко известен способ снизить сложность дискретного преобразования Фурье до O(N·log(N)). Быстрое преобразование Фурье широко используется как само по себе, так и для ускорения вычисления других преобразований - быстрого вычисления свертки и кросс-корреляции.

Реализация быстрого преобразования Фурье в ALGLIB

Пакет ALGLIB поддерживает быстрые преобразования Фурье комплексных последовательностей любой длины. В случае, если длина преобразования N является составным числом, используется алгоритм Cooley-Tukey, сводящий исходное преобразование Фурье к более коротким преобразованиям, соответствующим простым множителям N. Преобразования короткой длины (N ≤ 5) вычисляются с использованием специальных формул для коротких преобразований; более длинные преобразования, соответствующие простому N или крупным простым множителям составного N, вычисляются с использование алгоритма Блюштейна (Bluestein). В результате алгоритм имеет быстродействие O(N·log(N)) для любого N - простого или составного. Вместе с тем, некоторые преобразования вычисляются быстрее других. Если длина преобразования - простое число или составное число с крупными простыми множителями, то такое преобразование может потребовать в 4-6 раз больше времени, чем если бы длина была близким составным числом с малыми простыми множителями.

Вещественное быстрое преобразование Фурье в ALGLIB

Большинство алгоритмов БПФ разрабатывалось для комплексных последовательностей, т.к. комплексный случай поддается более легкому анализу, чем вещественный. Однако на практике очень часто приходится работать с вещественными числами, и отдельным вопросом является быстродействие БПФ вещественных последовательностей. Для четного N существует формула, позволяющая свести вещественное БПФ к комплексному БПФ в два раза меньшей длины - и тем самым примерно в два раза повысить быстродействие в сравнении с использованием комплексного БПФ той же длины. Однако для нечетного N отсутствует простой способ повысить быстродействие преобразования, и в пакете ALGLIB эта проблема пока не решена.

Таким образом, если длина преобразования - четное число, то вещественное преобразование будет примерно в два раза быстрее комплексного. Если же длина преобразования - нечетное число, то скорость вещественного преобразования не будет отличаться от скорости комплексного преобразования той же длины.