数理解析研究所講究録920 巻 1995 年 31-37

314.
Diophantine 近似グレブナ基底の計算
関川浩 (NTT白柳潔 (’)$\mathrm{C}\mathrm{S}$研)

4.1 はじめに数式処理において, 正確な計算をすると計算量が非常に大きくなってしまう場合が多々ある.

しかし, たとえ厳密解を要求する問題であっても, 途中の計算については適当な保証のもとでの近似計算で十分な場合もあり得るし (たとえば答が整数になることがわかっている場合など),似解が得られれば十分,という場面もあろう.

そもそも, 近したがって, 近似計算による計算量の軽減が重要な意味を持ってくる.
ただし, 一般にはアルゴリズムに対する入力をそのまま近似しただけでは得られた出力が正確な答の近似になっているとは限らないので注意を要する. たとえば, グレプナ基底に対する Btlchbel gc\iota$\cdot$$\cdot$の 7) レゴリズム (|1]) はその–つの例である.

グレブナ基底に対する Buchberger のアルゴリズムについては, 浮動小数近似を用い, 安定性を保証した浮動小数係数グレブナ基底アルゴリズムを提案しその有効性を確かめた ([3]).
[3] のアイディアはその後, 白柳-Sweedler によって近似概念とアルゴリズムという二つの方向に $-$般化され, 安定化理論という形に体系化された $([4],[5])$ . われわれはこの有効性をいろいろな実例によって検証する研究を行っている. 本稿ではその中で実数の連分数近似 (Diophantine 近似) を用いた Buchberger アルゴリズムに対する計算結果について報告する.

32

4.2 Diophantine 近似グレブナ基底
われわれは [3] において, 浮動小数係数グレブナ基底を求めるアルゴリズム

FP-G$\mathrm{B}$を提案した.

ここでは, 浮動小数近似の代わりに連分数近似 (Diophantine 近似) を用いたアルゴリズム DA-GBを提案する. 自然数\mu に対し, 精度\mu の DA-GB を[係数の Bracket 化]

係数$a$ム$p_{\mu}/q_{\mu}$と書く. その概略は以下の通りである.

まず, 入力の多項式の各係数を [近似値, 誤差] という Bracket に置き換える.

が有理数であるときは $[a, 0]$ とし,る. ただし,$\mathrm{D}\mathrm{A}- \mathrm{G}\mathrm{B}_{\mu}$

は

$a$

$a$

が無理数のときは連分数で近似し$[p_{\mu}/q_{\mu}, 1/q^{\frac{9}{},l},]$とすの第\mu 近似分数である ([6]). その結果に従来の Buchberger のアルゴリズ(除算を用いないバージョン) を適用する. なお, Bracket 係数$(\mathrm{B}\mathrm{C})$間の加減乗は以下のよ

うに自然に (誤差伝播がうまくぃくように) 定義しておく. 丸め誤差なしに BC 間の計算が行われるという点が FP-GB との違いである.

$[A, \alpha]+[B, \beta]=[A+B, \alpha+\beta]$$[A, \alpha]-[B, \beta]=[A-B, \alpha+\beta]$$[A, \alpha]\mathrm{x}[B, \beta]=[AB, |A|\beta+|B|\alpha+\alpha\beta]$[Bracket の零判定法】 Bracket 係数$[C, \gamma]$について,$[C, \gamma]=0\Leftrightarrow|C|\leq\gamma$を適用する.
つまり,$|C|\leq\gamma$であれば, 構わずその項を消せ, ということである.

この下野定法は–見大胆なようだが,これがわれわれの目的にかなった非常によい性質の近似グレブナ基底を導出してくれる. それが次の定理である.
定理 1 (Diophantine 近似グレブナ列)F を与えられた有限個の実係数多項式の集合とする. 自然数$\mu$に対し,

ナ基底$G$$\mathrm{D}\mathrm{A}- \mathrm{G}\mathrm{B}_{\mu}$に $F$ を入力した出力結果を$G_{\mu}$とする. このとき, 列$\{G_{\mu}\}_{\mu}$

は $F$ の真のグレブに収束する.

この収束は係数ごとの収束よりも強く, ある から先は台 (係数が$\mu$$0$でない項) の集合もすべて–致するという意味で台収束 (supportwise convergence) と呼んでいる. いいかえれば,係数は必ず有限ステップで$0$$0$に収束するに到達するという点に特徴がある. 定理 1 は安定化理論からの帰結であるが, その証明は [3] を参照されてもよい. そこでの浮動小数近似に対する議論と完全に並行な議論が連分数近似の場合にも成り立つ.33

4.3 実験結果
ここで二つの例についての実験結果を示す. 実装は Maple VRelease 3(|2]) on
る.

$\mathrm{H}\mathrm{P}9000/735$によ例は以下の通りである.

1.

$F=\{\sqrt{2}ex^{3}y+\sqrt{3}xy+\sqrt{7}/e, \sqrt{3}/ex^{2}y^{2}-\sqrt{7}xy+e/\sqrt{11}\}$

2.

$F=\{\sqrt{2}e/\pi X^{3}y+(\sqrt{3}+\pi)xy+\sqrt{7}/(e-\pi), (1-e\sqrt{3})/ex^{2}y^{2}-(\sqrt{7}-e)xy+e/\sqrt{11}\}$

いずれも [3] からの引用で無理数係数である. 例 1 は超越数$\mathrm{e}$.

を含み, 例 2 は二つの超越数$\mathrm{e},$$\pi$.

を含む. いずれの場合も項順序は $x>y$ とした全次数逆辞書式順序 (tdeg) とする. これらの例は 4 次式であり $-$ 見簡単に見えるが激しい係数膨張を起す.

とくに二つの超越数を含む例 2 の場合は著しい.

おのおのの例についての実験結果を表 1, 2 に示す. また, 比較のため例 2 については浮動小数近似による計算を表 3 に示す.

. 真のグレブナ基底を求める際, 公平を期すため, Maple 組み込みの gbasis を用いず, われわれが Buchberger のアルゴリズム (除算を用いないバージョン) を Maple でインプリメントしたも.のを使った.
$\{G_{\mu}\}_{\mathrm{J}}\leq’ r\leq 10$は精度が 1 から 10 までの Diophantine 近似グレブナ列である. 実際は有理数係数だが紙面の都合により 10 ケタの浮動小数で表示している.

.stop は$0$でない二つの Bracket の積が$0$となったため計算を打ち切ったことを示す. 一般に(浮動小数近似でも Diophantine 近似でも) 二つの$0$でない Bracket の積が$0$となることがあるので注意を要する. たとえば, Diophantine 近似の場合,$[1,$であり,これは$0$$\frac{1}{2}]^{2}=[1,$$\frac{5}{4}]$になってしまう.

. 例 2 について, われわれの環境では真のグレプナ基底は計算不能であった (268306 秒で ”objecttoo large” で終了).
いずれの例でも Diophantine 近似グレブナ基底の計算時間は真のグレブナ基底のそれよりもかなり短い.

また, 近似精度については早い段階で真の台に収束しているように見える.

ただし, 浮動小数近似と比較して時間がかかる傾向にある.

4.4 おわりに
表 1, 2, 3 に見られる通り, 近似グレブナ基底の計算は, 真の基底を求めるのに比べてかなり計算時間が短い. とくに例 2 の場合は真のグレブナ基底が計算不能であったからその差はさらに際立つ.

34

また, 近似精度についてもかなり早い段階で真の台に収束しているように見える.

ここで重要なのは, 単に収束するばかりではなく, 必ず有限の精度で真の台に到達することが理論的に保証されていることである. これが台収束の特徴である.

近似精度を上げていった場合, 浮動小数近似に比べて Diophantine 近似は計算時間の増加が早い傾向にあるが, これは Diophantine 近似の場合, 途中は正確演算によるため係数膨張をおこしがちであることを考えるとやむをえないといえる. しかし, 計算の途中での丸め誤差がない点を生かした活用法 (グレプナ基底の計算に限らない) があることを信じたい.
なお, 重要な未解決問題として,正しい台が得られる精度\mu (あるいはその上からの評価) を理論的に求めることや, 得られた台が真の台と -致するか否かを判定するための方法を見出すことなどが挙げられる. これらの問題が解決されない以上は, われわれのアプローチはまだ確率的といわざるを得ない.

しかし, 正確な計算では時間がかかりすぎて手に負えないような問題に対して,このような近似計算の手法が役立つ場合があるのではないかと思っている.

参考文献$[1]\mathrm{B}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{r}$, B., Gr\"obner Bases: An Algorithmic Method in Polynomial Ideal Theory, Multid.i-

mensional Systems Theory (Ed. N. K. Bose), D. Reidel Publishing Company (1985), 184-232.
$[2]\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{r}$, B. W., Geddes, K. O., Gonnet, G. H., Leong, B. L., Monagan, M. B., and Watt, S. M.,

First Leaves: A Tutorial Introduction to Maple, Springer-Verlag (1992).

$V$, K., An Algorithm to Compute Floating Point Gr\"obner Bases, Mathematical$[3]\mathrm{S}\mathrm{h}\mathrm{i}\mathrm{r}\mathrm{a}\mathrm{y}\mathrm{a}\mathrm{n}\mathrm{a}\mathrm{g}\mathrm{i}$Computation with Maple$V$: Ideas and Applications (Ed. T. Lee), $Birkh\tilde{a}uSer$ (1993), 95-106.

[4] 白柳潔, Sweedler, M., 近似代数計算における安定化理論, JSSAC’94 (沼津) 資料.
, K. and Sweedler, M., A Theory of Stabilizing Algebraic Algorithms, in prepara-$[5]\mathrm{S}\mathrm{h}\mathrm{i}\mathrm{r}\mathrm{a}\mathrm{y}\mathrm{a}\mathrm{n}\mathrm{a}\mathrm{g}\mathrm{i}$tion.
[6] 高木貞治, 初等整数論講義, 共立出版 (1971).

35

表1

例 1 に対する Diophantine 近似グレブナ基底の計算

真のグレブナ基底の 10 ケタの浮動小数表示 (計算時間 4050 秒){-3.076 $101960x^{2}$–07504363785$-3.2339\iota 5437x$ –.3950725311$\mu=6$$y^{3}$$y^{2}$–3703099133, $-13.44535658xy$ –1.666373738–1156215932$y$$y^{2}$}から 10 までの台は真の台に–致$0$$\mu$+4.375492414,$G_{\mu}$( $10$ ケタの浮動小数表示)への置換回数cpu time$(\sec)$$\ovalbox{\tt\small REJECT}_{9646}^{1\mathrm{t}\circ \mathrm{p}_{4\cross\iota 0_{9}^{93}16}}\iota 022\mathrm{s}630_{6}756710xy+2796394645\cross 10y-734268493\mathrm{X}^{\cross}0\}4S\mathrm{t}.\mathrm{p},$”

36

表2

例 2 に対する Diophantine 近似グレブナ基底の計算

真のグレブナ基底の計算は不能 (268306 秒で ” object too large” で終了)$\mu=5$から 10 まで台が–致
$0$

$\mu$

$G_{\mu}$( $10$ ケタの浮動小数表示)への置換回数cpu$\mathrm{t}\mathrm{i}$rne$(\sec)$

37

表3

例 2 に対する浮動小数近似グレブナ基底の計算$\mu=1$の場合は $f$ ] の定数項の分母が$\mu=5$から 10 まで台が– 致$0$となる$0$$\mu$$G_{\mu}$への置換回数cpu time$(\sec)$