A Fast Method for Interpolating Preconditioning

Given $n$ points $(x_{i},y_{i})$ the best algorithms for finding the unique interpolating polynomial $G(x)$ such that $G(x_{i})=y_{i}$ take $O(n^{2})$ arithmetic operations. If the $(x_{i}$ are known in advance then an algorithm for finding $G(x)$ is presented which takes only $O(n(\log n)^{3})$ steps. Also, it is shown how to precompute certain functions of the $x_{i}$, in $O(n^{2})$ steps, such that this restricted interpolation algorithm can be easily used. Finally, it is shown that speeding up the general interpolation problem is possible if one can solve a simpler problem, namely to find a polynomial $G(x)$ such that $G(x_{i})=0$ for $1 \leq i \leq j$ and $G(x_{i})=1$ for $j+1 \leq i \leq n$