数理解析研究所講究録920 巻 1995 年 247-257

247

27.1 Introduction
代数制約問題あるいは代数方程式を扱う手段として現在一般的に用いられる方法として,basis, や Ritt &Wu’s method は, すでによく紹介され知名度もある.

に言って代数閉体上での方程式の根を扱っている.

$\mathrm{G}\mathrm{r}\ddot{\circ}\mathrm{b}\mathrm{n}\mathrm{e}\mathrm{I}^{\cdot}$

これらの二つは, おおまかその–方で, 実根のみを扱うことを主眼に置いている研究も, すでに行われており, その代表的なものとして, 今回紹介する Cylindrical Algebraic

Decomposition が挙げられる. この方法の日本における知名度は, 初めの二つに比べるとそれほど高いと思われないが, 今後発展する可能性を秘めていると思われる.

実代数と代数閉体との違いと言えば, 簡単なところでは $(\exists x)x^{2}+bx+c=0$ は, 代数閉体上では恒真命題であるが, 実代数では, $b^{2}-4c\geq 0$ と同値となるといったことが, 挙げられる. 又, 科学技術計算に現実に表れる問題の多く (特にロボット制御など) は, 実空間で解を持つか持たないかが重要である場合が少なくない. この様に, 実代数制約問題は, より現実味を帯びた問題ともいえ, ここ数年, 世界
的にこの分野の研究が盛んになってきた. 今後は更に, この分野の研究の発展が科学技術計算全体に大きく影響するものと思われる.
1975 年に Collins によって発表された Cylindrical Algebraic Decomposition Algorithm (略してCAD) は, 限定記号 (quantffier) (V,$\exists$) を含む代数制約式を, 限定記号を含まない同値な表現へと変換(quantifier elimination) するために用意された sub-algorithm で, その後, Collins らを中心とした者たちによって, CAD の計算の効率化のための改良や, その応用が行われてきた.

248

CAD を– 口で言えば, 多変数版 sturm 法による空間分割法である. Gr\"obner basis が, 多項式の作るイデアルの標準線で, Ritt &Wu’s method が, イデアルの radical (多項式の零点集合と同値) の標準系を与えたのに対し, CAD は, 多項式に空間の点を代入した値の符号を不変とするような空間分割を与えていると言える. また, それぞれの基本となる演算が, Gr\"obner basis は, M-reduction, Ritt

&Wu’s method は, pseudo-division, であるのに対し, CAD は, sub-resultant であるとと言った所からも, それぞれの特徴が表れている. 次の section から, CAD 理論の概要を述べる.

27.2 Preliminary
は実数の集合,$\mathrm{R}$$\mathrm{Q}$は有理数の集合,$\mathrm{Q}[X]=\mathrm{Q}1^{x_{1},\ldots,X_{\Gamma}}]$は整数係数多項式環,$\mathrm{R}^{r}$

は

$r$

次元 R-

ベクトル空間であるとする.

Definition 27.2.1 ($\mathrm{R}^{r}$す.

$regi_{\mathit{0}}n$, cylinder, secion, sector, i.cell)の連結部分集合を region という. region $K$ に対し,
$f$を$I\iota’$から$\mathrm{R}$を’ の cylinder といい$I\backslash$’$Z(I\mathrm{i})$で表への実数値連続関数としたとき, $\{(a, f(a))|a\in I\mathrm{t}^{r}\}$ を $Z(K)$ の section, あると呼ぶ. $fi,$

いは $f$ -section$K\cross \mathrm{R}$$f_{2}$

を二つの実数値連続関数としたとき, $fi(a)<f_{2}(a)$ が, 任意の$a\in Ii^{r}$で成り立つとき, $fi<f_{2}$ と書く. この時, $\{(\alpha, b)|\alpha\in I\zeta, fi(\alpha)<b<f_{2}(\alpha)\}$ を $Z(K)$ の sector,
あるいは$(f_{1}, f_{2} )$-sector と呼ぶ.

$f_{i},$$f_{2}$(section も sector も region である)はそれぞれ, $fi=-\infty$ あるいは $f_{2}=\infty$ も許すことにする.

$\mathrm{R}^{r}$の部分集合で,$\mathrm{R}^{1}$と位相同型なものを -cell と呼ぶ.
$i$

Deflnition $27.2.2$ ( $cy\iota indrical$ decomposition)$\mathrm{R}^{r}$

の部分集合

$L$

が共通部分のない有限個の region の和集合として表されたとき, それを

decomposition という. region $K$ 上の実連続関数$(f|’ f,+1)- sector$ ( $i\in$to,$\ldots,$$k\},$ $f_{0}=-\infty,f_{k+\mathrm{l}}=\infty$

まる $Z(K)$ の decomposition を ($fi,$(2) $r>1$ かつ, ある]$<\ldots<f_{k}$が与えられているとき, $Z(K)$ の) 及び $Z(K)$ の$f_{1}\cdot sect\dot{\mathrm{t}}$で決まる) $K$ の stack と呼ぶ.

$f_{k}$$\ldots,$

が次の (1) あるいは (2) が成り立つとき,の stack である.

$f$$\Phi$$\mathrm{R}^{r-1}$

on $(i\in\{1, \ldots, k\})$ で決$\mathrm{R}^{r}$のcylindrical decomposition$\Phi’$.

$decompos\dot{\iota}iio7l$

は, cylindrical であるという. (1) $r=1$ かつ,
の

の

$L$

が存在して,$\Phi$$\Phi$

はは,$\Phi$$\mathrm{R}$$\Phi’$のすべての region $K$ の stack で構成されている.
($\Phi$$\Phi$に対する,を$\Phi’$の$\Phi’$

は, $-$ 意的に決まる. これを\Phi の induced cylindrical decomposition とよび, 逆に

extension と呼ぶ)

Definition 2723(semi-algebraic, formula)$\mathrm{R}^{r}$の部分集合 $K$ が, 集合 $\{x\in \mathrm{R}^{r}|f(x)\geq 0\},$ $(f\in \mathrm{Q}[X])$ の共通部分, 和集合, 補集合を組み合わせたものとして表されるとき,$I\mathfrak{i}^{r}$は semi-algebraic であるという. また, 多項式と等号, 不等号を用いて表された式及び, 限定記号のついた変数 ($\forall x$

.

あるいは

$\exists x_{1}$) が組み合わせられた論理式を formulaと呼ぶ. 限定記号がつかない formula を quantffier free formula とよぶ.

Example 1(Quartic problem)

249

次の 1 及び 2 は, 同値である. 1 から 2 を構成する事を quantifier elimination と呼ぶ.
(quantifier free formula は, -意的には決まらない) ‘& ’ は and,$‘||$は $or$ を表す事とする.

’

1. formula : $(\forall x)(x^{4}+px^{2}+qx+r\geq 0)$

2. quantifier free formula : $\delta\geq 0\ [p\geq 0||L<0||(L=0\ q=0)]$ ,where $\delta=256r^{3}$–

128 $p^{2}r^{2}+144pq^{2}r+16p^{4}r-27q^{4}-4p^{3}q^{2},$ $L=8pr-9q^{2}-2p^{3}$ .

Deflnition 27.2.4 (cylindrical algebrazc decomposition)
decomposition の各 region が semi-algebraic であるときその decomposition ti algebraic で$\mathrm{R}^{r}\text{の}$あるといい, 加えて, cylindrical であるときに, cylindrical algebraic decomposition (CAD) という.

Definition 272.5 (cylindrial algebraic sample)$\mathrm{R}^{r}$

CADの$\Phi$が与えられた時,$\Phi$

cell から選んだ代表点を sample point とよび, すべての cellのから取った sample point の集合を sample と呼ぶ.

$\Phi$のinduced CADし, cylinder $Z(R)$ に含まれるすべての sample point が, 等しい$X_{1},$$\ldots,$$X_{T-}1$

座標の集合 ($\ldots,$

sample) を induced sample というの$\Phi’$$X_{1},$の任意の cell$\Phi’$$R$に対座標を持つとき, その$X_{f}-1$

sample が, cylindrical であるとは, それが induces sample をもち, その induced sample が cylindrical であるときをいう、更にその座標が algebraic の時, cylindrical algebraic sample (CAS) という.

Definition 27 $2.6(invariant)$
$R$

き,

を
$f$

$\mathrm{R}^{r}$の部分集合とし,$f$を$\mathrm{Q}[X]$の要素とする. $R$ の任意の点$\alpha$で $f(a)$ の符号が不変であるとは $R$ で invariant, (あるいは, $R$ は f-invariant) であるという.

について, すべてのの集合

$f_{i}$

が $X$ -invaiant であるとき, $R$ は A-invariant という. 更に,については, その要素がすべて$S$多項式集合 $A=\{fi$ , ...,$A$

-invariant の時, 同じく$A$$f_{\mathfrak{n}}\}$の部分集合$\mathrm{R}^{r}$-invariant であるという.

Definition 27.2.7 (delineable, identically zero)$\mathrm{A}’$を$\mathrm{R}^{r-1}$のregion とし,$f$を$\mathrm{Q}[X]$の要素とする. $Z(K)$ ( $K$ によって作られる$\mathrm{R}^{r}$のcylindcr)上にある $f$ の零点集合が, 互いに共通部分のない section からなる場合, $f$ はん上 delineable であるという, この時, これらの section によって出来る stack を $S(f, K)$ と書く. $(S(f, K)$ は, f-invariant

である )$\mathrm{R}^{r-1}$の部分集合 $K$ 及び,$\mathrm{Q}[X1$の要素 $f$ に対し, $K$ の任意の点$\alpha$で $f(\alpha, X_{r})\equiv 0$ であるとき, $f$

は, ん上 identically zero であるという.

Example 2 多項式 $f=y^{4}-2y^{3}+y^{2}-3x^{2}y+\mathit{2}x^{4}$ に対し, f-invariant なの$\mathrm{R}^{2}$cylindricaldecomposition を考える. $g=res_{y}(f, f’)=2048x^{1}2-4608_{X^{1}+3}07x8+12x^{6}$ を取る. $g=0$ の realroot は, 計 5 個で, それらより形成される
ら成る.

$f$

は,

$\Psi$$\mathrm{R}$のdecomposition を$\Psi$とする.

の各 cell の上で delineable となっており, 各 cylinder 上集合が, f-invariant な$\mathrm{R}^{2}$の$\Psi$$f$

は, 11 個の cell かで定まる stack の和cylindri $cal$ decomposition を定めている. これを Fig

cylindrical decomposition は, 55 個の cell から成っている.

$\mathit{0}$

に記す.

この

250

Fig .
$\mathit{0}$27.3 CAD algorihtm$\mathrm{Q}[X|=\mathrm{Q}[x_{1},$の多項式の変数順序は $x_{r}>,..>x_{1}$ であるとする.

$x_{T}|$$\ldots,$$subres_{j}(f, g)$ ( $f,$ $g$ の$\mathrm{j}$-th sub-resultant) を

subresultant coefficient)$S_{\mathrm{j}}(f, g)$$\text{を}psCj(f, g)\geq\ovalbox{\tt\small REJECT}$$\langle$とし, $S_{j}(f, g)$ の$x_{r}^{j}$$f,$ $g\in \mathrm{Q}[X]$の係数 ( $f,$

. $n= \min(\deg(f), \deg(g))\mathit{0})\#*,$$g$の$\mathrm{j}$に対し,-th principal$psc_{n}(f, g)=1\text{と_{}j}-_{\mathrm{E}}$める.

ldcf $(f)$ を
ing term すなわち ldcf
$f\in Q[X|$ に対し,$(f)x_{r}^{\mathrm{d}}\mathrm{e}\mathrm{g}\mathrm{t}f)$$f$の$x_{r}$

についての leadingとし, 更に red $(f)$ を

coefficient とし, $ldt(f)$ を lead-$f-ldt(f)$とする.

red $(f)=red(red^{k1}-(f))(reCp(f)=f)$ とする. ここで, RED $(f)=$ {red $(f)$ }また, der $(f)=f’$ をとする$\{psc_{J} (f, g)\}\backslash \{0\}$$f$の$k\geq 0$$\backslash \{0\},$に対して,$PSC(f, g)=$についての微分とし, $der^{}(f)=f$ ,$x_{r}$

der $k(f)=der(d_{C}rk-1(f))$ とする.

Definition 27 .3.1
$A=\{fi, \ldots, f_{n}\}$の$(\mathrm{P}^{fO}jeCtion)$を$\mathrm{Q}[X]$の有限部分集合, に対して, Proj $(A)=$ Proj 1 $(A)\cup Proj2(A)$ を

projection と呼ぶ. ただし, $R_{i}=RED(f_{i})$ , としたとき Proj 1$PSC(g_{l}, g_{i}’))$$A$$(\{ld_{C}f(g1)\}\cup$, Proj $2(A)= \bigcup_{i<j}\bigcup_{g}.,g_{j}\in R,$ $PSC(g|’ g_{J})$ である.

Theorem 27. $3.1A$ をの時,$(A)= \bigcup_{i}\bigcup_{g},\in R,$$A$$\mathrm{Q}[X|$の部分集合, $K$ を Proj$(A)\cdot inva7\dot{\eta}ant$

な$\mathrm{R}^{r-1}$のregion とする.

この任意の要素は, $K$ 上で, delineable であるか, あるいは, identically zero である. また, 任

意の異なる

$A$

の要素 $f,$$g$について, $Z(K)$ の $f$ -section 及び$g$-section は, 共通部分を持たない.

Definition 2732(augmented projection)
Aproj $(A)=Proj(A)\cup Aprojl(A)$ を$\bigcup_{i}\bigcup_{\mathit{9},\in D},$

$PSC(g., \mathit{9}’i),$$A$の augmented projection$D_{i}=\{der k(f)|f\in R., 0<k<de_{\mathit{9}(}f)\}$と呼ぶ. ただし, Aproj 1 $(A)=$

である.

251

Der $(A)=\cup.D_{i}$ とする. すると, Theorem 273.1 に続いて, 次が成り立つ.
Theorem 27. $3.2A$ をの時,$I\iota^{\nearrow}$$\mathrm{Q}[X]$の部分集合, If を $Aproj(A)$ -invariant な$\mathrm{R}^{\gamma-1}$のregion とする.

こが algebraic に定義されていれば, $K$ の cylinder $Z(K)$ 内の各 cell は, algebraic に定義できる.

続いて, CAD algorithm について述べる.

この algorithmを用いた CAD 計算の具体例は, \S 6 で示す.

Procedure $1(main)$r 変数の個数に関する帰納的 Pro cedure)

$n$

入力 :

$n$

変数多項式の集合

出力 :

$A$

-inva

$7\dot{\mathrm{t}}ant$

.

$A$

CAD

な

$\Phi$$n=1$ の時

通常の–変数 sturm 法を$A$に適応し CAD を求める.

$n>1$ の時

Augmented Projection を $A’$ とする.

の

$A$

$A’$

の変数の個数は$D’$

を $A’$ invariant な

$D’$

の

cell をより小さいので, この pro cedure を帰納的に $A’$ に適応する.
$\mathrm{R}^{\mathfrak{n}-1}$. $=1,$$i$$\ldots$

CAD とする.

とする.

$\{\Psi_{1}, \ldots, \Psi\ell\}$, そについて,の$f$Procedure

上の$\Psi_{2}$CAD$\Phi$: を, Pro cedure 2 で求める.

が求める $A$ の CAD である.

$\{\Phi_{1}, \ldots, \Phi_{P}\}$$\mathit{2}(sub)$($f=f_{\Gamma}$ の次数の$\mathrm{R}^{n-1}$$r$に関する帰納的 Procedure)

region$\Psi,$$\Psi$

出力 . f-invariant な CAD$7^{\cdot}=1$のを $\prod_{h\in A}h$ の maximal sqare free part とする.

$f$

入力 :

$A$

-invariant で$\Phi$$x_{n}$

について$r$

次の多変数多項式

$f$

.

.

の時,

$Do=\{\{f(\alpha, x_{n})<0, \Psi(\alpha)\}, \{f(\alpha, x_{n})=0\not\in y\Psi(\alpha)\}, \{f(\alpha, x_{n})=0\mathrm{f}y\Psi(\alpha)\}\}$

が, 求めるもの.

$r>1$ の時,を

$f_{r-1}$

fr-l の$f_{\gamma}$のに関する微分

に関する次数は,$x_{n}$$f_{r}$$\frac{d}{dx_{n}}$力の maximal sqare free part とする.

より小さいので, 帰納的にこの procedure を $ff-1$ に適応.

CAD を三と置く.

$f_{r-l}$の三のcell を,$i=1,$$x_{n}$$t$$\ldots,$$\Phi_{3}\dot{.}=$$x_{n}$

座標が小さいほうから三 1 , ..., 乙と置く.

について,

{

$f(\alpha,$$\beta)=$O&\Psi \Psi \Psi (\alpha )&f, $(\beta)>0,--:-(\beta)$ },252$\Phi_{3\cdot-1}.=$$\Phi_{3i-2}=${{$f(\alpha,$ $\beta)=0\ \Psi\Psi$$f(\alpha,$$\Phi=\{\Phi_{1}, \ldots, \Phi_{3}t\}$(\alpha )&f $(\beta)=0,--\cdot(-.\beta)$ },$\beta)=0\ \Psi(\alpha)\ f_{\mathfrak{n}}(\beta)<0$は,$f_{\mathfrak{n}}$, 三,$(\beta)$},の $CAD$

Remark 273.1
Procedure 2 において,$f_{r}$の,$\Psi$

つしか含まれていない. よって,で定まる cylinder の各 sector は, $D”$ のいずれかの cell に, 高々$\Phi$

が,$f_{n}$のCAD となる.

Remark 2732

Procedure 2 の出力$\Phi$には, null set が, 明らかに, 多く含まれている.

Remark 2733
Collins (1975) の方法では, 同時に sample point も求めることで, 無駄な formula が多少押さえられている. ただし, Procedure は, いささか複雑である.

27.4 CAD の問題点
CAD は, 他の代数制約の手法である Gr\"obner basis や, Ritt &Wu’s method 等よりも歴史がやや新しく, また, 研究者の数も, 他に比べると少ないため, その応用や効率化などの面でやるべきことが,まだまだ多く残されている. 課題となっているものの中で, 特に本質的と思われるものは, 次の三点で

..
.

ある.

Projection,
Real root isolation,

Evaluation.

これらは, アルゴリズムの効率化の面でも特に注目されている事であり, それらに関する論文も多い.

この三点について–つ–つまとめながら, 今後の課題について議論を進めてみる.

27.4.1 Projection
Projection は, 多変数多項式を sub-resultant 等によって, 変数消去する操作であり, これによって結局, -変数多項式の実根を求めることに, 帰着される.

$n$変数多項式であれば, 当然$n$

回の Projectionが行われるわけであるが, その操作によって表れる多項式の集合は, 回を増す毎に巨大なものになるという性質があり, 特に変数の個数が多い場合には, 多項式の数ばかりでなく, その–つ –つのサイズも大きなものとなる場合が少なくない. 特に, Collins (1975) にある, オリジナルなもの (augmented
projection) では, その様な性格が著しく表れる.

-方, Projection は, 上記の Theorem 27.3.1 ある253

いは Theorem 27.3.2 が成り立てばいいわけで, Theoremm

を成立させるような多項式集合をもっと小さくできないかと考えるのは, 自然なことと思われる.
Arnon, Collins,$\mathrm{M}\mathrm{c}\mathrm{C}\mathrm{a}\iota$] $\mathrm{u}\mathrm{m}(1984)$ では, CAD の sample point に注目し, sample point のみを考える場合には, augmented projection は, 必要ないことを示し,$\mathrm{M}\mathrm{c}\mathrm{C}\mathrm{a}\iota \mathrm{l}\mathrm{u}\mathrm{m}(1988)$

では, ‘order invariant’というものを定義し, その条件の元で, Projection を更に小さいものにした. ただし,$\mathrm{M}\mathrm{c}\mathrm{C}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{u}\mathrm{m}$(1988)の方法は, (私見ではあるが) いささか理論的であり, 実計算には向かないかも知れない.
これらの論文以降での, Projection の改良は, 個々の問題に依存した場合では, いくつかなされているが, 一般的な場合での成果は, あまり見かけられない.

もし, ここに挙げたものが理論的限界であるならば, それを示す必要がある. また, 特殊な場合についての考察もまだ充分ではなく, 課題は, まだ残されている.

27.4.2 Real root isolation
再帰的な Projection の操作によって変数消去された多項式集合は, やがて –変数多項式の集合となる.

これらの–変数多項式の実根の分離が, real root isolation の第–段階である. これは, sturm 法

によってなされ, 実際に多項式 $f$ の根て,$\mathrm{R}$の cylindrical algebraic$\alpha$は $f(\alpha)=$ O&a $<\alpha<b$ と表される.

decomposition$\Phi_{1}$

これらの実根を用いが構成される. -変数多項式の根の分離については, Collins &Loos (1982) や, Collins &Johnson (1989) 等に, まとめられている.

次の段階として,を構成することで,$\Phi_{1}$$\mathrm{R}^{2}$の各 region 上で, 二変数多項式の根を分離し, それらを section とする stackの cylindrical algebraic decomposition

だけ段階をふんで, 最終的に$\mathrm{R}^{n}$$\Phi_{2}$が求まる. 同じことを変数の個数の cylindrical algebraic decomposition が得られる.

理論的には, この様な形で求められるわけであるが, 実際の計算では, 様々な問題が出てくる. 根の表現は–変数の場合ならば, -点であるからまだ簡単だが, 多変数の場合には, 一般に高次曲線あるいは, 高次曲面を表現しなくてはならない. よってそれを表現する方法によっては, CAD アルゴリズムの効率性に影響するため, この部分に関する研究も, 比較的盛んである. 特徴的なものでは, 次の様なものが挙げられている.

1. 多変数版 sturm 法を用いる方法 (Collins, 1975)
2. 限定記号を用いた方法 (Arnon&Collins&McCallum, 1984)
3.cylinder を輪切り (slice) する方法. (Arnon & Mignotte, 1988)
これらは, それぞれに長所短所があって, 決定版は今の所ない. (1) は理論的にしっかりしており, す
べての cell が, 機械的に quantifier free formulaとして, 記述できるため, インプリメントしゃすく,quantffier elimination への応用も簡単である. しかし, 本質的に augmented projection を用いているため, Projection が巨大になる傾向がある. (2) は, 簡便な方法ではあるが quantffier eliminationには使いづらい. (3) は, 人為的な操作が加わる分, 結果が見易く判りやすい. しかし, 輪切りの方法が与えられた問題に依存していて, -般論が作りづらい.

254

これらの他にも, 細かな改良が他の論文にも至る所に表れるが, 本質的解決になってない. 結局, 問

題に応じて戦略を変えるしかないのかも知れない.

27.4.3 Evaluation
cylindrical algebraic decomposition の応用は, 主として, quantifier elimination の計算である. その際各 cell の sample point の座標を多項式に代入し, その値の正負あるいは$0$を判定しなくてはならない.

一般に, 各 sample point の座標は, 代数的数で表示されている.
$\alpha^{3}-5=0$-例を挙げれば茜は,$\alpha=$and $1<\alpha<2$ と表され, この値を $f(x)=2x^{4}-4x^{2}-5\in \mathrm{Q}[x]$ に代入した値$f(c\rangle)$の正負を求める, といった様な事が要求される. (ちなみに, $f(\alpha)>0$ である.)

この場合は, 多項式 $x^{3}-5$ の根である$\alpha$を含む区間を sturm 法で狭めていき, その区間で,

$f$

の符号

が変わらないようにすればよい. しかし, sturm 法は, その係数が, 有理数のもの以外では, 実行が難し
く,$\alpha$の定義多項式に別の代数的数$\beta_{1},$$\beta$$\ldots,$.

を含んでいるときには, 別の考察が必要である. Collins(1975) 以来, CAD algorithm 実行中に複数の代数的数が表れた場合, それらの primitive element を求め, その最小多項式から, sturm 法で, 区間を狭める方法が取られてきた.
しかし, この方法のように,$-\text{々}$primitive element を計算するのは, 経験上, 非常に重たい事である. よって, primitive element を計算しないで, sturm 法を実行する事が出来れば, 計算効率がずいぶん上がるはずである.

27.5 最近の動き

27.5.1 Partial CAD
CAD の最も大きな応用分野は, 何度も言っている通り quantffier elimination である.の計算は, 非常に大きな計算で, quantifier elimination をするためだけに,$\mathrm{R}^{n}$

しかし CAD全体の空間分割を計算するのは, いささか大げさすぎることが否めない. その点の改良もいくつかなされている.

その–つが, Partial CAD (Collins&Hong, 1991) である. これは, CAD 計算と, quantifier elimination (実際には, evaluation) を同時に進めることで, 無駄な計算を省くものである.

27.5.2 Simplification
CAD algorithm を通じて, 機械的に求められた quantffier free formula は, 一般に, 非常に大きく

255

なる. しかし, それらの成分のうちほとんどは, 重複していたり, 空集合であったりというように, 余分なものであることが少なくない. よって, これらの quantifiier free formula を simplification しようとする考え方が出てくる. 詳細は, Hong (1992) をお読みいただきたい.

27.5.3 Comprehensive Gr\"obner Bases
CAD 以外の方法で, quantffier elimination を, 機械的に計算する手法もぼちぼち出始めており, その–つが Comprehensive Gr\"obner Bases を用いた方法である. 詳しくは, Weispfenning (1994) を参照のこと.

27.6 CAD の計算例
多項式, $f=y^{4}-2y^{3}+y^{2}-3x^{2}y+2x^{4}$ を考える.

この

$f$

に対し,

$f$

-invariant な cylindricalalgebraic decomposition を, Collins (1975) に多少手を加えた方法で計算する. 変数順序は $y>x$ とする. $f$ は, Fig 1 に表れる零点集合を持つ. $f$ の零点集合が delineable となるように,$\mathrm{R}^{2}$を cylinderに分割すると, Fig 2. となる.
(Collins (1975) の方法では, $f$ の augmented projection AProi $(f)$ を計算し, その零点集合でもって,cylinder に分割するのだが, この場合, $Aproj(f)$ は, 余分な polynimial を多く含んでいて使いづら$\mathrm{A}^{\mathrm{a}}.)$

Fig 2.

Fig 1
これらの分割直線のれる.

$x$座標は, $res_{y}(f, f’)=2048x^{12}-4608x10+37x^{8}+12x^{6}=0$ で表さ.

さて, Fig 2 に表れる各 cell を semi-algebraic に表す事が, 目標である.

$f’=4y^{3}-6y^{2}+2y-3x^{2}$ を用意する.

零点集合によって,$f$

そのためにまず,Fig 3 は, Fig 2 に $f’=0$ を重ねたものである.

の各 cylinder 内の零点集合が, 上下に分離できているのが確認できる.

$f’$

の

この

$f’=0$ を用いるには, 更に, $f’$ の零点集合を semi-algebraic に表現しなくてはいけない. そのために,$f”=12y^{\mathrm{o}}\sim-12y+2$になるように,$\mathrm{R}^{2}$を用意する. Fig 4 は, $f’$ と $f”$ の零点集合を重ね, $f’$ の零点集合が, delineable

を cylinder に分割したものである.

$f”$の零点集合によって, $f’$ のそれが, 分離で256きている. Fig 4 の各分割直線の$x$座標は, $res_{y}(f’, f\prime\prime)=64(243X^{4}-1)=0$ で表される.
O\epsilon り\subset \supset \subset \supset \leftrightarrow --\neg \supset$\text{ら}\overline{\overline{\infty-\ovalbox{\tt\small REJECT}}}^{-\cdot\cdot-}-$Fig 5.

Fig 4

Fig 3

さて, $f”=12y^{2}-12y+2$ (既約) の零点集合は,ある. それぞれの cell は, $f”’=2y-1$ を用いて,全体で delineable であり, cell の個数は, 5 で$\mathrm{R}$$\Phi_{1}^{2},$$\Phi_{5}^{2}$$\ldots,$と semi-algebraic に書ける.

Fig 5 #よ,$f”=0$ と $f”’=^{0}$ を重ねたものである.
$\Phi_{1}^{2}=\{f’’>0\ f^{\prime l\prime}>0\},$ $\Phi_{2}^{2}=\{f’’=0\ f^{\prime\prime l}>0\},$ $\Phi_{3}^{2}=\{f’’<0\}$$\Phi_{4}^{-}’=${ $f”$ =0&f

’

$<0$

,

}, $\Phi_{5}^{2}=\{f’’>0\ f’’’<0\}$ ,続いて, $f’$ について, まず, $243x^{4}-1=0$ で表されると表される. $\Psi_{1}^{1}=\{ 243_{X}4-1 >0\ x>0\}$ ,$\Psi_{2}^{1}=$の分割を行う. sturm 法によって,$x$$\Psi_{1}^{1},$$\ldots$,$\Psi_{5}^{1}${ $243x^{4}-1$ =O&x $>0$ }, A $=\{243_{X}4-1<0\}$ ,$\Psi$$\Psi_{4}^{1}=\{ 243X^{4}-1 =0\ x<0\}$ , $\Psi_{5}^{1}=\{ 243X^{4}-1 >0\ x<0\}$ .

これらを用いて, $f’$ による CAD の各 cell を semi-algebraic に表すと, 次の様に$\Phi_{1,1}^{1},$$\ldots$,$\Phi_{5,3}^{1}$

と

なる.

,

$\Phi_{1,1}^{1}=\Psi_{1}^{1}\ \{f’>0\}$,$\Phi_{1,2}^{1}=\Psi_{1^{\ \mathrm{t}f}}^{1}’=0\}$$\Phi_{2,1}^{1}=\Psi_{2}^{1}\ \{f^{J}>0\}$,$\Phi_{2,2}^{1}=\Psi_{2}^{1}\ \{f’=0\ \Phi_{1}^{2}\}$$\Phi_{2,3}^{1}=\Psi_{2}^{1}\$$\Phi_{1,3}^{1}=\Psi_{1}^{1}\ \{f’<0\}$( $\{f’$ <0&\Phi } V $\{f’<0\ \Phi_{2}^{2}\}\{f’$ <0&\Phi })$\Phi_{2,4}^{1}=\Psi_{2}^{1}\ \{f’=0\ \Phi_{4}^{2}\}$,$\Phi_{2,5}^{1}=\Psi_{2}^{1}\ \{fl<0\ \Phi_{5}^{2}\}$$\Phi_{3,1}^{1}=\Psi_{3}^{1}\ \{f’>0\ \Phi_{1}^{2}\}$,$\Phi_{3,2}^{1}=\Psi_{3}^{1}\ \{f’=0\ \Phi\ovalbox{\tt\small REJECT}\}$$\Phi_{3,3}^{1}=\Psi_{3}^{1}$&($\{f’$$\Phi_{3.5}^{1}=\Psi_{3}^{1}\ (\{f’$<0&\Phi } V$\{f’$<0&\Phi } V>0&\Phi ($\{f’$>0&\Phi$\Phi_{3,4}^{1}=\Psi_{3}^{1}\ \{f’=0\ \Phi_{5}^{2}\}$$\Phi_{4,1}^{1}=\Psi_{4}^{1}$&t $f’>0$ },$\Phi_{4,3}^{1}=\Psi_{4}^{1}\$$\Phi_{4.4}^{1}=\Psi_{4}^{1}$(&t$\{f^{l}$

$\}$

V

,

$f’=0\ \Phi_{4}^{2}\mathrm{I}$,$\Phi_{1,\mathrm{l}}^{0},$V $\{f’$ >0&\Phi$\}$$\Phi_{3,4}^{1}=\Psi_{3}^{1}\ \{f’=0\ \Phi(\}$)$\Phi_{3,5}^{1}=\Psi_{3}^{1}\ \{f’<0\ \Phi_{\mathrm{s}}^{2}\}$,$\{f’$<0&\Phi } V$\{f’$<0&\Phi })$\Phi_{4,5}^{1}=\Psi_{4}^{1}\ \{fl<0\ \Phi^{2}\mathrm{s}\}$$\Phi_{5.2}^{1}=\Psi_{5}^{1}\ \{f’=0\}$

以下, -例を除き, 大幅に省略するがcell から成り, 各々<0&\Phi }),$\Phi_{4,2}^{1}=\Psi_{4}^{1}\ \{f’=0\ \Phi_{1}^{2}\}$<0&\Phi } V$\Phi_{5,1}^{1}=\Psi_{5}^{1}\ \{f’>0\}$$\}$$\{f’$$\Phi_{21}^{0.0},$$\Phi_{1}1,1$$\ldots,$

$f$

の

,

$\Phi_{5.3}^{1}=\Psi_{5}^{1}\ \{f’<0\}$

CAD は, 計 $1+3+5+7+9+5+9+7+5+3+1=55$ 個のと, semi-algebraic に表現できる.

$2048x^{12}-4608x10+37x^{8}+12x^{6}=0$ で与えられる

$x$

軸の分割

これらは, -変数方程式$\Psi_{1}^{0\ldots$\Psi_{11}$0},,$及び上で与えられた257$\Phi_{5,3}1$$\Phi_{1,1}^{1},$$\ldots,$, 及び $f>0,$ $f=0,$ $f<0$ によって表現される. 例えば,$\Phi_{3.2}^{0}$は, 次の様に表現される.

$\Phi_{3,2}^{0}=\Psi_{3}^{0}\ (\{f= 0\ \Phi_{1,1}^{1}\}\mathrm{v}\mathrm{t}f=0\ \Phi_{2.1}^{1}\}\mathrm{t}f=0\ \Phi 3,1\}1)$.

References$\mathrm{D}.\mathrm{S}$.Arnon,$\mathrm{G}.\mathrm{E}$.Collins, S.

$\mathrm{M}\mathrm{c}\mathrm{C}\mathrm{a}\iota \mathrm{l}\mathrm{u}\mathrm{m}$. (1984). Cylindrical algebraic decomposition I: The basic

algorihtm. SIAM J. Comp., 13. 856-877.
$\mathrm{D}.\mathrm{S}$.Arnon, S.

$\mathrm{M}\mathrm{c}\mathrm{C}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{m}$(1892). Cylindrical Algebraic Decomposition by Quaiitifier Elimination.

EUROCAM’ 82. LNCS 144. 215-222.
$\mathrm{D}.\mathrm{S}$.Arnon, M. Mignotee. (1988). On methanical quantiier

elim..ination for$\mathrm{e}\iota_{\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{y}\mathrm{a}$]$\mathrm{g}\mathrm{e}\mathrm{b}\mathrm{r}\mathrm{a}’.\sim$and geometry JSC.1988,5 $(1,2)$ . 237-260.
B. Buchberger,$\mathrm{G}.\mathrm{E}$.Collins, B. Kutzler (1988). Algebraic Methods for Geometric Reasoning. Ann.

Rev. Comput. Sci. 1988, 3. 85-119.
$\mathrm{G}.\mathrm{E}$.Collins.

(1975) Quantifier elimination for the elementary theory of real closed fields by$\mathrm{c}\mathrm{y}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{r}\mathrm{i}_{\mathrm{C}}\mathrm{a}1$$\mathrm{G}.\mathrm{E}$algebraic decomposition. LNCS., 33. 134-183.

. Collins and H. Hong. (1991) Partial cylindrical algebraic decomposition for qualtifier elimination. JSC. 1991,12(3) 299-328.

$\mathrm{G}.\mathrm{E}$.Collins and$\mathrm{J}.\mathrm{R}$.Johnson. (1989) Quantifier elimination and the sign variation method forreal root isolation. Proceedings of ISSAC 1989. 264-271.
$\mathrm{G}.\mathrm{E}$. Collins and$\mathrm{R}.\mathrm{G}$.K. Loos. (1982). Real zeros of polynomials. Computer Algebra, Computing,

Suppl. Springer-Verlag 4, 83-94.
$\mathrm{J}.\mathrm{H}$.Davenport and Y.Siret and E.Tournier. (1988). Computer Algebra (systems and algorithms
for algebraic computation). Academic Press.

H. Hong. (1990). An impurovement of the projection operator in cylindrical algebraic decoInp0-

sition. Proceedings of ISSAC 1990. 261-264.
H.Hong. (1992). Simple Solution Formula Construction in Cylindrical Algebraic Decomposition

based Quantifier Elimination. Proceedings of ISSAC 1992. 177-188.
H.Hong. (1993). Qualitfier Elimination for Formulas Constrained by Quadratic Equations. Proceedings of ISSAC 1993. 264-274.

S.

$\mathrm{M}\mathrm{c}\mathrm{C}\mathrm{a}\iota \mathrm{l}\mathrm{u}\mathrm{m}$. (1988). An Improved Projection Operation for Cylindrical Algebraic Decompositionof Three-dimensional Space. JSC. 1988, 5. 141-161.

V.Weispfenning (1994) A new approach to quantifier elimination for. preprint.

$\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{e}\mathrm{b}\mathrm{r}\mathrm{a}arrow$