拉格朗日插值多项式的一种并行算法

A Parallel Algorithm for Lagrange Interpolation Polynomial

提出在机群系统并行环境下的构造拉格朗日插值多项式的一种并行算法.该算法以n个节点(x0,y0),(x1,y1),…,(xn-1,yn-1)的拉格朗日插值多项式公式为基础.当处理机数量为n2时,它的时间复杂度为3log(n)+O(1);当处理机数量为p2(p<n)时,算法的时间复杂度为O((n2/p2)log(n)).

This paper presents a parallel algorithm for Lagrange's polynomial interpolation which is based on cluster parallel environment. Noticeably, the algorithm is based on the Lagrange interpolation formula for n points of (x_0,y_0), (x_1,y_1),…,(x_(n-1),y_(n-1)) and it requires the 3log(n) +O(1) times while processors are used where is the number of input data points at which the values of the function will be specified. Furthermore,we also know that the algorithm has a time complexity of O((n^2/p^2)log(n)) while p^2(p<n) processors are used.