1
$\begingroup$

I am attempting to find a complexity for computing the order polynomial of partially ordered sets on a special family, and have come across the following problem. Assume we have the following values from a polynomial: $P(0)...P(n-k)=0$ and $P(n-k+1)...P(n)=y_{n-k+1}...y_n$: what is the complexity of polynomial interpolation in this environment?

Looking at the Lagrange polynomials, the first n+1-k become 0, and the k last follow a simple form:

$L_i = \frac{\Gamma(x+1)\Gamma(i-n)y_i}{\Gamma(x-n)\Gamma(i+1)(x-i)}$

This suggests to me the coefficients for each x should have some nice form. However I'm a bit lost at this point as to the complexity of computing the $L_i$ (which we need k of), perhaps there is a better method?

Improve this question
$\endgroup$
4
  • $\begingroup$ I'm not sure precisely what it is you're asking. Does replacing $\frac{\Gamma(x+1)}{(x-i)\Gamma(x-n)}$ by $\prod_{j=0, j\ne i}^n (x-j)$ and similar for $\Gamma(i-n)/\Gamma(i+1)$ solve your problem? $\endgroup$
    – Andrew Morgan
    Sep 25 '17 at 14:31
  • $\begingroup$ Sorry my overall question is simply what is the computational complexity of polynomial interpolation with the specifications given above. The rest was my rather unsuccessful attempt to simplify the problem $\endgroup$
    – Max Hopkins
    Sep 25 '17 at 18:50
  • 2
    $\begingroup$ Ah okay. I'm not sure whether it helps here, but if P' is the degree-at-most-(k-1) polynomial that agrees with P on the last k points, then $P = (x)(x-1)\cdots(x-n+k) \cdot P'$. So ignoring the cost of multiplying/dividing by the left factor, finding P is equivalent to arbitrary degree-(k-1) polynomial interpolation, since P' is essentially arbitrary. (All of these operations are computable in polynomial time, but I don't know the exact complexities off-hand.) $\endgroup$
    – Andrew Morgan
    Sep 25 '17 at 19:04
  • $\begingroup$ Yeah that gives O(nlog(n)) using FFT--good, but I wonder if you can do better. $\endgroup$
    – Max Hopkins
    Sep 25 '17 at 20:57

Your Answer

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

Browse other questions tagged or ask your own question.