転置原理なしで Monomial 基底から Newton 基底への変換

概要

[1] において解説されている、Newton 基底から Monomial 基底への変換のアルゴリズムを、転置原理無しで説明する。問題は以下の通り。

体 $\mathbb{K}$ 上の $n$ 次未満の多項式 $\displaystyle f(x) = \sum _ {i = 0} ^ {n - 1} c _ i x ^ i$ と、 $n$ 個の値 $p _ 0, p _ 1, \dots, p _ {n - 1}$ が与えられる。 $\displaystyle f(x) = \sum _ {j = 0} ^ {n - 1} d _ j \prod _ {k = 0} ^ {j - 1} (x - p _ k)$ を満たす $d _ 0, d _ 1, \dots, d _ {n - 1}$ を求めよ *1。

これを $\Theta(n (\log(n) ) ^ 2 )$ の時間計算量で解く *2。

$\mathbb{K} ( ( x ^ {- 1} ) )$ と多項式の余り付き除算

$\mathbb{K} ( ( x ^ {- 1} ) )$ は、有限の整数 $n$ と $c _ i \in \mathbb{K}$ に対して $\displaystyle \sum _ {i = - \infty} ^ {n} c _ i x ^ i$ と表されるような形式的な和に対し、自然に和や積を定義することで得られる体である。定義より、 $\mathbb{K}$ 上の多項式は全て $\mathbb{K} ( ( x ^ {- 1} ) )$ に含まれる。 $\mathbb{K} ( ( x ^ {- 1} ) )$ は多項式の余り付き除算と関係していることを説明する。

$f(x), g(x)$ をそれぞれ多項式で $g(x)$ は $0$ でないとする。 $f(x)$ を $g(x)$ で余り付き除算することを考えると、以下のような式を得る。

\begin{align} f(x) &= q(x) g(x) + r(x) \end{align}

ここで $q(x), r(x)$ は多項式であり、 $r(x)$ の次数は $g(x)$ の次数未満である。この式を $\mathbb{K} ( ( x ^ {- 1} ) )$ 上で考えて両辺を $g(x)$ で割ると

\begin{align} \frac{f(x)}{g(x)} &= q(x) + \frac{r(x)}{g(x)} \end{align}

となる。 $g(x)$ の次数を $d$ とすると、 $\frac{1}{g(x)}$ は $x ^ {- d}$ 以下の次数の項しか持たない *3。すると $r(x)$ の次数と併せて、 $\frac{r(x)}{g(x)}$ は $0$ 次未満の項しか持たないことが分かる。一方で $q(x)$ は多項式だから $0$ 次以上の項しか持たず、 $\frac{f(x)}{g(x)}$ の $0$ 次以上, 未満の項と $q(x), \frac{r(x)}{g(x)}$ が完全に対応していることが分かる。 $f(x)$ を $g(x)$ で割った余り $r(x)$ を計算したいときは、 $\frac{f(x)}{g(x)}$ の $0$ 次未満の項を取り出して $g(x)$ を掛ければよいということになる。実際には $-d$ 次から $-1$ 次までの項を計算して、 $g(x)$ を掛けた後 $0$ 次以上の項を取り出せばいい。

転置原理と多項式乗算が絡んだアルゴリズムは、自然な解法を多項式の余り付き除算で書き表して、 $\mathbb{K} ( ( x ^ {- 1} ) )$ を用いて式変形すると等価なものが導出できることがそこそこある。

Monomial 基底から Newton 基底への変換

求めるのは、以下の式を満たす $d _ i$ であった。

\begin{align} f(x) &= \sum _ {j = 0} ^ {n - 1} d _ j \prod _ {k = 0} ^ {j - 1} (x - p _ k) \end{align}

$0 \leq t \lt n$ を満たす整数 $t$ について、両辺を $\displaystyle T _ {t} (x) := \prod _ {k = 0} ^ {t} (x - p _ k)$ で割った余りを取ると

\begin{align} f(x) \bmod T _ t (x) &= \sum _ {j = 0} ^ {t} d _ j \prod _ {k = 0} ^ {j - 1} (x - p _ k) \end{align}

を得る。さらに両辺の $t$ 次の係数を見ると、

\begin{align} \lbrack x ^ {t} \rbrack \left( f(x) \bmod T _ t (x) \right) &= d _ t \end{align}

を得る。前述した議論より、この式の左辺は $\mathbb{K} ( ( x ^ {- 1} ) )$ 上で $f(x) / T _ t (x)$ を計算し、その $0$ 次未満の項のみを取り出して $T _ t (x)$ を掛け、 $t$ 次の係数を取り出すことで計算できる。ここで $T _ t (x)$ が $t + 1$ 次の多項式であることに着目すると、結果の $t$ 次の項に寄与するのは、 $f(x) / T _ t (x)$ の $- 1$ 次の項と $T _ t(x)$ の $t + 1$ 次の項との積だけである。さらに $T _ t (x)$ は monic だから、結局以下の式を得る。

\begin{align} \lbrack x ^ {- 1} \rbrack \frac{f(x)}{T _ t(x)} = \lbrack x ^ {- 1} \rbrack \frac{f(x)}{\prod _ {k = 0} ^ {t} (x - p _ k)} = d _ t \end{align}

$\displaystyle \frac{f(x)}{\prod _ {k = 0} ^ {t} (x - p _ k)}$ を、 $\displaystyle \frac{f(x)}{\prod _ {k = 0} ^ {n - 1} (x - p _ k)}$ に $\prod _ {k = t + 1} ^ {n - 1} (x - p _ k)$ を掛けることで計算すると考える。これを全ての $t$ に対して計算するには、多点評価のアルゴリズムの分割統治のような具合で分割統治を行えばよい。最終的な答えに影響する部分の係数だけを管理すれば、時間計算量は $\Theta(n (\log(n) ) ^ 2 )$ となる。