A parallel method for fast and practical high-order newton interpolation
A parallel method for fast and practical high-order newton interpolation
复制标题
一种快速实用的高阶牛顿插值并行方法
作者：
Ö. Eğecioğlu;Efstratios Gallopoulos;Ç. Koç
我们提出了并行算法的计算和评价的插值多项式。该算法使用并行前缀技术的插值多项式的牛顿表示的差的计算。对于n +1个给定的输入对，所提出的插值算法只需要2 [log（n+1）]+2个并行运算步骤和O（n ~ 2）的电路规模，将并行插值的电路规模减小了1/logn。的算法计算的划分差异被证明是数值稳定，不需要等距点，预先计算，或快速傅立叶变换。我们报告的数值实验比较，这与其他串行和并行算法。实验表明，该方法可以非常有用的非常高阶插值，这是可能的特殊集的插值节点。
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(n2), 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.