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

Improve this question
$\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$
    – Grigory Yaroslavtsev
    Aug 27, 2010 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, 2010 at 2:43
  • 1
    $\begingroup$ Can you give a reference to the $O(n\log^2 n)$ result? $\endgroup$
    – Mohammad Al-Turkistany
    Sep 10, 2010 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, 2010 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, 2010 at 14:14

2 Answers 2

Reset to default
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.

Improve this answer
$\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, 2010 at 6:46
  • $\begingroup$ True! I wish I had a more definitive answer. It's very interesting. $\endgroup$
    – Per Vognsen
    Sep 27, 2010 at 6:51
  • $\begingroup$ Bounty awarded! $\endgroup$
    – Jeffε
    Sep 28, 2010 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, 2012 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.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Is there a matching lower bound or is the lower bound $\Omega(\mathsf{M}(n))$? $\endgroup$
    – Turbo
    Oct 18, 2021 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, 2021 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$
    – Ryan Williams
    Oct 19, 2021 at 23:50
  • $\begingroup$ I had not made the connection between the first name and the author of the question... $\endgroup$
    – Bruno
    Oct 20, 2021 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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