Fast evaluation and interpolation at the Chebyshev sets of points

AbstractStable polynomial evaluation and interpolation at n Chebyshev or adjusted (expanded) Chebyshev points is performed using O(nlog2n) arithmetic operations, to be compared with customary algorithms either using on the order of n2 operations or being unstable. We also evaluate a polynomial of degree d at the sets of n Chebyshev or adjusted (expanded) Chebyshev points using O(d log d log n) if n ≤ d or O((d log d + n) log d) arithmetic operations if n > d