FAST PARALLEL ALGORITHM FOR POLYNOMIAL INTERPOLATION

Authors
JANA PK SINHA BP
Citation
Pk. Jana et Bp. Sinha, FAST PARALLEL ALGORITHM FOR POLYNOMIAL INTERPOLATION, Computers & mathematics with applications, 29(4), 1995, pp. 85-92
Citations number
4
Categorie Soggetti
Computer Sciences",Mathematics,"Computer Science Interdisciplinary Applications
Journal title
Computers & mathematics with applications → ACNP
ISSN journal
08981221
Volume
29
Issue
4
Year of publication
1995
Pages
85 - 92
Database
ISI
SICI code
0898-1221(1995)29:4<85:FPAFPI>2.0.ZU;2-3
Abstract
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(log n) time using n(2) process ors where n is the number of input data points at which the values of the function will be specified. We have also shown how the algorithm c an be extended to the case when only p(2) processors (p < n) will be a vailable. The algorithm mapped on p(2) processors has a time complexit y of O((n(2)/p(2)) log n).