 # new Processor Selector

Platform:
Segment:
View: show / edit bookmark site permalink
Mon 6 Apr 2009, 23:22

# Parallelization of a Polynomial Extrapolation Code

Parallelization of a Polynomial Extrapolation Code

The Problem

Polynomial interpolation is a process that take a set of N points, (xi, yi), and finds a polynomial function, P, such that the line graphing P passes through each of the N points. That is, yi = P(xi), for all 1≤ i ≤ N. Polynomial extrapolation finds the function value of a point, X, along the x-axis that is not within the original data set of N points defining the function. Extrapolating the value of a point within an interpolated polynomial is the goal of the code whose parallelization is described in this article.

Using Lagrange's Formula, you can interpolate the polynomial P and compute a solution for P(X). The computation requires the calculation of N terms that are added together, which describes a polynomial of degree N-1. The computation for each term involves 2N-2 subtractions and 2N-1 multiplications. Plenty of independent computations are available in this formulation, but there is no way to compute an error estimate and it can generate awkward coding that ensures the correct values are used to calculate each term.

An alternative is Neville's algorithm. This formulation uses finite difference calculations as it refines the functional value of increasingly higher degree polynomials. ...

Filed under: Parallel Programming and Multi-Core  