История создания алгоритма Быстрого Преобразования Фурье

Сразу после публикации статьи Кули и Тьюки [1], в которой описывался алгоритм вычисления быстрого преобразования Фурье (БПФ, FFT, Fast Fourier Transform), к авторам начали приходить письма с различными отзывами. Одни писали, что их новый революционный алгоритм распахнул невиданные горизонты для обработки сигналов и изображений, и теперь любая задача по плечу. Другие говорили [2], что алгоритм давным-давно известен и используется, так что их статья - лишь повтор того, что есть.
И те, и другие были по-своему правы.

Следует заметить, что время публикации статьи Кули и Тьюки [1] совпало с бурным развитием вычислительной техники, когда всё больше и больше задач решались на ЭВМ. В 1965 году, тем не менее, все высокоскоростные компьютеры были забиты заданиями под завязку. Более того, в те годы начали активно разрабатываться АЦП, которые позволяли вводить информацию в ЭВМ со скоростью нескольких тысяч отсчётов в секунду. Это означало, что теперь можно обрабатывать сигнал цифровым способом вместо использования аналоговых устройств. В свою очередь, потребовались эффективные алгоритмы обработки сигналов и изображений, многие из которых используют преобразование Фурье. Поэтому появление нового алгоритма, сулившего ускорить вычисление дискретного преобразования Фурье в $N/\log_2(N)$ , было очень кстати.

Создание алгоритма

По рассказам одного из авторов алгоритма, Джеймса Кули [3], всё началось в конце 1963 года. Джеймс Кули был нанят в IBM Thomas J. Watson Research Center в Yorktown Heights, что в Нью-Йорке. Кули работал над своим собственным проектом, когда к нему обратился Ричард Гарвин (Richard Garwin) и показал некоторые заметки Джона Тьюки (John Tukey) об алгоритме, который теоретически способен вычислять быстрое преобразование Фурье со скоростью, пропорциональной $N\log_2(N)$, а не $N^2$. Гарвин, в отличие от Кули, хорошо понимал всю важность этого алгоритма и его огромную практическую значимость, и поэтому настаивал на разработке этого алгоритма.

``- Позже, - вспоминает Кули [2]. - я выяснил, что Гарвин был значительно более заинтересован в улучшении дистанционного сейсмического мониторинга ядерных взрывов; русские едва ли согласились бы на проведение инспекций на их территории. Гарвин так же видел необходимость в разработке методов раннего акустического обнаружения подводных лодок. Как и многие другие, я не считал это важным, поэтому поставил задаче разработки алгоритма БПФ приоритет ниже, чем собственным исследованиям. Тем не менее, под напором авторитета Гарвина и его постоянных телефонных звонков, я написал алгоритм для вычисления трёхмерного БПФ.''

История БПФ

Перед публикацией нужно было проверить, является ли идея алгоритма новой, и Кули решил посоветоваться с Джоном Тьюки. Тьюки посоветовал просмотерть несколько статей, в одной из которых [4] описывался очень похожий метод, скорость которого была несколько меньше. Было понятно, что идея их алгоритма в целом не нова, и это заставило Кули глубже изучить историю БПФ. Его непосредственный начальник, Гарвин, обратился к своему коллеге, профессору Томасу (Professor L.H. Thomas), который был в своё время научным руководителем Кули в институте. Томас дал свою опубликованную статью [5], в которой описывалось вычисление рядов Фурье, которые он проделал в 1948 году в IBM на табуляторе с перфокартами. По словам Томаса, он просто пошёл в библиотеку и взял справочник [6]. Методы, опубликованные в этом справочнике, позволяли вычислять ряды Фурье и уменьшать объёмы вычислений используя свойство симметрии тригонометрических функций.

Вскоре после публикации [1] Кули получил письмо от Филипа Рудника из Института Океанографии в Санн-Диего, Калифорния. Рудник сказал, что сам реализовал подобный алгоритм, используя метод из [7]. Статья Рудника с улучшенным вариантом такого метода вышла [8] чуть позднее статьи Кули и Тьюки - он не решился публиковать её сразу.
Оказалось, что приёмы, лежащие в основе БПФ, были опубликовы ещё раньше. В том же справочнике Стампффа [6] нашлась ссылка на более ранние работы Рунге и Кёнига [9]. В той работе так же использовался метод ``бабочки'' (Метод ``бабочки'', butterfly, заключается в использовании сделанных вычислений для получения соседних значений сложением или вычитанием уже полученных) для ускорения вычислений и контроля ошибок.

Кули написал статью [10], в которой приводилась, как он полагал, полную историю предшествующих похожих алгоритмов вычисления БПФ вплоть до работ Рунге [9]. Однако пыль веков скрывала в себе много интересного, и вскоре Кули получил ссылку от коллеги [11] на ещё более ранюю работу по вычислению БПФ. Это была глава книги великого Карла Фридриха Гаусса [12]. В этой главе, написанной на неоклассической латыни, приводились основные соображения алгоритма БПФ. Гаусс применял разновидность интерполяции по Лагранжу, и это могло привести его к возможности сокращения количества операций при быстром преобразовании. Позже были опубликованы работы [13,11], в которых приведён краткий перевод работы Карла Гаусса, предвосхтившей БПФ, а так же упомянуты другие работы, посвящённые БПФ.

Выводы

Из всей этой истории читатель может извлечь ценные выводы:

1. Очевидно, что понимание важности и быстрая публикация значительных достижений очень и очень важны.
2. Аккуратное отношение к старой литературе может принести большую пользу. Награды за выдающиеся достижения должны предшествовать анализу старых публикаций и книг.
3. Общение между математиками, инженерами и специалистами прикладных областей является крайне плодотворным.
4. Не публикуйте статьи на нео-классической латыни.

Литература

1

Cooley J.W. and Tukey J.W. An algorithm for the machine calculation of the complex fourier series. Mathematics Computation, 19:297-301, 1965.

2

James W. Cooley. The re-discovery of the fast fourier transform algorithm. Mikrochimica Acta, III:33-45, 1987.

3

J.W. Cooley. How the FFT gained acceptance. Proceedings of the Association for Computing Machinery Conference on the History of Scientific and Numeric Computation, Princeton, NJ, pages 10-13, 1987.

4

J. Good I. J. Royal Statist. Soc.,, 20:361, 1958.

5

L. H. Thomas. Applications of Digital Computers, chapter Using a Computer to Solve Problems in Physics. Boston: Ginn and Company, 1963.

6

K. Stumpff. Grundlagen und Methoden der Periodenforschung, Tafeln und Aufgaben zur Harmonischen Analyse und Periodogrammrechnung. Springer, Berlin, 1939.

7

G. C. Danielson and C. Lanczos. Some improvements in practical fourier analysis and their application to x-ray scattering from liquids. J. Franklin Inst. 233, Pergamon Journals, Ltd., pages 365-80, 1942.

8

Philip Rudnick. Note on the calculation of fourier series. Math. Comp., Vol. 20, No.3:429-430, July 1966.

9

C. Runge and H. Konig. Vorlesungen uber Numerisches Rechnen (Die Grundlehren der Mathematischen Wissenschaften, Band XI). Springer, Berlin, 1924.

10

J.W. Cooley, P.A. Lewis, and P.D. Welch. An algorithm for the machine calculation of complex fourier series. IEEE Trans. Audio Electroacoustics, AU-15:76, 1967.

11

H.H. Goldstine. A History of Numerical Analysis from the 16th Through the 19th Century. Springer-Verlag, New York, Heidelberg, and Berlin, 1977.

12

C.F. Gauss. Nachla: Theoria interpolationis methodo nova tractata. (Carl Friedrich Gauss, Werke, Band 3), Konigliche Gesellschaft der Wissenschaften, Gottingen, pages 265-303, 1866.

13

M.T. Heideman, D.H. Johnson, and C.S. Burrus. Gauss and the history of the fast fourier transform. The ASSP Magazine, Vol. 1, No. 4:14-21, Oct. 1984.