Computing sum of sparse polynomials squared in O(n log n) time?

Question

Suppose we have polynomials $p_1,...,p_m$ of degree at most $n$, $n>m$, such that the total number of nonzero coefficients is $n$ (i.e., the polynomials are sparse). I am interested in an efficient algorithm for computing the polynomial:

$$\sum_i p_i(x)^2$$

Since this polynomial has degree at most $2n$, both input and output size is $O(n)$. In the case $m=1$ we can compute the result using FFT in time $O(n \log n)$. Can this be done for any $m<n$? If it makes any difference, I'm interested in the special case where coefficients are 0 and 1, and the computation should be done over the integers.

Update. I realized that a fast solution for the above would imply advances in fast matrix multiplication. In particular, if $p_k(x)=\sum_{i=1}^n a_{ik} x^i + \sum_{j=1}^n b_{kj} x^{nj}$ then we can read off $a_{ik} b_{kj}$ as the coefficient of $x^{i+nj}$ in $p_k(x)^2$. Thus, computing $p_k(x)^2$ corresponds to computing an outer product of two vectors, and computing the sum $\sum_k p_k(x)^2$ corresponds to computing a matrix product. If there is a solution using time $f(n,m)$ to computing $\sum_k p_k(x)^2$ then we can multiply two $n$-by-$n$ matrices in time $f(n^2,n)$, which means that $f(n,m)=O(n\log n)$ for $m\leq n$ would require a major breakthrough. But $f(n,m)=n^{\omega/2}$, where $\omega$ is the current exponent of matrix multiplication, might be possible. Ideas, anyone?

Answer 1

Squaring a polynomial with $x_i$ nonzero coefficients takes time $O(x_i^2)$ using ordinary term-by-term multiplication, so this should be preferred to the FFT for those polynomials where $x_i < \sqrt{n \log n}$. If $\sum_i x_i = n$, then the number of polynomials with $x_i$ greater than $\sqrt{n \log n}$ is $O(\sqrt{n / \log n})$, and these will take time $O(n^{3/2}({\log n})^{1/2})$ to square and combine (as will the remaining polynomials). This is an improvement over the obvious $O(m n \log n)$ bound when $m$ is $\Theta(\sqrt{n / \log n})$.

Answer 2

Not a full answer but maybe helpful.

Caveat: It only works well if the supports of the $p_i^2$ are small.

For a polynomial $q = a_0 + a_1x + \dots +a_nx^n$, let $S_q = \{i \mid a_i \not= 0\}$ be its support and $s_q = |S_q|$ be the size of the support. Most of the $p_i$ will be sparse, i.e, will have a small support.

There are algorithms to multiply sparse polynomials $a$ and $b$ in quasi-linear time in the size of the support of the product $a b$, see e.g. http://arxiv.org/abs/0901.4323

The support of $ab$ is (contained in) $S_a + S_b$, where the sum of two sets $S$ and $T$ is defined as $S + T := \{s + t \mid s \in S, t \in T\}$. If the supports of all products are small, say, linear in $n$ in total, then one can just compute the products and add up all monomials.

It is however very easy to find polynomials $a$ and $b$ such that the size of the support of $ab$ is quadratic in the sizes of the support of $a$ and $b$. In this particular application, we are squaring polynomials. So the question is how much larger $S + S$ compared to $S$. The usual measure for this is the doubling number $|S + S|/|S|$. There are sets with unbounded doubling number. But if you can exclude sets with large doubling number as supports of the $p_i$, then you can get a fast algorithm for your problem.

Answer 3

Just wanted to note the natural approximation algorithm. This doesn't take advantage of sparsity though.

You could use a random sequence $(\sigma_i)_{i\in[n]}$ Taking $X=\sum_i \sigma_i p_i(x)$ we can compute $X^2$ in $n\log n$ time using FFT. Then $EX^2 = \sum_i p_i(x)^2 = S$ and $\sqrt{VX^2} = O(S)$. So you can get a $1+\varepsilon$ approximation in time $O(\varepsilon^{-2} n \log n )$.