Fast algorithms for polynomial evaluation and differentiation at special knots

Abstract

We present fast evaluating and differentiating algorithms for the Hermite interpolating polynomials with the knots of multiplicity 2, which are generated dynamically in a field K = (K,+,⋅) by the recurrent formula of the formX^i = αx^i-1+β (i=1,2,..,n-1; x^0=γ).As in the case of Lagrange-Newton interpolating algorithms, the running time of these algorithms is C(n) + O(n) base operations from the field K, where C(n) = O(nlog n) denotes the time needed to compute the wrapped convolution in Kn.