умножение полиномов с использованием быстрого преобразования Фурье

StackOverflow https://stackoverflow.com/questions/1257010

  •  12-09-2019
  •  | 
  •  

Вопрос

Я просматриваю вышеупомянутую тему из CLRS (CORMEN) (страница 834) и я застрял на этом этапе.

Кто-нибудь может, пожалуйста, объяснить, как работает следующее выражение,

A(x)=A^{[0]}(x^2) +xA^{[1]}(x^2)

вытекает из,

n-1                       `
 Σ  a_j x^j
j=0

Где,

A^{[0]} = a_0 + a_2x + a_4a^x ... a_{n-2}x^{\frac{n}{2-1}}  
A^{[1]} = a_1 + a_3x + a_5a^x ... a_{n-1}x^{\frac{n}{2-1}}
Это было полезно?

Решение

Полином A(x) определяется как

A(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ...

Чтобы запустить стратегию «разделяй и властвуй» при умножении полиномов с помощью БПФ, CLRS вводит два новых полинома:один из коэффициентов при четных степенях x называется A[0] и один из коэффициентов при нечетных степенях x называется A[1]

A[0](x) = a_0 + a_2 x + a_4 x^2 + ...
A[1](x) = a_1 + a_3 x + a_5 x^2 + ...

Теперь, если мы заменим x^2 в A[0] и A[1], у нас есть

A[0](x^2) = a_0 + a_2 x^2 + a_4 x^4 + ...
A[1](x^2) = a_1 + a_3 x^2 + a_5 x^4 + ...

и если мы умножим A[1](x^2) к x, у нас есть

x A[1](x^2) = a_1 x + a_3 x^3 + a_5 x^5 + ...

Теперь, если мы добавим A[0](x^2) и x A[1](x^2), у нас есть

A[0](x^2) + x A[1](x^2) = (a_0 + a_2 x^2 + a_4 x^4 + ...) + (a_1 x + a_3 x^3 + a_5 x^5 + ...)
                        = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ...
                        = A(x)

К.Э.Д.

Другие советы

Если вы разделите полином на «нечетные показатели» и «четные показатели», вы обнаружите досадный факт, что полином A[1] (тот, который имеет нечетные показатели) имеет, ну, нечетные показатели!Для БПФ даже с показателями легче работать.Таким образом, можно просто выделить один «x» из всех значений в A[1] и переместить его за пределы выражения.

БПФ предпочитает работать только с полиномами, возведенными в степень.Таким образом, когда вы применяете принцип «разделяй и властвуй», вы хотите превратить выражение A[1] в полином «четной степени» и выполнить рекурсию по нему, и затем умножить обратно в этом x.Вы увидите, что это происходит во внутреннем цикле реального алгоритма.

Редактировать:Я понимаю, что ваше замешательство может быть связано с тем, что они «проходят» (x^2) в качестве ценить в полиноме.«x» в A[1] и A[0] отличаются от x в выражении (x^2).Вы увидите, как это должно быть, поскольку исходный полином A возрастает до показателя N, а A[1] и A[0] повышаются только до показателя (N/2).

Я не собираюсь отвечать на ваш вопрос, потому что чувствую, что предыдущие люди уже отвечали на него.Что я сделаю, так это попытаюсь объяснить назначение БПФ.

Во-первых, БПФ - это способ вычисления свертки между двумя векторами.То есть, предположим, что x = и y = являются векторами 1xn, тогда свертка x и y равна

\sum_{i=0} ^n {xi y{n-i}}.

Вам придется смириться с тем фактом, что вычисление этого значения чрезвычайно полезно в широком спектре приложений.

Теперь рассмотрим следующее.

Предположим, мы построим два многочлена

A (z) = x0 + x1 *z + x2 * z ^ 2 + ..+ xn ^ z ^ n B(z) = y0 + y1*z + y2 * z ^ 2 + ..+ ин^з^н

тогда умножение равно

AB(z) = A(z)B(z) = \sum_{i=0} ^ n (\sum_{k=0} ^ i xk*y{i-k}) z ^i

где внутренняя сумма явно представляет собой свертку разного размера для разных значений k.

Теперь мы можем четко вычислить коэффициенты (свертки) AB за n ^ 2 времени методом грубой силы.

Однако мы также можем быть гораздо умнее.Учтите тот факт, что любой многочлен степени n может быть однозначно описан n+ 1 точками.То есть при наличии n + 1 точки мы можем построить уникальный многочлен степени n, проходящий через все n + 1 точки.Далее подробнее рассмотрим 2 многочлена в виде n+1 точек.Вы можете вычислить их произведение, просто умножив n + 1 y-значений и сохранив x-значения, чтобы получить их произведение в точечной форме.Теперь, учитывая многочлен в форме n + 1 точки, вы можете найти уникальный многочлен, который описывает его за O (n) время (на самом деле я не уверен в этом, это может быть O (nlogn) время, но, конечно, не больше.)

Это именно то, что делает БПФ.Однако точки, которые он выбирает, чтобы получить n + 1 точек для описания многочленов A и B, подобраны ОЧЕНЬ тщательно.Некоторые из точек действительно сложны, потому что так уж получилось, что вы можете сэкономить время при вычислении многочлена, рассматривая такие точки.То есть, если бы вы выбрали только реальные точки вместо тщательно выбранных точек, которые использует БПФ, вам потребовалось бы O (n ^ 2) времени для оценки n + 1 точек.Если вы выберете БПФ, вам понадобится всего O (nlogn) времени.И это все, что есть в БПФ.О, и есть уникальный побочный эффект в том, как БПФ выбирает точки.Учитывая многочлен n-й степени, вы должны выбрать 2 ^ m точек, где m выбрано таким образом, чтобы 2 ^ m было наименьшей степенью 2, большей или равной n.

A(x) is broken in to even x^2, and odd x parts,

for example if A(x) = 21 x^5 + 17 x^4 + 33 x^3 + 4 x^2 + 8 x + 7

then A0 = 17 y^2 + 4 y + 7
     so that A0(x^2) = 17 x^4 + 4 x^2 + 7

and  A1 = 21 y^2 + 33 y + 8
     so that A1(x^2) = 21 x^4 + 33 x^2 + 8
     or  x * A1(x^2) = 21 x^5 + 33 x^3 + 8 x

clearly, in this case, A(x) = A0(x^2) + x A1(x^2) = even + odd parts
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top