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



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

Свистульки, бубенчики и рюшечки в документах LaTeX



13 коммент.
Как все уже хорошо знают, в ЛаТеХ добиться хорошего качества документов по умолчанию очень просто: используя десяток стандартных команд, вы получите неизменно превосходный результат (ТМ) без лишних усилий. То есть документ будет хорош, но ведь иногда хочется украшательств, мигалок, свистулек и бубенчиков. На эту тему автор уже собрал небольшую коллекцию, которой и рад поделиться. Кроме того, автор открыл для себя удивительные книги Edward Tufte, который знает толк в визуальной подаче информации.


Читать далее

Как написать статью в LaTeX



17 коммент.
Результатом любого приличного исследования являются публикации. Вы делаете что-то новое, и это по идее должно немного (или значительно) двинуть научное знание вперёд. А так как научные тексты удобнее писать в LaTeX, специально для этого созданным не абы кем, а Дональдом Кнутом, то возникает непраздный вопрос: как же написать статью в LaTeX?!

Вернее, вопросов два: как написать научную статью и как это сделать в ЛаТеХе?


Как написать научную статью
В Сети есть много хороших и правильных постов о том, как следовало бы писать статьи. Там вам скажут, что сначала придумывается заглавие, потом аннотация (abstract), потом красивое введение, потом, собственно, результаты исследований и, как апофеоз экзистенциального катарсиса, заключение.

В жизни всё несколько иначе. Обычно стоит большая задача, которую нужно решить. Мы сидим, чещем затылок и листаем журналы в поисках намёков на решение. Пробуем то и это, и чаще всего либо оно не работает вообще, либо работает, но не так, как надо. Потом иногда приходит какая-нибудь хорошая и свежая мысль, и внутренний голос говорит "О! Это интересно", а внешний - "Ахххаааа!".

После прихода этого самого "Аха!" вместе с хорошей идеей автор начинает что-то быстро писать на бумаге, прикидывать, покрякивать и энергично потирать ручонки. Далее, в состоянии полного угара творчества что-то ваяется, вычисляется, математически выводится, разливается по колбам, экспериментируется, программируется и численно симулируется. Это самое счастливое время, когда забываешь обо всём на свете и делаешь что-то занятное - за это, собственно, научным сотрудникам и платят деньги.

Через некоторое время угар творчества проходит и автор видит наброски, куски кода, булькающие колбы, вереницы данных, таблицы и графики. Работа принимает более организованный характер: нужно сравнить с имеющимися методами, провести дополнительные эксперименты или расчёты. Если это что-то, чего ещё никто не делал - самое время приступать к написанию статьи.

Основная часть таким образом у автора в том или ином виде уже есть, так что статья начинается с середины, а именно - с полученных данных. Всё, что написано про оформление диплома или курсового проекта в LaTeX, полностью справедливо и здесь.

В основной части считается хорошим тоном привести математическую формулировку или модель, которая соответствует процессам. Сравнение численной модели с реальным экспериментом тоже добавляет веса и доверию статье. Также стоит упомянуть, на каком компьютере проводились симуляции (особенно если вы предлагаете новый алгоритм и сравниваете с предыдущими), какое оборудование использовали и что булькало в пробирках.


Заглавие обычно выбирается из пары десятков нагенерированных коллегами и автором вариантов. Как правило, заглавие статьи должно содержать некие ключевые слова, которые описывают содержимое статьи. Это важно, так как позволяет быстрее и проще вашу статью потом найти другим людям в поисковых системах.


После этого пишется обычно одна из самых занудных частей статьи - Заключение. Дело это непростое и обычно приходит с опытом и набитием шишек. Так как люди обычно читают аннотацию (abstract), введение и заключение к статье, то они должны быть отполированы до зеркального блеска.

Обычно заключение отвечает на три вопроса:
  1. Что за проблема решалась в статье?
  2. Какие результаты были получены в статье?
  3. Ну и что!?
Для ответа на эти вопросы, в особенности на последний, хорошо поиграть в игру "Ну и что?!". То есть представьте, что вы беседуете с редактором журнала, и он вас спрашивает: "ну и что в статье интересного-то?" или "почему я должен обратить на это внимание?".


Введение это вторая по трудности часть после заключения. Введение обычно даёт формулировку целей исследования и достаточный обзор существующей литературы. Но это легко сказать, а что писать-то? Ну, например, автор этих строк пользуется следующей болванкой:
  1. Почему это исследование вообще проводилось?
  2. Какая литература уже существует по этому вопросу? Здесь можно провести обзор и показать ту брешь, которую вы хотите заткнуть своей статьёй.
  3. Какова конкретная цель исследований? Это теоретическое обоснование чего-то, или экспериментальная работа, или численные симуляции.
  4. В чём новизна работы?
После написания введения и заключения можно писать аннотацию (abstract).


Аннотация (abstract) это короткое описание цели работы, результатов и что в работе сообщается. В целом, аннотация пишется обычно из надёрганных предложений из Введения и Заключения. Обычно аннотации короткие и должны быть не длиннее, скажем, 250 слов (у журналов и конференций по этому поводу свои правила).






Как написать научную статью в LaTeX
Эпиграф:
LaTeX is capable of most things 
but not always in the most obvious manner.

Собственно, как уже говорилось выше, почти всё, что нужно для этого, есть в постах о написании диплома в LaTeX:
Есть одно НО: у каждого журнала или конференции есть свой собственный, не имеющий аналогов в мире, стилевой файл  LaTeX разной степени корявости и тухлости. Как правило, там содержится рабочий пример статьи, так что лучше попробовать сначала собрать пример.

Но если вы думаете, что отправленную вами в журнал статью примут "с колёс" и без редакции, то вы либо крутой нобелевский лауреат, либо большой оптимист. И поэтому скорее всего вам предстоит общение с рецензентами и редактором журнала. Вот тут-то LaTeX нам и сослужит добрую службу....


Рецензии и правки научных статей в LaTeX
Ещё до того, как вы отправите статью, лучше всего использовать одноколоночный набор и включить нумерацию строк, чтобы рецензенты ссылались не просто на страницу, а сразу на конкретную строку.


Нумерация строк в LaTeX
Нумерация строк включается пакетом lineno, который можно скачать здесь. В преамбуле документа добавляем
\usepackage[mathlines]{lineno}% Enable numbering 
Отлично, теперь вставляем команду:
\linenumbers\par %%% <---- turn on the numeration of lines
там, где мы хотим начать нумерацию линий. Если нужно оборвать нумерацию в конце статьи перед, скажем, списком литературы, команда выглядит так:
\nolinenumbers %%% do not use line numbers any more.
Важно то, что пакет lineno позволяет не только автоматически проставлять номера строк, но ещё и ссылаться на них. Автор настоятельно рекомендует использовать эту возможность, чтобы не сойти с ума самому при правках и не злить рецензентов.

Для этого в том месте, которое вы обещаете рецензенту поправить (и делаете это), ставим ссылку:
\linelabel{review:1R1}
Как и везде в ЛаТеХе, ссылки стоит ставить разумные: например, здесь написано, что это ответ на замечание 1 от рецензента 1 (они обычно анонимные).

Далее в тексте ответа на замечания рецензентов пишем что-то типа:
We clarified this on page~\pageref{review:1R1} line~\ref{review:1R1}.

Наступает счастье: здесь мы приводим не только ссылку на строку (\ref{review:1R1}) но и сразу на страницу (\pageref{review:1R1}).

Вместо конструкции $$ ..... $$  следует использовать \[ ... \] или \begin{displaymath} ....\end{displaymath}, тогда пакет lineno правильно проставит номера строк в тексте с математическими формулами.

Больше о нумерации строк вам расскажет весьма толковая документация к пакету lineno.


Ссылка на сноски в LaTeX
Допустим, вы сказали, что угоняете часть тектса в сноску. Об этом лучше написать рецензенту прямо, чтобы он не искал кусок пропавшего текста по всему документу.

Для этого пишем в преамбуле документа:
\newcommand{\footnoteremember}[2]{\footnote{#2} \newcounter{#1} \setcounter{#1}{\value{footnote}}} \newcommand{\footnoterecall}[1]{\footnotemark[\value{#1}]}
Теперь в тексте можно написать:

The Finite Element Analysis was perfomed on a crappy computer\footnoteremember{footnotelatitude}{Simulations were run on the Dell Latitude E5400 notebook with Intel Celeron 2.2 GHz processor, 2GB DDR2 SDRAM, 120 GB SATA HDD 5400 rpm under Debian GNU/Linux v 5.0 with MATLAB v2007b for UNIX.}.

Так что у нас есть ссылка footnotelatitude которая ведёт на сноску. Теперь сослаться на неё можно так:
(see footnote\footnoterecall{footnotelatitude})
И вы теперь сможете видеть номер сноски, на которую вы ссылаетесь. Трюк позаимствован отсюда.


Перевод PDF в простой текст
Сгенерированные ЛаТеХом документы часто переводятся в PDF, но иногда требуется перевести всё в простой текст. Часто это следует делать с сохранением структуры, и тут нам поможет pdftotext:
pdftotext -layout  -nopgbrk   reviewnotes_12-0238_MS.pdf
где ключи означают:
 -layout           : maintain original physical layout
 -nopgbrk          : don't insert page breaks between pages
Если нужно перевести в текст только со страницы 5 по страницу 10, даём команду:
pdftotext  -f 5 -l 10 reviewnotes_12-0238_MS.pdf
После этого текст можно вставлять в веб-форму для ответа рецензентам.




Ссылка название раздела или главы в LaTeX
Тоже часто используется, особенно если вы при правках радикально меняете структуру статьи (скажем, рецензенты вам это настоятельно советуют). Делается ссылка на название раздела с помощью пакета nameref и который входит в пакет hyperref - он входит в стандартный набор TexLive и потому уже должен быть установлен.

Включаем пакет в преамбуле:
\usepackage{nameref}

Ставим метку для раздела (section):

\section{Introduction}\label{intro}
И ссылемся в тексте:
See more details in the \nameref{intro} section that has number \ref{intro}.
Вместо этого мы при компиляции увидим:
See more details in the Introduction section that has number 1.
Этот удобный и простой трюк подсмотрен тут.


Вместо заключения
Собственно, этот пост - небольшая зарубка на память и собрание нескольких рецептов из моего уже порядком разросшегося черновика. Полностью приведённый пример можно посмотреть на моей странице в Google Code.

Читать далее

Вырываем список книг для чтения из zotero с мясом, Tcl-ем и SQlite-ом



3 коммент.
В этом посте мы продолжим беспощадную борьбу с кошмарным интерфейсом недо-системы управления библиографией под названием zotero с целью получить список книг для чтения. Даже для такой простой вещи, как получения списка книг, находящихся в базе zotero, нужно брать в руки автоген, скальпель и кувалду. Линуксоидов этим, конечно, не напугать, но маководов от экранов просьба удалиться во избежание.

В этом посте мы безтрепетной рукой вырвем с мясом из зотеры список книг, засунутых туда через графический, скажем так, интерфейс. В этом нам поможет язык Tcl (Тикль), Debian и SQLite3.

Читать далее