Numerically stable evaluation of factored univariate real polynomial

83 Views Asked by At

Suppose we have a real univariate factored polynomial, meaning we have its factors: an arbitrary number of polynomials of degree less than or equal to two. To simplify things, if necessary, let's assume that we multiply together factors of degree zero and one, so we'd be left with only degree-two polynomials as factors. Afterwards we round all the coefficients to machine precision.

Furthermore, while evaluating, we want to multiply the factors together in a structure of a binary tree, to minimize sequential dependencies and enable as much parallelism as possible in the evaluation.

Now the question is: if we want to minimize the maximum error (either absolute or relative) over an interval while evaluating the polynomial, how should we distribute the factors among the leaves of the binary tree? This is necessary because multiplication in floating-point arithmetic lacks associativity.

For example, if we have four factors, $a$, $b$, $c$ and $d$ (with known coefficients), is it better to evaluate them like so: $(ab)(cd)$ or like so: $(ac)(bd)$ or like so: $(ad)(bc)$?

Note that we can't just try all configurations, because the count of configurations grows too quickly with the count of factors: while there are only three configurations with four factors, for eight factors there are already $105$ configurations, and $675675$ for sixteen factors. There are $203067496256625$ configurations with $32$ factors. (I'm only considering power-of-two counts of factors for simplicity.)