Let’s say we have two vectors of polynomials $p = [p_1(x), p_2(x),…,p_n(x)]$ and $q= [q_1(x), q_2(x),…,q_n(x)]$ where elements $p_i(x)$ and $q_i(x)$ are polynomials of degree $n$ , each. Also, let’s say the polynomials $p_i(x)$ and $q_i(x)$ are given to me in the evaluation domain, i.e., $p_i(x)$ is given as $[p_i(0), p_i(1),p_i(2),\ldots,p_i(n)]$. I want to note that, we are given only $n+1$ points on each of the input polynomials.

I want to compute the inner-product of the vectors $p$ and $q$, i.e., compute the polynomial $r(x) = \sum^n_{i=1} p_i(x)\cdot q_i(x)$.

My question is, what is the time complexity of computing the polynomial $r(x)?$ A naive way is to first compute $p_i(x).q_i(x)$ for every $i$. This will cost me $O(n\log n)$ using number theoretic transform (NTT) for each $i$. Hence the total time will be $O(n^2 \log n)$. I wonder if the inner product can be computed in time $O(n^2)$?

I am fine with either representation of $r(x)$, i.e., either $r(0), r(1),r(2),\ldots,r(2n)$ or the coefficients of $r(x)$.


1 Answer 1


Probably not. Winograd proved in his paper: On the algebraic complexity of inner product that the computation of the inner product in a ring takes $\Omega(n)$ ring multiplications. Our ring in this case is $R[x]$, for some other ring $R$.

Currently, the best known algorithm to compute the product of 2 polynomials of degree $n$ in $R[x]$ uses $\mathcal{O}(n \log(n))$ ring operations in $R$.

Hence, $\mathcal{O}(n^2 \log(n))$ is the best we can do at the moment, it can only be improved if a faster polynomial multiplication algorithm is found.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .