caa a22 4500 465821499 CHVBK 20180323112137.0 cr unu---uuuuu 170327e19900601xx s 000 0 eng 10.1007/BF02017348 doi (NATIONALLICENCE)springer-10.1007/BF02017348 A parallel method for fast and practical high-order newton interpolation [Elektronische Daten] [Ö. EĞecioĞlu, E. Gallopoulos, Ç. Koç] 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. BIT Foundations, 1990 EĞecioĞlu Ö. Department of Computer Science, University of California Santa Barbara, 93106, Santa Barbara, CA, USA aut Gallopoulos E. Department of Computer Science, University of California Santa Barbara, 93106, Santa Barbara, CA, USA aut Koç Ç. Department of Electrical Engineering, University of Houston, 77204, Houston, Texas, USA aut BIT Kluwer Academic Publishers 30/2(1990-06-01), 268-288 0006-3835 30:2<268 1990 30 10543 https://doi.org/10.1007/BF02017348 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02017348 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- EĞecioĞlu Ö. Department of Computer Science, University of California Santa Barbara, 93106, Santa Barbara, CA, USA aut NATIONALLICENCE 700 1- Gallopoulos E. Department of Computer Science, University of California Santa Barbara, 93106, Santa Barbara, CA, USA aut NATIONALLICENCE 700 1- Koç Ç. Department of Electrical Engineering, University of Houston, 77204, Houston, Texas, USA aut NATIONALLICENCE 773 0- BIT Kluwer Academic Publishers 30/2(1990-06-01), 268-288 0006-3835 30:2<268 1990 30 10543 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer