A parallel method for fast and practical high-order newton interpolation |
| |
Authors: | Ö E?ecio?lu E Gallopoulos Ç K Koç |
| |
Institution: | (1) Department of Computer Science, University of California Santa Barbara, 93106 Santa Barbara, CA, USA;(2) Center for Supercomputing Research and Development and Department of Computer Science, University of Illinois at Urbana-Champaign, 61801 Urbana, IL, USA;(3) Department of Electrical Engineering, University of Houston, 77204 Houston, Texas, USA |
| |
Abstract: | We present 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. Forn+1 given input pairs, the proposed interpolation algorithm requires only 2 log(n+1)]+2 parallel arithmetic steps and circuit sizeO(n
2), reducing the best known circuit size for parallel interpolation by a factor of logn. 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. We report on numerical experiments comparing this with other serial and parallel algorithms. The experiments indicate that the method can be very useful for very high-order interpolation, which is made possible for special sets of interpolation nodes.Supported in part by the National Science Foundation under Grant No. NSF DCR-8603722.Supported by the National Science Foundation under Grants No. US NSF MIP-8410110, US NSF DCR85-09970, and US NSF CCR-8717942 and AT&T under Grant AT&T AFFL67Sameh. |
| |
Keywords: | 65D05 65W05 68C25 |
本文献已被 SpringerLink 等数据库收录! |
|