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.pdfAddendum: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:
Computing a subproduct tree
trees;binary trees;polynomials;subtree