About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Computer and System Sciences
Paper
Evaluation of polynomials with super-preconditioning
Abstract
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 ε{lunate} Δ(f) rather than f? Observations and open questions concerning several operators are discussed. © 1978.