Now let us practice the polynomial multiplication by FFT. Suppose that you want

Question

Now let us practice the polynomial multiplication by FFT. Suppose that you want to multiply the two polynomials 1 + x + 2x 2 and 2 + 3x using the FFT. Choose an appropriate power of two. find the FFT of the two polynomials, and then multiply the results component wise. You only need to give the point evaluation form for the resulting polynomial (i.e you do not need to perform interpolation to obtain the coefficient representation).

Explanation / Answer

2 down vote accepted Just use your polynomial coefficients as input for fft: octave:16> poly1=[1 0 1 0] poly1 = 1 0 1 0 Note: this means x^2+1 octave:17> poly2=[1 1 0 0] poly2 = 1 1 0 0 octave:18> ifft( fft(poly1).*fft(poly2)) ans = 1 1 1 1 This is the result. Interpret as x^3+x^2+x+1, which is the product of the two polynomials. OR Given polynomial A(x) = 6x3 + 7x2 - 10x + 9 and B(x) = -2x3 + 4x - 5, their product C(x) can be calculated by the simple "school book" method as follows: 6x3 + 7x2 - 10x + 9 - 2x3 + 4x - 5 ------------------------------------- - 30x3 - 35x2 + 50x - 45 24x4 + 28x3 - 40x2 + 36x - 12x6 - 14x5 + 20x4 - 18x3 ------------------------------------------------------------------ - 12x6 - 14x5 + 44x4 - 20x3 - 75x2 + 86x - 45 In summation form, if A(x) and B(x) are of degree m, 2m j C(x) = Sum cj xj, where cj = Sum ak bj - k. j=0 k=0 Polynomial A(x), above, could be shown in a coefficient representation as the vector of coefficients (9, -10, 7, 6). [Note that coefficients are typically specified with the x0 coefficient first, then the coefficient of the x1 term, and so on in increasing order.] Alternatively, it could be specified in a point-value representation by evaluating it at m+1 distinct points. For example, if A(x) were evaluated at the points x = 0, 1, 3, -1, its point-value representation would be {(0, 9), (1, 12), (3, 204), (-1, 20)}. The inverse of evaluation is interpolation. That is, the coefficient representation of a polynomial can be derived from a point-value representation by interpolation. Any set of m+1 point-value pairs (xi, yi) such that all the xi values are distinct uniquely defines a polynomial. If two polynomials are specified in point-value representation using the same evaluation points, they can be multiplied by pointwise multiplication. However, because the product C(x) of two m-degree polynomials will be of degree 2m, we would need to extend the point-value representation of polynomials A(x) and B(x) to 2m+1 points in order to be able to interpolate C(x) from the pointwise multiplication of the 2m+1 points of A(x) and B(x). For example, if A(x) and B(x) above are each evaluated at the points x = -3, -2, -1, 0, 1, 2, and 3, their point-value representations would be A = {(-3, -60), (-2, 9), (-1, 20), (0, 9), (1, 12), (2, 65), (3, 204)} B = {(-3, 37), (-2, 3), (-1, -7), (0, -5), (1, -3), (2, -13), (3, -47)} Since the product C(x) can be found by pointwise multiplication of two polynomials in point-value representation, polynomial multiplication in this form is O(n), compared with the O(n2) cost of the "school book" multiplication of polynomials in coefficient representation. Convolution The convolution of two n-vectors U and V, denoted U * V, is an n-vector W with components n-1 wi = Sum uj vi - j, j=0 where 0

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.