Polynomial evaluation

General methods

Horner's rule

Horner's method evaluates a polynomial using repeated bracketing: $${\displaystyle \begin{array}{cc}{a}_0+& a_{1}x+a_2{x}^2+a_3{x}^3+\cdots +a_n{x}^n\\ & =a_0+x(a_1+x(a_2+x(a_3+\cdots +x(a_{n-1}+x{a}_n)\cdots ))).\end{array}}$$ This method reduces the number of multiplications and additions to just ${\displaystyle n}$

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.

Multivariate

If the polynomial is multivariate, Horner's rule can be applied recursively over some ordering of the variables. E.g.

${\displaystyle P(x,y)=4+x+2xy+2x^{2}y+x^2{y}^2}$

can be written as

${\displaystyle \begin{array}{cc}P(x,y)& =4+x(1+y(2)+x(y(2+y)))\text{or}\\ P(x,y)& =4+x+y(x(2+x(2))+y(x^2)).\end{array}}$

An efficient version of this approach was described by Carnicer and Gasca.

Estrin's scheme

While it's not possible to do less computation than Horner's rule (without preprocessing), on modern computers the order of evaluation can matter a lot for the computational efficiency. A method known as Estrin's scheme computes a (single variate) polynomial in a tree like pattern:

$${\displaystyle \begin{array}{c}P(x)=(a_0+a_{1}x)+(a_2+a_{3}x)x^2+((a_4+a_{5}x)+(a_6+a_{7}x)x^2)x^4.\end{array}}$$

Combined by Exponentiation by squaring, this allows parallelizing the computation.

Evaluation with preprocessing

Arbitrary polynomials can be evaluated with fewer operations than Horner's rule requires if we first "preprocess" the coefficients ${\displaystyle a_n,\dots ,a_0}$.

An example was first given by Motzkin who noted that

${\displaystyle P(x)=x^4+a_3{x}^3+a_2{x}^2+a_{1}x+a_0}$

can be written as

${\displaystyle y=(x+{\beta }_0)x+{\beta }_1,P(x)=(y+x+{\beta }_2)y+{\beta }_3,}$

where the values ${\displaystyle {\beta }_0,\dots ,{\beta }_3}$ are computed in advanced, based on ${\displaystyle a_0,\dots ,a_3}$. Motzkin's method uses just 3 multiplications compared to Horner's 4.

The values for each ${\displaystyle {\beta }_i}$ can be easily computed by expanding ${\displaystyle P(x)}$ and equating the coefficients:

${\displaystyle \begin{array}{cccccc}{\beta }_0& =\frac{1}{2}(a_3-1),& z& =a_2-{\beta }_0({\beta }_0+1),& {\beta }_1& =a_1-{\beta }_{0}z,\\ {\beta }_2& =z-2{\beta }_1,& {\beta }_3& =a_0-{\beta }_1({\beta }_1+{\beta }_2).\end{array}}$

Example

To compute the Taylor expansion ${\displaystyle \exp (x)\approx 1+x+x^2/2+x^3/6+x^4/24}$, we can upscale by a factor 24, apply the above steps, and scale back down. That gives us the three multiplication computation

${\displaystyle y=(x+1.5)x+11.625,P(x)=(y+x-15)y/24+\mathrm{2.63477.}}$

Improving over the equivalent Horner form (that is ${\displaystyle P(x)=1+x(1+x(1/2+x(1/6+x/24)))}$) by 1 multiplication.

Some general methods include the Knuth–Eve algorithm and the Rabin–Winograd algorithm.

Multipoint evaluation

Evaluation of a degree-n polynomial ${\displaystyle P(x)}$ at multiple points ${\displaystyle x_1,\dots ,x_m}$ can be done with ${\displaystyle mn}$ multiplications by using Horner's method ${\displaystyle m}$ times. Using the above preprocessing approach, this can be reduced by a factor of two; that is, to ${\displaystyle mn/2}$ multiplications.

However, it is possible to do better and reduce the time requirement to just ${\displaystyle O((n+m){\log }^2(n+m))}$. The idea is to define two polynomials that are zero in respectively the first and second half of the points: ${\displaystyle m_0(x)=(x-x_1)\cdots (x-x_{n/2})}$ and ${\displaystyle m_1(x)=(x-x_{n/2+1})\cdots (x-x_n)}$. We then compute ${\displaystyle R_0=P{modm}_0}$ and ${\displaystyle R_1=P{modm}_1}$ using the Polynomial remainder theorem, which can be done in ${\displaystyle O(n\log n)}$ time using a fast Fourier transform. This means ${\displaystyle P(x)=Q(x)m_0(x)+R_0(x)}$ and ${\displaystyle P(x)=Q(x)m_1(x)+R_1(x)}$ by construction, where ${\displaystyle R_0}$ and ${\displaystyle R_1}$ are polynomials of degree at most ${\displaystyle n/2}$. Because of how ${\displaystyle m_0}$ and ${\displaystyle m_1}$ were defined, we have

${\displaystyle \begin{array}{cc}{R}_0(x_i)& =P(x_i)\text{for }i\le n/2\text{and}\\ R_1(x_i)& =P(x_i)\text{for }i>n/2.\end{array}}$

Thus to compute ${\displaystyle P}$ on all ${\displaystyle n}$ of the ${\displaystyle x_i}$, it suffices to compute the smaller polynomials ${\displaystyle R_0}$ and ${\displaystyle R_1}$ on each half of the points. This gives us a divide-and-conquer algorithm with ${\displaystyle T(n)=2T(n/2)+n\log n}$, which implies ${\displaystyle T(n)=O(n(\log n{)}^2)}$ by the master theorem.

In the case where the points in which we wish to evaluate the polynomials have some structure, simpler methods exist. For example, Knuth section 4.6.4 gives a method for tabulating polynomial values of the type

${\displaystyle P(x_0+h),P(x_0+2h),\dots .}$

Dynamic evaluation

In the case where ${\displaystyle x_1,\dots ,x_m}$ are not known in advance, Kedlaya and Umans gave a data structure for evaluating polynomials over a finite field of size ${\displaystyle F_q}$ in time ${\displaystyle (\log n{)}^{O(1)}({\log }_{2}q{)}^{1+o(1)}}$ per evaluation after some initial preprocessing. This was shown by Larsen to be essentially optimal.

The idea is to transform ${\displaystyle P(x)}$ of degree ${\displaystyle n}$ into a multivariate polynomial ${\displaystyle f(x_1,x_2,\dots ,x_m)}$, such that ${\displaystyle P(x)=f(x,x^d,x^{d^2},\dots ,x^{d^m})}$ and the individual degrees of ${\displaystyle f}$ is at most ${\displaystyle d}$. Since this is over ${\displaystyle modq}$, the largest value ${\displaystyle f}$ can take (over ${\displaystyle \mathbb{Z}}$) is ${\displaystyle M=d^m(q-1{)}^{dm}}$. Using the Chinese remainder theorem, it suffices to evaluate ${\displaystyle f}$ modulo different primes ${\displaystyle p_1,\dots ,p_{\ell }}$ with a product at least ${\displaystyle M}$. Each prime can be taken to be roughly ${\displaystyle \log M=O(dm\log q)}$, and the number of primes needed, ${\displaystyle \ell }$, is roughly the same. Doing this process recursively, we can get the primes as small as ${\displaystyle \log \log q}$. That means we can compute and store ${\displaystyle f}$ on all the possible values in ${\displaystyle T=(\log \log q{)}^m}$ time and space. If we take ${\displaystyle d=\log q}$, we get ${\displaystyle m=\frac{\log n}{\log \log q}}$, so the time/space requirement is just ${\displaystyle n^{\frac{\log \log q}{\log \log \log q}}.}$

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.

Specific polynomials

While general polynomials require ${\displaystyle \mathrm{\Omega }(n)}$ operations to evaluate, some polynomials can be computed much faster. For example, the polynomial ${\displaystyle P(x)=x^2+2x+1}$ can be computed using just one multiplication and one addition since ${\displaystyle P(x)=(x+1{)}^2}$

Evaluation of powers

A particularly interesting type of polynomial is powers like ${\displaystyle x^n}$. Such polynomials can always be computed in ${\displaystyle O(\log n)}$ operations. Suppose, for example, that we need to compute ${\displaystyle x^{16}}$; we could simply start with ${\displaystyle x}$ and multiply by ${\displaystyle x}$ to get ${\displaystyle x^2}$. We can then multiply that by itself to get ${\displaystyle x^4}$ and so on to get ${\displaystyle x^8}$ and ${\displaystyle x^{16}}$ in just four multiplications. Other powers like ${\displaystyle x^5}$ can similarly be computed efficiently by first computing ${\displaystyle x^4}$ by 2 multiplications and then multiplying by ${\displaystyle x}$.

The most efficient way to compute a given power ${\displaystyle x^n}$ is provided by addition-chain exponentiation. However, this requires designing a specific algorithm for each exponent, and the computation needed for designing these algorithms are difficult (NP-complete), so exponentiation by squaring is generally preferred for effective computations.

Polynomial families

Often polynomials show up in a different form than the well known ${\displaystyle a_n{x}^n+\cdots +a_{1}x+a_0}$. For polynomials in Chebyshev form we can use Clenshaw algorithm. For polynomials in Bézier form we can use De Casteljau's algorithm, and for B-splines there is De Boor's algorithm.

Hard polynomials

The fact that some polynomials can be computed significantly faster than "general polynomials" suggests the question: Can we give an example of a simple polynomial that cannot be computed in time much smaller than its degree? Volker Strassen has shown that the polynomial

${\displaystyle P(x)=\sum _{k=0}^n{2}^{2^{k{n}^3}}{x}^k}$

cannot be evaluated with less than ${\displaystyle \frac{1}{2}n-2}$ multiplications and ${\displaystyle n-4}$ additions. At least this bound holds if only operations of those types are allowed, giving rise to a so-called "polynomial chain of length ${\displaystyle <n^2/\log n}$".

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 ${\displaystyle \mathrm{\Omega }(n/\log n)}$ multiplications.

For other simple polynomials, the complexity is unknown. The polynomial ${\displaystyle (x+1)(x+2)\cdots (x+n)}$ is conjectured to not be computable in time ${\displaystyle (\log n{)}^c}$ for any ${\displaystyle c}$. This is supported by the fact that, if it can be computed fast, then integer factorization can be computed in polynomial time, breaking the RSA cryptosystem.

Matrix polynomials

Sometimes the computational cost of scalar multiplications (like ${\displaystyle ax}$) is less than the computational cost of "non scalar" multiplications (like ${\displaystyle x^2}$). The typical example of this is matrices. If ${\displaystyle M}$ is an ${\displaystyle m\times m}$ matrix, a scalar multiplication ${\displaystyle aM}$ takes about ${\displaystyle m^2}$ arithmetic operations, while computing ${\displaystyle M^2}$ takes about ${\displaystyle m^3}$ (or ${\displaystyle m^{2.3}}$ using fast matrix multiplication).

Matrix polynomials are important for example for computing the Matrix Exponential.

Paterson and Stockmeyer showed how to compute a degree ${\displaystyle n}$ polynomial using only ${\displaystyle O(\sqrt{n})}$ non scalar multiplications and ${\displaystyle O(n)}$ scalar multiplications. Thus a matrix polynomial of degree n can be evaluated in ${\displaystyle O(m^{2.3}\sqrt{n}+m^{2}n)}$ time. If ${\displaystyle m=n}$ this is ${\displaystyle O(m^3)}$, as fast as one matrix multiplication with the standard algorithm.

This method works as follows: For a polynomial

${\displaystyle P(M)=a_{n-1}{M}^{n-1}+\cdots +a_{1}M+a_{0}I,}$

let k be the least integer not smaller than ${\displaystyle \sqrt{n}.}$ The powers ${\displaystyle M,M^2,\dots ,M^k}$ are computed with ${\displaystyle k}$ matrix multiplications, and ${\displaystyle M^{2k},M^{3k},\dots ,M^{k^2-k}}$ are then computed by repeated multiplication by ${\displaystyle M^k.}$ Now,

${\displaystyle \begin{array}{cc}P(M)=& (a_{0}I+a_{1}M+\cdots +a_{k-1}{M}^{k-1})\\ +& (a_{k}I+a_{k+1}M+\cdots +a_{2k-1}{M}^{k-1})M^k\\ +& \dots \\ +& (a_{n-k}I+a_{n-k+1}M+\cdots +a_{n-1}{M}^{k-1})M^{k^2-k},\end{array}}$,

where ${\displaystyle a_i=0}$ for i ≥ n. This requires just ${\displaystyle k}$ more non-scalar multiplications.

We can write this succinctly using the Kronecker product:

${\displaystyle P(M)={\left[\begin{array}{c}I\\ M\\ ⋮\\ M^{k-1}\end{array}\right]}^T\left(\left[\begin{array}{cccc}{a}_0& a_1& a_2& \dots \\ a_k& a_{k+1}& \ddots \\ a_{2k}& \ddots \\ ⋮\end{array}\right]\otimes I\right)\left[\begin{array}{c}I\\ M^k\\ M^{2k}\\ ⋮\end{array}\right]}$.

The direct application of this method uses ${\displaystyle 2\sqrt{n}}$ non-scalar multiplications, but combining it with Evaluation with preprocessing, Paterson and Stockmeyer show you can reduce this to ${\displaystyle \sqrt{2n}}$.

Methods based on matrix polynomial multiplications and additions have been proposed allowing to save nonscalar matrix multiplications with respect to the Paterson-Stockmeyer method.