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

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

0 голосов
/ 11 августа 2009

Я прохожу вышеупомянутую тему от 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}}

Ответы [ 4 ]

4 голосов
/ 11 августа 2009

Полином 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)

1028 * что и требовалось доказать *

3 голосов
/ 11 августа 2009

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

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

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

1 голос
/ 15 августа 2009

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

Во-первых, БПФ - это способ вычисления свертки между двумя векторами. То есть предположим, что 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 + .. + yn ^ z ^ n

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

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). И это все, что есть в БПФ. О, и есть уникальный побочный эффект от способа, которым FFT выбирает точки. Для заданного полинома n-й степени вы должны выбрать 2 ^ m точек, где m выбрано так, что 2 ^ m является наименьшей степенью 2, большей или равной n.

0 голосов
/ 11 августа 2009 
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
...