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.