2
$\begingroup$

Reference: Page 4 of this document

Given two polynomials $p(x)$ and $q(x)$ each of degree $n$ represented in coefficient form, it takes $\mathcal{\Theta}(n)$ time to evaluate given some input $x$.

In the reference linked, in order to get product of these two polynomials, $c(x) = p(x)q(x)$, via brute force, we have to compute new coefficients via convolution $\left(c_k = \sum_{i=0}^k a_i b_{k-i} \right)$ which takes $\mathcal{\Theta}(n^2)$ time.

However, if we wanted to evaluate this product with some given input $x$, we can evaluate the two polynomials $p(x)$ and $q(x)$ separately and then multiply the two scalar results. Overall, this would take $\mathcal{\Theta}(n)$ time for two evaluations and a scalar multiplication. This lets us avoid having to do convolutions and would be faster than $\mathcal{\Theta}(n^2)$.

Question: When it comes to evaluation of the product of two polynomials, is it actually $\mathcal{\Theta}(n)$ using the method above or are we somehow still doomed to $\mathcal{\Theta}(n^2)$?

I'm aware there's a faster way to do this in $\mathcal{O}(n \log n)$ time via Fast Fourier Transform, but I'm more curious about the necessity of the convolution calculations. I suspect it's more if we care about getting the coefficients of the product than the actual evaluation, as in we more care about knowing $\{c_0, c_1, c_2, \dotsc\}$ than $c(x) = p(x)q(x)$.

$\endgroup$
  • 2
    $\begingroup$ I'm not entirely sure what you are asking. If you're asking how to get the coefficients of the product polynomial $p(x) q(x)$, you already know how to do it -- use the FFT; it takes $O(n \log n)$ time. What more is there to say? What is your question? $\endgroup$ – D.W. Feb 3 '18 at 6:16
  • $\begingroup$ I wasn't asking what the typical/fast method was to find the coefficients of a product of two polynomials. I was asking whether the evaluation/calculation of the product of two polynomials $c(x) = p(x)q(x)$ given an input $x$ is $\mathcal{\Theta}(n)$ instead of $\mathcal{\Theta}(n^2)$ from directly computing the coefficients of $c(x)$ followed by its evaluation. $\endgroup$ – user83865 Feb 3 '18 at 17:22
3
$\begingroup$

Given two polynomials $P_n(x)$, $Q_n(x)$, you can obviously calculate the value $P_n(x) · Q_n(x)$ in $O(n)$ for every x. The document asks about calculating the coefficients, which is a very different question. If all you want is to evaluate $P_n(x) · Q_n(x)$ for various values of x, then calculating the coefficients of the product polynomial isn't actually useful on current processors (due to latency, you can usually calculate two polynomials of degree n in parallel in practically the same time as one, and almost twice as fast as one polynomial of degree 2n). However, there are situations where the coefficients are exactly what you want.

As the document says, the coefficients can be calculated using FFT in $O (n log n)$. A straightforward divide-and-conquer method doesn't improve on the trivial $O(n^2)$. The document mentions a more clever divide-and-conquer method that multiplies polynomials of degree $2^k$ in $O (3^k)$. Knuth's "Art of Computer Programming" has an improvement on this which multiplies polynomials of degree $m^k$ in $O ((2m-1)^k)$, for every fixed m, but with constant factors growing quite quickly.

$\endgroup$
  • $\begingroup$ Thanks. I selected your answer since it answered two points: that the product of two polynomials can be evaluated in $\mathcal{O}(n)$ and that calculating the coefficients of that that product is a different problem from calculating/evaluating that product given some input $x$. $\endgroup$ – user83865 Feb 3 '18 at 17:14
  • $\begingroup$ @instantwipe2000, precision of language is important in maths. The "product of two polynomials" is a polynomial: to evaluate the product of two polynomials is to explicitly find that polynomial - although what that means is a matter of representation. I think the failure to distinguish clearly between evaluating the product of two polynomials vs evaluating their product at a point is why D.W. wasn't sure what you were asking. I wasn't entirely sure either, but my aim was to give you the understanding to answer your question yourself. Perhaps I should have made that clearer. $\endgroup$ – Peter Taylor Feb 3 '18 at 22:26
  • $\begingroup$ (And for the avoidance of doubt, I'm not complaining about you selecting this as the accepted answer: you should select the one which helps you more. Rather I'm hoping to promote clear communication of mathematics). $\endgroup$ – Peter Taylor Feb 3 '18 at 22:30
3
$\begingroup$

In the reference linked, in order to get product of these two polynomials, $c(x) = p(x)q(x)$, via brute force, we have to compute new coefficients via convolution $\left(c_k = \sum_{i=0}^k a_i b_{k-i} \right)$ which takes $\mathcal{\Theta}(n^2)$ time.

That's not what it says. It says firstly that convolution is equivalent to polynomial multiplication (i.e. an algorithm for convolution is also an algorithm for polynomial multiplication and vice versa); and secondly that

The direct approach is to compute all $c_k$ using the formula above

and that this approach has complexity $\Theta(n^2)$. The FFT approach calculates a convolution (and indeed, the continuous Fourier transform produces a convolution of two functions: the convolution of two coefficient sequences is a discrete analogue).

$\endgroup$

Your Answer

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