Necessity of convolution operations for product of two polynomials via brute force method

Question

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

Answer 1

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.

Answer 2

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