# Multiplication of polynomials in their point value form

I've never really understood how point-value multiplication of polynomials work, so I was wondering if somebody could talk me through it with an example.

Say if I was given the following two polynomials $A(x)$ and $B(x)$ in their point value representations: $((1,4), (i,0), (-1,0), (-i,0))$ and $((1,6),(i,0),(-2,0),(-i,0))$ respectively. How would I go about computing $C(x) = A(x) \cdot B(x)$?

I know that I have to multiply the values of $A$ and $B$ at each point, but that would only give 4 points which would not be enough to deduce the coefficient form of $C(x)$. I've read in some books that I would have to extend the point-value representation of $A(x)$ and $B(x)$ but I don't know how I would do this.

(I'm not sure if this will make much difference to the suggestions/explanations, but I need to know about this in the context of the Fast Fourier Transform and using it to multiply polynomials in $\Theta (n \cdot log(n))$ time)

• well, first thing in order to do the multiplication A and B you need to know the degree bound of A and B.
– dave
Jun 13, 2016 at 20:40

Suppose you have

A(x)=1+x

B(x)=1-x

degree of C(x) is 2

so I choose A=(1,1,0,0) B=(1,-1,0,0)

the point value representations are

A=( (i,1+i),(-1,0),(-i,1-i),(1,2) )

B=( (i,1-i),(-1,2),(-i,1+i),(1,0) )

Then

C=( (i,2),(-1,0),(-i,2),(1,0)} )

so now you can do the inverse of the Fast Fourier Transform and obtain

1-x^2=(1,0,-1,0)