4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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
    Commented Jul 6, 2018 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
    Commented Jul 6, 2018 at 10:08
  • 1
    $\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
    Commented Jul 6, 2018 at 10:52

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\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$
    – Vadim Pelyushenko
    Commented Jul 6, 2018 at 20:47
  • $\begingroup$ Is it known if we can do better in case of finite fields with prime order $p$ and at interpolation points $1, 2, 3, ..., n$? $\endgroup$
    – Somnium
    Commented Jun 21, 2022 at 9:19
  • 1
    $\begingroup$ @VadimPelyushenko it's not general case - the field should have 2N roots of unity. For example GF(2^k) fields doesn't have nontrivial roots of 1 at all $\endgroup$
    – Bulat
    Commented Jun 22, 2022 at 10:45
  • 1
    $\begingroup$ @Somnium we can do better if we do interpolation/evaluation at roots of unity (instead of 1..n) - we can directly use FFT/iFFT in this case with O(n*log n) speed $\endgroup$
    – Bulat
    Commented Jun 22, 2022 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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