Дискретное преобразование Фурье

Определение:

Дискретное преобразование Фурье (англ. Discrete Fourier Transform (DFT)) — многочлена [math]A(x)[/math] называют вектор значений этого многочлена в точках [math]x = \omega_{n,k}[/math]: [math] DFT(a_0, a_1, \ldots , a_{n-1}) = (y_0, y_1, \ldots , y_{n-1}) = (A(\omega_{n,0}), A(\omega_{n,1}), \ldots , A(\omega_{n,n-1})) [/math] [math] = (A(\omega_n^0), A(\omega_n^1), \ldots , A(\omega_n^{n-1})), [/math] где [math]\omega_{n,k} = e^{i\frac{2\pi k}{n}}[/math] — [math] k-[/math]ый из [math]n[/math] комплексных корней из единицы. [math]\omega_n = \omega_{n,1} = e^{i\frac{2\pi}{n}}[/math] называется главным значением корня [math]n[/math]-ой степени из единицы, а все остальные корни являются его степенями: [math]\omega_{n,k} = (\omega_n)^k[/math].

Определение:

Обратное дискретное преобразование Фурье (англ. Inverse DFT) для вектора значений многочлена [math]A(\omega_n)[/math] [math](y_0, y_1, \ldots , y_{n-1})[/math] — это вектор коэффициентов этого многочлена [math](a_0, a_1, \ldots , a_{n-1})[/math]: [math] InvDFT(y_0, y_1, \ldots , y_{n-1}) = (a_0, a_1, \ldots , a_{n-1}). [/math]

Применение ДПФ

Дискретное преобразование Фурье используют для быстрого перемножения двух полиномов [math]A[/math] и [math]B[/math].

Для того чтобы получить произведение двух многочленов за время, меньшее чем [math]O(n^2)[/math], необходимо сначала посчитать [math]DFT[/math] обоих многочленов. Так как при умножении двух многочленов их значения просто перемножаются в каждой точке. Следовательно, если [math]DFT[/math] — это вектор значений многочлена, то мы можем получить значение произведения двух многочленов, просто перемножив их ДПФ. Значит, чтобы получить коэффициенты полученного многочлена, применим обратное ДПФ.

[math] A \times B = InvDFT(DFT(A) \times DTF(B)). [/math]

Так как ДПФ многолчена — это вектор его значений, значит, перемножение двух ДПФ требует только [math]O(n)[/math] операций. Осталось только вычислять ДПФ и обратное ДПФ за время [math]O(n)[/math]. Для этого используем быстрое преобразование Фурье.

ДПФ в модульной арифметике

В основе ДПФ используются комплексные числа, являющиеся корнями [math]n[/math]-ой степени из единицы. Для эффективного вычисления использовались свойства комплексных корней, которые образуют группу, то есть степень одного корня всегда является другим корнем. Среди них есть корень, называемый примитивным.

Однако, то же верно и в случае корней [math]n[/math]-ой степени из единицы в модульной арифметике. Не для любого модуля [math]p[/math] найдется [math]n[/math] различных корней, но такие модули все же существуют. Необходимо найти примитивный корень, то есть:

[math] (\omega_n)^n = 1 (mod p), [/math]

[math] (\omega_n)^k \ne (mod p), 1 \leqslant k \lt n. [/math]

Как и с комплексными корнями, остальные [math]n-1[/math] корней [math]n[/math]-ой степени из единицы по модулю [math]p[/math] можно получить как степени примитивного корня [math]\omega_n[/math]

См. также

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

Источники

• Википедия — Дискретное преобразование Фурье
• MAXimal::algo::Быстрое преобразование Фурье за O (N log N)