Fast parallel algorithm for polynomial interpolation

This paper presents a parallel algorithm for polynomial interpolation implemented on a mesh of trees. The algorithm is based on the Lagrange’s interpolation formula. It requires O(logn) time using n² processors where n is the number of input data points at which the values of the function will be specified. The authors have also shown how the algorithm can be extended to the case when only p² processors (p<n) will be available. The algorithm mapped on p² processor has a time complexity of O((n²/p²)logn).