Введение

Алгоритм быстрого преобразования Фурье

Алгоритм Кули–Туки, названный в честь Дж. В. Кули и Джона Туки, является наиболее распространенным алгоритмом быстрого преобразования Фурье (FFT). Он представляет дискретное преобразование Фурье (DFT) произвольного составного размера как N1 меньших DFT размеров N2, рекурсивно, чтобы сократить время вычисления до O(N log N) для сильно составных N (гладких чисел). Благодаря важности алгоритма, конкретные варианты и стили реализации получили собственные названия, как описано ниже. Поскольку алгоритм Кули–Туки разбивает DFT на более мелкие DFT, его можно произвольно комбинировать с любым другим алгоритмом для DFT. Например, алгоритм Радера или Блюштейна можно использовать для обработки больших простых множителей, которые не могут быть разложены алгоритмом Кули–Туки, или алгоритм разложения на простые множители можно использовать для повышения эффективности при выделении взаимно простых множителей. Алгоритм, вместе с его рекурсивным применением, был изобретен Карлом Фридрихом Гауссом. Кули и Туки независимо друг от друга заново открыли и популяризировали его 160 лет спустя.

История

Этот алгоритм, включая его рекурсивное применение, был изобретен около 1805 года Карлом Фридрихом Гауссом, который использовал его для интерполяции траекторий астероидов Паллада и Юноны, но его работа не получила широкого признания (опубликована лишь посмертно и на неолатинском языке). Гаусс, однако, не анализировал асимптотическую сложность вычислений. Различные ограниченные формы алгоритма также неоднократно открывались заново на протяжении XIX и начала XX веков. По сообщениям, Туки пришел к этой идее во время заседания Научного консультативного комитета при президенте Кеннеди, обсуждавшего способы обнаружения ядерных испытаний в Советском Союзе с использованием сейсмометров, расположенных за пределами страны. Эти датчики генерировали бы сейсмологические временные ряды. Однако анализ этих данных требовал бы быстрых алгоритмов для вычисления дискретного преобразования Фурье (ДПФ) из-за большого количества датчиков и длительности измерений. Эта задача была критически важна для ратификации предлагаемого договора о запрещении ядерных испытаний, чтобы любые нарушения можно было обнаружить без необходимости посещения советских объектов. Другой участник заседания, Ричард Гарвин из IBM, разглядел потенциал метода и познакомил Туки с Кули. Однако Гарвин позаботился о том, чтобы Кули не знал об истинной цели исследования. Вместо этого Кули сообщили, что алгоритм необходим для определения периодичности спиновых ориентаций в трехмерном кристалле гелия-3. Впоследствии Кули и Туки опубликовали совместную статью, и широкое распространение алгоритма последовало незамедлительно благодаря одновременной разработке аналого-цифровых преобразователей, способных выполнять дискретизацию со скоростью до 300 кГц. Тот факт, что Гаусс описал тот же алгоритм (хотя и не анализировал его асимптотическую сложность), был осознан лишь спустя несколько лет после публикации работы Кули и Туки в 1965 году.