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