Knuth–Eve algorithm

In computer science, the Knuth–Eve algorithm is an algorithm for polynomial evaluation. It preprocesses the coefficients of the polynomial to reduce the number of multiplications required at runtime. Ideas used in the algorithm were originally proposed by Donald Knuth in 1962. His procedure opportunistically exploits structure in the polynomial being evaluated. In 1964, James Eve determined for which polynomials this structure exists, and gave a simple method of "preconditioning" polynomials (explained below) to endow them with that structure.

In computer science, the Knuth–Eve algorithm is an algorithm for polynomial evaluation. It preprocesses the coefficients of the polynomial to reduce the number of multiplications required at runtime. Ideas used in the algorithm were originally proposed by Donald Knuth in 1962. His procedure opportunistically exploits structure in the polynomial being evaluated. In 1964, James Eve determined for which polynomials this structure exists, and gave a simple method of "preconditioning" polynomials (explained below) to endow them with that structure. Consider an arbitrary polynomial p \in \mathbb{R}[x] of degree n . Assume that n \geq 3 . Define m such that: if n is odd then n = 2m+1 , and if n is even then n = 2m+2 . Unless otherwise stated, all variables in this article represent either real numbers or univariate polynomials with real coefficients. All operations in this article are done over \mathbb{R} . Again, the goal is to create an algorithm that returns p(x) given any x . The algorithm is allowed to depend on the polynomial p itself, since its coefficients are known in advance. p(x) = q(x) \cdot (x^2 - \alpha) + (\beta x + \gamma), where x^2 - \alpha is the divisor. Picking a value for \alpha fixes both the quotient q and the coefficients in the remainder \beta and \gamma . The key idea is to cleverly choose \alpha such that \beta = 0 , so that p(x) = q(x) \cdot (x^2 - \alpha) + \gamma. This way, no operations are needed to compute the remainder polynomial, since it's just a constant. We apply this procedure recursively to q , expressing p(x) = \left( \left( q(x) \cdot (x^2 - \alpha_m) + \gamma_m \right) \cdots \right) \cdot (x^2 - \alpha_1) + \gamma_1. After m recursive calls, the quotient q is either a linear or a quadratic polynomial. In this base case, the polynomial can be evaluated with (say) Horner's method. For arbitrary p , it may not be possible to force \beta = 0 at every step of the recursion. Consider the polynomials p^e and p^o with coefficients taken from the even and odd terms of p respectively, so that p(x) = p^e(x^2) + x \cdot p^o(x^2). If every root of p^o is real, then it is possible to write p in the form given above. Each \alpha_i is a different root of p^o , counting multiple roots as distinct. Furthermore, if at least n-1 roots of p lie in one half of the complex plane, then every root of p^o is real. Ultimately, it may be necessary to "precondition" p by shifting it by setting p(x) \gets p(x + t) for some t to endow it with the structure that most of its roots lie in one half of the complex plane. At runtime, this shift has to be "undone" by first setting x \gets x - t . Let p^e and p^o be the polynomials such that p(x) = p^e(x^2) + x \cdot p^o(x^2) Let \alpha_1, \cdots \alpha_m \in \mathbb{R} be the roots of p^o . All of its roots will be real. Initialize q \gets p For i \gets 1, \cdots, m : Divide q by x^2 - \alpha_i to get quotient q^\prime \in \mathbb{R}[x] and remainder \gamma_i \in \mathbb{R} . The remainder will be a constant polynomial a number. Set q \gets q^\prime Output: The derived values t , \alpha_1, \cdots, \alpha_m , and \gamma_1, \cdots, \gamma_m ; as well as the base-case polynomial q While any t \geq \text{Re}(r_2) can work, it is possible to remove one addition during evaluation if t is also chosen such that two roots of p(x + t) are symmetric about the origin. In that case, \alpha_1 can be chosen such that the shifted polynomial has a factor of x^2 - \alpha_1 , so \gamma_1 = 0 . It is always possible to find such a t . One possible algorithm for choosing t is: If r_1 \in \mathbb{R} : If r_2 \in \mathbb{R} : t = \tfrac{1}{2} (r_1 + r_2) Else: t = \text{Re}(r_2) Else: t = \text{Re}(r_1) Set x \gets x - t Let s = x^2 . Compute this once so it can be reused. Compute y \gets q(x) using Horner's method For i \gets m, \cdots, 2, 1 : Let y \gets y \cdot (s - \alpha_i) + \gamma_i Output: y Assuming t is chosen optimally, \gamma_1 = 0 . So, the final iteration of the loop can instead run y \gets y \cdot (s - \alpha_i), saving an addition.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1371042535 under CC BY-SA 4.0; modifications have been made.