38
$\begingroup$

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

$\endgroup$
13
  • $\begingroup$ Nice question, seems like I've seen something similar in someone's blog, but I can't remember where it was. $\endgroup$ Aug 27 '10 at 19:51
  • 3
    $\begingroup$ 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.) $\endgroup$ Aug 28 '10 at 2:43
  • 1
    $\begingroup$ Can you give a reference to the $O(n\log^2 n)$ result? $\endgroup$ Sep 10 '10 at 2:14
  • 2
    $\begingroup$ 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. $\endgroup$
    – Zeyu
    Sep 10 '10 at 4:47
  • 1
    $\begingroup$ Can we compute the convolution of $n$ vectors of constant dimension 2 in time $O(n \log n)$? $\endgroup$
    – Kaveh
    Sep 10 '10 at 14:14
7
+50
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ On the other hand, an $\Omega(n\log^2 n)$ lower bound for such a natural problem seems equally implausible! $\endgroup$
    – Jeffε
    Sep 27 '10 at 6:46
  • $\begingroup$ True! I wish I had a more definitive answer. It's very interesting. $\endgroup$ Sep 27 '10 at 6:51
  • $\begingroup$ Bounty awarded! $\endgroup$
    – Jeffε
    Sep 28 '10 at 1:36
  • $\begingroup$ @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? $\endgroup$ Feb 21 '12 at 4:58
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Is there a matching lower bound or is the lower bound $\Omega(\mathsf{M}(n))$? $\endgroup$
    – Mr.
    Oct 18 at 7:11
  • $\begingroup$ 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). $\endgroup$
    – Bruno
    Oct 18 at 8:16
  • 1
    $\begingroup$ Believe me when I say that Mihai knew this... but it is good to name the problem, and give references. $\endgroup$ Oct 19 at 23:50
  • $\begingroup$ I had not made the connection between the first name and the author of the question... $\endgroup$
    – Bruno
    Oct 20 at 16:04

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.