Given two polynomials which have the following:

P(1) = 2x³ + 3x -5 and P(2) = 2 x³ 3 x² + 1

Use Fast Fourier Transform (FFT) approach to finding the solution of their product

P(1) * P(2), by computing DFT_n (a) in time ?(n log n). The approach uses divide-and-conquer strategy, using the even-indexed and odd-indexed coefficients of A(x) separately to define the two new polynomials A^[0] (x) and A^[1] (x) of degree-bound n/2. The problem of evaluating A(x) at (i.e., A( ) , k = 0, 1, 2, , n-1 ) reduces to evaluating the degree-bound n/2 polynomials A^[0] (x) and A^[1] (x) at the points , and then combining the results to form A(x) = A^[0] (x²) + x * A^[1] (x²) .

a.What are the coefficient vectors for P(1) and P(2)?

b. Choose a complex roots of unit as the evaluation points.

c.Compute their (namely P(1) and P(2) point-value representations by taking the

discrete Fourier transform (DFT) of their corresponding coefficient vector.

d.Compute P(1) * P(2) using pointwise multiplication.

e. Then, convert from point-value representation back to coefficient representation,

using interpolation at the complex roots of unity.

Finally, we achieve the Convolution of P(1) and P(2) in the order of O(n log₂ n): For any two vectors a and b of length n, where n is a power of 2,

a ? b = ?DFT?_2n^(-1) (?DFT?_2n (a)*?DFT?_2n (b))

where the vectors a and b are padded with 0s to length 2n and * denotes the component-wise product of two 2n-element vectors.