38

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

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Mihai
  • 1,870
  • 13
  • 14
  • Nice question, seems like I've seen something similar in someone's blog, but I can't remember where it was. – Grigory Yaroslavtsev Aug 27 '10 at 19:51
  • 3
    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.) – ShreevatsaR Aug 28 '10 at 02:43
  • 1
    Can you give a reference to the $O(n\log^2 n)$ result? – Mohammad Al-Turkistany Sep 10 '10 at 02:14
  • @turkistany: do divide and conquer. the merge step is a single multiplication on two polys of degree n/2, which can be done in n log n time via FFT. so the overall recurrence is 2T(n/2) + n log n. – Suresh Venkat Sep 10 '10 at 04:15
  • 2
    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 04:47
  • You're talking about computing the coefficients of the polynomial, right? Is this equivalent to computing the product of $\sqrt{n}$ $\sqrt{n}$-bit integers in time $\tilde O(n \log n)$ (where $\tilde O$ hides sub-logarithmic factors)? – Joshua Grochow Sep 10 '10 at 05:55
  • @Joshua not sure I see the connection – Suresh Venkat Sep 10 '10 at 07:50
  • @Suresh: as far as I can see, the two questions are not obviously equivalent. The connection is that they both can use divide-and-conquer and then the FFT to get time $\tilde O(n \log^2(n))$. In a sense both questions are asking whether $n$ FFT-based multiplications can be done in the same asymptotic running time as a single such multiplication; I wouldn't be surprised if a positive answer to one implied a positive answer to the other, but again, it's not obvious. – Joshua Grochow Sep 10 '10 at 13:19
  • @Joshua, I'm confused, What does $n$ represent here? Is it the number of bits or is it the number of polynomials? – Mohammad Al-Turkistany Sep 10 '10 at 13:55
  • 1
    Can we compute the convolution of $n$ vectors of constant dimension 2 in time $O(n \log n)$? – Kaveh Sep 10 '10 at 14:14
  • @turkistany, in both cases it is the number of bits. In the original question, Mihai stipulated that the coefficients fit into a single word, so the number of bits is O(n). In my question I stipulated $\sqrt{n}$ numbers of $\sqrt{n}$ bits each, for a total of $n$ bits. – Joshua Grochow Sep 12 '10 at 04:58
  • @Joshua: You're correct, but (and I'm about to say something that's nigh-heresy in a theoretical discussion) machine word size probably grows slower than anything else in all of computer science. For any actual machine a $\sqrt(n)$-bit machine word is just a byte. A "don't care" assumption, as in the question, makes plenty of sense; but taking the further step of treating machine words as a "true" $O(n)$-size object seems too impractical to make much sense to me.. – Daniel Apon Sep 23 '10 at 11:56
  • @Daniel: The standard assumption is that a word is O(log n) bits long. This is sometimes generalized to allow words of length w ≥ log n, but even then, the word size w is typically assumed to be O(polylog n). Word sizes around √n would make a number of things unreasonably easy, thanks to massive bit-level parallelism. But yes, O(n)-bit words are right out. – Jeffε Sep 25 '10 at 05:21

2 Answers2

7

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.

Jan Johannsen
  • 4,630
  • 2
  • 33
  • 50
Per Vognsen
  • 2,161
  • 16
  • 25
2

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

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