Consider the following description of a subproduct tree.

We define a tree T for some points x[0] to x[n-1], and define m = log_2(n).

Tree T is represented as a matrix where each row-column entry i, j is the product of pairwise nodes in the row above it. In total, there are m rows; the 1st row is has n column entries, and the last row has 1 column entry.

In short, how does one compute the coefficients for a large n? Once m > 4, the coefficients of the entries become greater than 64-bits. Consider the product of (x - i) for i = 0 to 15. The coefficients become very large.

Unless we are working in a finite field, it seems as though one cannot construct such a subproduct tree for say n = 2^20.

Formally: http://specfun.inria.fr/bostan/publications/BoSc05.pdf



I understand the complexity of the operation, as stated in the next section of the paper. However, I'm unsure how one would practically approach computing the coefficients of this subproduct tree as size n grows to be large (say 2^20).

Ex, consider the following simple example:


  • $\begingroup$ It looks like you might have inadvertently created two accounts. I encourage you to merge them and also to register your account to ensure you retain access to it. $\endgroup$ – D.W. May 30 '16 at 1:17
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Aug 26 '16 at 8:46
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Aug 26 '16 at 8:47

How does the computation scale?

Keep reading! The paper describes how this scales for $n$, in the very next line after the excerpt you show. In particular, the next line is Proposition 1, which states the running time of computing the subproduct tree, as a function of $n$. That tells you how the running time scales for large $n$.

How do you compute the coefficients?

Follow the algorithm described in the paper! You already described the algorithm. Use exactly what you described.

Don't the coefficients become large, when $n$ is large?

Yes, potentially. This is inherent to the task: if you want to compute some polynomial (the product) whose coefficients are large, then yes, the coefficients produced by such an algorithm will be large. This is pretty much a tautological statement.

| cite | improve this answer | |
  • $\begingroup$ Thanks D.W. for the clarification and cleanup! I would like to consider the arithmetic sequence case where the arithmetic progression is 0, 1, 2, ..., n, where n is 2^20. In this case, the direct computation is unable to proceed past row 4 of the subproduct tree (including bad_alloc). Is there an alternative algorithm or representation that could allow one to reach row 20 (m = log_2(2^20)) of the subproduct tree? $\endgroup$ – H W May 30 '16 at 1:28
  • $\begingroup$ @HW, I feel like you haven't fully absorbed the last paragraph of my answer yet. If the answer to the question is too large to write down in a feasible amount of time, then there is no algorithm that will ever produce that answer in a reasonable amount of time. This is not something that can be solved by a different algorithm; this is inherent to the task. Your best bet is to try to figure out what you plan to do with the final polynomial, and see if there's a way to achieve that goal without actually finding the coefficients explicitly. $\endgroup$ – D.W. May 30 '16 at 1:34
  • $\begingroup$ I see, thanks D.W. I'm just a bit surprised by the stark contrast in resulting performance of the Newton to monomial (and back) basis conversion algorithms in the geometric and arithmetic cases. The algorithms for the geometric case as provided on pg 26 does remarkably well for large sizes of n, while the algorithms for the arithmetic case as provided on pgs 11 & 14 cannot in practice even work for n > 16, if the progression we consider is the natural numbers. $\endgroup$ – H W May 30 '16 at 1:49
  • $\begingroup$ @HW, sorry, I lack context to understand that statement. It sounds like you might not have asked quite the right question. Perhaps you might like to try posting a new question that gets more directly at the contrast that is puzzling you? (Do provide background in the question and explain why this difference puzzles you.) I suspect the answer is going to be that "in general, this is hard, but for some specific cases it might be easier than the general case", in which case there is no contradiction. $\endgroup$ – D.W. May 30 '16 at 2:12

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.