Сложность вычисления дискретного преобразования Фурье?

18

Какова сложность (в стандартном целочисленном ОЗУ) вычисления стандартного дискретного преобразования Фурье вектора из N целых чисел?

Классический алгоритм для быстрых преобразований Фурье , неуместно [1] приписываемый Кули и Тьюки, обычно описывается как выполняющийся за О(NжурналN) времени. Но большинство арифметических операций, выполняемых в этом алгоритме, начинаются с сложных N х корней единицы, которые (для большинства N ) иррациональны, поэтому точная оценка в постоянном времени нецелесообразна. Та же проблема возникает с наивным алгоритмом времени О(N2) (умножением на матрицу Вандермонда комплексных корней единицы).

Даже не ясно, как точно представить вывод ДПФ (в любой полезной форме). Другими словами, не ясно, что вычислительные ДПФ действительно возможны!

Итак, предположим, что нам нужно только битов точности в каждом выходном значении. Какова сложность вычисления дискретного преобразования Фурье в зависимости от n и b ? (Для конкретности, не стесняйтесь предполагать, что n является степенью 2. )бNbn2

Или каждый случай «БПФ» в литературе на самом деле означает «быстрое теоретико-числовое преобразование »? [2]

Смотрите мои связанные вопросы о сложности гауссовского исключения и евклидовых кратчайших путей .

[1] Он действительно должен называться (некоторый префикс) алгоритмом Гаусса-Рунге-Кенига-Йейтса-Штумпфа-Даниэльсона-Ланчоса-Кули-Тьюки.

[2] И если да, то почему в большинстве учебников описывается только алгоритм комплексных чисел?

Jeffε
источник
1
Я думаю, что в этом его суть: теоретически вам не нужно беспокоиться о , но в любой АКТУАЛЬНОЙ реализации вы ДОЛЖНЫ беспокоиться об этом и об ошибке, которая может возникнуть. b
Суреш Венкат
1
На самом деле это хороший вопрос каждый дополнительный бит точности добавляет к интенсивности сигнала (умножить на 2 ). Поэтому я думаю, что этот вопрос будет наиболее полезным, если размеры промежуточного слова могут быть расширены! 3dB2
против
3
Вычислительный анализ рассмотрел этот и связанные вопросы. Эта статья дает оценку сложности для вычисления преобразования Фурье в рамках эффективности Вейрауха II типа. Ограничение состоит в том, что он является линейным в представлении (бесконечного, действительного) ввода. И вход, и выход определены в этой системе относительно параметров точности, поэтому может быть способ перевести это в модель ОЗУ.
Аарон Стерлинг
3
Взгляните на метод А в статье Шёнхаге и Штрассена о целочисленном умножении. Он использует сложные преобразования Фурье с ограниченной точностью. Я думаю, это также описано в Кнут Vol. 2.
Маркус Блезер
2
Маркус, Аарон: переходить на ответы?
Суреш Венкат

Ответы:

9

Этот ответ представляет собой вариант анализа первого алгоритма («Метод A») Шёнхаге и Штрассена для умножения длинных целых чисел.

Предположим, что мы хотим вычислить БПФ длиной K=2k . Масштаб ввод таким образом, что все значения меньше 1. Предположим сначала , что мы вычислим с -разрядного фиксированной точкой арифметика ( м бит после двоичной точки). Пусть δ = 2 1mm быть ( "комплекс") единица наименьшего положения. Пустьω=exp(2πi/K).δ=21/2mω=exp(2πi/K)

1) Можно вычислить приближения , для которых | ω j - ω j | ( 2 к - 1ωj для всех 0 j K - 1 . Это можно сделать за время O ( K M ( m ) ), где M ( m ) - время, необходимое для умножения m- битных чисел. (см. Кнут, том 2, 3-е изд., стр. 309).|ωjωj|(2k1)δ0jK1O(KM(m))M(m)м

Если стандартное целочисленное ОЗУ означает логарифмическую стоимость, то . Если стандартное целочисленное ОЗУ означает слово ОЗУ, то M ( m ) = OM(m)=O(mlogm) . (Шенхаге и Штрассен показывают в «Методе А», как уменьшить за линейное время умножение m- битных чисел на m умножение O ( log m ) битовых чисел. Последнее можно сделать за единицу стоимости.)M(m)=O(m)mmO(logm)

2) Классическое БПФ Кули-Тьюки вычисляет операции вида . Мы используем m- битную арифметику с фиксированной точкой, эти операции становятся a = t r u n c a t e ( b + ω a=b+ωjcm. Если мы знаемbиc′ сточностью доϵ, мы получаемa′ сточностью до2ϵ+2a=truncate(b+ωjc)bcϵa .2ϵ+2kδ

3) Используя индукцию, легко видеть , что мы получаем окончательный результат с ошибкой . Чтобы получить точность b в конце, m k + log k + b + O ( 1 ) . (2k1)2kδbmk+logk+b+O(1)

4) Таким образом, конечное время работы .O(KkM(k+b))

Это также должно работать с числами с плавающей запятой: 1) все еще может быть сделано с арифметикой с фиксированной запятой, 2) также верно для чисел с плавающей запятой.


В арифметике с фиксированной точкой, я думаю, это можно сделать даже быстрее. Сначала мы сводим вычисление БПФ к умножению полиномов с использованием трюка Блюштейна. Длина коэффициентов, необходимых для получения желаемой точности, должна быть . Затем мы сводим умножение многочленов к умножению длинных целых чисел. (Добавьте коэффициенты к длинному числу и разделите их блоками нулевой длины O ( k + b).O(k+b) .) Длина целых чисел O ( K ( k + b ) ) .O(k+b)O(K(k+b))

Маркус Блезер
источник
Итак, из пункта (4), установив K = n и b = O (log n), и предположив, что мы работаем над словом RAM, мы получаем время выполнения . Правильно? O(nlog2n)
Джефф
Да. Второй алгоритм даже дает , предполагая, что точность O ( k + b ) достаточна. (Я не вижу смысла, почему этого недостаточно, но я не делал подробностей.)O(nlogn)O(k+b)
Маркус Блезер
2
Кстати, если меньше, чем O ( log n ) , то также первый алгоритм дает время работы O ( n log n ), так как M (bO(logn)O(nlogn) . M(O(logn))=1
Маркус Блезер
Мне посчастливилось взглянуть на книгу Ахо, Хопкрофта и Уллмана «Разработка и анализ алгоритмов», и они обсудили алгоритм в битовой модели и связанные с этим вопросы в некоторых деталях.
Чандра Чекури
Но, насколько я помню, они обсуждают только «теоретико-числовое БПФ» в битовой модели.
Маркус Блезер
8

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

Позвольте мне начать с вопроса, почему вы хотите знать ответ на этот вопрос? Как правило, люди, которым небезразлична проблема такого рода, сталкиваются с фактической реализацией высокопроизводительного БПФ для практического применения. Такие люди меньше заботятся об асимптотической сложности в некоторой идеализированной вычислительной модели, чем о максимизации производительности при определенных аппаратных и программных ограничениях. Например, разработчики самого быстрого преобразования Фурье на Западе пишут в своей статье:

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

Это те проблемы, которые теоретики обычно не хотят осквернять, но они имеют большое значение в реальных реализациях. Если теоретик заявляет: «Я вычислил абсолютную наилучшую асимптотическую битовую сложность в модели RAM», практикующий может сказать: «Это хорошо», но может найти такой теоретический результат бесполезным для своих целей.

Сказав это, я думаю, что вам лучше всего взглянуть на литературу по численному анализу. Например, Таш и Цойнер внимательно изучили числовую стабильность алгоритма БПФ. Это все еще может быть не совсем то, что вы хотите, потому что общее мнение среди практиков, как представляется, заключается в том, что для достижения определенного количества числовой точности лучший практический подход заключается в предварительно вычислить определенные числа, называемые «коэффициентами твида», с высокой точностью. Если вы делаете только одно БПФ, то это не будет самым быстрым подходом, потому что вы не можете амортизировать стоимость ваших одноразовых предварительных вычислений по большому количеству вычислений БПФ. Тем не менее, их анализ ошибки округления наихудшего случая все еще должен быть актуальным для вашего вопроса.

Тимоти Чоу
источник
11024100 дополнительных умножений по текущим алгоритмам.
против
1
Меня интересует как чисто теоретический вопрос, в интересах правильной и честной стипендии. Довольно часто читать «и здесь мы используем FFT, который, как всем известно, выполняется за O (n log n) времени» в середине чисто комбинаторного алгоритма, иначе анализируемого с точки зрения обхода указателей и O (log n). ) -битная целочисленная арифметика. Если, на самом деле, целочисленная свертка может быть выполнена за O (n log n) времени с использованием небольшого варианта БПФ, это, возможно, простительно, но все еще небрежно. Если нет, то любой бедняга, который пытается реализовать алгоритм, получит НЕПРАВИЛЬНЫЙ ОТВЕТ.
Джеффс
И, конечно, я не ожидаю, что ответ на мой вопрос окажет какое-либо влияние на практике.
Джефф
2
Джефф, что касается честной стипендии, разве недостаточно сказать, что БПФ требует O (n log n) кольцевых операций? Это естественный способ измерения сложности алгоритма FFT. Я не вижу мотивации для преобразования всего в одну конкретную модель вычислений. Есть ли какая-то теорема, которую вы пытаетесь доказать, где важно отслеживать количество битов точности? Что касается вашего бедного чмо, я не куплюсь, что он получит «неправильный ответ». В любой реальной реализации вопрос, который вы здесь задаете, вряд ли будет доминирующим.
Тимоти Чоу
O(nlogn) кольцевых операций, если вы анализируете БПФ изолированно. Но если БПФ является лишь одним из компонентов более крупного алгоритма, то для сообщения о времени работы более крупного алгоритма требуется согласованная модель вычислений для всех составляющих его подпрограмм, включая БПФ. Например, «свертывание двух целочисленных последовательностей с использованием алгоритма FFT Кули-Тьюки, а затем вставка полученных коэффициентов в хэш-таблицу» (чтобы составить полностью фальшивый пример) вызывает проблемы.
Джефф