There's a neater general formula for generating Lagrange interpolator polynomials of any order that avoids having to perform matrix inversion.
Interpolated values can be calculated in O(N) time, so Lagrange interpolation is always faster than FFT interpolation. Calculate the left Product(0..i-1) of each term in left-to-right order. If you carry the value from term to term, you only need one multiplication per term. and the Product(i+1..N-1) of each term in right-to-left order.
Lagrange interpolators with degrees that are close to PiN tend to be smoother, with less aliasing, when processing audio signals. (N=3, 6, 9, 13, &c). Truncating the Langrange polynomial is akin to windowing in FFT. Having an order that's roughly PiN ensures that the analogous window of the Langrange polynomial has smaller tail values.
Walking that back a bit. Given a set of points (x[n],y[n]), the interpolated value can be calculated in O(N^2) time if the x coordinates change, and in O(N) time if only the y values change. For common cases, this means O(N^2) initialization, and O(N) evaluation, even if the Y values change.
This paper is (admittedly) a significant improvement to the method I've been using to date. Probably the most significant improvement is a method for calculating Lagrange polynomials that provide stability guarantees. After having read it, I'm going to point you to that paper, instead of describing how I did it.
The application that I'm familiar with, is interpolation of audio signals, and fractional delay lines. In these cases, x[N] can be considered to have the fixed values [0,1,2,3,...], and then subsequent interpolations can be calculated using an offset into the buffer of audio samples. Initialization takes O(N^2). Evaluation takes O(N).
There's a neater general formula for generating Lagrange interpolator polynomials of any order that avoids having to perform matrix inversion.
Interpolated values can be calculated in O(N) time, so Lagrange interpolation is always faster than FFT interpolation. Calculate the left Product(0..i-1) of each term in left-to-right order. If you carry the value from term to term, you only need one multiplication per term. and the Product(i+1..N-1) of each term in right-to-left order.
Lagrange interpolators with degrees that are close to PiN tend to be smoother, with less aliasing, when processing audio signals. (N=3, 6, 9, 13, &c). Truncating the Langrange polynomial is akin to windowing in FFT. Having an order that's roughly PiN ensures that the analogous window of the Langrange polynomial has smaller tail values.