Кратко и по делу.
Что вычисляет DFT:
$$X_k=\sum _{j=0}^{n-1}{x}_j{e}^{-2\pi ijk/n},k=0,\dots ,n-1.$$
Идея разбиения (Cooley–Tukey, radix-2):
- Разделим вход на чётные и нечётные индексы:
$$x_j^{(e)}=x_{2j},x_j^{(o)}=x_{2j+1},j=0,\dots ,n/2-1.$$ - DFT длины $n$ выражается через две DFT длины $n/2$:
$$X_k=E_k+{\omega }_n^k{O}_k,X_{k+n/2}=E_k-{\omega }_n^k{O}_k,$$ где
$$E_k=\sum _{j=0}^{n/2-1}{x}_j^{(e)}{\omega }_{n/2}^{jk},O_k=\sum _{j=0}^{n/2-1}{x}_j^{(o)}{\omega }_{n/2}^{jk},{\omega }_n=e^{-2\pi i/n}.$$ - То есть рекурсивно вычисляем две DFT на половинах и комбинируем («twiddle factors» ${\omega }_n^k$).
Рекурсия и сложность:
- Рекуррентное соотношение:
$$T(n)=2T(n/2)+O(n).$$ - По мастер-теореме получаем
$$T(n)=O(n\log n).$$
Итеративная реализация и бит-реверс:
- Часто делают in-place итеративный алгоритм с перестановкой индексов по обратному порядку битов (bit-reversal) и поуровневым «баттлом» пар длиной $2^s$. Это снижает накладные расходы рекурсии и улучшает кеш-поведение.
Практические варианты и оптимизации:
- Radix-2, mixed-radix (используется если $n$ факторизуется по другим базам), split-radix (немного меньше операций), Bluestein/Chirp-Z (для произвольных $n$), Rader (для простых $n$).
- Реальные входы: real-FFT экономит примерно вдвое памяти/вычислений, объединяя симметрию.
- Предвычисление/кеширование twiddle-факторов $e^{-2\pi ik/n}$ и использование рекуррентной формулы для синусов/косинусов снижает расходы.
- Векторизация и SIMD (AVX/NEON), многопоточность, планировщики (FFTW) для оптимизации под конкретный CPU.
- GPU-решения (cuFFT) дают большой выигрыш на больших массивах.
- Для целочисленных свёрток: NTT (численное преобразование по модулю) + CRT для точного умножения больших целых.
- Для слишком больших данных: внешняя память / out-of-core FFT, блочные методы и overlap-save/overlap-add для поточных свёрток.
- Для точности: масштабирование, выбор двойной/длинной точности, использование алгоритмов с меньшей накопительной ошибкой.
Применения:
- Быстрое умножение многочленов/больших целых (через свёртку).
- Цифровая обработка сигналов: спектральный анализ, фильтрация, ускорение свёрток.
- Решение дифференциальных уравнений (спектральные методы).
- Сжатие и обработка изображений (JPEG, фильтры), радиолокация, связь, акустика, машинное обучение (свертки, спектральные признаки).
- Корреляция и поиск шаблонов (cross-correlation, matched filtering).
Практические советы при больших входах:
- Выбирать $n$ с хорошей факторизацией (производные смешанные радиксы) или применять Bluestein для произвольных $n$.
- Использовать оптимизированные библиотеки (FFTW, Intel MKL, FFTW_planner, cuFFT) вместо собственной реализации.
- Минимизировать пропуски кеша: in-place, блокирование, порядок доступа.
- Параллелить уровни и/или блоки; на GPU использовать специализированные ядра.
- Комбинировать с NTT при необходимости точного целочисленного результата; использовать несколько модулей и CRT для очень больших коэффициентов.
- Профилировать: часто узким местом являются память и трансфер, а не число операций.
Если нужно, могу показать короткий рекурсивный псевдокод или пример применения (умножение многочленов).