New fast algorithms for polynomial interpolation and evaluation on the Chebyshev node set
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.
scientific article; zbMATH DE number 1192718