New fast algorithms for polynomial interpolation and evaluation on the Chebyshev node set (Q1129510)

Let \(A=\{\cos((2k+1)/(2n+2))\pi \}_{k=0,\ldots,n}\), the author proves the following results: interpolation to a polynomial of a degree at most \(n\) on the node set \(A\) can be performed by using \(O(n\log n)\) arithmetic operations; a polynomial of degree at most \(n\) can be evaluated on the node set \(A\) at the cost of \(O(n\log n)\) arithmetic operations.