Алгоритм Гуда — Томаса

Для произвольного натурального числа ${\displaystyle n}$ дискретным преобразованием Фурье комплексного вектора ${\displaystyle x(j)}$, где ${\displaystyle j=0,\ldots ,n-1}$, называется комплексный вектор ${\displaystyle X(k)}$, где ${\displaystyle k=0,\ldots ,n-1}$, компоненты которого задаются формулой:

${\displaystyle X(k)=\sum \limits _{j=0}^{n-1}x(j)\omega ^{kj},\;k=0,\ldots ,n-1,}$

где ${\displaystyle \omega =e^{-{\frac {2\pi i}{n}}}}$.

Пусть ${\displaystyle n=n_{1}n_{2}}$, где ${\displaystyle n_{1}}$ и ${\displaystyle n_{2}}$ взаимно просты. Пусть также ${\displaystyle j_{1}}$ и ${\displaystyle j_{2}}$ — новые входные индексы, задающиеся соотношениями^[5]:

${\displaystyle j_{1}=j\ ({\mbox{mod}}\ n_{1}),\ j_{2}=j\ ({\mbox{mod}}\ n_{2}).}$

Отсюда по китайской теореме об остатках и соотношению Безу следует, что существуют такие целые числа ${\displaystyle N_{1}}$ и ${\displaystyle N_{2}}$, что

${\displaystyle j=j_{1}N_{2}n_{2}+j_{2}N_{1}n_{1}\ ({\mbox{mod}}\ n)}$

и ${\displaystyle N_{1}n_{1}+N_{2}n_{2}=1.}$ Аналогично, пусть ${\displaystyle k_{1}}$ и ${\displaystyle k_{2}}$ — новые выходные индексы, задающиеся соотношениями

${\displaystyle k_{1}=N_{2}k\ ({\mbox{mod}}\ n_{1}),\ k_{2}=N_{1}k\ ({\mbox{mod}}\ n_{2}).}$

Тогда

${\displaystyle k=n_{2}k_{1}+n_{1}k_{2}\ ({\mbox{mod}}\ n).}$

С использованием обозначений

${\displaystyle x'(j_{1},j_{2})=x(j_{1}N_{2}n_{2}+j_{2}N_{1}n_{1}),}$

${\displaystyle X'(k_{1},k_{2})=X(n_{2}k_{1}+n_{1}k_{2}),}$

${\displaystyle \beta =\omega ^{N_{2}\left(n_{2}\right)^{2}},}$

${\displaystyle \gamma =\omega ^{N_{1}\left(n_{1}\right)^{2}},}$

исходная формула принимает вид

${\displaystyle X'(k_{1},k_{2})=\sum \limits _{j_{1}=0}^{n_{1}-1}\sum \limits _{j_{2}=0}^{n_{2}-1}\beta ^{j_{1}k_{1}}\gamma ^{j_{2}k_{2}}x'(j_{1},j_{2}),}$

то есть произошёл переход от одномерного преобразования длины ${\displaystyle n}$ к двумерному преобразованию размера ${\displaystyle (n_{1}\times n_{2})}$. При этом число умножений и число сложений стало равно примерно ${\displaystyle n(n_{1}+n_{2})}$^[6].

• Разделение на потоки. Каждый вычислительный блок обрабатывает свою строку/столбец матрицы. Игровые и профессиональные GPU (такие как архитектуры NVIDIA Ampere, Hopper или Ada Lovelace) используют модель памяти с высокой пропускной способностью^[7].
• Использование cuFFT и VkFFT.Хотя для длин, являющихся степенью двойки, применяются традиционные алгоритмы (Кули — Тьюки), современные программные библиотеки включают алгоритмы разложения на взаимно простые множители. К примеру, фреймворк VkFFT отслеживает и оптимизирует доступ к памяти без банковских конфликтов, поддерживая эффективные длины последовательностей^[8].
• Векторизация в малых полях. Для специфических научных вычислений используются реализации, где базовые длины вроде 3, 5, 7 или 13 трансформируются с помощью разделения по блокам (thread block level) и вычисляются непосредственно в быстрой разделяемой памяти^[9].