%$OpenXM: OpenXM/doc/compalg/poly.tex,v 1.2 2000/03/28 02:02:30 noro Exp $
\chapter{多項式}

\section{多項式の表現}
整数の場合その一部を取り出して用いることはほとんどないが, 多項式は, そ
の一部 (例えば係数) を多項式あるいは数として取り出す必要がしばしばある. 
従って, その表現も, 用途に応じてさまざまなものが考えられる. ここでは, 
それらの中で{\bf 再帰表現}と {\bf 分散表現} について述べる.

\subsection{再帰表現}
再帰表現とは, 多項式に現れる変数に順序をつけ, その順序に従って, 多項式を
一変数多項式とみなして, その各係数を, この変数順序に従ってさらに分解して
いく表現である. 

\begin{ex}
$(x+y+z)^2 = 1 \cdot x^2 + (2 \cdot y + (2 \cdot z)) \cdot x + ((2 \cdot z) \cdot y + (1 \cdot z^2 ))$
\end{ex}
この表現は, 実際のシステムにおいては最も一般的に用いられる. 特に, 多項
式を, ある変数に関する一変数多項式とみなして進行するアルゴリズムに対し
て有効である. このようなアルゴリズムには, 多項式の四則演算を初めとして, 
多項式の GCD, 因数分解など, 基本的で重要なものが多く, 従って, 内部表現
として再帰表現を採用することは, システムの効率の点から見て自然である. 
ただし, 再帰表現においては, 主変数でない変数に関する係数を取り出す場合
に, 主変数に関する場合に比較して多くの時間がかかるのが難点である. この
ため, 計算に先だって, 異なる変数順序による再帰表現に変換することがしば
しば行なわれるが, 変数, 項の個数が多い場合には, 多くの時間がかかる場合
もある. 

再帰表現を計算機上で実現する場合, 文字通り再帰的な表現となる. ここで, 
主変数を一つ決めれば, その多項式は, その主変数に関する指数と係数のペア
の並びとして表現される. 
  
\subsection{分散表現}

分散表現とは, 多項式を, 単項式の和として表現する方式である. ここで, 
単項式とは, 変数の冪積と係数の積である. 

\begin{ex}
$(x+y+z)^2 = 1 \cdot x^2 + 2 \cdot xy + 2 \cdot xz + 1 \cdot y^2 + 2 \cdot yz + 1 \cdot z^2$
\end{ex}
この場合, 各単項式の順序に不定性があるが,  各変数は平等に扱われる. この表現
は, 後述する グレブナ基底計算において最も好都合な表現形式であり, そこでは
単項式の間の順序が本質的な役割を果たす. これについては, グレブナ基底の
ところで詳しく述べる. 

多項式は, 計算機上ではリスト (木構造) あるいは配列で表現される. 配列表
現の多項式に関しては, 同一次数の係数の取り出しが容易のため, 四則演算の
アルゴリズムは自明である. しかし, リスト表現の場合, 四則演算は, 項の順
序を比較しながら, もし順序が等しい場合には係数に対する演算を行うという
もので, ソーティングの変形と考えられる. ただし, 対象となる多項式は既に
ソートされているため, その性質を利用して効率よく演算を行うことが必要で
ある.

\section{加減算}
配列表現の場合, 加減算は自明である. 

リスト表現の場合, 演算結果リストを空に初期化し, 先頭の項の次数を比較し, 
次数の大きい方の項をそのまま, 演算結果のリストに繋ぎ, もし次数が等しい
場合には, 係数どうしを演算し, それが 0でない場合に演算結果リストに繋ぐ, 
という操作を繰り返す.

\section{乗算}
乗算は, 分配法則により一方の多項式の各単項式ともう一方の多項式の積の和
となるが, 単項式と多項式の積は, 係数は係数どうしの積で, 各項の次数は単
なる平行移動となるため, 一方の多項式の項の個数だけの多項式の和となる. 

\section{冪}
多項式の冪の計算は, 数の場合とは異なり演算の方法により大きく効率が異な
る. 

整数演算の項で述べた冪の 2 進計算法では, 見掛けの乗算の回数は冪指
数の対数程度であるが, 実際には中間に現れる多項式の項の個数が増え, かつ
途中の積における次数の等しい各項の間の演算回数も増えるため, 実際の演算
時間は急激に増加する. このため, 一見効率が悪そうに見える, 二項定理を用
いる方法の方が効率よく冪を計算できる. 即ち, 冪乗すべき多項式を 2つに分
け, 二項定理により冪を計算するのである. この際二項係数が必要になるが, 
ある程度の大きさまで予めテーブルにしておいても良いし, あるいはその都度
計算しても, 素朴な方法に比較して充分高速であ
る. 

\section{除算, 剰余演算}
除算, 剰余演算は, ある変数 (主変数) を決めて, 主変数に関する 1 変数多項式
として行う. 体 $K$ 上の一変数多項式の除算は次のアルゴリズムで計算できる. 

\begin{al}
\begin{tabbing}
\\
Input : $f, g \in K[x]$, $g\neq 0$\\
Output : $f = qg+r$, $q,r \in K[x]$, $\deg(r) < \deg(g)$ なる $q,r$\\
$q\leftarrow 0$, \quad $r\leftarrow f$\\
while \= ( $\deg(r)\ge \deg(g)$ ) \{\\
\> $t \leftarrow \lc(r)/\lc(q)\cdot x^{\deg(r)-\deg(g)}$\\
\> $r \leftarrow r-tg$,\quad $q \leftarrow q+t$\\
\}\\
return $(q,r)$
\end{tabbing}
\end{al}

\section{Karatsuba アルゴリズム}

ここでは, 1 変数多項式の高速乗算法およびその応用について述べる. 既に述
べた方法では, 2 つの $n$ 次の密な多項式の積計算は $O(n^2)$ の計算量
が必要である. 
これに対し, Karatsuba アルゴリズムは $O(n^{\log_23}) \simeq
O(n^{1.58})$ の計算量で積を計算する. さらに計算量の小さい FFT アルゴリズム
については \cite[Section 4.3]{KNUTH} に詳しい解説がある. 

まず, 1 次式 $f=ax+b$, $g=cx+d$ の積は, 係数環における積 3 回で実行できること
に注意する. すなわち, 
$$fg=(ax+b)(cx+d)=acx^2+((a-b)(d-c)+ac+bd)x+bd$$
で, ここに現れる係数環の積演算は, $ac$, $bd$, $(a-b)(d-c)$ の 3 回である.
これを, 高次の場合にも再帰的に適用する. 
\begin{pr}
$2^m-1$ 次式どうしの積は, $O(3^m)$ の計算量で計算できる. 
\end{pr}
\proof
$2^m-1$ 次式どうしの計算コストを $T(m)$ とする. 
係数環における和, 積のコストをそれぞれ $A$, $M$ とする. 
$f$, $g$ を $2^m-1$ 次式とする. 
\begin{center}
$f=f_1x^m+f_2,\quad g=g_1x^m+g_2 \quad (\deg(f_1),\deg(f_2),\deg(g_1),\deg(g_2)<m)$
\end{center}
と書くと, 
$$fg=(f_1g_1x^{2m}+((f_1-f_2)(g_2-g_1)+f_1g_1+f_2g_2)x^m+f_2g_2$$
ここで $fg$ の計算コストは, 高々 $3T(m-1)+3\cdot 2^mA$, すなわち
$T(m) \le 3T(m-1)+3\cdot 2^mA \quad (m\le 1).$
さらに, $T(0)=M$ から
$T(m) \le (M+6A)3^m-6A\cdot 2^m.$ \qed

この命題より, $n$ 次式どうしの積は, $O(n^{\log_23})$ の計算量で計算できる
ことが分かる. 更に詳しく, 通常の $O(n^2)$ アルゴリズムと比較してみよう. 
$2^m-1$ 次式どうしの通常のアルゴリズムによる計算コストを $T_0(m)$ とすれば, 
$T_0(m)=M2^{2m}+A(2^m-1)^2$
である. 
$$T_0(m)-T(m) \ge M2^{2m}+A(2^m-1)^2-((M+6A)3^m-6A\cdot 2^m)$$
で, 右辺の $m=0,\cdots,7$ に対する値は次のようになる. 

\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|} \hline
$m$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline
右辺 & 0 & M-5A & 7M-21A & 37M-65A & 175M-165A & 781M-305A & 3367M-21A \\ \hline
\end{tabular} 
\end{center}

一般に, $M>A$ だから $m \ge 4$ すなわち 15 次式以上の積に対しては, Karatsuba
法は常に高速であり, $M$ が $A$ に比べて大きい場合ほど, 低い次数から Karatsuba
法が効果的であることが分かる. 更に, 計算量のオーダの違い 
($O(n^2)$ と  $O(n^{\log_23})$) により, 高次程 Karatsuba 法が高速になり, 
例えば $M/A=5$ の時, $2^m-1$ 次式の積の通常法と Karatsuba 法の計算コストの
比は次のようになる. 

\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|} \hline
$m$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
計算コスト比 & 1 & 1 & 0.84 & 0.67 & 0.53 & 0.41 & 0.31 & 0.24 & 0.18 & 0.13 & 0.10 \\ \hline
\end{tabular} 
\end{center}

すなわち, 100 次で 4 倍, 1000 次式で 10 倍程度の差がつくことになる. 
Karatsuba 法における, 多項式の分割, 関数呼び出しの手間などが
かかるため, 実際にはこの数字を達成することは難しいが, 多項式の積に
関しては, Karatsuba 法は十分実用的であると言える. 

\section{除算を乗算で行うには?}
既に述べた多項式除算は, 次数 $n$ について $O(n^2)$ の計算量を必要とする. 
これを, より少ない手間で計算するために, 乗算を用いて除算を行うことを
考える. 

\begin{pr}
$f = \sum_{i=0}^n a_ix^i$ を, $a_0\neq 0$ なる多項式とする. 
$g_0 = 1/{a_0}, \quad g_i = 2g_{i-1}-g_{i-1}^2f \bmod x^{2^i}$
とすれば, $g_if \equiv 1 \bmod x^{2^i}.$
\end{pr}

\begin{df}
$n$ 次多項式 $f$ に対し, $f^{*} = x^nf(1/x)$ と定義する. 
\end{df}

\begin{pr}
$f$, $g$ を各々 $n$, $m$ 次 ($n\ge m$) 多項式とし, 
$f=gq+r \quad (\deg(r)<m)$
とする. この時 $tg^{*}\equiv 1 \bmod x^{n-m+1}$ なる $t$ により
$q = (tf^{*} \bmod x^{n-m+1})^{*}.$
\end{pr}
\proof
$f=gq+r$ より 
$x^nf(1/x)=x^mg(1/x)x^{n-m}q(1/x)+x^nr(1/x).$
すなわち 
$f^{*}=g^{*}q^{*}+x^{n-\deg(r)}r^{*}.$
ここで, $\deg(r)<m$ より $n-\deg(r)\le n-m+1.$ よって
$f^{*}\equiv g^{*}q^{*} \bmod x^{n-m+1}.$
よって $tf^{*}\equiv q^{*} \bmod x^{n-m+1}$ となるが, 
$\deg(q)=n-m$ より
$q = (tf^{*} \bmod x^{n-m+1})^{*}.$
\qed\\
$r=f-gq$ より, $q$, $r$ が何回かの乗算で計算できることがわかる.

\begin{itemize}
\item $t$ を求める際に必要な乗算の回数は $\log_2{(n-m)}$ 程度,
\item $t$ が求まっていれば, $q$, $r$ の計算には乗算 2 回で済む. 
\item 乗算に Karatsuba 法 (あるいは FFT 法) を用いることにより $O(n^2)$ より
真に少ない手間で除算が計算できる. 
\item $g$ を法とする演算のように, $g$ が固定の場合, $t$ を 1 回計算して
おけばよいから, $n$, $m$ が大きい時には有効. (50 次程度から効いてくる.)
\end{itemize}