7/28/2014

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

Сразу после публикации статьи Кули и Тьюки [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.

9 комментариев:

  1. Миша, все ссылки ведут мимо.

    ОтветитьУдалить
  2. @Anton Yakutovich комментирует...
    Миша, все ссылки ведут мимо.
    Ну не умею я пользоваться latex2html - не смогла я, не смогла :-)

    Ссылки поправил (вообще убрал гиперссылки), вроде полегчало.

    Пост несколько выбивается из тематики блога, и тем не менее я решился его выложить. Написано давно, и вообще показательная история. Недавно у меня такое же было: мы с шефом пытались сделать быстрый алгоритм, сводящийся к approximate matrix inversion, чтобы не решать оптимизационную проблему. Шеф выдал импровизацию, я её улучшил и доработал напильником. Работает сносно, и решили показать её на местной конференции (Australian Control Conference). Конференция рецензируемая, и один из рецензентов нам написал что-то вроде "друзья, ваш метод мне сильно напоминает Jacobi iterations" и дал ссылку на справочник по численным расчётам. Я открываю - шайтан, это оно, двести лет спустя :-) Ну почти, но идея очень сходная. Долго ли, коротко - в общем, в нашем случае это имело физический смысл (the conference paper in question, in English, for anyone who is curious enough). В общем, ситуация в посте - не редкость, и уже приключилась с автором этих строк.

    Этот пост из той же оперы, что и пост про Лену. Фотография там была лучше, конечно :-)

    В ближайшие посты, как у меня освободится время, будет про вебдваноль и андроид. Математикой постараюсь больше не грузить :-)

    ОтветитьУдалить
  3. В ближайшие посты, как у меня освободится время, будет про вебдваноль и андроид
    Ждем с нетерпением :-)

    ОтветитьУдалить
  4. Доброго времени суток! Весьма познавательно. Спасибо. Михаил, мне кажется у Вас очепятка --- Гичард Гарвин в "Создание алгоритма" наверное должно быть Ричард

    ОтветитьУдалить
  5. @Vladimir Vlsu комментирует...
    Ждем с нетерпением :-)

    Frankly, looking at this,, my motivation to write anything in russian on this blog (and in russian in general) vanishes. Moreover, I don't have much time these days (my research program takes more and more of my attention), and I'm not going to sacrifice my research time when some can block the major part of the audience of this site.

    Of course, I'm not going to participate in any of these restrictive schemes - because, you know, I'm not a journalist. I'm an engineer, and I'm not going to change my career :-)

    Anyway, this blog is located in USA, so anyone can reach it (at least with proxies). I'm writing to my Lunodrome (markdown-based simple blog) more and more anyway, and the fact that Scriptogram is based on Dropbox is very important (you can backup the data easily).

    Enjoy freedom while it lasts...

    @Виктор Дубинич комментирует...
    Весьма познавательно. Спасибо.

    You are welcome.

    Михаил, мне кажется у Вас очепятка --- Гичард Гарвин в "Создание алгоритма" наверное должно быть Ричард

    Corrected. Thank you.

    ОтветитьУдалить
  6. @virens
    Ответ здесь: https://dl.dropboxusercontent.com/u/59440546/qr/message.jpg
    Прочитать этим: http://zxing.org/w/decode.jspx

    ОтветитьУдалить
  7. >в которой описывался алгоритм вычисления быстрого преобразования Фурье

    Очевидно, здесь ошибка. Следует читать: "описывался алгоритм вычисления дискретного преобразования Фурье".

    ОтветитьУдалить
  8. Спасибо. Очень интересно и , действительно, поучительно.

    ОтветитьУдалить
  9. Здорово, virens! Я, оказывается, такой замечательный пост пропустил. Сам как? Черкни пару строчек мне на email. Ты случаем не в Москве?

    ОтветитьУдалить