How to multiply two polynomials represented by values at distinct points? I have two polynomials of degree $d$. However, I do not have equations for them. I simply have $d + 1$ distinct points on each polynomial. How would I find the product of these polynomials without deriving an equation for them/finding their coefficients? I would want the product of these polynomials to be represented through $2d+1$ distinct points.

Example:
  Let $A(x)$ represent the first polynomial, let $B(x)$ represent the second, and $C(x)$ be the product of these polynomials, where
  $$A(x) = A\left(x_0\right), A\left(x_1\right), \ldots ,A\left(x_d\right)\\
B\left(x\right) = B\left(x_0\right), B\left(x_1\right), \ldots,B\left(x_d\right)\\
C\left(x\right) = B\left(x\right) A\left(x\right)
$$

How would I find $C\left(x\right)$ without converting $A\left(x\right)$ and $B\left(x\right)$ into coefficient form? Why would this take $\mathcal{O}\left(n\right)$ time rather than $\mathcal{O}(n^2)$ time? (like multiplying in coefficient form does).
 A: You can not recover $C(x)$ from values at $d+1$ points.As in your previous question (couple of hours ago), you need $2d+1$ points to fully characterize a degree $2d$ polynomial.
Let $A(x)$ and $B(x)$ be degree $d$ polynomials. Assume we know the values of $A(x)$ and $B(x)$ at $2d+1$ distinct points:
$$\{ A(x_1), A(x_2), \ldots, A(x_{2d+1}) \},\\
\{ B(x_1), B(x_2), \ldots, B(x_{2d+1}) \}.$$
To find $C(x) = A(x) B(x),$ use the fact that $C(x_i) = A(x_i) B(x_i)$ for any $x_i,$ and compute the following pointwise product:
$$\{ A(x_1)B(x_1), A(x_2)B(x_2), \ldots, A(x_{2d+1})B(x_{2d+1}) \}.\tag{1} $$
You can easily interpolate $C(x)$ from $(1).$ Computing $(1)$ requires $\mathcal O(d)$ operations. Interpolating $C(x)$ from $(1)$ will cost more, e.g. $\mathcal O(d^2)$ naively, and something like $\mathcal O(d \log d)$ using fast polynomial arithmetic.
A: If you represent $A(x)$ as a vector $[a_0, a_1, \dots a_d]$ and $B(x)$ as $[b_0, b_1, \dots b_d]$.  Then to find $C(x) = A(x) * B(x)$ is equivalent to 
$$ A^{T} B = A B^{T} = \sum_{i=0}^d a_i b_i$$
