Estrin's scheme

Last updated

In numerical analysis, Estrin's scheme (after Gerald Estrin), also known as Estrin's method, is an algorithm for numerical evaluation of polynomials.

Contents

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 + ⋯ + Dn/2yn/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.

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, C5C6, C7, C8, C9C10, C11, C12, C13C14, 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

Related Research Articles

In mathematics and computer science, Horner's method is an algorithm for polynomial evaluation. Although named after William George Horner, this method is much older, as it has been attributed to Joseph-Louis Lagrange by Horner himself, and can be traced back many hundreds of years to Chinese and Persian mathematicians. After the introduction of computers, this algorithm became fundamental for computing efficiently with polynomials.

<span class="mw-page-title-main">Newton's method</span> Algorithm for finding zeros of functions

In numerical analysis, the Newton–Raphson method, also known simply as Newton's method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots of a real-valued function. The most basic version starts with a real-valued function f, its derivative f, and an initial guess x0 for a root of f. If f satisfies certain assumptions and the initial guess is close, then

In mathematics, a polynomial is a mathematical expression consisting of indeterminates and coefficients, that involves only the operations of addition, subtraction, multiplication and exponentiation to nonnegative integer powers, and has a finite number of terms. An example of a polynomial of a single indeterminate x is x2 − 4x + 7. An example with three indeterminates is x3 + 2xyz2yz + 1.

In information theory and coding theory, Reed–Solomon codes are a group of error-correcting codes that were introduced by Irving S. Reed and Gustave Solomon in 1960. They have many applications, including consumer technologies such as MiniDiscs, CDs, DVDs, Blu-ray discs, QR codes, Data Matrix, data transmission technologies such as DSL and WiMAX, broadcast systems such as satellite communications, DVB and ATSC, and storage systems such as RAID 6.

In numerical analysis, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function f is a number x such that f(x) = 0. As, generally, the zeros of a function cannot be computed exactly nor expressed in closed form, root-finding algorithms provide approximations to zeros. For functions from the real numbers to real numbers or from the complex numbers to the complex numbers, these are expressed either as floating-point numbers without error bounds or as floating-point values together with error bounds. The latter, approximations with error bounds, are equivalent to small isolating intervals for real roots or disks for complex roots.

The city of Buenos Aires is formally divided in 48 barrios (neighborhoods), grouped into 15 comunas (communes), which are defined as "units of decentralized political and administrative management governed by designated residents".

British C-class submarine

The British C-class submarines were the last class of petrol engined submarines of the Royal Navy and marked the end of the development of the Holland class in the Royal Navy. Thirty-eight were constructed between 1905 and 1910 and they served through World War I.

<span class="mw-page-title-main">Kogge–Stone adder</span> Arithmetic logic circuit

In computing, the Kogge–Stone adder is a parallel prefix form of carry-lookahead adder. Other parallel prefix adders (PPA) include the Sklansky adder (SA), Brent–Kung adder (BKA), the Han–Carlson adder (HCA), the fastest known variation, the Lynch–Swartzlander spanning tree adder (STA), Knowles adder (KNA) and Beaumont-Smith adder (BSA).

In algebra, the greatest common divisor of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers.

A system of polynomial equations is a set of simultaneous equations f1 = 0, ..., fh = 0 where the fi are polynomials in several variables, say x1, ..., xn, over some field k.

In mathematics, the Conway polynomialCp,n for the finite field Fpn is a particular irreducible polynomial of degree n over Fp that can be used to define a standard representation of Fpn as a splitting field of Cp,n. Conway polynomials were named after John H. Conway by Richard A. Parker, who was the first to define them and compute examples. Conway polynomials satisfy a certain compatibility condition that had been proposed by Conway between the representation of a field and the representations of its subfields. They are important in computer algebra where they provide portability among different mathematical databases and computer algebra systems. Since Conway polynomials are expensive to compute, they must be stored to be used in practice. Databases of Conway polynomials are available in the computer algebra systems GAP, Macaulay2, Magma, SageMath, at the web site of Frank Lübeck, and at the Online Encyclopedia of Integer Sequences.

<span class="mw-page-title-main">Affine root system</span>

In mathematics, an affine root system is a root system of affine-linear functions on a Euclidean space. They are used in the classification of affine Lie algebras and superalgebras, and semisimple p-adic algebraic groups, and correspond to families of Macdonald polynomials. The reduced affine root systems were used by Kac and Moody in their work on Kac–Moody algebras. Possibly non-reduced affine root systems were introduced and classified by Macdonald (1972) and Bruhat & Tits (1972).

<i>Televisions Greatest Hits: Black and White Classics</i> 1996 compilation album

Television's Greatest Hits: Black & White Classics, prefaced with "TeeVee Toons Presents", is a 1996 compilation album of television theme songs from the 1950s and 1960s released by TVT Records as the fourth volume of the Television's Greatest Hits series.

<i>Televisions Greatest Hits: In Living Color</i> 1996 compilation album

Television's Greatest Hits: In Living Color, prefaced with "TeeVee Toons Presents", is a 1996 compilation album of 65 television theme songs from the 1960s and 1970s released by TVT Records as the fifth volume of the Television's Greatest Hits series.

<i>Televisions Greatest Hits: Remote Control</i> 1996 compilation album

Television's Greatest Hits: Remote Control, prefaced with "TeeVee Toons Presents", is a 1996 compilation album of 65 television theme songs from the 1970s and 1980s released by TVT Records as the sixth volume of the Television's Greatest Hits series.

<i>Televisions Greatest Hits: Cable Ready</i> 1996 compilation album

Television's Greatest Hits: Cable Ready, prefaced with "TeeVee Toons Presents", is a 1996 compilation album of television theme songs from the 1980s and early 1990s released by TVT Records as the seventh volume of the Television's Greatest Hits series.

<span class="mw-page-title-main">Road signs in Nepal</span> Road signs in Nepal are controlled by the Nepali Department of Roads Following international norms

Following international norms, road signs in Nepal are controlled by the Nepali Department of Roads and are heavily influenced by those used in the United Kingdom.

Indian Railways operates India's railway system and comes under the purview of the Ministry of Railways of Government of India. Indian Railways operates more than 4000 cargo and goods trains daily. It hauls variety of cargo to cater to various requirements and have specialized rolling stock corresponding to the cargo hauled. Indian Railways uses a specific wagon numbering system, adopted in 2003.

<span class="mw-page-title-main">Eastern Beskids</span>

The Eastern Beskids or Eastern Beskyds are a geological group of mountain ranges of the Beskids, within the Outer Eastern Carpathians. As a continuation of the Central Beskids, this mountain range includes the far southeastern corner of Poland, the far eastern corner of Slovakia, and stretches southward through western parts of Ukraine, up to the border of Romania.

References

Further reading