In mathematics and computer science, polynomial evaluation refers to computation of the value of a polynomial when its indeterminates are substituted for some values.
In the former case, polynomials are evaluated using floating-point arithmetic, which is not exact.
Thus different schemes for the evaluation will, in general, give slightly different answers.
Horner's method evaluates a polynomial using repeated bracketing:
Horner's method is so common that a computer instruction "multiply–accumulate operation" has been added to many computer processors, which allow doing the addition and multiplication operations in one combined step.
If the polynomial is multivariate, Horner's rule can be applied recursively over some ordering of the variables.
E.g. can be written as An efficient version of this approach was described by Carnicer and Gasca.
A method known as Estrin's scheme computes a (single variate) polynomial in a tree like pattern:
Combined by Exponentiation by squaring, this allows parallelizing the computation.
Arbitrary polynomials can be evaluated with fewer operations than Horner's rule requires if we first "preprocess" the coefficients
Motzkin's method uses just 3 multiplications compared to Horner's 4.
and equating the coefficients: To compute the Taylor expansion
, we can upscale by a factor 24, apply the above steps, and scale back down.
That gives us the three multiplication computation Improving over the equivalent Horner form (that is
[4] The idea is to define two polynomials that are zero in respectively the first and second half of the points:
In the case where the points in which we wish to evaluate the polynomials have some structure, simpler methods exist.
For example, Knuth[5] section 4.6.4 gives a method for tabulating polynomial values of the type In the case where
are not known in advance, Kedlaya and Umans[6] gave a data structure for evaluating polynomials over a finite field of size
Kedlaya and Umans further show how to combine this preprocessing with fast (FFT) multipoint evaluation.
This allows optimal algorithms for many important algebraic problems, such as polynomial modular composition.
operations to evaluate, some polynomials can be computed much faster.
However, this requires designing a specific algorithm for each exponent, and the computation needed for designing these algorithms are difficult (NP-complete[8]), so exponentiation by squaring is generally preferred for effective computations.
Volker Strassen has shown[9] that the polynomial cannot be evaluated with less than
At least this bound holds if only operations of those types are allowed, giving rise to a so-called "polynomial chain of length
The polynomial given by Strassen has very large coefficients, but by probabilistic methods, one can show there must exist even polynomials with coefficients just 0's and 1's such that the evaluation requires at least
Paterson and Stockmeyer[12] showed how to compute a degree
This method works as follows: For a polynomial let k be the least integer not smaller than
We can write this succinctly using the Kronecker product: The direct application of this method uses
non-scalar multiplications, but combining it with Evaluation with preprocessing, Paterson and Stockmeyer show you can reduce this to
Methods based on matrix polynomial multiplications and additions have been proposed allowing to save nonscalar matrix multiplications with respect to the Paterson-Stockmeyer method.