数理解析研究所講究録
第 722 巻 1990 年 1-16

$1$

PC-PRS GCD 算法の改良
理化学研究所
理化学研究所1

鈴木正幸 (Masayuki SUZUKI)
佐々木建昭 (Tateaki SASAKI)

はじめに
我々は 2 年前、 PC-PRS GCD と名付けた多変数多項式用の GCD 算法を提案した。 PC-PRS(Power-series Coefficient Polynomial Remainder Sequence) とは、主変数以外の変数をべき級数と見て、各変数およびそれら全体の次数和 (これを項次数と呼ぶ) について、 あらかじめ定めた次数以上の項を切捨てて計算した剰余列のことである。 GCD は与多項式から有理演算だけで計算でき、 しかも余多項式に比べて次数やサイズが小さい。 したがって、 GCD の次数分だけ PRS が計算されていれば、 PRS を全部の次数について計算することなく、 GCD を計算できる。 PRS の最後の要素は余多項式に比べて一般に巨大なものとなるので、 PC-PRS により GCD を計算すれば著しい効率化が期待できる。
我々は PC-PRS GCD 算法を定式化し、 インプリメントしてみた [11。その結果、従来の PRS算法に比べて PC-PRS GCD 算法は著しく高効率であったが、 EZ GCD 算法と比較するとまだ改善の必要を感じた。本論文はその改善等に関するものである。

PC-PRS GCD 算法の計算量は、 GCD に含まれる各変数の次数上限と係数部の項次数上限をいかに見積もるかに大きく依存する。 GCD の各変数に関する次数上限は与えられた多項式を一変数多項式に写影して簡単に求めることができるが、係数部の項次数上限を [1] の理論に基づいて求めると、$\bullet$$\bullet$

項次数の見積りが高くなることが多い。
項次数自身の計算に (主係数間の)GCD が必要なため、時間がかかることがある。

という欠点がある。

経験上は、 GCD の係数部の項次数を、各従変数の次数上限の中で最大のもの程度に見積もれば十分であることが多い。 こうすれば、 PC-PRS GCD 算法に比べ、項次数上限を大きく下げて計算できることになり、効率が大きく改善される。例えば、表 1 に、 [11 の問題 IV に対しどの程度効率が改良されるのかを示した。

1

り[1] の問題 IV.

$G=( \sum_{i=1}^{n}x_{i}+1)^{m},$$P_{1}=G \cdot(\sum_{i=1}^{n}\sum_{j\neq i}^{n}\{x_{i}(x_{j}-1)\}^{m}),$$P_{2}=G \cdot(\sum_{i=1}^{n}\sum_{j\neq i}^{n}\{x_{i}(x_{j}^{2}+1)\}^{m})$PC-PRS (1):GCD の項次数上限として従変数の最大次数を選んだもの ($G$の項次数と一致する)。

PC-PRS (2): [1] の理論を用いて計算したもの (理論上限値は最右の$E$列に示した)。

表 1: 項次数上限の違いによる PC-PRS GCD 算法の効率比較

2

.

3

PC-PRS GCD 算法の項次数上限をこのように変更すれば、効率が大きく改善されることが分かるが、 しかし、 この見積りは小さ過ぎることがあり、 その場合に項次数の上限を増やし PCPRS GCD 算法で最初から GCD を再計算するのでは最初の計算を無駄にする。 そこで、本論文では、 PC-PRS GCD 算法で項次数$e$まで計算された多項式から、 GCD $G$ を構成する方法を検討する。
一つは Hensel 構成 [2] を使う方法である。 PC-PRS GCD 算法により GCD $G$ が項次数で求められているということは、従変数を $y,$$\cdots,$ $z$$e$まとすれば、多項式の法を $S=(y, \cdots, z)$ に取り、 G(mod Se+l) が求められていることになる。 したがって、 Hensel 構成を用いて項次数 e ま
での $G$ より項次数 $e+1$ までの $G$ が構成できることがわかる。

もう一つの方法は、関係式 $P_{k}=A_{k}P_{1}+B_{k}P_{2}$ を用いて、項次数$e$まで求められた$P_{k}$

を項

次数 $e+1$ まで持ち上げるものである。 この方法は簡単でありながら、従来検討されることがな

かった方法であり、本論文で検討する。 この方法では、 Hensel 構成に必要な$G_{0}\equiv G(m\alpha 1q, S)$$F=G\cdot H$ のときと $H_{0}\equiv H(mod q, S)$ が互いに素” という条件が不要なため、簡単で効率的な算法を作ることができる。
さらに、 この算法では$A_{k}$と$B_{k}$

を同時に求めることもできる。 これらが効率的に求められれ

ば、不定積分の低減化や代数的数の逆元など、 $gcd(P_{1}, P_{2})=AP_{1}+BP_{2}$ を満たす $A$ と $B$ を計算する必要のある算法の効率化にも役立つと思われる。

2 記法と注意
本論文を通じて用いる記法と前提事項について説明する。 $P,$ $G,$y,$\cdots$は、主変数が

$x$

、

係数が

, z の多項式とする。 [I] では GCD の係数部の項次数上限を定めるために項次数と各変数の次数の両方を使っていたが、 本章では項次数だけを用いて議論する。 また、 剰余列は精度の低下が起こらないように計算されるものとする。つまり、剰余列の各君の主係数が定数項を持つように前処理してから計算するものとする。 この処理により、 GCD および構成時に必要となる主係数同士の GCD は定数項を持つ。

以後、以下の記法を用いる。

$[P]_{e_{l}^{h}}^{e}$$\lceil P\rceil^{e}$$\lfloor P\rfloor_{e}$$P^{\overline{e}}$$P_{\underline{e}}$$P_{\overline{\underline{e^{e_{l^{h}}}}}}$$A\equiv eB\llcorner$に含まれるの部分多項式を取り出す演算。
: 係数の各項の項次数が
の略記
:
の略記
:
と等しい多項式を表す名前。
: 各係数部が項次数 以下で、と等しい多項式を表す名前。
: 各係数部が項次数 以以上上で、と等しい多項式を表す名前。
: 各係数部が項次数 と の間にあって、との各係数部が項次数 まで等しいことを表す。
:$P$$[e_{l}, e_{h}]$$[P]_{0}^{e}$$[P]_{e}^{\infty}$$e$$\lceil P\rceil^{e}$$e$$\lfloor P\rfloor_{e}$$e_{l}$$A$$B$$[P]_{e_{l}}^{e_{h}}$$e_{h}$

$e$

3

4

GCD 計算のあらすじ 項次数 $e+1$ 以上の係数項を$0$と置いて計算した PRS(多項式剰余列) を、$(P_{1^{\overline{e}}}, P_{2^{\overline{e}}}, \cdots, P_{k}^{\overline{e}}\neq 0, P_{k+1^{\overline{e}}}=0)$とする。 $e\geq$ tdeg(G) であれば、$P_{i}^{\overline{e}},$$i=1,$$\cdots,$,$k-1$ , で精度の低下が起きていない場合、が真の GCD を与える。 しかし $e<t\deg(G)$ の時には

$P_{k}^{\overline{e}}$$P_{k}^{\overline{e}}$は $G$ を与えず、 その時に次の二通りの場合がある。
$\bullet$$P_{k+1}$

が実は$\bullet$$P_{k+1}$

は

$0$

$0$

ではない場合。

であるが、$P_{k}^{\overline{e}}$の係数の項次数上限が小さ過ぎる場合。

$e$

これらを考慮して、 GCD を求める算法のあらましは次のようになる。

Step 1. 剰余列計算により、
Step 2.

$P_{k}^{\overline{e}}$$P_{k}^{\overline{e}}\neq 0,$

から GCD の候補$\tilde{P}$$P_{k+1^{\overline{e}}}=0$

を計算する

となる

$P_{k}^{\overline{e}}$を PC-PRS GCD 算法により求める。

$(\tilde{P}=\gamma P_{k}^{\overline{e}}, 1c(\tilde{P})=g$となるように主係数の調整を行なう)。
$G^{\overline{e}}=pp(\tilde{P})$Step 3.

$P_{k-1}^{\overline{e+1}}$とStep 4.

$P_{k+1^{\overline{e+1}}}$

が

へ

と置き、
$P_{k}^{\overline{e+1}}$$0$$G^{\overline{e}}|P_{1}$かつ$G^{\overline{e}}|$凸ならを構成し、除算により$G^{\overline{e}}$$P_{k+1}^{\overline{e+1}}$が求める GCD である。

を構成する。

なら $earrow e+1$ とし、そうでなければ $earrow e+1,$ $karrow k+1$ として、 Step 2.

$0$

Step 3. の$P_{k}^{\overline{e+1}}$の構成には Hensel 構成と、拡張された Euclid の公式 $P_{k}=A_{k}P_{1}+B_{k}P_{2}$ を用いる構成 (以後、拡張 Euclid 構成と呼ぶことにする) の二通りの方法がある。以下、 この二つの構成方法とこれらの構成方法を用いた GCD 算法について説明する。

3 Hensel 構成の利用
今 $P_{1}=P=G\cdot H$ であり、良く知られているように$P_{k}^{\overline{e}}$$G^{\overline{0}}$$G^{\overline{0}}$がわかっているとする。

$G^{\overline{0}}$と$H^{\overline{0}}$が互いに素であるなら、から $G$ が構成できる。 PC-PRS GCD 算法では、$P_{k}^{\overline{e}}\equiv eG^{\overline{e}}$となるが求められていて、 これから G を Hensel 構成する。

3.1 Hensel の補題
まず Hensel の補題の証明を PC-PRS GCD 算法とつなげられるように書き直し、計算上の注

意点を述べる。

5

ある整数

$e$

に対

(1)

,

(2)

$Pe+1\equiv G^{\overline{e+1}}H^{\overline{e+1}}$$|_{\}}$$|$となる$G^{\overline{e+1}}$と$H^{\overline{e+1}}$が構成できる。

証以こ明下とにの項より x得ら+れ以る上と。すの項る。に分まずけて考はえを、そるべ。れぞ級れ数係数、の多項と式表除す算によとり、を満たす$G_{\underline{e+1}}^{\overline{e+1}}$と$H_{\underline{e+1}}^{\overline{e+1}}$が構成できる。 このを求めれば、

は次のように求められる。今、$G^{\overline{0}}$と$A_{0}^{\overline{0}}G^{\overline{0}}+B_{0}^{\overline{0}}H^{\overline{0}}=1,$$H^{\overline{0}}$は互いに素で、主変数$\deg(A_{0}^{\overline{0}})<\deg(H^{\overline{0}}),$$x$$\deg(B_{0}^{\overline{0}})<\deg(G^{\overline{0}})$$X^{:\overline{0};\overline{0}_{H=x}}G_{A_{0}^{\overline{e}}}\text{と_{}G^{H_{+}^{\overline{e}}\text{より、}G_{\overline{0}}^{\overline{e+1}}\text{と}H^{\overline{e+1}}}}$

$x$

の多項式

$A_{0}^{\overline{0}}$と$B_{0}^{\overline{0}}$が存在する。 この式の両辺に$x^{i}$$G_{\underline{e+1}}^{\overline{e+1}}$だけの多項式であるから、

$|$

となる

の係数部を RG; を項で割次数るをかけると、,と$H_{\underline{e+1}}^{\overline{e+1}}$

6

となるが、

$x^{i}A_{0}^{\overline{0}}$と$H^{\overline{0}}$に対しては$\deg(R_{i}^{\overline{0}})<\deg(H^{\overline{0}})$$x^{i}A_{0}^{\overline{0}}=Q_{i^{\overline{0}}}H^{\overline{0}}+R_{i}^{\overline{0}},$,となる除算が有理数体上で可能であるから、$R_{i}^{\overline{0}}G^{\overline{0}}+\{Q_{i^{\overline{0}}}G^{\overline{0}}+x^{i}B_{0}^{\overline{0}}\}H^{\overline{0}}=x^{i}$を得る。 したがって、$A_{i}^{\overline{0}}=R_{i\text{、}}^{\overline{0}}B_{i}^{\overline{0}}=Q_{i^{\overline{0}}}+x^{i}B_{0}^{\overline{0}}$

,

と置くど、

$P_{\underline{e+1}}^{\overline{e+1}}= \sum_{i=0}^{d}C_{i_{\underline{e+1}^{X}}}^{\overline{e+1}i}$$= \sum_{i=0}^{d}C_{i_{\underline{e+1}}}^{\overline{e+1}}(A_{i}^{\overline{0}}G^{\overline{0}}+B_{i}^{\overline{0}}H^{\overline{0}})$

$=$

以上より、

$H_{\underline{e+1}}^{\overline{e+1}}= \sum_{i=0}^{d}C_{i_{\underline{e+1}}}^{\overline{e+1}}A_{i}^{\overline{0}},$$( \sum_{i=0}^{d}C_{i_{\underline{e+1}}}^{\overline{e+1}}A_{i}^{\overline{0}})G^{\overline{0}}+(\sum_{i=0}^{d}C_{i_{\underline{e+1}}}^{\overline{e+1}}B_{i}^{\overline{0}})H^{\overline{0}}$$G_{\underline{e+1}}^{\overline{e+1}}= \sum_{i=0}^{d}C_{i_{\underline{e+1}}}^{\overline{e+1}}B_{i}^{\overline{0}}$$\deg(H_{\underline{e+1}}^{\overline{e+1}})$$<$$\deg\{G_{\underline{e+1}}^{\overline{e+1}})$$=$.

と置けばよい。 これらの次数は$\deg(H^{\overline{0}})$$\deg(G^{\overline{0}})$

,

.

口

注 3.1 この補題で項次数の演算を行なっているところは、

計算、$P-G^{\overline{e}}\cdot H^{\overline{e}}$のところだけであ. る。

$\lceil 1c(P)\rceil^{0}\neq 0$$\lceil P\rceil^{e}$をびで割るところと、の条件があるので、$P_{\underline{e+1}}^{\overline{e+1}}$$H^{\overline{0}}\neq 0$$G^{\overline{0}}\neq 0$

、

の

で

あり、 この計算で精度の低下が起こることはない。 口

この補題による構成では$1c(H^{\overline{e+1}})=1c(H^{\overline{e}})$て、一般にこの構成を繰り返して得られる$uG,$ $u\in Z${$y,$ $\cdots$

だが、一般に$G^{\overline{\infty}}\equiv\tilde{G}$$1c(G^{\overline{e+1}})\neq 1c(G^{\overline{e}})$となる。 したがっは $P$ の因子 $G$ とは単元倍の違いがある:$\tilde{G}=$, z} 。すなわち、 いわゆる主係数問題が起こる。

3.2 主係数問題の回避法
前節で述べたように、 Hensel 法で構成されるのは $G$ と $H$ ではなく、 $uG$ と $vH$

1 、であり、主係数の不定性がある。

$G$、

ただし $uv=$の主係数があらかじめわかっでいれば、 その不定性をなくすように構成できる。 その方法について簡単に復習し、項次数の記法で書き直す。
問題点は、 $d=\deg(P)$ として、

$x^{d}=A_{d}^{\overline{0}}G^{\overline{0}}+B_{d}^{\overline{0}}H^{\overline{0}}$を満足する$A_{d}^{\overline{0}}kB_{d}^{\overline{0}}$がユニークに決められないことである。今、 $\tilde{g}=gcd(1c(P_{1}), 1c(P_{2}))$ とすると、 $1c(G)|\tilde{g}$ である。 そこで、 $G$ の代わりに、$1c(\tilde{G})=\tilde{g}$かつ$G|\tilde{G}$なる$\tilde{G}$を求めることにすれば、構成すべき多項式の主係数がわ$r_{\ell}$

かっていることになる。 つまり、 $G,$ $H,$ $P$ のかわりに,$\tilde{G}^{\overline{e}}\equiv e\lceil\tilde{g}\rceil^{e}G^{\overline{e}}/1c(C^{\overline{e}})$$\tilde{H}^{\overline{e}}\equiv^{e}1c(P^{\overline{e}})H^{\overline{e}}/1c(H^{\overline{e}})$,,$\tilde{P}=\tilde{g}P$なる$\tilde{G}$,$\tilde{H}$および$\tilde{P}$を構成すれば良い。 このに対し Hensel 構成を行ない、$\tilde{P}$$G^{\overline{e}}$の主係数を$\lceil\tilde{g}\rceil^{e}$にそろえれぽ、 G が構成できる。 この算法は EZ 構成と呼ばれている。 これらの計算が項次数 eまでの精度で行なわれるためには 9 に項次数

3.3

$e$

までの精度があることが必要である。

$PC- PRS+Hensel$ GCD 算法の性能

PC-PRS 算法と Hensel 構成の合成算法を以後 PC-PRS $+Hensel$ GCD 算法と呼ぶことにする。 この算法は数式処理システム GAL 上に、 [I] で述べた PC-PRS

GCD を用いて実現した。

項次数上限による打ち切りは、 GAL のべき級数計算機構を用いて実行している。三変数以上の多項式の GCD を計算する場合には、項次数を表すために新たな変数を導入している。 PRS を求めるための公式としては縮小 PRS のものを用いている。入力多項式の係数が定数項を持つよう\epsilon 、変数変換により前処理する。 また主変数は最も高い次数を持つ変数を選んでいる。次数上限をできるだけ下げる方が、 PRS の長さを短くすることより効率的であると考えられるからである。 もし、 $1c(P_{1})=$ 定数あるいはり、次数上限を$P_{1}$と$P_{2}$$1c(P_{2})=$定数の時は次数上限が最悪の時であり、 この時に限の主変数に関して最低次数の項によって決めている。

表 2 と 3 は PC-PRS $+Hensel$ GCD および REDUCE に装備されている二つの GCD 算法の実行速度である。 (単位はミリ秒)。

$P_{1},$$P_{2}$,

G の多項式の大きさを表中のする各列に示す。表の一列目の $X-(i_{n}, i_{m})$ における

$i_{n}$$P_{1},$と鰯は問題 $X$ の中の$n$$P_{2},$$G$に対応と $m$ の値を意味する。 GAL は Cambridge Lisp 上のもの、 REDUCE は SLISP 上のものである。計算機は FA-

COM M780 である。
ここで用いたテスト問題では、 いずれも

$G_{0}$と$H_{0}$

が互いに素になる。 GCD の主変数に関す$i=1,2$ の次数の約半分であり、る次数を 4 と表すと、 これらの問題では 4 は与多項式$PC- PRS+Hensel$ GCD 算法の場合の Hensel 構成の回数は係数部の項次数で決まり、問題 I と問
題 II でそれぞれ回である。
回、$P_{1},$$d_{g}$、$2d_{g}$PC-PRS $+Hensel$ GCD 算法で純粋な PRS 計算の時間と Hensel 構成に要する時間を、表の(PRS) と (Hensel) の列に示した。残りの時間は、前後処理 (変数変換、項次数の見積り、項次数を表す変数の導入など) に費やされている。問題 I については、 Hensel 構成に要する時間は 1/3程度であり、問題 II については約半分を占めるようになる。問題の次数が高くなるにつれて、PRS の計算時間の占める割合は大きくなる。
これらの問題では、 ほとんどの場合について GAL 上の PC-PRS $+Hensel$ GCD 算法が EZ

GCD 算法を上回る結果を示している。 Hensel 構成の回数が少ない問題 I の方が $PC- PRS+Hensel$

8

問題

$L$

,

$G=\Sigma_{l=1}^{m}(\Sigma_{i=1}^{n}x_{i}^{l}+\Sigma_{i\neq j}^{n}x_{i}^{l}x_{j}^{l})$$P_{1}=G\cdot(1+2x_{1}+\Sigma_{l=1}^{m}(\Sigma_{i=1}^{n}x_{i}^{l}))$,$P_{2}=G\cdot(1+\Sigma_{l=1}^{m}\Sigma_{i=1}^{n}x_{i}^{l+1})$$E$はヒューリスティックに決めた $G$ の項次数上限値である。

表 2: $PC- PRS+Hensel$ GCD 算法の実行速度 $-(1)$問題皿.
$G=\Sigma_{l=1}^{m}(\Sigma_{i=1}^{n}x_{i}^{l}+\Sigma_{i\neq j}^{n}x_{i}^{l}x_{j}^{l}+\Sigma_{1\neq j\neq k}^{n}x_{i}^{l}x_{j}^{l}x_{k}^{l})$$P_{1}=G\cdot(1+2x_{1}+\Sigma_{l=1}^{m}(\Sigma_{i=1}^{n}x_{i}^{l}))$,,$P_{2}=G\cdot(1+\Sigma_{l=1}^{m}\Sigma_{i=1}^{n}x_{i}^{l+1})$

表 3: $PC- PRS+Hensel$ GCD 算法の実行速度-(2)$q$

GCD 算法に有利という結果が出ているが、 二つの問題で PRS 計算に要する時間はほぼ同じであるので、 これは我々の Hensel 構成プログラムにまだ改良の余地があるということを意味する。
次数の増加に対する計算時間の増加の割合は、 $PC- PRS+Hensel$ GCD 算法の方が大きい。 この
理由は二つ考えられる。一つは、項次数を表すために余分な変数を導入していることであり、 もう一つは数係数の膨張である。 これらについては、 今後の改良点にしたい。

4$A_{k}P_{1}+B_{k}P_{2}=P_{k}$Hensel 構成の欠点はを利用した構成 (拡張 Euclid 構成)$G^{\overline{0}}$と$H^{\overline{0}}$が互いに素な多項式でなければならないことである。 そのため、 Hensel 構成に基づく EZ GCD 算法では、与式をまず無平方分解することで、互いに素なと$H^{\overline{0}}$$G^{\overline{0}}$が作れるように前処理を行なっているが、 PC-PRS GCD 算法と組み合わせるにはこの方法は効率的ではない。 これに対し、以下で述べる構成方法は必要とせず、任意の

$k$

にっいて

$P_{k}^{\overline{e}}$を$P_{k}^{\overline{e+1}}$$G^{\overline{0}}$と$H^{\overline{0}}$が互いに素という条件をにリフティングできるものである。 したがって GCDの構成にも使え、 Hensel 構成よりも一般的な方法である。 この構成方法を拡張 Euclid 構成と呼ぶことにする。

4.1 拡張 Euclid 構成のための定理
拡張 Euclid 構成のための定理を示す。

定理 4.1 与多項式

$P_{1}$と $P_{2\text{、}}P_{i}\in Z[y, \cdots, z][x],$ $i=1,2$、$P_{k}^{\overline{0}}\equiv 0A_{k}^{\overline{0}}P_{1}+B_{k}^{\overline{0}}P_{2}$

に対し、

,

$\deg A_{k}^{\overline{0}}<\deg(P_{2})-\deg(P_{k}^{\overline{0}})$

(3)

,
,

$\deg B_{k}^{\overline{0}}<\deg(P_{1})-\deg(P_{k}^{\overline{0}})$を満たす$P_{k}^{0},$$A_{k}^{0},$$B_{k}^{0}$がわかっているとする。 これより、任意の正の整数$P_{k}^{\overline{e}}\equiv eA_{k^{\overline{e}}}P_{1}+B_{k}^{\overline{e}}P_{2}$

$e$

に対し、

,
,
,

$\deg A_{k^{\overline{e}}}<\deg(P_{2})-\deg(P_{k}^{\overline{e}})$$\deg B_{k}^{\overline{e}}<\deg(P_{1})-\deg(P_{k}^{\overline{e}})$$P_{k}\equiv 0P_{k}^{\overline{e}}$$A_{k}^{\overline{0}}\equiv 0A_{k^{\overline{e}}}$$B_{k}^{\overline{0}}\equiv 0B_{k}^{\overline{e}}$となる$P_{k}^{\overline{e}},$$A_{k^{\overline{e}}},$$B_{k}^{\overline{e}}$,,を構成できる。

証明拡張された Euclid の定理より $P_{k}=A_{k}P_{1}+B_{k}P_{2}$ を満たす

を満たす

$P_{k}^{\overline{e}}$と$A_{k}^{\overline{e}},$(4),$B_{k}^{\overline{e}}$$A_{k}$と$B_{k}$が存在するので、 (4) 式が存在するのは明らか。証明は項次数に関する数学的帰納法による。

$\ovalbox{\tt\small REJECT} 9$

10

仮定より、

構成すべき

$P_{k}^{\overline{0}},$$A_{k}^{\overline{0}},$と$P_{k}^{\overline{e+1}}$$B_{k}^{\overline{0}}$が得られている。今、$A_{k}^{\overline{e+1}},$$B_{k}^{\overline{e+1}}$$P_{k}^{\overline{e}}$の各係数を項次数$e$と$A_{k^{\overline{e}}},$$B_{k}^{\overline{e}}$が構或できていると仮定する。

以下の項と $e+1$ の項に分けて考える。

,$B_{k}^{\overline{e+1}}A_{k}^{\overline{e+1}}==B_{k}^{\overline{e}}+BA_{k}^{\overline{e}}+A_{\frac{\underline{\overline e+1+1}}{\underline e+1e+1}}^{e}$,$P_{k}^{\overline{e+1}}=P_{k}^{\overline{e}}+P_{\underline{e+1}}^{\overline{e+1}}$

すると、$P_{k}^{\overline{e+1}}e+1\equiv$$(A_{k^{\overline{e}}}+A_{\underline{e+1}}^{\overline{e+1}})P_{1}+(B_{k}^{\overline{e}}+B_{\underline{e+1}}^{\overline{e+1}})P_{2}$.

$P_{k}^{\overline{e}}+[(A_{k^{\overline{e}}}P_{1}+B_{k}^{\overline{e}}P_{2})]_{e+1}^{e+1}+A_{\underline{e+1}}^{\overline{e+1}}\lceil P_{1}\rceil^{0}+B_{\underline{e+1}}^{\overline{e+1}}\lceil P_{2}\rceil^{0}$$\equiv$

したがって、 次式を得る。
$P_{\underline{e+1}}^{\overline{e+1}}e+1\equiv A_{\underline{e+1}}^{\overline{e+1}}\lceil P_{1}\rceil^{0}+B_{\underline{e+1}}^{\overline{e+1}}\lceil P_{2}\rceil^{0}+[(A_{k}^{\overline{0}}P_{1}+B_{k}^{\overline{0}}P_{2})]_{e+1}^{e+1}$$\deg(P_{e+,=^{\iota}}^{\overline{e+1}})\leq\deg(P_{k}^{\overline{0}})$$\deg(A_{e+1,=}^{e+1})\leq\deg(A_{k}^{\overline{0}})$$\deg(\prime B_{\underline{e+1}}^{e+1})\leq\deg(B_{k}^{\overline{0}})$

この式を満たす
注 4.1$A_{k}$

や$B_{k}$$A_{\underline{e+1}}^{\overline{e+1}}$$B_{\underline{e+1}}^{\overline{e+1}}$

’

,

,

,

.

および P 甜は、副剰余列算法 [3] によって求めることができる。

$\square$は一般に大きな多項式となるので、 この方法は一見すると効率が悪そうに見える。 しかし、我々が欲しいのは tdeg $(G)$ までの項次数の際に現れる多項式は$A_{i}^{\overline{0}},$$B_{i}^{\overline{0}},P_{i}^{\overline{0}},$$A_{\underline{e+1}}^{\overline{e+1}},$だけである。 したがって、$B_{\underline{e+1}}^{\overline{e+1}}$$A_{k}^{\overline{e}}$と$B_{k}^{\overline{e}}$であり、副剰余列を計算する, P;ll 、つまり係数部の項次数がP–e–e++ll を求めるための計算量はそう多くない。

$0$と $e+1$ の多項式

口4.2 拡張 Euclid 構成 GCD 算法の性能
この算法は数式処理システム GAL 上で実現した。項次数上限による打ち切りを必要とする計算には、 GAL のべき級数計算機構を用いている。 三変数以上の多項式の GCD を計算する場
合には、 係数部の項次数を表すために新たな変数を導入している。 入力多項式の係数が定数項を持つように、変数変換により前処理する。 また主変数は最も高い次数を持つ変数を選んでいる。

PC-PRS GCD 算法とつなげる意味と、係数の項次数を低くすれば数式膨張が抑えられて効率的であると考えられるからである。 また、係数の項次数が低ければ拡張 Euclid 構成の回数も少なくて済む。 なお、以下の性能評価は、純粋に拡張 Euclid 構成だけで GCD を求める算法についてである。 すなわち、 まず$P_{k}^{\overline{0}}$と$A_{k}^{\overline{0}},$$B_{k}^{\overline{0}}$を計算し、 これらから拡張 Euclid 構成で$P_{k}^{\overline{e}}A_{k^{\overline{e}}},$$B_{k}^{\overline{e}}$を構成する方法である。 こうすることで、拡張 Euclid 構成の効率と Hensel 構成の効率を比較することができる。
$-$

10

11

表 4 から表 7 は、 [11 の問題 I から IV に対し、純粋に拡張 Euclid 構成だけで GCD を求めた場
合と、 二つの PC-PRS GCD 算法で求めた場合、 そして REDUCE に装備されている二つの GCD

算法の実行速度の比較である。 (単位はミリ秒)。

に関する情報を表申の$G$に対応する各列に示す。表の一列目の $X-(i_{n}, i_{m})$ におけるらと嘱は問題 $X$ の中のパラメータ$n$$P_{1},$$P_{2},$$G$$P_{1},$$P_{2},$と $m$ の値を意味する。拡張 Euclid 構成算法および二つの PC-PRS GCD 算法は Cambridge Lisp

上の GAL システムで実現したものであり、 REDUCE は SLISP 上のものである。計算機は FA-

COM M780 である。
[11 の問題 I この問題に対しては、 PC-PRS 算法が最も良い結果を得ている。拡張 Euclid 構成算

法は、 PC-PRS GCD 算法の約 2 倍程度の時間がかかっている。 EZ GCD 算法と拡張 Eu-

clid 構成算法を比べると、変数の次数の低いところでは拡張 Euclid 構成算法が速いが、途中で逆転し、次数が高くなるとその差は大きくなる傾向にある。
注 4.2 PC-PRS (1)、すなわち項次数上限として従変数の最大次数を選ぶ PC-PRS 算法、 は

今の場合、最適の項次数上限で計算することになり、係数部をリフティングする必要はな
い。 このことは、 [1] の問題 $II\sim IV$ に対しても同じである。 口[11 の問題皿 この問題についても、 [11 の問題 I と同じ傾向が見られる。
[1] の問題 III この問題には構成法が有利である。 EZ GCD 算法と拡張 Euclid 構成算法を比べると、次数の低いところでは拡張 Euclid 構成算法が速いが、 3 次の所で逆転し、次数が高くなるとその差はわずかに大きくなる傾向にあるが、 [1] の問題 I ほどではない。
注 4.3 PC-PRS (1) と (2) は今の場合、 同じ項次数上限で同じ計算をするが、 (1) の方が (2)より効率的になる理由は、 (2) では項次数上限の計算に多大な時間がかかるからである。
口[1] の問題 IV この問題に対しては、 三つの算法がそれぞれ異なる傾向を見せている。 まず、 PC-

PRS GCD 算法は変数の数によらず、低次数のところで良い結果を得ている。拡張 Euclid
構成算法は、変数の個数が多い方が良い結果を得ている。 EZ GCD 算法は、変数の個数が少ない方が、 また次数が高い方が良い結果を得ている。
以上より拡張 Euclid 構成算法は、低次数の多項式に対して EZ GCD 算法を上まる性能を示すこと、変数の個数が多くなれば EZ GCD 算法より有利になる傾向があること、が分かる。 したがって、拡張 Euclid 構成算法だけでも十分実用になるものと思われる。

11

12

[1] の問題 I.
$P_{1}$$P_{2}$

上式の$=$$(1+y)x^{4}+(1+y-y^{2}-yz)x^{3}+(-1-y+z-2y^{2}-2yz-z^{2})x^{2}$$+$$(-2-y+3z+y^{2}+2yz-z^{2}+y^{3}+y^{2}z)x+(-1+y+3z-2yz-3z^{2}+yz^{2}+z^{3})$ ,$=$$(-1+z)x^{4}+(-4+y+2z-yz-z^{2})x^{3}+(-2+4y+3z)x^{2}$$+$$(3+y-2z-y^{2}-yz)x+(2-y-3z-y^{2}+z^{2})$ ,$P_{1}$と$P_{2}$

に対し次の置き換えをする。
$x arrow\sum_{i=0}^{m}x^{i},$$y arrow\sum_{i=0}^{m}y^{i},$$z arrow\sum_{i=0}^{m}z^{i}$.

PC-PRS (1): GCD の項次数の上限として従変数の最大次数を選んだもの ($G$の項次数と一致する)。

PC-PRS (2): [1] の理論を用いて計算したもの (上限値は最右の
表 4: 拡張 Euclid 構成算法の実行速度-(1)$E$

列に示した)。

13[1] の問題皿.
$G= \sum_{1=1}^{n}x_{i}+1$, 君$=G \cdot(\sum_{i=1}^{n}x_{i}^{n}-2)$, 凸$=G \cdot(\sum_{i=1}^{n}x_{i}^{n-1}+2)$

表 5: 拡張 Euclid 構成算法の実行速度-(2)[11 の問題 IIL$G= \sum_{i=1}^{n}\sum_{j=1}^{n}x_{i}^{j}+1,$$P_{1}=G$.

($\sum_{i=1}^{n}\sum_{j=1}^{n}x_{i}^{j}$

一

$2$

),

$P_{2}=G\cdot(.\cdot x^{j-1}+2)$

表 6: 拡張 Euclid 構成算法の実行速度-(3)

13

14

[1] の問題 IV.

$G=( \sum_{i=1}^{n}x_{i}+1)^{m},$$P_{1}=G \cdot(\sum_{i=1}^{n}\sum_{j\neq i}^{n}\{x_{i}(x_{j}-1)\}^{m}),$$P_{2}=G \cdot(\sum_{i=1}^{n}\sum_{j\neq i}^{n}\{x_{i}(x_{j}^{2}+1)\}^{m})$表 7: 拡張 Euclid 構成算法の実行速度-(4)

14

.

15’

5

まとめ
本論文では、 PC-PRS GCD 算法において、 GCD の項次数の上限をビューリスティックに見積もる算法を示し、上限の推定値が小さ過ぎて GCD が求まらない場合に、低い次数で打ち切られた多項式 (剰余列の最後の要素) の係数をリフティングして、真の GCD を構成する方法を示した。一つは従来の Hensel 構成を使う方法 (PC $PRS+Hensel$ GCD 算法) であり、 もう一つは関係
式 $A_{k}P_{1}+B_{k}P_{2}=P_{k}$ を使った新しい構成方法 (拡張 Euclid 構成 GCD 算法) である。

注 5.1 [PC-PRS GCD の改良算法] 2 節で示した算法は、 GCD の構成という点からは簡潔な算法であるが、十分効率的ではない。現実問題では、 2 節の算法の Step. 2 で GCD が求まらないのは、 Pke の係数の打ち切り次数 e が小さ過ぎる場合がほとんどで、

Pk+l–e+l が実は 0 ではないという場合は確率的にはずっと少ないからである。 したがって、から$P_{k}^{\overline{e}}$$P_{k}^{\overline{e+1}}$

をまずリフティン

グして GCD を構成する方を優先すべきで、 それでも GCD が求まらない場合にを構成し、除算により$P_{k+1^{\overline{e+1}}}$を構成すべきである。

$P_{k}^{\overline{e}}$$P_{k-1^{\overline{e+1}}}$から GCD を構成する際には、と$P_{k}^{\overline{e+1}}$$G^{\overline{0}}$と$H^{\overline{0}}$が互いに素であるなら Hensel 構成を使い、互いに素でない時には拡張 Euclid 構成を使う。拡張

Euclid 構成のためには Pk-e の他に Ak’, Bk-e が必要である。 PC-PRS GCD 算法においてこの Akと$B_{k}^{\overline{e}}$を同時に計算するのはオーバーヘッドになるので、除算の商を保存しておき、必要になった時点で$B_{k}$$A_{k^{\overline{e}}}$と$B_{k}^{\overline{e}}$を計算することにするのがよい。 なお、 $A_{k}P_{1}+B_{k}P_{2}=P_{k}$ を満たす

$A_{k}$やは、不定積分や代数的数の取り扱いなどにおいて必要となる。拡張 Euclid 算法は PC-PRS GCD

算法の改良のためばかりでなく、$A_{k}$と$B_{k}$

を高速に求めるという算法にも使えると予測できる。

口

実験の結果、項次数上限をビューリステックな方法で見積り、 PC-PRS GCD 算法で GCD を求めると効率が良いことが分かった。 PC-PRS GCD 算法のこの改良版は、密な多項式であれば変数の数が増えるに従い EZ GCD 算法より効率が良くなる傾向を示す。一方、多項式の次数が上がるに従い EZ GCD 算法の方が有利になる。 しかし、項次数上限の見積り方法、構成プログ

ラムの効率化、 数係数の膨張を抑えるための工夫、 専用べき級数演算の作成等、 プログラム上改良すべき点が多々ある。 これらの改良を行なえぱ、 現在の数式処理システムが扱う多項式の次数程度では、 PC-PRS GCD 算法は EZ GCD 算法をしのぐ可能性がある。

EZ GCD 算法は、現在最高速の多変数多項式 GCD 算法であり、 1973 年の発表以来、工夫に工夫を重ねて効率化されてきた。 その EZ GCD 算法に比べて、 まだ充分にチューニングされたとは言えない我々の算法が遜色のない性能を示すことは驚きに僖する。本章に示した PC-PRS の二
つの改良算法と EZ GCD 算法は、変数の個数と次数の増加に対し、 それぞれ異なった特性を示

PC-PRS GCD 算法をさらにチューニングし、多くのケースでテストして特性を調べた上で EZ GCD 算法と組み合わせれば、最適化された GCD 算法が得られるであろう。 そす。 したがって\mbox{\boldmath $\tau$}

れは今後の課題にしたい。

15

16

参考文献
[1] T. Sasaki and M. Suzuki. Three New Algorithms for Multivariate Polynomial GCD. J. Symbolic

Computation, submitted.
[2] J. Moses and D.Y.Y. Yun.

The EZ GCD Algorithm. In Proceedings of $ACM’ 73$ , page 159,

1973.
[3] T. Sasaki and A. Furukawa. Secondary Polynomial Remainder Sequence and an Extension of

Subresultant Theory. J. Inf. Proces., 7: 175-184, 1984.

16