数理解析研究所講究録
第 1572 巻 2007 年 72-81

72

ネーター作用素計算におけるモニックでない多項式による割り算の効率化
庄司卓夢
TAKUMU SHOJI

新潟大学自然科学研究科
GRADUATE SCHOOL OF SCIENCE AND TECHNOLOGY, NIIGATA UNIVERSITY

田島慎一
SHINICHI TAJIMA

新潟大学工学部情報工学科
FACULTY OF ENGINEERING, NIIGATA UNIVERSITY
Abstract
本稿で取り上げる問題は, Asir 上での計算機実験の中で見つかった問題である. ネーター作用素は, 有理関数の特異性を記述できる微分作用素であり, 極におけるローラン展開や留数とダイレクトに関連している. その具体的な計算アルゴリズムは論文 ([1]) で与えた. そのアルゴリズムでは, 有理関数の分母の各既約因子による割り算が何度も必要になるが, 割る多項式がモニックでない場合, その剰余の多項式は有理数係数となるため, モニックな場合に比べて, 計算が遅くなるという弱点があった. この問題点を克服する
ための 1 っの解決法を提示する.

1

ネーター作用素計算アルゴリズム

本稿の内容は, 論文 ([1]) で与えた留数用のネーター作用素計算アルゴリズムの部分的な効率化がテーマである. 改良部分だけを説明してもわかりにくいので, まずアルゴリズムの概要を再説する.
$P_{m}\in N$ とし, 次の有理関数$f_{m}(x)$ を$fi(x),$
上で既約な多項式, $h(x)\in \mathbb{Q}[x],$$l_{1},$$\mathbb{Q}$$\ldots,$$\ldots,$$\frac{h(x)}{f_{1}(x)^{\ell\iota}\cdots f_{m}(x)^{\ell_{m}}}$が定める代数的局所コホモロジー類$[ \frac{h(x)}{f_{1}(x)^{\ell_{1}}\cdots f_{m}(x)^{\ell_{n}}}]$のネーター作用素表示$[ \frac{h(x)}{f_{1}(x)^{\ell_{1}}\cdots f_{m}(x)^{\ell_{n}}}]=T_{1}[\frac{f_{1}’(x)}{f_{1}(x)}]+\cdots+T_{m}[\frac{f_{m}’(x)}{f_{m}(x)}]$を求める問題を考える. これらのター作用素を呼ぶ.

$T_{1},$$\ldots,$$T_{m}$

を有理関数の分母の既約因子 $fi(x),$$\ldots,$$f_{m}(x)$に対応するネー73
ここで, 各$T_{k}$は,(1)$T_{k}=(- \frac{d}{dx})^{\ell_{k}-1}t_{0}(x)+(-\frac{d}{dx})^{\ell_{k}-2}t_{1}(x)+\cdot..$ $+(- \frac{d}{dx})t_{\ell_{k}-2}(x)+t_{\ell_{k}-1}(x)$なる $\ell_{k}-1$ 階の微分作用素である.
$(- \frac{d}{dx})^{\ell-1-i}t_{i}(x)$のように, 微分作用素にマイナスをつけ, 多項式を微分作用素の左側でなく右側につけて表現しているが, これは意図的にそうしている. この形の方が, ローラン展開との関係やネーター作用素の形式

的随伴作用素を考える際に便利であるだけでなく, 計算効率の面でもよいのである. なお,$t_{0}(x),$ $\ldots$,$t_{\ell_{k}-1}(x)$は, 多項式ではなく, 多項式倍という写像 (零階の微分作用素) である.

今, 有理関数の分母の$k$

番目の既約因子 $f_{k}(x)$ に対応するネーター作用素

号を見やすくするため, 以下, $T=T_{k},$ $f(x)=f_{k}(x),$$l=\ell_{k},$$g(x)=f_{1}(x)^{\ell_{1}}\cdots f_{k-1}(x)^{\ell_{k-1}}f_{k+1}(x)^{\ell_{k+1}}\cdots f_{m}(x)^{f_{m}}$と表す\sim - とにする.

を求める問題を考える. 記$T_{k}$$a(x)=f_{1}(x)\cdots f_{k-1}(x)f_{k+1}(x)\cdots f_{m}(x)$,(1) の各係数
は, to $(x)=(f’(x)^{p}g(x))^{-1}$ を共通因子にもつことが知られているので, まずそれで微分作用素全体をくくると, (1) は$t_{0}(x),$ $\ldots,t_{\ell-1}(x)$

$T$

(2)

$\{(-\frac{d}{dx})^{\ell-1}s_{0}(x)+(-\frac{d}{dx})^{\ell-2}s_{1}(x)+\cdots+(-\frac{d}{dx})s_{\ell-2}(x)+s_{\ell-1}(x)\}t_{0}(x)$$=$となる. to $(x)$ は係数が複雑な多項式なので, その分 $s_{0}(x),$,$\ldots$$s_{\ell-1}(x)$はかなり軽くなっている.

$sp-1(x)$ は, $f’(x)a(x)$ の逆幕を因子にもつことが知られている. $s_{1}(x)$ は $(f’(x)a(x))^{-1}$ を因子
s0 $(x),$は $(f’(x)a(x))^{-2}$ を因子にもち, 以下同様に,にもち,は $(f’(x)a(x))^{-(\ell-1)}$ を因子にもつ. そこで (2) を,$\ldots,$$\epsilon_{2}(x)$$s_{\ell-1}(x)$

$T$

$=$

$\{(-\frac{d}{dx})^{\ell-1}(f’(x)a(x))^{\ell-1}c_{0}(x)+(-\frac{d}{dx})^{\ell-2}(f’(x)a(x))^{\ell-2}c_{1}(x)$(3)$+ \cdots+(-\frac{d}{dx}.)(f’(x)a(x))c_{\ell-2}(x)+c_{\ell-1}(x)\}t_{0}(x)(f’(x)a(x))^{-(\ell-1)}$と式変形する. 見やすいように, $B_{i}=(-dTx)^{i}(f’(x)a(x))^{i},$ $u(x)=t_{0}(x)(f’(x)a(x))^{-(\ell-1)}$ とおくと, (3) は,
$T$

$=$

となる. 逆幕は有理数係数の複雑な多項式となるため, その分 $co(x),$$c_{0}(x),$$\ldots,$$c_{\ell-1}(x)$(4)$\{B_{\ell-1}c_{0}(x)+B_{\ell-2}c_{1}(x)+\cdots+B_{1}c_{\ell-2}(x)+B_{0}c_{\ell-1}(x)\}u(x)$は次の漸化式により逐次的に計算できる.

$\ldots$,$c_{\ell-1}(x)$は軽くなっでいる.

$p(x)=-fi(x)f_{2}(x)\cdots f_{m}(x),$ $q(x)=$$\ell_{1}f_{1}’(x)f_{2}(x)\cdots f_{m}(x)+\ell_{2}f_{1}(x)f_{2}’(x)\cdots f_{m}(x)+\cdots+l_{m}fi(x)f_{2}(x)\cdots f_{m}’(x)$とおくとき, $i=0,$ $\ldots,\ell-1$に対して,$c_{0}(x)$

$=$

1,

$q(x)$$=$$- \frac{1}{i}\sum_{j=1}^{i}\{(\ell j-i++1j)p^{(j+1)}(x)+(\ell -1-i+jj)q^{(j)}(x) \}(f’(x)a(x))^{j-1}c_{i-j}(x)$.

(5)

を求めるには $c_{0}(x)$ を使い, $c_{2}(x)$ を求めるには $co(x),$ $c_{1}(x)$ を使
この漸化式を見てもわかるように,う. 以下同様に,を求めるには $c_{0}(x),$を使う. 従つて, 先に求まるデータのサイズが小さ
い程, 後に求まるデータの計算が楽になる. 上述した共通因子のくくり出しは, (1) をそのまま求める方法と比べて, 計算効率を向上させる上で有効であることがわかる.
ここからが本稿のテーマに深く関係する話である. $c_{0}(x),$は, 求める過程で, 剰余体
上で四則演算が行えるという性質がある. この性質により, 計算過程で, 次数が deg $f$ 以上になった場合,$f(x)$ で割り算を行い剰余を求めることで, 常に次数を deg $f-1$ 次以下に保つことができる. その結果, 計算は劇的に高速化される. しかしその一方で, $f(x)$ がモニックでない場合には, 剰余の多項式が有理数係数$c_{1}(x)$$c_{\ell-1}(x)$$\ldots,$$c_{\ell-2}(x)$)$c_{\ell-1}(x)$$\mathbb{Q}[x]/\langle f(x)\rangle$

74となるために Asir の約分 $(gcd)$ 計算と通分 (lcm) 計算が頻繁に発生し, 計算が重くなる問題が生じる. これを本稿では, 「モニックでない多項式による割り算の副作用 (以下, 単に副作用)」 と呼ぶことにする.

この

副作用を軽減することが本稿のテーマである.
例 11 有理関数$\frac{1}{(x^{6}--x+3)^{2}(7x^{3}+x^{2}-2x+2)^{5}}$のネーター作用素を求める問題を考える.
この有理関数が定める代数的局所コホモロジー類のネーター作用素表示は, $fi(x)=x^{6}-x+3,$ $j_{2}(x)=$$7x^{3}+x^{2}-2x+2$ とおくと,$[ \frac{1}{f_{1}(x)^{2}f_{2}(x)^{5}}]=T_{1}[\frac{f_{1}’(x)}{f_{1}(x)}]+T_{2}[\frac{f_{2}’(x)}{f_{2}(x)}]$である.

分母は 2 つの因子をもつが, ここではモニックでない方の因子ゐ $(x)$ に注目する. 記号を$7x^{3}+x^{2}-2x+2$ ,$f(x)$$=$$f_{2}(x)$$f’(x)$$=$$21x^{2}+2x-2$ ,$a(x)$$=$$f_{1}(x)$$g(x)$$=$$f_{1}(x)^{2}$

$T$

$=$

$T_{2}$$=$$=$$x^{6}-x+3$ ,$=$$(x^{6}-x+3)^{2}$と表すことにする.

この注目因子 $f(x)$ に対応するネーター作用素は,$T=\{B_{4}c_{0}(x)+B_{3}c_{1}(x)+B_{2}c_{2}(x)+B_{1}c_{3}(x)+B_{0}c_{4}(x)\}u(x)$なる形をしている.
ここで, 微分作用素$B_{4},$$\ldots,$$f’(x)a(x)$$B_{0}$$=$

は次のように与えられる.
$(21x^{2}+2x-2)(x^{6}-x+3)$

mod $\langle 7x^{3}+x^{2}-2x+2\rangle$$\frac{1}{76}(1128849x^{2}+5038x+16802)$$B_{0}$$=$

1$B_{1}$$=$$(- \frac{d}{dx})(f’(x)a(x))$$=$$(- \frac{d}{dx})(\frac{1}{7^{6}}(1128849x^{2}+5038x+16802))$$=$$(- \frac{d}{dx})^{2}(f’(x)a(x))^{2}$$B_{2}$$=$$B_{3}$$($ 一$\frac{d}{dx})^{2}(\frac{1}{7^{12}}(20894882933107x^{2}-20221265530832x+2403193227262))$$=$$(- \frac{d}{dx})^{3}(f’(x)a(x))^{3}$$=$$(- \frac{d}{dx})^{3}(\frac{1}{7^{19}}(657998048809565280923x^{2}-711550370990973543808x$+367253696927888667990))

75$B_{4}$$=$$(- \frac{d}{dx})^{4}(f’(x)a(x))^{4}$$=$$(- \frac{d}{dx})^{4}(\frac{1}{7^{26}}(37421330292569046014853648379x^{2}-23578495073635594066150630288x$$+12986771140995011457151703126))$$u(x)$ は,次の逆幕計算で求められる.

$u(x)$$=$$(f’(x))^{-5}(g(x))^{-1}(f’(x)a(x))^{-4}$$=$$(21x^{2}+2x-2)^{-9}(x^{6}-x+3)^{-6}$mod$\langle f(x)\rangle$

mod $\langle 7x^{3}+x^{2}-2x+2\rangle$$\frac{1}{(17)^{6}(23)^{6}(409)^{6}(11334283)^{2}}(911231313103017791200661096401218968441x^{2}$$+131656892697912134004021478031654433007x$$-559954382226892127053138867846579608128)$

本稿で中心的に扱う計算部分は, (5) の漸化式である. この漸化式で句 $(x),$$\ldots,$$c_{4}(x)$$c_{0}(x)$$=$1$c_{1}(x)$$=$$\frac{1}{7^{4}}(2027316x^{2}-3395624x-54620)$$c_{2}(x)$$=$$\overline{710}^{(263204780161860x^{2}-85931976549912x}+74943002879916$)$c_{3}(x)$$=$$\frac{1}{7^{16}}(5936011123298611805880x^{2}-5982874458822140668368x$を求めると,

1+2611284323721531371976)$c_{4}(x)$$=$$\frac{1}{7^{22}}(107791902802055995065394546320x^{2}-6840991795956849954495586152Ox$+30339589970097307513358170320)となる.
$7x^{3}+x^{2}-2x+2$ で割り算を行うことにより, 次数が 2 次以下に抑えられていることがわかる. しかし割る多項式 (イデアル) がモニックでないため, その副作用として, 有理数係数となってしまっている.

76
2

副作用の対処法
この節では, 前節で述べた副作用に対し, 具体例を通じて, その対処法を述べる.

例 212 つの剰余体$\mathbb{Q}[x]/\langle x^{3}-x-1\rangle$と $\mathbb{Q}[x]/\langle 3x^{3}-x-1\rangle$ において,$x^{30}$をイデアルで割った剰余を求める問題を考える.

この 2 つの剰余体における割り算にかかる時間は, 前者の方が速い. その理由は, これまで述べてきた通りである. 実際に計算を行うと,$[0]sr\circ m(x^{-}30.x^{-}3-x-1)$ ;$1081*x^{-}2+1432*x+816$$x^{30}\equiv 1081x^{2}+1432x+816$

mod$\langle x^{3}-x-1\rangle$

srem $(x^{-}30,3*x^{arrow}3-x-1)$ ;[1]$20809/4782969*x^{-}2+17720/4782969*x+8152/4782969$

mod \langle $3x^{3}-x-1$ )$x^{30} \equiv\frac{20809}{4782969}x^{2}+\frac{17720}{4782969}x+\frac{8152}{4782969}$となる. 後者は有理数係数となり, 前者より複雑な多項式となることがわかる. イデアルがモニックであるかモニックでないかは, 計算効率の面で, 大きな違いである.
対処法 1

この問題を解決する方法として, Asir の Dalg という機能を使うことが考えられる. 上記の例なら,
[101]

Alg

.

newalg $(3*x^{arrow}3-x-1)$ ;$(\# 0)$[102] set-field([Alg]);$0$

algtodalg (subst ( $x^{-}30.x$ , Alg)) ;$((20809)*<<2>>+(17720)*<<1>>+(8152)*<<0>>)/4782969$[103]

といったように自動的に整数係数化してくれる. この機能を使えば, 単純に srem を使うよりもずっと速くなるだけでなく, 各係数部分を通分した値も得られるという利点がある. しかし, この機能は汎用的な機能であるため, 本稿で扱うような特殊な問題に対しては, ロスが生じると思われる.
対処法 2

一時は対処法 1 を採用していたが, 後になって次の方法を考えることにした. 本研究では,$\bullet$

割る多項式は常に $f(x)$ で一定$\bullet$

割り算の回数は数えられるという 2 つの事実に注目し, 割り算によって生じる有理数の分母の整数を見積もって, あらかじめかけておく方法を考える.
多項式による割り算の回数は, 高々 「割られる多項式の次数 割る多項式の次数 $+1$ 」 回である. 高々と–書いた理由は, 実際はこの上限より割り算の回数が減る場合があるからである. それは, 割られる多項式が77
スパースで, かつ割る多項式の最高次数と 2 番目に高い次数の項との次数差が 2 以上の場合などに起きる.

正確に割り算の回数を数えるには, 割られる多項式と割る多項式の項の情報も見なければならない.
例 21 でいうと, 割り算の回数は, 高々$\deg(x^{30})-\deg(3x^{3}-x-1)+1=28$

回であることがわかるが, 割られる多項式はスパースであり, 割る多項式もの項がないため割り算の回
数はその半分の 14 回である. 従って,をあらかじめかけておけば剰余の多項式の係数に有理数はでてこ$x^{2}$$3^{14}$ない.

srem $(3^{-}14*x^{-}30.3*x^{-}3-x-1)$ ;[259]$20809*x^{-}2+17720*x+8152$\Phi @/(3^14);[260]$20809/4782969*x^{-}2+17720/4782969*x+8152/4782969$

正しい答えを得るには, 割り算を行った後で, かけておいた数で割り直さなければならないが, この計算は–瞬である. というのは, プログラムでは, 有理数係数の多項式を, 整数係数化した多項式と, 係数部分の通分値とに分離して計算を進行させているため, かけておいた数での割り直しの計算は, 分母の整数同士の積であり, gcd を計算するわけではないからである.

3

副作用を軽減するネーター作用素計算アルゴリズム

実際に, 留数用のネーター作用素計算アルゴリズムの場合で考える. 副作用が最も大きく影響する計算
パートは, (5) の漸化式の計算であるので, この部分を中心に考える. 割り算の回数を数えるために, 各係数$c_{0}(x),$$\ldots,$$c_{\ell-1}(x)$の次数に注目する. 見やすいように, (5) の漸化式における全体の 4 と $p^{(j+1)}$ と$q^{(j)}$の係数部分を取り去って書き下すと,

1$c_{0}$$\simeq$$c_{1}$$\simeq$$c_{2}$$\simeq$$(p^{(2)}+q^{(1)})c_{1}+(p^{(3)}+q^{(2)})(f’a)c_{0}$$c_{3}$$\simeq$$(p^{(2)}+q^{(1)})c_{2}+(p^{(3)}+q^{(2)})(f’a)c_{1}+(p^{(4)}+q^{(3)})(f’a)^{2}c_{0}$$c_{4}$$\simeq$$(p^{(2)}+q^{(1)})c_{3}+(p^{(3)}+q^{(2)})(f’a)c_{2}+(p^{(4)}+q^{(3)})(f’a)^{2}c_{1}+(p^{(5)}+q^{(4)})(f’a)^{3}c_{0}$$(p^{(2)}+q^{(1)})c_{0}$:儒$\simeq$$\sum_{j=1}^{i}(p^{(j+1)}+q^{(j)})(f’a)^{J-1}$

亀-j:$c_{\ell-1}$$\simeq$$\sum_{j=1}^{p-1}(p^{(j+1)}+q^{(j)})(f’a)^{j-1}c_{\ell-1-j}$となる.
$p(x)$ は有理関数の分母の無平方部分であり常に deg $q=\deg p-1$ である. 従って,

, 次数は deg $p=\deg fi+\cdots+\deg f_{m}$ である. $q(x)$ の次数は,の次数は, 高々deg $p-2$ である. また, $f’(x)a(x)$ の$c_{\ell-1}(x)$ の次数を求めていく.
次数は, $\deg(f’a)=\deg p-1$ である. これを元に, 各係数 $c0(x),$$(p^{(j+1)}+q^{(j)})$$\ldots,$

78
まず, co の次数はである.

の次数は deg $p-2$ である.

の次数は, $(p^{(2)}+q^{(1)})c_{1}$ と $(p^{(3)}+q^{(2)})(f’a)c_{0}$のの高い方の次数で決まるが, どちらも次数が $2(\deg p-2)$ であるから, deg $c_{2}=2(\deg p-2)$ である.
$(p^{(2)}+q^{(1)})c_{2}$$(p^{(4)}+q^{(3)})(f’a)^{2}c_{0}$$(p^{(3)}+q^{(2)})(f’a)c_{1}$とと次数は,の中で最も次数が高いもので決まる
が, 3 つとも次数は $3(\deg p-2)$ であるから, deg $c_{3}=3(\deg p-2)$ である.の次数も同様にして考えると,$0$$c_{1}$$c_{2}$$c_{3}$$c_{4}$

deg $c_{4}=4(\deg p-2)$ とわかる. 以下同様に, deg $c_{\ell-1}=(l-1)(\deg p-2)$ である. まとめると,$\deg c_{0}$

$=$

$0$

deg

$c_{1}$$=$

deg $p-2$$c_{2}$$=$

2 $(\deg p-2)$$c_{3}$$=$

3 $(\deg p-2)$$c_{4}$$=$$4(\deg p-2)$$\deg c_{t}$$=$$i(\deg p-2)$$=$$(\ell-1)(\deg p-2)$

deg
deg

deg

deg

$c_{\ell-1}$

となる.

3.1

見積もり法 1$f(x)$ の最高次の係数を CF とすると, $f(x)$ で割った剰余の多項式の係数の分母にでてくる数は, CF の幕である. この CF の幕が最も大きくなるのは, 最も次数が高い多項式 $c_{\ell-1}(x)$ を $f(x)$ で割ったときである.

その時の割り算の回数を

$s$

とすると,
$s$

-deg $f+1$

$=$

deg

$=$

( –l)(deg $p-2$ ) -deg $f+1$$c_{\ell-1}$$\ell$

であるから, あらかじめかけておくべき整数の上限は CF’ と見積もれる.
ところで, 漸化式を見ればわかるように, $c_{0}(x),$る.

$c_{0}(x)$を$CF^{\iota}$

は, $c_{0}(x)$ を共通因子にもつ構造になってい$c_{\ell-1}(x)$ を均等に倍してから漸化式を計算していくことは, 既に求まってある $c_{0}(x),$$\ldots,$$c_{\ell-1}(x)$$\ldots,$

倍する) ことと同じである. 従って, あらかじめ $co(x)$ を
CF’ 倍する (言い換えれば, 微分作用素 をの係数に有理数はでてこないことになる. 後,
CF’ 倍しておけば, 漸化式の計算において,は, 正しい答えを得るために後で CF’ で割り直せばよい.
$T$$CF^{*}$$c_{0}(x),$ $\ldots$

32$c_{\ell-1}(x)$見積もり法 2

見積もり法 1 では, 最初に上限分の整数をかけ, 漸化式を逐次的に計算していくにつれて, かけておいた
整数と係数部分がキャンセルされて小さくなっていく. この細工で確かに有理数はでてこなくなるが, 最初に大きな数をかけているので冗長な計算をしている. そこで, 漸化式を 1 つ 1 つ細かくケアしていくことを考える.

上記を見てもわかるように $co(x),$ $\ldots,c_{\ell-1}(x)$ の次数は比例して上がっていく. そこで隣接 2 項間の次数の差分に注目し$L=CF^{\deg p-2}$

79
とおく. $d_{t}(x)=L^{i}q(x)$ とおき, 漸化式を
$c_{0}(x)=d_{0}(x),$$c_{1}(x)= \frac{d_{1}(x)}{L}$, ...,$c_{\ell-1}(x)= \frac{d_{\ell-1}(x)}{L^{\ell-1}}$と置き換えて考えると,$d_{0}$$\simeq$1$d_{1}$$\simeq$$L(p^{(2)}+q^{(1)})d_{0}$$d_{2}$$\simeq$$L(p^{(2)}+q^{(1)})d_{1}+L(p^{(3)}+q^{(2)})L(f’a)d_{0}$$d_{3}$$\simeq$$L(p^{(2)}+q^{(1)})d_{2}+L(p^{(3)}+q^{(2)})L(f’a)d_{1}+L(p^{(4)}+q^{(3)})L^{2}(f’a)^{2}d_{0}$:$d_{i}$$\simeq$$\sum_{j=1}^{i}L(p^{(j+1)}+q^{(j)})(Lf’a)^{j-1}d_{i-j}$:.
$d_{\ell-1}$$\simeq$$\sum_{j=1}^{\ell-1}L(p^{0+1)}+q^{(j)})(Lf’a)^{j-1}d_{\ell-1-j}$と書ける. ここで $L(p^{(J+1)}+q^{(j)})(Lf’a)^{j-1}$ はじめ計算しておける. 特に, $j=0,$$\ldots,$$\ell-1$$i$のみで変化する値であるので,$i$のノレープの外側であらかに対して,$b_{j}(x)=(Lf’(x)a(x))^{j}$mod ($f(x)\rangle$

とおいて計算しておく. このデータはネーター作用素の形式的随伴作用素を分子に施す計算の際にも必要になる.

このとき, ネーター作用素は,
$T$

$=$

$\{B_{\ell-1}c_{0}(x)+B_{\ell-2}c_{1}(x)+\cdots+B_{1}c_{l-2}(x)+B_{0}c_{\ell-1}(x)\}u(x)$$=$$\{B_{\ell-1}d_{0}(x)+B_{\ell-2}\frac{d_{1}(x)}{L}+\cdots+B_{1}\frac{d_{\ell-2}(x)}{L^{\ell-2}}+B_{0}\frac{d_{\ell-1}}{L^{\ell-1}}\}u(x)$$=$$\{(-\frac{d}{dx})^{\ell-1}\frac{b_{\ell-1}(x)}{L^{\ell-1}}d_{0}(x)+(-\frac{d}{dx})^{t-2}\frac{b_{1-2}(x)d_{1}(x)}{L^{\ell-2}L}$$+ \cdots+(-\frac{d}{dx})\frac{b_{1}(x)}{L}\frac{d_{\ell-2}(x)}{L^{\ell-2}}+b_{0}(x)\frac{d_{\ell-1}(x)}{L^{\ell-1}}\}u(x)$$=$$\{(-\frac{d}{dx})^{\ell-1}bp-1(x)+(-\frac{d}{dx})^{\ell-2}b_{\ell-2}(x)d_{1}(x)+\cdots+(-\frac{d}{dx})b_{1}(x)d_{\ell-2}(x)+d_{\ell-1}(x)\}\frac{u(x)}{L^{\ell-1}}$となっている. 従って, 正しい答えを得るには後で $L^{l-1}$ で割り直せばよい.

3.3

さらなる細工$f’(x)$ を因子にもっ多項式を $f(x)$ で割った場合, 1 回目の割り算で,その剰余の多項式の最高次の係数に有理数はでてこないことになる. これを利用すれば, 若干ながら見積もりの精度を上げられる. また, 前節で述べたように, 割られる多項式と割る多項式の項の情報によって割り算の回数は激減する場合がある. これを利用すれば, さらに見積もりの精度を上げられる.

80
4

計算機実験
次の 5 通りの方法に基づくアルゴリズムを Asir 上に実装し, 副作用が最も影響する計算である (5) の漸化式の計算時間を計る.

ネーター作用素を求める計算において, 計算効率に影響を与える要素としては, 分子多項式の複雑さ, 注目
する分母の既約因子の次数と項数, 注目する分母の既約因子の重複度, 注目する分母の既約因子以外の因子の複雑さ, 注目する分母の既約因子の係数の大きさ, などが挙げられる. しかしこの中で, 分子多項式の複雑さは (5) の漸化式の計算には関係しないのでここでは考察から除外する.
実験環境

CPU 1. $30GHz$ , 248MB RAM.
実験データ

実験は, 次の 5 っの有理関数を使って行う.
$\bullet$c 下 sel$\frac{1}{(x^{3}+2x-4)^{4}(x^{2}-3x+5)^{5}(17x^{3}-x-1)^{200}}$

注目因子 17x3 $-x-1$ .
$\bullet$case2$\frac{1}{(x^{3}+2x-4)^{4}(x^{2}-3x+5)^{5}(499x^{3}-x-1)^{200}}$

注目因子 $499x^{3}-x-1$ . casel より最高次の係数が大きい.
$\bullet$case3$\frac{1}{(x^{3}+2x-4)^{4}(x^{2}-3x+5)^{6}(17x^{3}-x-1)^{600}}$

注目因子 $17x^{3}-x-1$ . casel より重複度が高い.
$\bullet$cas 殆 4$\ovalbox{\tt\small REJECT}(x^{3}+2x-4)^{4}(x^{2}-3x+5)^{5}(7x^{5}+2x^{4}-x^{3}+2x^{2}+3x-7)^{200}1$.

注目因子 $7x^{5}+2x^{4}-x^{3}+2x^{2}+3x-7$ .

$ca\epsilon el$より多項式の次数が高く項数も多い.

case5$\frac{1}{(x^{10}+3x^{7}-x^{3}-x^{2}+2x-3)^{5}(x^{5}+2x^{4}+2x^{3}-3x+5)^{4}(x^{4}+1)^{4}(17x^{3}-x-1)^{200}}$

注目因子 $17x^{3}-x-1$ . casel より注目因子以外の因子が複雑.

81
上記の 5 つの case における (5) の漸化式の計算時間 (秒)本提案手法は, 方法 3 と方法 4 であるが, 方法 4 の方がずっと速いことがわかる.
casel,2,3,5 は, 注目因子にの項がないために, 割り算の回数は上限より減っている. その分も見積もったのが方法 4(b) であり, 方法 4(a) に比べて速くなっている. 特にこの細工は, case5 のように注目因子以外$x^{2}$の因子が, 次数が高くかつスパースな場合に威力を発揮する.

ちなみに, 方法 1 と参考を比較すると, 副作用の大きさがうかがえる. 参考のタイミングデータを限界値と考えれば, 今回の改良で副作用を大分軽減できたといえる.

5

まとめ

本稿は, 留数用のネーター作用素計算アルゴリズムにおける, モニックでない多項式による割り算の副作用の軽減をテーマに挙げ, その解決法を提示した. そして実際にプログラムも改良した. 計算機実験の結果,
本提案手法は, 計算の効率化に有効であることがわかった. 本稿では触れなかったが, ローラン展開用のネーター作用素計算アルゴリズムにも今後同様の効率化を加えたい.

参考文献[1] 庄司卓夢, 田島慎一, 高遠留数計算アルゴリズム,
京都大学数理解析研究所講究録 1456 「 $Computer$ Algebra.Design of Algorithms, Implementations andAPplicatiooJ (2005), 133-143.