Многомерное дискретное преобразование Фурье

Многоме́рное дискре́тное преобразова́ние Фурье́ (МДПФ), применяется к массиву комплексных чисел с целочисленным мультииндексом ${\displaystyle i=(i_{1},i_{2},\ldots ,i_{m})}$, пробегающим множество ${\displaystyle [0,n_{1})\times [0,n_{2})\times \ldots \times [0,n_{m})}$ мощности ${\displaystyle n=n_{1}n_{2}\ldots n_{m}}$, и вычисляет массив того же вида. МДПФ зависит от выбора нескольких параметров ${\displaystyle w_{1},w_{2},\ldots ,w_{m}}$, являющихся первообразными корнями из единицы степеней ${\displaystyle n_{1},n_{2},\ldots ,n_{m}}$ соответственно, и при ${\displaystyle m>1}$ задаётся формулой

${\displaystyle {\text{ДПФ}}_{n_{1},n_{2},\ldots ,n_{m},w_{1},w_{2},\ldots ,w_{m}}:}$
${\displaystyle \,}$
${\displaystyle x_{j_{1}j_{2}\ldots j_{m}}\mapsto y_{i_{1},i_{2},\ldots ,i_{m}}=\sum _{j_{1}=0}^{n_{1}-1}\sum _{j_{2}=0}^{n_{2}-1}\ldots \sum _{j_{m}=0}^{n_{m}-1}{w_{1}}^{i_{1}j_{1}}{w_{2}}^{i_{2}j_{2}}\dots {w_{m}}^{i_{m}j_{m}}x_{j_{1}j_{2}\ldots j_{m}}}$,

где ${\displaystyle i_{1}=0,1,\ldots n_{1}-1;\,i_{2}=0,1,\ldots ,n_{2}-1;...;\,i_{m}=0,1,\ldots ,n_{m}-1}$.

В большинстве публикаций в этой формуле фиксируются первообразные корни вида

${\displaystyle w_{k}=e^{-2\pi i/n_{k}}=\cos(-2\pi /n_{k})+i\sin(-2\pi /n_{k}),\quad k=1,2,\ldots ,m}$.

MДПФ может быть получено многократным применением одномерных дискретных преобразований Фурье размеров ${\displaystyle n_{1},n_{2},\ldots ,n_{m}}$. При использовании быстрого преобразования Фурье для вычисления всех необходимых одномерных дискретных преобразований Фурье вычисление МДПФ может быть проведено путём выполнения ${\displaystyle O(n\,\log _{2}n)}$ арифметических операций над комплексными числами, где ${\displaystyle n=n_{1}n_{2}\ldots n_{m}}$.

Преобразование, обратное к ${\displaystyle {\text{ДПФ}}_{n_{1},n_{2},\ldots ,n_{m},w_{1},w_{2},\ldots ,w_{m}}}$, даётся формулой

${\displaystyle {\frac {{\text{ДПФ}}_{n_{1},n_{2},\ldots ,n_{m},{\bar {w}}_{1},{\bar {w}}_{2},\ldots ,{\bar {w}}_{m}}}{n_{1}n_{2}\ldots n_{m}}}}$,

где надчёркивание означает комплексное сопряжение.

Аналогично одномерному случаю могут быть определены многомерные теоретико-числовые дискретные преобразования Фурье. Такие преобразования используются в алгоритмах быстрого умножения ${\displaystyle n}$-значных двоичных чисел, в том числе в опубликованном в 2021 г. рекордном алгоритме, выполнимом путём проведения ${\displaystyle O(n\,\log _{2}n)}$ битовых операций.

В случае ${\displaystyle n_{1}=n_{2}=\ldots =n_{m}=2}$ МДПФ порядка ${\displaystyle (2,2,2,\ldots ,2)}$ совпадает с известным преобразованием Уолша – Адамара.