Find a collection of values of polynomial

Question

Given a polynomial $f(x)\in \mathbb C[x]$ where $\deg f(x)=n-1.$ Assume that we need to find a collection of values of this polynomial corresponding to the following set of $x$-values: $\{ e^{ik} \}$ where $k= 0, …, n-1,$ and $i$ denotes the imaginary unit.

There is an algorithm that can solve this problem for any collection of $x$-values using FFT in $O(n\log^2(n)).$ On the other hand, if all $x$-values are $n$ - roots of unity, then FFT can solve the problem in $O(n\log n).$

Question: Is it possible to solve the above problem in $O(n\log n)$ as well?

Answer 1

Hint: Use the equation $e^{ikl}=e^{i\frac{k^2}{2}}e^{-i\frac{(k-l)^2}{2}}e^{i\frac{l^2}{2}}$ and properties of Toeplitz matrices.