2.3. Быстрая свертка

2.3.1. Понятие свертки

Определение. Пусть даны два массива:

a = (…,a_-1, a₀, a₁, a₂, …), b = (…,b_-1 ,b₀,b₁, b₂, …) – конечные или бесконечные в одну или в обе стороны. Тогда сверткой последовательности a и b называется массив

c = (.., c_-1, c₀, c₁, c₂, …), где (2.5a)

т.е. суммирование производится по всевозможным сочетаниям, в которых k + l = i. Обозначается свёртка как: c = a*b.

В случае, когда последовательности (массивы) a и b бесконечны в обе стороны, выражение для c_i можно представить в виде

(2.5б)

Аналогичным образом определяется свертка для конечных массивов (в формулу (2.5.б) подставляются конечные пределы суммирования).

Пример. Даны два массива:

a = (a₀, a₁);

b = (b₀, b₁, b₂).

Определим свёртку этих массивов , используя формулу (2.5а):

c₀ = a₀b₀,

c₁ = a₀b₁ + a₁b₀,

c₂ = a₁b + a₀b₂,

c₃ = a₁b₂.

Рассмотрим классический пример свёртки.

1. При умножении многочленов:

a(x) = a₀ + a₁x + … + a_n-1 x^n-1,

bx) = b₀ + b₁x + … + b_n-1- x^n-1.

a(x)*b(x) = c(x) = c₀ + c₁x₁ + … + c_2n-2 x^{2n – 2},

c = a*b.

2. При перемножении числе столбиком (если не делать переносы в старшие разряды).

3. Пусть a и b – дискретные независимые случайные величины, такие что P(a = i) = a_i, P(b = i) = b_i. Причем a и b – обязательно независимые случайные величины (независимые случайные величины – те, для которых справедливо высказывание: P((xA) и (y B)) = P(xA) · P(y B), где x, y – значения случайных величин, А и В – некоторые множества из области значений соответствующих случайных величин).

Тогда, случайная величина c = a + b имеет распределение, которое есть ни что иное, как всёртка массивов a_i и b_i.

.

2.3.2. Обычный и быстрый алгоритм свертки

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

Имеем:

a = (a₀, a₁, a₂, …, a_n-1)

b = (b₀, b₁, b₂, …, b_n-1).

Оценим трудоемкость вычисление свертки по обычному алгоритму:

c₀ = a₀b₀ - состоит из 1 слагаемого

c₁ = a₀b₁ + a₁b₀ - состоит из 2 слагаемых

c₂ = … - состоит из 3 слагаемых

до середины массива с количество слагаемых, из которых состоят его элементы, увеличивается до n

с_n-1 = a₀b_n-1 + … + a_n-1b₀,

n слагаемых

а от c_n до c_2n-2 уменьшается. Последний элемент массива – c_{2n – 2} – имеет одно слагаемое. Итого:

T(n) = 1 + 2 + 3 + … + (n-1) + n + (n-1) + … + 3 + 2 + 1 = n².

Если реализовать вычисления по формуле (2.5а), т.е. нерационально – путем организации трех вложенных циклов (во внутреннем цикле будет проверка по условию k + l = i), то трудоемкость будет даже не n², а n³. На самом деле, используя в формулах свертки преобразование Фурье, можно снизить трудоемкость с n² до nlog(n). Для вывода этих формул сначала докажем теорему.

Теорема 2.1. Пусть a = (a₀, a₁, a₂, … , a_n-1, 0, 0, 0 … 0)

и b = (b₀, b₁, b₂, … , b_n-1, 0, 0, 0 … 0) – массив длины 2n полученные из первоначальных массивов длины n путем дописывания n нулей. Соответственно, F(a) и F(b) – преобразования Фурье от этих массивов, т.е.

F(a) =

F(b) =( .

Тогда преобразование Фурье от их свертки:

есть ничто иное, как покоординатное произведение массивов F(a) и F(b), помноженное на 2n: .

Доказательство. Введем переменную w = exp { -2i/2n}.

Тогда, по формулам преобразования Фурье:

Аналогично,

Теперь мы можем перемножить и . Посмотрим, что получится в результате:

Ввёдем новую переменную m = l +j.

В результате получаем

Теорема доказана.

Используя Теорему 2.1, в которой фактически сказано, что преобразование Фурье от свертки есть

F(c) = F(a*b) = 2n F(a) ○ F(b)

Операция покоординатного перемножения массивов

приходим к выводу, что можно выполнять свертку с помощью преобразования Фурье по следующей формуле:

a*b = F^-1(2nF(a) ○ F(b)), (2.6)

где F^-1 – обратное преобразование Фурье. => Свертка массивов a и b может быть выполнена по формуле 2.6.

Трудоемкость свертки по формуле 2.6:

T(n) = 3 · 2n · log(2n) ≈ n logn << n²

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

трудоемкость покоординатного перемножения массивов