# efficiently computing a sum of products of polynomials

Let $$F$$ be a prime finite field. Let $$d$$ be a power of two dividing $$p-1$$. Suppose I have $$d$$ pairs of univariate polynomials $$f_i,g_i$$ over $$F$$ for $$i=1,\ldots,d$$. All have degree less than $$d$$. I want to compute the coefficients of the polynomial

$$h(X)\triangleq \sum_{i=1}^d f_i(X) g_i(X)$$

I can do this in $$O(d^2\cdot \log d)$$ operations by computing each product using FFT techniques in time $$O(d\log d)$$ and then summing the $$d$$ products.

Can I do this in time $$O(d^2)$$ somehow? Is there an indication that would contradict some conjectured lower bound?

I don't mind computing $$h$$ in any basis, doesn't have to be the monomial basis.

• A very brief remark: Restating your problem as the inner product of two vectors of polynomials, it is clear that a $O(d^2)$ algorithm implies a $O(d^3)$ algorithm for matrix-vector product with polynomial matrices. I cannot find a reference where it is explicitly written, but all the complexity results I know of for polynomial matrices use FFT-based techniques, and thus have the $\log d$ factor in the complexity. Cf for instance this recent paper for references. Of course, I do not claim any lower bound though... Feb 5, 2021 at 18:06