NEW FAST ALGORITHMS FOR POLYNOMIAL INTERPOLATION AND EVALUATION ON THE CHEBYSHEV NODE SET

For a polynomial p(x) of a degree n, we study its interpolation and ev aluation on a set of Chebyshev nodes, x(k) = cos((2k + 1)pi/(2n + 2)), k = 0, 1, ..., n. This is easily reduced to applying discrete Fourier transforms (DFTs) to the auxiliary polynomial q(w) = w(n)p(x), where 2x = alpha w + (alpha w)(-1), alpha = exp(pi root-1/(2n)). We show the back and forth transition between p(x) and q(w) based on the respecti ve back and forth transformations of the variable: alpha w = (1 - z)/( 1 + z), y = (x - 1)/(x + 1), y = z(2). All these transformations (like the DFTs) are performed by using O(n log n) arithmetic operations, wh ich thus suffice in order to support both interpolation and evaluation of p(x) on the Chebychev set, as well as on some related sets of node s. This improves, by factor log n, the known arithmetic time bound for Chebyshev interpolation and gives an alternative supporting algorithm for the record estimate of O(n log n) for Chebyshev evaluation, obtai ned by Gerasoulis in 1987 and based on a distinct algorithm.