Вычисление свертки

Разобравшись с тем, для чего нужна свертка, перейдем к задаче ее эффективного вычисления. Для простоты будем рассматривать случай векторов равной длины (то есть m = n), хотя все сказанное может быть напрямую применено к случаю векторов разной длины.

Вычисление свертки — тема более тонкая, чем кажется на первый взгляд. В конце концов, из определения свертки следует абсолютно законный способ ее вычисления: для каждого к вычисляется сумма

а результат используется как значение координаты к. Проблема в том, что при таком прямолинейном способе вычисления свертки приходится вычислять произ- ведение аb. для каждой пары (i,j), а это означает Θ(η2) арифметических операций. Время выполнения O(n2) для вычисления свертки выглядит естественно, так как в определении задействованы O(n2) умножений аb. Однако неочевидно, что вы- числение свертки обязательно должно выполняться за квадратичное время, по- скольку и ввод и вывод имеют только размер O(n).

Возможно ли разработать алгоритм, который обходит квадратичный размер определения свертки и вычисляет его другим, более умным способом?

Как ни удивительно, это возможно. Ниже описан метод, который вычисляет свертку двух векторов с использованием только O(n log n) арифметических опе- раций. В его основу заложен эффективный прием, называемый быстрым преоб- разованием Фурье (Fast Fourier Transform).

Быстрое преобразование Фурье широко применяется для анализа последова- тельностей числовых значений; быстрое вычисление свертки, которым мы будем заниматься здесь, — всего лишь одно из таких применений.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Вычисление свертки:

  1. Вычисление символических дирекций
  2. ВЫЧИСЛЕНИЕ СРОКА СТАБИЛЬНОСТИ БРАКА
  3. Вычисление ошибки выборки.
  4. Вычисление ошибки выборки.
  5. Вычисление ошибки выборки.
  6. Вычисление местного звездного времени
  7. Статья 676. Вычисление гарантийного срока
  8. Статья 860. Порядок вычисления гарантийного срока
  9. Вычисление ошибки репрезентативности для собственно случайной выборки.
  10. СТАНДАРТИЗОВАННОСТЬ