<p>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?</p>

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

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

<p>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?</p>

CC BY-SA 3.0
2017-09-25T14:31:48.457Z
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?
Andrew Morgan
CC BY-SA 3.0
2017-09-25T18:50:58.243Z
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
Max Hopkins
CC BY-SA 3.0
2017-09-25T19:04:01.960Z
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.)
Andrew Morgan
CC BY-SA 3.0
2017-09-25T20:57:31.013Z
Yeah that gives O(nlog(n)) using FFT--good, but I wonder if you can do better.
Max Hopkins
<polynomials><analysis-of-algorithms>
Computational complexity of polynomial interpolation with k non-zero terms
Max Hopkins
# Computational complexity of polynomial interpolation with k non-zero terms

(Asked by: username_0 on 2017-09-24)

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?

**Tags:** polynomials, analysis-of-algorithms
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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  
> **username_1**: 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.)  
> **username_0**: Yeah that gives O(nlog(n)) using FFT--good, but I wonder if you can do better.  

---

## 0 answers

