For Fourier, given an N-dim vector you would compute the N Fourier coefficients in Nlog(N) time, stored in memory, then whenever a new x-value is requested it t

For Fourier, given an N-dim vector you would compute the N Fourier coefficients in Nlog(N) time, stored in memory, then whenever a new x-value is requested it takes linear time to evaluate the point (add up the basis vectors with the stored coefficients). Chebyshev polynomials are more accurate than Fourier. In fact they are the most accurate interpolating polynomials in general. They're not as wildly known, but often used in numerical analysis. The problem with Fourier is that if your function is not periodic, the coefficients do not converge quickly, making the interpolant less accurate for a given number of nodes. Chebyshev gets around this problem, but instead of using equally spaced points, points are spaced out along the uneven "Chebyshev nodes". So to get an interpolated point, say 2.5, 2.5 no longer falls halfway between the 2nd and 3rd Cheb node, you would first have to figure out the value of 2.5 in the nonuniform Chebyshev distribution of points, and then compute the interpolating value in linear time at this point.[1] Both Chebyshev and Fourier are "global" interpolants. As opposed to cubic splines and your other ones. If you change a single value in your vector, the entire interpolant is affected and needs to be recomputed. [1] http://en.wikipedia.org/wiki/Chebyshev_polynomials http://en.wikipedia.org/wiki/Chebyshev_polynomials