Fastest Implementation of polynomial interpolation? Suppose I am working over a field $\mathbb{F}$ and have $n$ points in the point-value representation $(x_0,x_1,\cdots,x_{n-1})$. What is the fastest way to do polynomial interpolation and convert this to the coefficient form, that is, obtain the coefficients of polynomial $f()$ such that $f(i)=x_i, i \in \{0,\cdots,n-1\}$ ? Based on my understanding, it would take $O(n^2)$ computations using the Lagrange interpolation method. If the point-value representations were for the roots of unity then we could use FFT to get the coefficients in $O(nlogn)$ but in the general case which is the most efficient method? More specifically, can we do better than $O(n^2)$?
 A: Polynomial interpolation can be done via multiplying a Vandermonde matrix (or its inverse) by your coefficient/evaluation vector --- it is a change of basis on the vector space of polynomials of bounded degree. If this matrix has special structure (such as when the evaluation points are roots of unity --- here the matrix is Toeplitz) this matrix-vector multiplication can be done faster (in $O(n\log n)$ time) this is precisely the FFT. But any choice of evaluation points such that you have fast(er) matrix-vector multiplication algorithms suffices. This might give you a slightly more general question to investigate, which might be useful.
A: In the special case of these evaluation points you can easily get the coefficients to write the polynomial as $\sum_0^{n-1}c_j\binom{x}j$ .
You find this explained here  , among other places. It just involves taking the differences and their differences etc. So for $6,10,7,12$ you would take the differences $4,-3,5$ then $-7,8$ then $15$ Yielding the cubic $$6\binom{x}0+4\binom{x}1-7\binom{x}2+15\binom{x}3.$$
I said easily, not quickly. That is still $O(n^2)$, but just subtractions. And if you want the standard coefficients there is still work to do.
