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
STOC 1976
Conference paper
Evaluation of polynomials with super-preconditioning
Abstract
In an effort to understand the complexity of arithmetic computation, a number of researchers [1,5,7,8,9,11] have studied the following question: Given a polynomial f(x), Find a minimal cost straightline program that computes f(x). In this paper this question is generalized to the following question: Given a polynomial f(x) and an operator A that maps polynomials to sets of polynomials, Find a minima] cost straightline program that computes some h(x) ϵ ΔA(f(x)). We call this model super-preconditioning. It allows the replacement of f(x) by any other h(x)ϵ Δ A(f(x)). The motivation for.