Estrin's scheme

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 additions 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.

Description of the algorithm

Estrin's scheme operates recursively, converting a degree-n polynomial in x (for n≥2) to a degree-⌊n/2⌋ polynomial in x2 using ⌈n/2⌉ independent operations (plus one to compute x2).

Given an arbitrary polynomial P(x) = C0 + C1x + C2x2 + C3x3 + ⋯ + Cnxn, one can group adjacent terms into sub-expressions of the form (A + Bx) and rewrite it as a polynomial in x2: P(x) = (C0 + C1x) + (C2 + C3x)x2 + (C4 + C5x)x4 + ⋯ = Q(x2).

Each of these sub-expressions, and x2, may be computed in parallel. They may also be evaluated using a native multiply–accumulate instruction on some architectures, an advantage that is shared with Horner's method.

This grouping can then be repeated to get a polynomial in x4: P(x) = Q(x2) = ((C0 + C1x) + (C2 + C3x)x2) + ((C4 + C5x) + (C6 + C7x)x2)x4 + ⋯ = R(x4).

Repeating this ⌊log2n⌋+1 times, one arrives at Estrin's scheme for parallel evaluation of a polynomial:

  1. Compute Di = C2i + C2i+1x for all 0 ≤ i ≤ ⌊n/2⌋. (If n is even, then Cn+1 = 0 and Dn/2 = Cn.)
  2. If n ≤ 1, the computation is complete and D0 is the final answer.
  3. Otherwise, compute y = x2 (in parallel with the computation of Di).
  4. Evaluate Q(y) = D0 + D1y + D2y2 + ⋯ + D⌊n/2⌋y⌊n/2⌋ using Estrin's scheme.

This performs a total of n multiply-accumulate operations (the same as Horner's method) in line 1, and an additional ⌊log2n⌋ squarings in line 3. In exchange for those extra squarings, all of the operations in each level of the scheme are independent and may be computed in parallel; the longest dependency path is ⌊log2n⌋+1 operations long. A similar idea[1] enables a fast matrix multiplication algorithm to evaluate a polynomial at a series of points.

Examples

Take Pn(x) to mean the nth order polynomial of the form: Pn(x) = C0 + C1x + C2x2 + C3x3 + ⋯ + Cnxn

Written with Estrin's scheme we have:

P3(x) = (C0 + C1x) + (C2 + C3x) x2
P4(x) = (C0 + C1x) + (C2 + C3x) x2 + C4x4
P5(x) = (C0 + C1x) + (C2 + C3x) x2 + (C4 + C5x) x4
P6(x) = (C0 + C1x) + (C2 + C3x) x2 + ((C4 + C5x) + C6x2)x4
P7(x) = (C0 + C1x) + (C2 + C3x) x2 + ((C4 + C5x) + (C6 + C7x) x2)x4
P8(x) = (C0 + C1x) + (C2 + C3x) x2 + ((C4 + C5x) + (C6 + C7x) x2)x4 + C8x8
P9(x) = (C0 + C1x) + (C2 + C3x) x2 + ((C4 + C5x) + (C6 + C7x) x2)x4 + (C8 + C9x) x8
…

In full detail, consider the evaluation of P15(x):

Inputs: x, C0, C1, C2, C3, C4, C5 C6, C7, C8, C9 C10, C11, C12, C13 C14, C15
Step 1: x2, C0+C1x, C2+C3x, C4+C5x, C6+C7x, C8+C9x, C10+C11x, C12+C13x, C14+C15x
Step 2: x4, (C0+C1x) + (C2+C3x)x2, (C4+C5x) + (C6+C7x)x2, (C8+C9x) + (C10+C11x)x2, (C12+C13x) + (C14+C15x)x2
Step 3: x8, ((C0+C1x) + (C2+C3x)x2) + ((C4+C5x) + (C6+C7x)x2)x4, ((C8+C9x) + (C10+C11x)x2) + ((C12+C13x) + (C14+C15x)x2)x4
Step 4: (((C0+C1x) + (C2+C3x)x2) + ((C4+C5x) + (C6+C7x)x2)x4) + (((C8+C9x) + (C10+C11x)x2) + ((C12+C13x) + (C14+C15x)x2)x4)x8

In combination with Horner's method

Estrin's full scheme uses a very large number of multiply–accumulate operations in the first step. While this is useful to fully exploit modern superscalar processors, it will eventually exceed the available computing resources, at which point it may be useful to use Estrin's scheme to a limited depth, and then Horner's method on the residual.

For example, if a computer can perform four multiply-accumulate operations before the result of the first operation is available, then two levels of Estrin's scheme will keep its instruction pipeline full. Each iteration, it can perform the following operations in parallel:

Level 1: (Estrin) Compute D2i = C4i + C4i+1x and D2i+1 = C4i+2 + C4i+3x
Level 2: (Estrin) Compute Ei+1 = D2i+2 + D2i+3x2
Level 3: (Horner) Compute Fi+2 = Ei+2 + Fi+3x4

The final result is F0.

A more capable processor may be able to have four 4-operand SIMD operations in progress at once, in which case four levels of Estrin's scheme could be used to evaluate a sufficiently high-degree polynomial.

References

  1. ^ Borodin, Allan; Munro, Ian (1971). "Evaluating polynomials at many points". Information Processing Letters. 1 (2): 66–68. doi:10.1016/0020-0190(71)90009-3.

Further reading

This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.