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)$?
Polynomial Interpolation – Fastest Implementation Techniques
interpolationpolynomials
Best Answer
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.