Карта → событие
БПФ: алгоритм, опередивший потребность
Что было дорого
Ряд Фурье к 1960-м стал главным инструментом обработки любых сигналов: звук, сейсмограмма, радиоизлучение, дифракционная картина — всё раскладывается на частоты. Машина работает с конечным набором отсчётов, и вместо интеграла считает дискретное преобразование Фурье: по $N$ отсчётам получить $N$ амплитуд.
Прямой счёт по определению требует $N^{2}$ операций — каждая из $N$ амплитуд есть сумма $N$ слагаемых. Пока $N$ порядка сотни, это пустяк. При $N=10^{6}$ получается $10^{12}$ операций — недели работы машины 1960-х.
Именно это и упиралось: записи сейсмических станций и радиотелескопов длинные, а спектр по ним нужен весь.
Заседание
Весной 1963 года Джон Тьюки — статистик, работавший разом в Принстоне и в Bell Labs, — сидит на заседании научного консультативного комитета при президенте Кеннеди. Обсуждают, как отличить подземный ядерный взрыв от землетрясения по сейсмическим записям: от этого зависит, можно ли подписывать договор о запрете испытаний, не имея инспекций на месте. Нужен спектральный анализ длинных сейсмограмм, и он слишком дорог.
Тьюки набрасывает на заседании идею. Присутствующий Ричард Гарвин из IBM видит набросок и передаёт его программисту Джеймсу Кули в исследовательский центр Уотсона — назвав, для секретности, совсем другую задачу, кристаллографическую. Кули пишет программу. В 1965 году выходит их совместная статья на четыре страницы.
Разделяй
Идея — рекурсивное разбиение. Сумму из $N$ слагаемых разбивают на две: по чётным номерам и по нечётным. Каждая оказывается дискретным преобразованием Фурье вдвое меньшего размера, а сложить их результаты стоит $N$ действий.
$$T(N)=2\,T(N/2)+N \quad\Longrightarrow\quad T(N)=N\log_{2}N.$$
Для $N=10^{6}$ это примерно $2\cdot10^{7}$ операций вместо $10^{12}$ — ускорение в пятьдесят тысяч раз. Не «на порядок быстрее», а «стало возможным».
БПФ — это компрессия звука и изображения, цифровое радио, томография, радиоастрономия, распознавание речи, всякая обработка сигнала вообще. В списках важнейших алгоритмов XX века он стоит первым или вторым, смотря кто составлял список.
Он уже был
В 1984 году Хайдеман, Джонсон и Беррус разбирали историю вопроса и обнаружили полный алгоритм — рекурсивное разбиение, всё как у Кули и Тьюки, — в работе ГауссаКарл Фридрих Гаусс«Король математиков», у которого напечатанное было заметно меньше сделанного: половина результатов пролежала в дневнике до самой смерти — включая неевклидову геометрию. «Theoria interpolationis methodo nova tractata».
Работа написана осенью 1805 года. Гаусс интерполировал наблюдения астероидов Паллады и Юноны, ему требовалось разложить их по тригонометрическим суммам, и он придумал, как сделать это быстро.
Вдумаемся в дату. Мемуар ФурьеЖозеф ФурьеУтверждал, что любую функцию можно сложить из синусов, — и был не прав ровно настолько, чтобы математике понадобилось сто лет и три новые теории, чтобы разобраться. прочитан в Институте в 1807 году. То есть быстрый алгоритм для анализа Фурье был придуман раньше, чем сам анализ Фурье.
Гаусс это не опубликовал. Работа вышла посмертно, в третьем томе собрания сочинений 1866 года, на новолатинском языке и в устаревшей уже тогда нотации, — и сто восемнадцать лет пролежала непрочитанной.
Почему её не прочли
Причина не только в латыни, и она составляет главную мысль этой точки.
Алгоритм опередил не публикацию, а потребность. Выигрыш $N/\log N$ ничтожен при малых $N$: при шестнадцати точках, которые Гаусс считал руками, разница между $256$ и $64$ действиями не стоит усложнения. Быстрое преобразование Фурье имеет смысл только тогда, когда $N$ измеряется миллионами, — то есть только при машине.
Читатели 1866 года не могли оценить эту работу не потому, что были невнимательны, а потому, что у них не было задачи, на которой видна разница.
Мы уже видели в этой линии человека, который сделал открытие и не сумел его рассказать. Здесь случай тоньше и печальнее: рассказ был написан и напечатан, но мир ещё сто лет не имел органа, которым это можно услышать.
Следующая точка: Цюрих — где оказалось, что и умножение матриц мы делали неоптимально.