1 Attachment(s)

polynomial multiplication using FFT

I apologize if this is in the wrong section, wasnt positive.

Im reviewing a problem to prepare myself for an exam and im having a hard time figuring out how my professor puts A(x) in the form (1+2x^2)+x(1+0+x^2) and how he calculates the roots. If anyone could give me some pointers on what methods he did I would be extremely grateful (Nod). Posted the original question and the solution below.

Attachment 23081

Re: polynomial multiplication using FFT

The two polynomial can be written as and . The product of and using FFT can be performed in the following steps...

a) if , then trasform by inserting zeroes and into polynomial of degree 2n-1...

b) perform the FFT of and calling the FFT of and the FFT of ...

c) compute the product ...

d) perform the inverse FFT of obtaining the product ...

http://www.sv-luka.org/ikone/ikone180a.jpg

Marry Christmas from Serbia