多項式補間：アルゴリズム

$n$ 次の多項式の補間を $O(n \log(n)^2)$ で求めるアルゴリズムを紹介します。

ラグランジュ基底の線形結合によって補間は簡単に求まります（ラグランジュ補間）：

ラグランジュ補間：
$x$ 座標の相異なる $n$ 点 $(x_1,f(x_1)), (x_2,f(x_2)), \ldots, (x_n,f(x_n))$ が与えられます。$f$ を $n-1$ 次以下とすると、$f$ は中国剰余定理より一意に定まり、
$$f(x)=\sum_{i=1}^n y_i \prod_{j \neq i}\frac{x-x_j}{x_i-x_j}$$と書けます。このラグランジュ基底の線形結合による補間をラグランジュ補間といいます。

求めたいのは、ラグランジュ基底を単項式に変換した形です。愚直だと $O(n^2)$ で求まります。

各 $i=1,2,\ldots,n$ に対して、$\prod_{j \neq i}(x_i-x_j)$ は $O(n)$ で求まります。$g(x):=\prod_{i=1}^n (x-x_i)$ を求めておけば、各 $i=1,2,\ldots,n$ に対して、$\prod_{j \neq i}(x-x_j) = \frac{g(x)}{x-x_i} $ は $O(n)$ で求まります。両方合わせて、全体で $O(n^2)$ です。

1 アルゴリズム
2 評価点が等差数列のとき
3 評価点が等比数列のとき
4 参考文献

アルゴリズム

$g(x):=\prod_{i=1}^n (x-x_i)$ と置くと、ラグランジュ補間は$$f(x) = g(x)\sum_{i=1}^n \frac{y_i}{g'(x_i)(x-x_i)}$$と書けます。$g(x)$ は分割統治、$g'(x_1), g'(x_2), \ldots, g'(x_n)$ は multipoint evaluation により $O(n\log(n)^2)$ で計算できます。$n$ 個の1次式 $f_1, .., f_n$ は前計算 $O(n\log(n)^2)$ の下で、積 $f_lf_{l+1}\ldots f_{l+d}$ が $O(d\log(d))$ で展開できることを用いて、分割統治で計算してもよいです。

$a_i := y_i / g'(x_i)$ と置きます。サイズ半分の二つの同じ問題に分けられます：$$\sum_{i=1}^n a_i/(x-x_i) = \sum_{i=1}^{\lfloor n/2 \rfloor} a_i/(x-x_i) + \sum_{i=\lfloor n/2 \rfloor + 1}^{n} a_i/(x-x_i)$$それぞれ、分母分子は高々次数 $n/2$ の多項式なので、2つの部分問題の結果を通分するのは $O(n\log(n))$ でできます。$\sum_{i=1}^n a_i/(x-x_i)$ を通分するのに必要な計算量を $T(n)$ とすると漸化式 $T(n) = 2T(n/2) + O(n\log(n))$ が成り立ちます。漸化式を解いて、$T(n) = O(n\log(n)^2)$ です。

全体で $O(n\log(n)^2)$ です。

評価点が等差数列のとき

評価する点が等差数列 $(x_i)=(ai+b)$ のとき、ラジグランジュ補間を用いて、ほかの１点 $x=c$ （定数）の評価を $O(n)$ でできます。$\prod_{j=0,i\neq j}^{n-1} (x_i-x_j) =a^{n-1}(-1)^{n-i}i!(n-i)!$ と $\prod_{j=0,i\neq j}^{n-1} (c-x_j) = \frac{1}{c-x_j}\prod_{j=0}^{n-1} (c-x_j)$ を $i=0,\ldots,n-1$ について列挙するのは、$O(n)$ でできるからです（逆元の計算は $O(1)$ と仮定）。

例題：$1^k+2^k+\cdots+n^k \bmod p$ ($p$ : 素数) を $O(k\log(p))$ で求めてください。

評価点が等比数列のとき

評価する点が等比数列 $(x_i)=(q^i)$ のとき log を一つ落として、$O(n\log(n))$ で多項式補間できます[2]。

$h(x)=\prod_{i=1}^{n/2} (x-q^i)$ とすると、$$q^{(n/2)^2}h(x/q^{n/2})=\prod_{i=1+n/2}^{n} (x-q^i)$$なので、$g(x)$ は $O(n\log(n))$ で求まります。q-2項定理を用いて $O(n)$ で展開することもできます。$g'(q^1),g'(q^2),\ldots,g'(q^n)$ は評価点が等比数列なので、特殊な multipoint evaluation により $O(n\log(n))$ で求まります（アルゴリズム）。$O(n)$ で列挙することもできます（熨斗袋さん）。等比級数の公式により
\begin{align}\sum_{i=1}^n \frac{a_i}{x-q^i} &= \sum_{i=1}^n \sum_j -a_iq^{-i(1+j)} x^j \\ &= \sum_j A(q^{-(1+j)}) x^j \end{align}となります。ただし、$A(x)=-\sum a_ix^i$ と置きました。また、評価点が等比数列になったので、特殊な multipoint evaluation により $O(n\log(n))$ で求まります（アルゴリズム）。以上より、評価点が等比数列の多項式補間が $O(n\log(n))$ でできました。

参考文献

Borodin, Allan, and Robert Moenck. “Fast modular transforms.” Journal of Computer and System Sciences 8.3 (1974): 366-386
- $O(n\log(n))$ の多項式補間が提案された論文
Bostan, Alin, and Éric Schost. “Polynomial evaluation and interpolation on special sets of points.” Journal of Complexity 21.4 (2005): 420-446.
- 等比数列が評価点の時のアルゴリズム