PIPELINED ALGORITHM FOR NEWTONS DIVIDED DIFFERENCE INTERPOLATION

The problem of numerical interpolation is encountered in many engineer ing and scientific applications. Newton's methods are commonly used to solve these problems. Generally, Newton's algorithms are of O(n(2)) s equential complexity. In this paper, Newton's divided difference inter polation algorithm is reorganized to well-suite vector processing. The proposed algorithm has O(log n) vector complexity. It requries 2 log n + 4 vector instructions to set up the divided differences, and log n + 4 vector instructions to evaluate the interpolating polynomial at a given point.