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

Question

Я просматриваю вышеприведенную тему от CLRS (CORMEN) (page 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}} 

Answer 1

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

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

Чтобы начать стратегию разделяй и властвуй полиномиального умножения на FFT, 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) 

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

Answer 2

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

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

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

Answer 3

 
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 

Answer 4

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

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

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

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

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

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

А (г) = х0 + х1 * х2 + г * г^2 + .. + х^г^п В (г) = у0 + y1 * г + у2 * г^2 + .. + уп^г^п

то умножение

АВ (г) = А (г) в (г) = \ sum_ {г = 0}^п (\ sum_ {k = 0}^i xk * y {ik}) 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) времени (фактически Im не уверен в этом, это может быть O (nlogn) время, но, конечно, не больше.)

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