# polynomial multiplication using FFT

• Dec 14th 2011, 10:12 PM
Evan.Kimia
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
• Dec 15th 2011, 06:47 AM
chisigma
Re: polynomial multiplication using FFT
The two polynomial can be written as $\displaystyle P_1(z)= \sum_{k=0}^{n_{1}} a_{k}\ z^{-k}$ and $\displaystyle P_2(z)= \sum_{k=0}^{n_{2}} b_{k}\ z^{-k}$. The product of $\displaystyle P_{1}(z)$ and $\displaystyle P_{2}(z)$ using FFT can be performed in the following steps...

a) if $\displaystyle n=\text{max} [n_{1},n_{2}]$, then trasform by inserting zeroes $\displaystyle P_{1}(z)$ and $\displaystyle P_{2}(z)$ into polynomial of degree 2n-1...

b) perform the FFT of $\displaystyle P_{1}(z)$ and $\displaystyle P_{2}(z)$ calling $\displaystyle \Pi_{1} (\omega)$ the FFT of $\displaystyle P_{1}(z)$ and $\displaystyle \Pi_{1} (\omega)$ the FFT of $\displaystyle P_{2}(z)$ ...

c) compute the product $\displaystyle \Pi (\omega)= \Pi_{1} (\omega)\ \Pi_{2} (\omega)$...

d) perform the inverse FFT of $\displaystyle \Pi (\omega)$ obtaining the product $\displaystyle P(z)=P_{1}(z)\ P_{2}(z)$...

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

Marry Christmas from Serbia

$\displaystyle \chi$ $\displaystyle \sigma$