18
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Hi Rasmus. I think you intended for this to go on the main site. This is the meta site, for questions about the site. $\endgroup$ – Suresh Venkat Feb 21 '11 at 4:51
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What I'm interested in is a method that computes the sum without computing each term. Doing FFT or term-by-term multiplication for each product will be too slow for the application I have in mind. $\endgroup$ – Rasmus Pagh Feb 21 '11 at 19:38
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Although I am not familiar with additive combinatorics, I think that generalized arithmetic progressions and the Freiman-Ruzsa theorem are about sets with small doubling. $\endgroup$ – Tsuyoshi Ito Apr 27 '11 at 13:15
  • $\begingroup$ @Tsuyoshi: You are right, I will edit my answer. Nevertheless, there are GAPs with large doubling constant. $\endgroup$ – 5501 Apr 27 '11 at 14:23
  • $\begingroup$ Personally I do not think that this approach is promising. A (pretty inaccurate) implication of the Freiman-Ruzsa theorem is that |S+S|/|S| is small only in special cases, and therefore the part “If you can exclude sets with larger doubling number as supports of the p_i” is a very big if. However, as I said, I am not familiar with additive combinatorics, and you should take my words on it with a grain of salt. $\endgroup$ – Tsuyoshi Ito Apr 27 '11 at 14:59
  • $\begingroup$ Of course it only works if the application in mind (which I do not know) gives nice supports. $\endgroup$ – 5501 Apr 27 '11 at 15:07
  • $\begingroup$ Then it would be easier to understand if you make that assumption more explicit in your answer. The current way of writing the assumption in the answer suggests that you consider that the assumption of small doubling number is not a big deal. $\endgroup$ – Tsuyoshi Ito Apr 27 '11 at 20:31
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice approach! But don't you need more repetitions to get all coefficients right with high probability? $\endgroup$ – Rasmus Pagh Jun 30 at 22:37
  • $\begingroup$ @RasmusPagh Right, you'll probably get a $\log(n/\delta)$ term if you want all coefficients to be preserved with probability $1-\delta$. $\endgroup$ – Thomas Ahle Jul 1 at 12:07

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.