×

A parallel method for fast and practical high-order Newton interpolation. (English) Zbl 0708.65008

From the authors’ abstract: The paper deals with parallel algorithms for the computation and evaluation of interpolating polynomials. The algorithms use parallel prefix techniques for the calculation of divided differences in the Newton representation of the interpolating polynomial. For \(n+1\) given input pairs, the proposed algorithm requires only \(2\lceil \log (n+1)\rceil +2\) parallel arithmetic steps and circuit size \(O(n^ 2)\), reducing the best known circuit size for parallel interpolation by a factor of log(n). The algorithm for the computation of the divided differences is shown to be numerically stable and does not require equidistant points, precomputation or the fast Fourier transform.
The numerical experiments indicate that the method can be useful for high-order interpolation.
Reviewer: C.Simerská

MSC:

65D05 Numerical interpolation
41A05 Interpolation in approximation theory
65Y05 Parallel numerical computation
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Abramowitz and I. A. Stegun,Handbook of Mathematical Functions, Dover, 1965. · Zbl 0171.38503
[2] A. Bilgory and D. Gajski,A heuristic for suffix solutions, IEEE Trans. Comput., C-35 (January 1986), pp. 34–42. · doi:10.1109/TC.1986.1676655
[3] P. J. Davis,Interpolation and Approximation, Dover, 1975. · Zbl 0329.41010
[4] O. EĞecioĞlu, E. Gallopoulos, and Ç. Koç,Fast and practical parallel polynomial interpolation, Tech. Rep. 646, Center for Supercomputing Research and Development, January 1987.
[5] O. EĞecioĞlu, E. Gallopoulos, and Ç. Koç,Fast computation of divided differences and parallel Hermite interpolation, J. Complexity, (to appear). · Zbl 0689.65003
[6] O. EĞecioĞlu, E. Gallopoulos, and Ç. Koç,Parallel Hermite interpolation: an algebraic approach, Computing, (to appear).
[7] B. Fischer and L. Reichel,Newton interpolation in Fejér and Chebyshev points, Math. Comp., 53 (1989), pp. 265–278. · Zbl 0673.65004
[8] S. Fortune and J. Wyllie,Parallelism in Random Access Machines, in Proc. 10th ACM Symp. Theory of Computing, San Diego, CA., May 1978. · Zbl 1282.68104
[9] G. R. Gao,A stability classification scheme and its application to pipelined solution of linear recurrences, Parallel Comput., 4 (June 1987), pp. 305–322. · Zbl 0626.65021 · doi:10.1016/0167-8191(87)90029-9
[10] E. Horowitz,A fast method for interpolating using preconditioning, IFIP Letters, 1 (1972), pp. 157–163. · Zbl 0297.65005
[11] F. Krogh,Efficient algorithms for polynomial interpolation and divided differences, Math. Comp., 24 (January 1970), pp. 185–190. · Zbl 0198.21101 · doi:10.1090/S0025-5718-1970-0258240-X
[12] C. P. Kruskal, L. Rudolph, and M. Snir,The power of parallel prefix, IEEE Trans. Comput., C-34 (October 1985), pp. 965–968.
[13] H. T. Kung,Fast evaluation and interpolation, Tech. Rep., Department of Computer Science, Carnegie-Mellon University, January 1973.
[14] R. Ladner and M. Fischer,Parallel prefix computation, J. Assoc. Comput. Mach., 27 (October 190), pp. 831–838. · Zbl 0445.68066
[15] A. Macleod,A comparison of algorithms for polynomial interpolation, J. Comput. Appl. Math., 8 (1982), pp. 275–277. · Zbl 0494.65006 · doi:10.1016/0771-050X(82)90051-1
[16] K. Maruyama,On the parallel evaluation of polynomials, IEEE Trans. Comput., C-22 (January 1973), p. 25. · Zbl 0252.65038 · doi:10.1109/T-C.1973.223593
[17] G. P. McKeown,Iterated interpolation using a systolic array, ACM Trans. Math. Softw., 12 (June 1986), pp. 162–170. · Zbl 0608.65008 · doi:10.1145/6497.6500
[18] W. Miller,Computational complexity and numerical stability, SIAM J. Comput., 4 (June 1975), pp. 97–107. · Zbl 0303.65028 · doi:10.1137/0204009
[19] I. Munro and M. Paterson,Optimal algorithms for parallel polynomial evaluation, J. Comput. Sys. Sci., 7 (1973), pp. 189–198. · Zbl 0256.68013 · doi:10.1016/S0022-0000(73)80043-1
[20] L. Reichel and G. Opfer,Chebyshev-Vandermonde systems, Tech. Rep. 88/48, IBM Bergen Scientific Centre, November 1988. · Zbl 0755.65032
[21] J. Reif,Logarithmic depth for algebraic functions, SIAM J. Comput., 15 (February 1986), pp. 231–242. · Zbl 0611.68014 · doi:10.1137/0215017
[22] W. Rönsch,Stability aspects in using parallel algorithms, Parallel Comput., 1 (August 1984), pp. 75–98. · Zbl 0576.65008 · doi:10.1016/S0167-8191(84)90435-6
[23] K. Singhal and J. Vlach,Accuracy and speed of real and complex interpolation, Computing, 11 (1973), pp. 147–158. · Zbl 0263.65009 · doi:10.1007/BF02252904
[24] M. Snir,On parallel search, in Ottawa Conf. Distr. Comput., August 1982.
[25] F. Stummel,Perturbation theory for evaluation algorithms of arithmetic expressions, Math. Comp., 37 (October 1981), pp. 435–473. · Zbl 0515.65039 · doi:10.1090/S0025-5718-1981-0628707-8
[26] H. Tal-Ezer,High degree polynomial interpolation in Newton form, Tech. Rep. 88-39, ICASE, 1988.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.