polynomial multiplication using FFT

**Evan.Kimia** · December 14th 2011, 10:12 PM

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

. Posted the original question and the solution below.

polynomial multiplication using FFT-screen-shot-2011-12-15-2.04.08-am.png

**chisigma** · December 15th 2011, 06:47 AM

The two polynomial can be written as $P_1(z)= \sum_{k=0}^{n_{1}} a_{k}\ z^{-k}$ and $P_2(z)= \sum_{k=0}^{n_{2}} b_{k}\ z^{-k}$ . The product of $P_{1}(z)$ and $P_{2}(z)$ using FFT can be performed in the following steps...

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

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

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

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

Marry Christmas from Serbia

$\chi$ $\sigma$

Thread: polynomial multiplication using FFT

LinkBack

Thread Tools

Display

polynomial multiplication using FFT

Re: polynomial multiplication using FFT

Similar Math Help Forum Discussions

Need a walkthrough Polynomial Multiplication

Pesky Polynomial Multiplication Problem

Simple Polynomial Multiplication problem

Polynomial (evaluation - multiplication - interpolation)

Polynomial multiplication: which of these two answers are correct?

Search Tags