An algebraic approach to approximate evaluation of a polynomial on a set of real points

The previous best algorithm for approximate evaluation of a polynomial on a real set was due to Rokhlin and required of the order ofmu+nu ³ infinite precision arithmetic operations to approximate [on a fixed bounded setX(m) ofm+1 real points] a degreen polynomial $p\left( z \right) = \sum\nolimits_{i = 0}^n {p_i x^i } $ within the error bound $2^{ - u} \sum\nolimits_{i = 0}^n {\left| {p_i } \right|} $ . We develop an approximation algorithm which exploits algebraic computational techniques and decreases Rokhlin's record estimate toO(mlog² u+nmin-u, logn}). For logu=o(logn), this result may also be favorably compared with the record boundO(m+n)log² n) on the complexity of the exact multipoint polynomial evaluation. The new algorithm can be performed in the fields (or rings) generated by the input values, which enables us to decrease the precision of the computations [by using modular (residue) arithmetic] and to simplify our computations further in the case whereu=O(logn). Our algorithm allows NC and simultaneously processor efficient parallel implementation. Because of the fundamental nature of the multipoint polynomial evaluation, our results have further applications to numerical and algebraic computational problems. In passing, we also show a substantial improvement in the Chinese remainder algorithm for integers based on incorporating Kaminski's fast residue computation.     

Accurate evaluation of a polynomial in Chebyshev form

This paper presents a compensated algorithm to accurately evaluate a polynomial expressed in Chebyshev basis of the first and second kind with floating-point coefficients. The principle is to apply error-free transformations to improve the traditional Clenshaw algorithm. The new algorithm is as accurate as the Clenshaw algorithm performed in twice the working precision. Forward error analysis and numerical experiments illustrate the accuracy and properties of the proposed algorithm.