Evaluation of polynomials with super-preconditioning

摘要

Certain questions concerning the arithmetic complexity of univariate polynomial evaluation are considered. The principal technical results show that there exist polynomials f,g, and h with h = fg, such that h requires substantially fewer arithmetic operations than either f or g. However, if the coefficients of f are algebraically independent, then any h = fg is as hard to evaluate as f. The question of the relative complexities of f and fg is viewed as a special case of the following question: given an operator Δ which maps polynomials to sets of polynomials, what savings in arithmetic operations is achievable by evaluating some polynomial h ϵ Δ(f) rather than f? Observations and open questions concerning several operators are discussed.