Results 1 to 2 of 2

Thread: polynomial multiplication using FFT

  1. #1
    Member
    Joined
    Sep 2009
    Posts
    149

    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 . Posted the original question and the solution below.

    polynomial multiplication using FFT-screen-shot-2011-12-15-2.04.08-am.png
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6

    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)$...



    Marry Christmas from Serbia

    $\displaystyle \chi$ $\displaystyle \sigma$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Need a walkthrough Polynomial Multiplication
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 11th 2010, 03:57 AM
  2. Pesky Polynomial Multiplication Problem
    Posted in the Algebra Forum
    Replies: 5
    Last Post: Jul 13th 2010, 01:24 PM
  3. Simple Polynomial Multiplication problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Apr 21st 2009, 04:09 PM
  4. Replies: 2
    Last Post: Feb 8th 2009, 08:19 AM
  5. Replies: 1
    Last Post: Jul 10th 2008, 07:48 PM

Search Tags


/mathhelpforum @mathhelpforum