<p>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 &lt; \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})$.</p>

CC BY-SA 2.5
2011-02-21T19:38:06.373Z
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.
Rasmus Pagh
CC BY-SA 2.5
2011-02-21T17:42:51.807Z
2011-02-21T17:42:51.807Z
mjqxxxx
<p>Just wanted to note the natural approximation algorithm. This doesn't take advantage of sparsity though.</p>

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

CC BY-SA 4.0
2019-06-30T22:37:08.130Z
Nice approach! But don't you need more repetitions to get all coefficients right with high probability?
Rasmus Pagh
CC BY-SA 4.0
2019-07-01T12:07:08.547Z
@RasmusPagh Right, you'll probably get a $\log(n/\delta)$ term if you want all coefficients to be preserved with probability $1-\delta$.
Thomas Ahle
CC BY-SA 4.0
2019-06-16T10:22:18.733Z
2019-06-16T10:22:18.733Z
Thomas Ahle
<p>Not a full answer but maybe helpful.</p>

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

<p>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.</p>

<p>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. <a href="http://arxiv.org/abs/0901.4323" rel="nofollow">http://arxiv.org/abs/0901.4323</a></p>

<p>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. </p>

<p>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.   </p>

CC BY-SA 3.0
2011-04-27T13:15:18.140Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-27T14:23:16.237Z
@Tsuyoshi: You are right, I will edit my answer. Nevertheless, there are GAPs with large doubling constant.
5501
CC BY-SA 3.0
2011-04-27T14:59:57.170Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-27T15:07:00.053Z
Of course it only works if the application in mind (which I do not know) gives nice supports.
5501
CC BY-SA 3.0
2011-04-27T20:31:47.803Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-04-28T12:52:03.730Z
Good point, I will edit my answer
5501
CC BY-SA 3.0
2011-05-25T22:09:40.720Z
Thanks for the answer. I did not know about the algorithm of van der Hoeven and Lecerf. Unfortunately, each term in my application is likely to be dense, so it does not help for this.
Rasmus Pagh
CC BY-SA 3.0
2011-04-27T11:41:14.957Z
2011-04-28T12:57:16.187Z
2011-04-28T12:57:16.187Z
5501
<p>Suppose we have polynomials $p_1,...,p_m$ of degree at most $n$, $n&gt;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:</p>

<p>$$\sum_i p_i(x)^2$$</p>

<p>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&lt;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.</p>

<p><strong>Update.</strong> 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?</p>

CC BY-SA 2.5
2011-02-21T04:51:40.167Z
Hi Rasmus. I think you intended for this to go on the main site. This is the meta site, for questions about the site.
Suresh Venkat
<ds.algorithms><algebra><polynomials>
Computing sum of sparse polynomials squared in O(n log n) time?
Rasmus Pagh
# Computing sum of sparse polynomials squared in O(n log n) time?

(Asked by: username_0 on 2011-02-21)

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

**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?

**Tags:** ds.algorithms, algebra, polynomials

> **Comments:**
> **username_1**: Hi Rasmus. I think you intended for this to go on the main site. This is the meta site, for questions about the site.  

---

## 3 answers

### Answer by username_2 on 2011-02-21. Score: 3

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

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_3 on 2019-06-16. Score: 2

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

> **Comments:**
> **username_0**: Nice approach! But don't you need more repetitions to get all coefficients right with high probability?  
> **username_3**: @RasmusPagh Right, you'll probably get a $\log(n/\delta)$ term if you want all coefficients to be preserved with probability $1-\delta$.  

---

### Answer by username_4 on 2011-04-27. Score: 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.

> **Comments:**
> **username_5**: 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.  
> **username_4**: @Tsuyoshi: You are right, I will edit my answer. Nevertheless, there are GAPs with large doubling constant.  
> **username_5**: 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.  
> **username_4**: Of course it only works if the application in mind (which I do not know) gives nice supports.  
> **username_5**: 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.  
> **username_4**: Good point, I will edit my answer  
> **username_0**: Thanks for the answer. I did not know about the algorithm of van der Hoeven and Lecerf. Unfortunately, each term in my application is likely to be dense, so it does not help for this.  

---

