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

-
If degree of $A(x), B(x)$ is $d,$ then degree of $C(x)$ is at most $2d.$ You have to represent $C(x)$ using $2d+1$ points. –  user2468 May 12 '12 at 18:12
You treat them like vector implementation (not matrices). You would have for polynomials of degree $n$, $n$ multiplications and $n-1$ addition for product. –  Kirthi Raman May 12 '12 at 18:25

2 Answers

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

-
I don't understand this answer at all. Aren't $A^TB$ and $AB^T$ a matrix and a scalar respectively? How does this help you find $C(x)$? –  Rahul May 12 '12 at 21:51
Computationally if you store them as a vector, that is equivalent to what J.D. has answered. (If one has written a program in any language one would know) –  Kirthi Raman May 13 '12 at 0:36

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.

-