( b ) ( 10 points) Let be a primitive nth root of unity. The fast Fourier trans-

Question

( b ) ( 10 points) Let be a primitive nth root of unity. The fast Fourier trans- form implements the multiplication with the matrix ij F=(u")i,j inlo.n-11- I need answer for c, d, e. Pleaseanswer for those questions cause this is connecting questions. Thanks in advance Show that the inverse of the F is given by n. [Hint: rn_ 1 = (z-1)on-l + . . . +z +1), so any power at #1 must be a root of r+++1. ] Thus, the inverse FFT, called IFFT, is nothing but the FFT using w1 instead of w, and multiplying the result with 1/rn (c) (10 points) Describe how to do a polynomial multiplication tusing the FFT (d) (15 points) How can you modify the polynomial multiplication algorithm (e) (5 points) What kind of problems can occur in the previous approach to and IFFT for polynomials A(z) and B(a) of degree S n-1. Make sure that you describe the length of the FFT and IFFT needed for this task. based on FFT and IFFT to do multiplication of long integers in base 10? Make sure that you take care of carries in a proper way multiply long integers and how would you overcome them? Hint: How does the idealized FFT algorithm differ from a version implemented on a computer?]

Explanation / Answer

(c)

The process for polynomial multiplication using the fast Fourier transformation (FFT) is follows.

Let A(x) and B(x) be the polynomials of degree <=n-1

First add n-1 higher-order zero coefficients to A(x) and B(x)

Then evaluate A(x) and B(x) using FFT 2n-2 points

Then point wise multiplication of point-value forms

Finally Interpolatec(x), the product ofA(x) and B(x), using FFT to compute inverse DFT.

The time consumed to find the product of polynomials of degree bound n-1using FFT and IFFT is big theta((n-1)log(n-1)) with both the input and output in coefficient form

The length of the process can measure from time consumption of the process.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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