Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of unity, it can be interpolated in $O(n\log n)$ time with the Fast Fourier Transform. Or at least, that's the only situation that I am aware of that can be done better than $O(n^2)$.

Are there any other forms of input that can be interpolated in better than $O(n^2)$ time?

I am particularly interested in knowing whether or not there is an algorithm that interpolates a polynomial from evenly spaced points (in the x-coordinate that is) that beats $O(n^2)$, because I think I've come up with something that does it in $O(n\log n)$ time.

  • $\begingroup$ It’s often irrelevant because interpolation with large n becomes numerically unstable. You really don’t want to put a degree 100 polynomial through 101 points. $\endgroup$
    – gnasher729
    Jul 6 '18 at 10:06
  • $\begingroup$ And evenly spaced isn’t very good. Look up Chebychev or Clenshaw/Curtis (not sure about the names and spelling) $\endgroup$
    – gnasher729
    Jul 6 '18 at 10:08
  • $\begingroup$ @gnasher729 It's perfectly good f.e. in Galois Fields. In particular I used it for fast Reed-Solomon codec: github.com/Bulat-Ziganshin/FastECC - we evaluate order-N polynomial at M points at encoding and then can restore polynomial coefficients from any N survived points. $\endgroup$
    – Bulat
    Jul 6 '18 at 10:52

Fast polynomial interpolation and Fast polynomial evaluation are algorithms that seem to be discovered back in 1973. They allow to interpolate/evaluate polynomial at N arbitrary points as far as field has 2N (?) roots of unity. Both are based on Fast polynomial division. All three are $O(n\log^2 n)$ time.

Currently they are taught at university courses and I downloaded a lot of lecture notes some time ago. Unfortunately, most links are now dead. So you can download my archive from https://mega.nz/#!ugYRXIYB!T_0cKabvJpZmBNN7ym98nofPIOksqTN5XFxToSKj9Zg

Or read the only course still available at the old address: http://people.csail.mit.edu/madhu/ST12/scribe/lect06.pdf http://people.csail.mit.edu/madhu/ST12/scribe/lect07.pdf

Or just look for up-to-date notes among google search results of 1, 2 and 3. Or, yeah, try to understand the original paper.

  • $\begingroup$ So, to clarify, there are already algorithms that can interpolate a polynomial from any arbitrary set of points in $O(n\log^2 n)$, and polynomial interpolation is not in fact $O(n^2)$ in the general case? $\endgroup$ Jul 6 '18 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.