научное
9 коммент.
Сразу после публикации статьи Кули и Тьюки [1], в которой описывался алгоритм вычисления быстрого преобразования Фурье (БПФ, FFT, Fast Fourier Transform), к авторам начали приходить письма с различными отзывами. Одни писали, что их новый революционный алгоритм распахнул невиданные горизонты для обработки сигналов и изображений, и теперь любая задача по плечу. Другие говорили [2], что алгоритм давным-давно известен и используется, так что их статья - лишь повтор того, что есть.
И те, и другие были по-своему правы.
Следует заметить, что время публикации статьи Кули и Тьюки [1] совпало с бурным развитием вычислительной техники, когда всё больше и больше задач решались на ЭВМ. В 1965 году, тем не менее, все высокоскоростные компьютеры были забиты заданиями под завязку. Более того, в те годы начали активно разрабатываться АЦП, которые позволяли вводить информацию в ЭВМ со скоростью нескольких тысяч отсчётов в секунду. Это означало, что теперь можно обрабатывать сигнал цифровым способом вместо использования аналоговых устройств. В свою очередь, потребовались эффективные алгоритмы обработки сигналов и изображений, многие из которых используют преобразование Фурье. Поэтому появление нового алгоритма, сулившего ускорить вычисление дискретного преобразования Фурье в $N/\log_2(N)$ , было очень кстати.
``- Позже, - вспоминает Кули [2]. - я выяснил, что Гарвин был значительно более заинтересован в улучшении дистанционного сейсмического мониторинга ядерных взрывов; русские едва ли согласились бы на проведение инспекций на их территории. Гарвин так же видел необходимость в разработке методов раннего акустического обнаружения подводных лодок. Как и многие другие, я не считал это важным, поэтому поставил задаче разработки алгоритма БПФ приоритет ниже, чем собственным исследованиям. Тем не менее, под напором авторитета Гарвина и его постоянных телефонных звонков, я написал алгоритм для вычисления трёхмерного БПФ.''
Вскоре после публикации [1] Кули получил письмо от Филипа Рудника из Института Океанографии в Санн-Диего, Калифорния. Рудник сказал, что сам реализовал подобный алгоритм, используя метод из [7]. Статья Рудника с улучшенным вариантом такого метода вышла [8] чуть позднее статьи Кули и Тьюки - он не решился публиковать её сразу.
Оказалось, что приёмы, лежащие в основе БПФ, были опубликовы ещё раньше. В том же справочнике Стампффа [6] нашлась ссылка на более ранние работы Рунге и Кёнига [9]. В той работе так же использовался метод ``бабочки'' (Метод ``бабочки'', butterfly, заключается в использовании сделанных вычислений для получения соседних значений сложением или вычитанием уже полученных) для ускорения вычислений и контроля ошибок.
Кули написал статью [10], в которой приводилась, как он полагал, полную историю предшествующих похожих алгоритмов вычисления БПФ вплоть до работ Рунге [9]. Однако пыль веков скрывала в себе много интересного, и вскоре Кули получил ссылку от коллеги [11] на ещё более ранюю работу по вычислению БПФ. Это была глава книги великого Карла Фридриха Гаусса [12]. В этой главе, написанной на неоклассической латыни, приводились основные соображения алгоритма БПФ. Гаусс применял разновидность интерполяции по Лагранжу, и это могло привести его к возможности сокращения количества операций при быстром преобразовании. Позже были опубликованы работы [13,11], в которых приведён краткий перевод работы Карла Гаусса, предвосхтившей БПФ, а так же упомянуты другие работы, посвящённые БПФ.
1. Очевидно, что понимание важности и быстрая публикация значительных достижений очень и очень важны.
2. Аккуратное отношение к старой литературе может принести большую пользу. Награды за выдающиеся достижения должны предшествовать анализу старых публикаций и книг.
3. Общение между математиками, инженерами и специалистами прикладных областей является крайне плодотворным.
4. Не публикуйте статьи на нео-классической латыни.
Читать далее
И те, и другие были по-своему правы.
Следует заметить, что время публикации статьи Кули и Тьюки [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.
