# Multiplying n polynomials of degree 1

The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time.

You can do $O(n \log^2 n)$ time by applying FFT in a tree fashion. Can you do $O(n \log n)$?

• Nice question, seems like I've seen something similar in someone's blog, but I can't remember where it was. Aug 27 '10 at 19:51
• Minor observation: we know (working over Q, say) the n roots $\alpha_i = -b_i/a_i$, so the problem is equivalent to: Given $\alpha_1, \dots , \alpha_n$, compute the polynomial $(x-\alpha_1)\dots(x-\alpha_n)$. (I guess.) Aug 28 '10 at 2:43
• Can you give a reference to the $O(n\log^2 n)$ result? Sep 10 '10 at 2:14
• As @Suresh mentioned, it is a simple divide-and-conquer approach. It can be generalized so that n polys may have different degrees $d_i$, in which case you can divide in a Huffman tree fashion. See Strassen: The computational complexity of continued fractions.
– Zeyu
Sep 10 '10 at 4:47
• Can we compute the convolution of $n$ vectors of constant dimension 2 in time $O(n \log n)$? Sep 10 '10 at 14:14

Warning: This is not yet a complete answer. If plausibility arguments make you uncomfortable, stop reading.

I will consider a variant where we want to multiply $$(x - a_1) \cdot ... \cdot (x - a_n)$$ over the complex numbers.

The problem is dual to evaluating a polynomial at n points. We know this can be done cleverly in $$O(n \log n)$$ time when the points happen to be $$n$$-th roots of unity. This takes essential advantage of the symmetries of regular polygons that underlie the Fast Fourier Transform. That transform comes in two forms, conventionally called decimation-in-time and decimation-in-frequency. In radix two they rely on a dual pair of symmetries of even-sided regular polygons: the interlocking symmetry (a regular hexagon consists of two interlocking equilateral triangles) and the fan unfolding symmetry (cut a regular hexagon in half and unfold the pieces like fans into equilateral triangles).

From this perspective, it seems highly implausible that an $$O(n \log n)$$ algorithm would exist for an arbitrary set of $$n$$ points without special symmetries. It would imply that there is nothing algorithmically exceptional about regular polygons as compared to random sets of points in the complex plane.

• On the other hand, an $\Omega(n\log^2 n)$ lower bound for such a natural problem seems equally implausible! Sep 27 '10 at 6:46
• True! I wish I had a more definitive answer. It's very interesting. Sep 27 '10 at 6:51
• Bounty awarded! Sep 28 '10 at 1:36
• @PerVognsen: Can you give a reference for this point of view re: symmetries of polygons / interlocking symmetry? Or if this is an observation of your own, could you expand on it a bit more? Feb 21 '12 at 4:58

In computer algebra, this computation is usually referred as computing the subproduct tree and is a subroutine of multipoint evaluation and interpolation. See for instance: von zur Gathen, Gerhard. Modern Computer Algebra, 3rd edition, 2013 [chapter 10]. As far as I know, the best known complexity is $$O(\mathsf{M}(n)\log n)$$ where $$\mathsf M(n)$$ denotes the cost of multiplying two degree-$$n$$ polynomials. (This applies over any ring.)

• Is there a matching lower bound or is the lower bound $\Omega(\mathsf{M}(n))$?
– Mr.
Oct 18 at 7:11
• For the original problem, I do not think so. For the subproduct tree used in multipoint evaluation, the output size is $O(n\log n)$ so this gives a lower bound independent from $\mathsf{M}(n)$ (though not larger). Oct 18 at 8:16
• Believe me when I say that Mihai knew this... but it is good to name the problem, and give references. Oct 19 at 23:50
• I had not made the connection between the first name and the author of the question... Oct 20 at 16:04