[TUTORIAL] Basic Lagrange Interpolation pt. 2

Revision en1, by grhkm, 2021-08-22 10:49:39

As promised, here's "interpolating multiple values" in $$$O(n\log^2 n)$$$.

Pre-req: Polynomial multiplication and modulos, basic lagrange interpolation knowledge (you can read my previous post here)

As a reminder, polynomial mod is $$$O(n\log n)$$$.

Main results:

Given $$$f(x)$$$ and $$$x_1, x_2, \cdots, x_n$$$, we can find $$$f(x_1), f(x_2), \cdots, f(x_n)$$$ in $$$O(n\log^2 n)$$$.

Given a bunch of points $$${(x_0, y_0), (x_2, y_2), \cdots, (x_n, y_n)}$$$, we can find a degree $$$n$$$ polynomial $$$f(x)$$$ such that

$$$\forall 0\leq i\leq n, f(x_i)=y_i$$$

Why useful?

It helps you AC problems that you can't with $$$O(n^2)$$$.

It also gives you contribution on CF


Idea 1:

Since the pre-req says polynomial modulo, let's see if we can mod something to calculate some of $$$f(x_1), f(x_2), \cdots$$$ quickly.

It can be seen that we can split the set of $$$x$$$ into two halves — $$$X_0={x_1, x_2, \cdots, x_{\lfloor\frac{n}{2}\rfloor}}$$$ and the rest $$$X_1={x_{\lfloor\frac{n}{2}\rfloor+1}, x_{\lfloor\frac{n}{2}\rfloor+2}, \cdots, x_n}$$$

Now the crucial observation is that if we consider the polynomial $$$g_0(x)=\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor} (x-x_i)$$$, then $$$\forall x\in X_0, g_0(x)=0$$$.

We can then see that polynomial mod helps us, as writing

$$$f(x)=g_0(x)\cdot Q(x)+f_0(x)$$$
$$$f(x)\equiv f_0(x)\mod g_0(x)$$$

Moreover, $$$\forall x\in X_0, f(x)=f_0(x)$$$ and the RHS can be calculated by polynomial mod. It is similar for $$$X_1$$$.

Now just recur and time complexity is $$$T(n)=2T(\frac{n}{2})+O(n\log n)=O(n\log^2 n)$$$.


Idea 2:

Given $$$(x_1,y_1),\cdots,(x_{n+1},y_{n+1})$$$, find a $$$(n-1)$$$-degree polynomial $$$f(x)$$$.

From my first post, we know that

$$$f(x)=\sum_{i=1}^{n+1} \prod_{j\neq i} \frac{x-x_j}{x_i-x_j}y_i$$$

Now look at that denominator $$$\prod_{j\neq i}x_i - x_j$$$. We can think of it as the whole product divided by $$$(x_i-x_i)$$$. We can't divide by zero but limits are cool:

$$$\prod_{j\neq i}(x_i-x_j)=\lim_{x\to x_i}\frac{\prod_{j=1}^{n+1} (x-x_j)}{x-x_i}=\lim_{x\to x_i}\frac{d}{dx}(\prod_{i=1}^{n+1} x-x_j)$$$

We can write $$$P(x)=\prod_{i=1}^{n+1} x-x_j$$$, which can be calculated in $$$O(n\log n)$$$ via divide and conquer. Then $$$P'(x)$$$ can also be found.

Now going back to the original expression, $$$f(x)=\sum_{i=1}^{n+1} \frac{y_i}{M'(x_i)}\prod_{j\neq i}(x-x_j)$$$. Simplifying a bit we shall write $$$v_i=\frac{y_i}{M'(x_i)}$$$ and that $$$f(x)=\sum_{i=1}^{n+1} v_i\prod_{j\neq i}(x-x_j)$$$. I swear this is not becoming a graph problem.

Now let's consider what happens if we try to divide and conquer on this term. By divide and conquering we will get the terms

$$$f_0(x)=\sum_{i=1}^{\lfloor\frac{n+1}{2}\rfloor} v_i\prod_{j\neq i,1\leq j\leq \lfloor\frac{n+1}{2}\rfloor}(x-x_j)$$$

,

$$$f_1(x)=\sum_{i=\lfloor\frac{n+1}{2}+1\rfloor}^{n+1} v_i\prod_{j\neq i,\lfloor\frac{n+1}{2}\rfloor\leq j\leq n+1}(x-x_j)$$$

Comparing those with the $$$f(x)$$$ we want we can notice that the product part in $$$f_0(x)$$$ is missing the later half's terms, so we can "put them back" via multiplying $$$f_0(x)$$$ by $$$M_1(x)=\prod_{\lfloor\frac{n+1}{2}\rfloor\leq j\leq n+1}(x-x_j)$$$. Doing the same for $$$f_1(x)$$$, we get that

$$$f(x)=f_0(x)M_1(x)+f_1(x)M_0(x)$$$

which can then be calculated by divide and conquer.

Also note that $$$M_0(x)$$$ and $$$M_1(x)$$$ is calculated in the process of calculating the original $$$M(x)=\prod (x-x_i)$$$, so those don't require extra time.

Time complexity is $$$O(n\log^2 n)$$$ for similar reasons.


Thank you for reading the post. I'm too lazy to code it up but I still hope this blog helps someone.

I might start working through the "maths blog post recommendation" topics and post a few more blogs~

HKOI
Tags lagrange-interpolation, grhkm, math, number-theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English grhkm 2021-08-23 17:14:14 2 Tiny change: 'n $O(n\log n)$ via d' -> 'n $O(n\log^2 n)$ via d'
en2 English grhkm 2021-08-23 08:38:47 7 Tiny change: ' such that\n\n$$\forall ' -> ' such that $$\forall '
en1 English grhkm 2021-08-22 10:49:39 4192 Initial revision (published)