35
$\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$
  • $\begingroup$ Nice question, seems like I've seen something similar in someone's blog, but I can't remember where it was. $\endgroup$ – Grigory Yaroslavtsev 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$ – ShreevatsaR Aug 28 '10 at 2:43
  • 1
    $\begingroup$ Can you give a reference to the $O(n\log^2 n)$ result? $\endgroup$ – Mohammad Al-Turkistany 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) ... (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 nth 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$
  • 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$ – Per Vognsen 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$ – Joshua Grochow Feb 21 '12 at 4:58

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.