Estrin's Scheme Algorithm

An Estrin's Scheme Algorithm is a Polynomial Evaluation Algorithm that is a recursive algorithm that converts a $n$-degree polynomial in $x$ to a $n/2$-degree polynomial in $x^2$ using $n/2+1$ independent operations.

• AKA: Estrin's Method Algorithm.
• Example(s):
  • https://en.wikipedia.org/wiki/Estrin%27s_scheme#Description_of_the_algorithm
  • …
• Counter-Example(s):
  • Clenshaw Algorithm,
  • De Casteljau's Algorithm,
  • De Boor's Algorithm,
  • Horner's Scheme Algorithm.
  • Lill's Method Algorithm,
  • Ruffini's Rule Algorithm.
• See: Recurrence Relation, Numerical Analysis, Recursion, Polynomial Root-Finding Algorithm, Newton's Method, Gerald Estrin.

---

---

References

2021

• (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/Estrin's_scheme Retrieved:2021-9-5.
  • In numerical analysis, Estrin's scheme (after Gerald Estrin), also known as Estrin's method, is an algorithm for numerical evaluation of polynomials.

    Horner's method for evaluation of polynomials is one of the most commonly used algorithms for this purpose, and unlike Estrin's scheme it is optimal in the sense that it minimizes the number of multiplications and addition required to evaluate an arbitrary polynomial. On a modern processor, instructions that do not depend on each other's results may run in parallel. Horner's method contains a series of multiplications and additions that each depend on the previous instruction and so cannot execute in parallel. Estrin's scheme is one method that attempts to overcome this serialization while still being reasonably close to optimal.

1973

• (Munro & Paterson, 1973) ⇒ Ian Munro, and Michael Paterson (1973). "Optimal Algorithms for Parallel Polynomial Evaluation". In: Journal of Computer and System Sciences 7, 189-198.
  • QUOTE: Estrin's algorithm computes $p(x)$ as
    $p(x) = q(x) x^{(n/2)+1}+ r(x)\;,$
    where
    $q(x) = a_nx^{n/2}+ \ldots + a_{(n/2)+ t}$
    and
    $r(x) = a_{n/2}x^{n/2} + \ldots + a_0$
    and then computes $q(x)$ and $r(x)$ similarly by a binary splitting. Thus it starts by computing
    $a_1x + a_0 \;,\; a_2x + a_2 ,\ldots$
    and then
    $\left(a_3x + a_2\right) x^2 + \left(a_lx + a_0\right),\ldots$ , etc.
    If an unlimited number of processors are available, this algorithm runs in time about $2 \log n$.

---