polynomial multiplication using fastfourier transform

Question

I am going through the above topic from CLRS(CORMEN) (page 834) and I got stuck at this point.

Can anybody please explain how the following expression,

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

follows from,

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

Where,

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

The polynomial A(x) is defined as

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

To start the divide-and-conquer strategy of polynomial multiplication by the FFT, CLRS introduces two new polynomials: one of the coefficients of the even-powers of x called A[0] and one of the coefficients of the odd-powers of x called 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 + ...

Now if we substitute x^2 into A[0] and A[1], we have

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 + ...

and if we multiply A[1](x^2) by x, we have

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

Now if we add A[0](x^2) and x A[1](x^2), we have

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)

Q.E.D.

Answer 2

If you divvy the polynomial up into "odd exponents" and "even exponents", you'll find the annoying fact that the A[1] polynomial (the one with odd exponents) has, well odd exponents! Even exponents are easier to work with, for FFT. So, one can simply factor out a single "x" from all of the values in A[1], and move it outside of the expression.

FFT likes working with even-exponented polynomials only. Thus, when you're dividing-and-conquering, you want to turn your A[1] expression into an "even-exponented" polynomial, and recurse on that, and then multiply-back-in that x. You will see that occur in the inner loop of the actual algorithm.

Edit: I realize that your confusion may stem from the fact that they're "passing in" (x^2) as the value in the polynomial. The "x" in A[1] and A[0] are different from the x in the (x^2) expression. You'll see how that must be, as while the original polynomial A goes up to exponent N, A[1] and A[0] both only go up to exponent (N/2).

Answer 3

I'm not going to answer your question because I feel that previous people have answered it. What I will do is try to explain the purpose of the FFT.

First, the FFT is a way to compute the convolution between two vectors. That is, suppose x = and y= are 1xn vectors then the convolution of x and y is

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

You will have to accept the fact that computing that value is EXTREMELY useful in a wide range of applications.

Now consider the following.

Suppose we construct two polynomials

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

then the multiplication is

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

where the inside sum is clearly a convolution of different size for different values of k.

Now we can clearly compute the coefficients (convolutions) of AB in n^2 time by a brute force method.

However, we can also be much more clever. Consider the fact that any polynomial of degree n can be described uniquely by n+1 points. That is given n+1 points we can construct the unique polynomial of degree n that goes through all n+1 points. Further more consider 2 polynomials in the form of n+1 points. You can compute their product by simply multiplying the n+1 y-values and keeping the x-values to result in their product in point-form. Now given a polynomial in n+1 point-form you can find the unique polynomial that describes it in O(n) time (actually Im not sure about this, it may be O(nlogn) time but certainly not more.)

This is exactly what the FFT does. However, the points that it picks to get the n+1 points to described the polynomials A and B are VERY carefully chosen. Some of the points are indeed complex because it just so happens that you can save time in evaluating a Polynomial by considering such points. That is if you were to choose just real points instead of the carefully chosen points that the FFT uses you would need O(n^2) time to evaluate the n+1 points. If you choose the FFT you only need O(nlogn) time. And thats all there is to the FFT. Oh and there is a unique side effect to the way that the FFT chooses points. Given an n-th degree polynomial, you must choose 2^m points where m is chosen such that 2^m is the smallest power of 2 greater than or equal to n.

Answer 4

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