Optimal evaluation of polynomials / rational functions

Question

A common way to compute the value a polynomial is to write it in Horner form. However, this isn't always the fastest way to evaluate it. Setting aside concerns of numerical precision, take the poynomial:

$$P(x) = \sum_{k=0}^n \binom{n}{k} x^k$$

with $n$ known. One technique would be to precompute the coefficients and evaluate the polynomial using the Horner form. However that will take time linear in $n$, whereas we might observe that

$$P(x) = (x+1)^n$$

which can be evaluated in $\mathcal{O}(\log n)$ multiplications.

In general, identifying patterns inside a polynomial that lend themselves to simplification can speed up evaluation. This is not always obvious

For instance $75938+99169x+45123x^2-805x^3-10745x^4-5523x^5-1309x^6-127x^7$ can also be written as $(x+5)^7-(2x+3)^7$.

Things become even more complicated once multiple variables are introduced, or when we generalize to rational functions.

Clearly there exists an algorithm to find the most efficient computation of a given expression in terms of arithmetic operations and variable assignments: iterate through all possible computations in order of their number of operations, decide if they are equivalent to the target equation and if so stop.

This of course is cost prohibitive. Is there a known efficient algorithm to solve this problem, or at least to approximate it?

Answer 1

In Knuth Vol II Theorem E on page 494 he presents an algorithm that can evaluate a polynomial using $\frac{n}{2} + 2$ multiplications. The theoretical minimum is $\frac{n}{2}$, assuming generic polynomials. The algorithm requires factoring polynomials. There is another algorithm from Rabin & Winograd that only requires division, but runs in $\frac{n}{2} + \log n$.

Your question is about automatically identifying special structure that can be exploited to optimize further, which these algorithms do not do.

Square-free factorization can be used to efficiently find repeated terms like $p(x)\cdot (q(x))^7$. It won't find your sum example.

If $n$ is not too big, it might actually be feasible to iterate through all circuits with $\frac{n}{2} + 1$ multiplication gates and arbitrary addition/subtraction gates. Reduce them symbolically to coefficient form and try to solve the resulting set of polynomial equations. I guess this last step would the hardest.