4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – user2468
    May 12, 2012 at 18:12
  • $\begingroup$ You treat them like vector implementation (not matrices). You would have for polynomials of degree $n$, $n$ multiplications and $n-1$ addition for product. $\endgroup$
    – Kirthi Raman
    May 12, 2012 at 18:25

2 Answers 2

Reset to default
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ How do you get the extra $d + 1$ points if each polynomial is represented with just $d$ points? Wouldn't that require to make $\Theta (n)$ evaluations of the polynomials, each taking $\Theta (n)$ time, making the entire procedure take $\Theta (n^2)$ time? $\endgroup$
    – Kelmikra
    Jul 18, 2015 at 22:22
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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)$? $\endgroup$
    – user856
    May 12, 2012 at 21:51
  • $\begingroup$ 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) $\endgroup$
    – Kirthi Raman
    May 13, 2012 at 0:36
  • $\begingroup$ Don't you need $2d + 1$ points to find $C$, as explained in user2468's answer? $\endgroup$
    – Kelmikra
    Jul 18, 2015 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy