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

Цели урока

• Понять алгоритм Кули-Тьюки: как рекурсивное разбиение ДПФ на чётные/нечётные снижает сложность с O(N^2) до O(N log N)
• Научиться применять FFT-свёртку для умножения многочленов и решения ДУ с постоянными коэффициентами
• Разобраться в NTT, FFTW и спектральном дифференцировании как ключевых приложениях FFT

Предварительные знания

• Многосеточные методы

• Многосеточные методы

Shazam и Spotify: аудио-фингерпринтинг за миллисекунды через FFT-спектрограммы

• Shazam и Spotify: аудио-фингерпринтинг за миллисекунды через FFT-спектрограммы
• RSA и постквантовая криптография Kyber: умножение больших чисел и полиномов через NTT
• NOAA глобальные атмосферные модели: псевдоспектральные методы через FFT
• PyTorch torch.nn.Conv2d: крупные свёртки вычисляются через cuFFT на GPU

История алгоритма

Кули и Тьюки в 1965 году переоткрыли алгоритм - оказалось, Гаусс знал о нём ещё в 1805 году, но не публиковал. Их статья в Mathematics of Computation изменила обработку сигналов навсегда. Гарвард Рейдер в 1968 году обобщил алгоритм на произвольные N. Сегодня FFTW (Frigo, Johnson, MIT, 1997) - стандарт де-факто, используется в NumPy, MATLAB, GNU Radio.

Алгоритм Кули-Тьюки: divide and conquer Фурье

1965 год. Кули и Тьюки опубликовали алгоритм, который IEEE назвал одним из 10 важнейших алгоритмов XX века. Сложность ДПФ упала с O(N^2) до O(N log N). Для N = 1 000 000: 10^12 операций против 20 · 10^6. Разрыв в 50 000 раз.

Spotify использует FFT для аудио-фингерпринтинга: 30-секундный фрагмент при 44 100 Гц обрабатывается за 2 миллисекунды вместо 4 секунд. Каждый Shazam-матч - FFT в реальном времени. Каждая обратная свёртка в PyTorch - FFT под капотом.

Для произвольных N используют смешанные основания (mixed-radix FFT) или алгоритм Блюштейна (Bluestein chirp-z). numpy.fft.fft принимает любой N, внутри автоматически выбирает оптимальный алгоритм через pocketfft.

FFT в решении ДУ и умножении многочленов

FFT - не только про звук. Умножение двух многочленов степени N занимает O(N^2) наивно и O(N log N) через FFT. Именно это делают библиотеки BigInteger в Java и Python. RSA с 4096-битными ключами опирается на умножение гигантских чисел - FFT-свёртка.

Псевдоспектральный метод для ДУ: производная функции = умножение спектра на ik. Уравнение Пуассона в Фурье-пространстве: умножение на -k^2 и деление. Одно FFT туда, одна операция, одно FFT обратно. Для периодических задач это точнее МКЭ при том же числе узлов.

Эффект Гиббса: FFT-методы дают осцилляции вблизи разрывов функции (окно Хэннинга, фильтрация по Зигмунду). Для негладких задач конечные разности или МКЭ с адаптивными сетками могут быть предпочтительнее спектральных методов.

Обобщения FFT: NTT, FFTW, распределённый FFT

FFTW (Fastest Fourier Transform in the West) - библиотека MIT, используемая в MATLAB, NumPy, scipy. Автоматически выбирает оптимальный алгоритм для конкретного N и архитектуры (SIMD, кэш, многоядерность). На практике 2-5x быстрее простой реализации.

Распределённый FFT: в суперкомпьютерных расчётах (GROMACS, FFTMPI) FFT вычисляется на распределённой памяти. Ключевая операция - транспонирование матрицы через MPI_Alltoall. Для трёхмерных FFT это часто узкое место: communication bound, а не compute bound.

В PyTorch и TensorFlow свёртка реализована через FFT при достаточно большом размере ядра. torch.fft.fft2 использует cuFFT на GPU. FlashAttention-2 использует специальные тайлинг-стратегии для attention-свёртки, аналогичные оптимизациям FFTW.

Спектральное дифференцирование и фильтрация

Производная функции в Фурье-пространстве - умножение спектра на ik. Вторая производная - умножение на -k^2. Это делает ДУ с постоянными коэффициентами легко решаемыми в спектральном пространстве. NOAA использует этот факт в глобальных атмосферных моделях.

Связь с другими темами

FFT - основа спектральных методов (nm-23), используется в многосеточных методах для спектральных сглаживателей (nm-21). Псевдоспектральные ДУ-решатели применяют FFT для дифференцирования. В ML: свёртки в CNN, вычисление attention через FFT в длинных последовательностях.

• Spectral PDE Solvers — Связанная тема
• Convolution in Signal Processing — Связанная тема
• Number Theoretic Transform — Связанная тема

Итоги

• FFT снижает сложность ДПФ с O(N^2) до O(N log N) через рекурсивное разбиение на чётные/нечётные: butterfly-операция объединяет два ДПФ размера N/2 за N операций
• FFT-свёртка: коэффициенты -> значения (FFT) -> поточечное умножение -> коэффициенты (IFFT); умножение многочленов за O(N log N)
• Спектральная производная = умножение Фурье-коэффициентов на ik; машинная точность для гладких периодических функций
• NTT - FFT в конечных полях Z_p для точной целочисленной арифметики; FFTW выбирает оптимальный алгоритм автоматически

Вопросы для размышления

• Алгоритм Гаусса 1805 года - предвестник FFT. Почему он не был применён на практике до 1965 года? Что изменилось?
• Спектральное дифференцирование даёт машинную точность для гладких функций, но осциллирует у разрывов (эффект Гиббса). Как это влияет на выбор метода для задач с ударными волнами?
• PyTorch использует FFT для больших свёрток. При каком размере ядра свёртки FFT-подход быстрее прямой реализации, и почему?

Связанные уроки

• nm-21 — многосеточный метод использует FFT в спектральных вариантах
• nm-23 — спектральные методы строятся на основе FFT
• nm-25-autodiff — FFT-свёртки используют автодифференцирование в PyTorch
• la-01-vectors-intro