Greedy algorithms for optimizing multivariate Horner schemes

Abstract

For univariate polynomials f ( x 1 ), Horner's scheme provides the fastest way to compute a value. For multivariate polynomials, several different version of Horner's scheme are possible; it is not clear which of them is optimal. In this paper, we propose a greedy algorithm, which it is hoped will lead to good computation times.The univariate Horner scheme has another advantage: if the value x 1 is known with uncertainty, and we are interested in the resulting uncertainty in f ( x 1 ), then Horner scheme leads to a better estimate for this uncertainty that many other ways of computing f ( x 1 ). The second greedy algorithm that we propose tries to find the multivariate Horner scheme that leads to the best estimate for the uncertainty in f ( x 1 ,..., x n ).