\documentclass{slides}
%\documentclass[pdf,distiller,slideColor,colorBG,azure]{prosper}
\usepackage{color}
\usepackage{rgb}
\usepackage{graphicx}
\usepackage{epsfig}
\newcommand{\qed}{$\Box$}
\newcommand{\mred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}}}
\newcommand{\tmred}[1]{\smash{\mathop{\hbox{\rightarrowfill}}\limits_{\scriptstyle #1}\limits^{\scriptstyle *}}}
\newtheorem{prop}{\redc 命題}
\def\gr{Gr\"obner basis }
\def\st{\, s.t. \,}
\def\ni{\noindent} 
\def\init{{\rm in}} 
\def\Q{{\bf Q}} 
\def\Z{{\bf Z}} 
\def\Spoly{{\rm Spoly}}
\def\Span{{\rm Span}}
\def\Supp{{\rm Supp}}
\def\StdMono{{\rm StdMono}}
\def\Im{{\rm Im}}
\def\Ker{{\rm Ker}}
\def\NF{{\rm NF}}
\def\HT{{\rm HT}}
\def\LT{{\rm LT}}
\def\ini{{\rm in}}
\def\rem{{\rm rem}}
\def\Id#1{\langle #1 \rangle}
\def\ve{\vfill\eject} 
\textwidth 9.2in
\textheight 7.2in
\columnsep 0.33in
\topmargin -1in
\def\tc{\color{orange}}
\def\fbc{\bf\color{orange}}
%\def\itc{\color{LimeGreen}}
\def\itc{\color{DarkGreen}}
%\def\urlc{\bf\color{DarkGreen}}
\def\urlc{\bf\color{LimeGreen}}
\def\goldc{\color{goldenrod3}}
\def\redc{\color{orange}}
\def\vs{\vskip 1cm}
\def\vsh{\vskip 0.5cm}
\def\ns{\itc\LARGE}
\title{\tc\bf\ns 代数体上のイデアルのグレブナー基底計算について}

%\slideCaption{代数体上のイデアルのグレブナー基底計算について}
\author{{\bf\Large 野呂 正行\\ 神戸大学理学部}}
\date{\bf\Large Dec. 16, 2004}
\begin{document}
\setlength{\parskip}{20pt}
\maketitle

%\itc: item color
%\fbc: fbox color
%\urlc: URL color
%\goldc: bold color a
%\redc: bold color b

\large
\bf
\setlength{\parskip}{0pt}

\begin{slide}{\ns 代数体の元の表現方法}

原始元による表現は可能 : $F=\Q[t]/(m(t))$
$\Rightarrow$ 係数の増大を招く
$\Rightarrow$ 逐次拡大が現実的
$$F_0=\Q,\quad F_i = F_{i-1}(\alpha_i)\quad (i=1,\ldots,n),\quad F=F_m$$
$m_i(t,\alpha_1,\ldots,\alpha_{i-1})$ : $\alpha_i$ の最小多項式 $/F_{i-1}$

$m_i$ の既約性チェックはかつて困難
$\Rightarrow$ knapsack factorization によりそうでもなくなった. 以下,
$$I=\langle m_1(x_1),m_2(x_1,x_2),\ldots,m_n(x_1,\ldots,x_n)\rangle$$
で, $I$ が $\Q[X]=\Q[x_1,\ldots,x_n]$ の極大イデアルとする.
\end{slide}

\begin{slide}{\ns 代数的数の簡約}

$m_i$ : 主変数 $x_i$ に関する主係数は有理数としてよい.
$\Rightarrow$ 
$G=\{m_1,\ldots,m_n\}$ は, 
$x_n > x_{n-1} > \cdots > x_1$ なる辞書式順序に関する $I$ のグレブナー基底.

$h(x) \bmod I \in Q[X]/I$ に対し,

$h_0 \equiv h \bmod I$, $\deg_{x_i}(h_0) < d_i$ 
$\Rightarrow$ $h=h\NF_G(h)$

$h_0=\rem_{x_1}(\rem_{x_2}(\cdots \rem_{x_n}(h,m_n)\cdots),m_2),m_1)$

でもあるが, \underline{この順で計算してはいけない!!}

($f(a) \bmod b$ を $c=f(a)$ $\Rightarrow$ $c \bmod b$ と計算するようなもの)
\end{slide}

\begin{slide}{\ns 単項簡約による代数的数の簡約}

かといって, 順序を変えればよい, というわけでもない

\underline{多項式剰余自体が危険} : 他の変数の次数が急に上がる

$\Rightarrow$ $G$ による単項簡約を用いる

各簡約ステップに用いる $m_i$ : $i$ の小さいもの優先
\end{slide}

\begin{slide}{\ns 簡約の例}

$m_1(x_1)=x_1^7-7x_1+3$,\\
$m_2(x_1,x_2)=x_2^6+x_1x_2^5+x_1^2x_2^4+x_1^3x_2^3+x_1^4x_2^2+\cdots$\\
$m_3(x_1,x_2,x_3)=63x_3^4+\cdots$

で定義される $F=\Q(\alpha_1,\alpha_2,\alpha_3)$ は $m_1(x_1)$ の
最小分解体.

$(\alpha_1+\alpha_2+\alpha_3)^{20}$ の簡約

$i$ が小さい $m_i$ 優先で簡約 : 0.1 秒

$i$ が大きい $m_i$ 優先で簡約 : 260 秒
\end{slide}

\begin{slide}{\ns 逆元計算}

逆元計算はボトルネックの一つ

拡大次数を $d$ とする.

単拡大 $\Rightarrow$ $O(d^2)$ (拡張 Euclid 互除法)

逐次拡大にも再帰的に適用可能

$h(x_1,\ldots,x_n) \bmod I$ の逆元を計算

$x_n$ に関し $h$, $m_n$ に拡張 Euclid 互除法を適用する

$\Rightarrow$ $\exists a,\exists b, \exists r$, $ah+bm_n=r(x_1,\ldots,x_{n-1})$

$\Rightarrow$ $r$ の逆元を計算すれば, $h$ の逆元が求まる
\end{slide}

\begin{slide}{\ns この方法の問題点}

\begin{itemize}
\item 中間式膨張

最終結果に比較して, $r$ の逆元が巨大になる場合がある.
(計算方法に依存)

\item 簡約化との関係 (部分終結式算法を使う場合)

\begin{itemize}
\item $h \in (\Q[x_1,\ldots,x_{n-1}])[x_n]$ と見なす

係数の除算は多項式の整除となるが, これらに
現われる変数に対する簡約化が行われないので, 一般に大きな多項式
が係数に現われる. 

\item $h\in (\Q(\alpha_1,\ldots,\alpha_{n-1}))[x_n]$ と見なす

係数除算が体演算となり, 逆元計算が必要となる.
\end{itemize}
\end{itemize}
\end{slide}

\begin{slide}{\ns モジュラー計算による逆元計算}

代数的数の計算にはモジュラー計算が有効 

([NORO96], [HOEIJ02]).

\begin{itemize}
\item 中国剰余定理

十分多くの法 $p$ に対し, 法 $p$ での逆元を計算

中国剰余定理,  整数-有理数変換により逆元を得る

有限個の $p$ を除いて法 $p$ での逆元は計算できる. 

\item 未定係数法
$$M=\{x_1^{e_1}\cdots x_n^{e_n} \bmod I \,|\, 0 \le e_i \le d_i-1
(i=1,\ldots,n)\}$$ により逆元を $u = \sum_{t \in M} a_t t$ と表し, $hu
\equiv 1 \bmod I$ から $a_t$ の線形方程式系を作って解く
\end{itemize}
\end{slide}

\begin{slide}{\ns 未定係数法 + Hensel lifting}

未定係数法 は $O(d^3)$ だが, 線形方程式系を Hensel lifting+整数-有理数変換
で解ける

$\Rightarrow$ 

\begin{itemize}
\item $O(d^3)$ は有限体上の LU 分解のみ

結果が大きい係数をもつならば, 計算時間は
Hensel lifting (1 step あたり $O(d^2)$) が dominant

\item $\NF_G(th)$ ($t \in M$) の計算のみで線形方程式ができる

中間式膨張や体除算による問題は現われない.
\end{itemize}
\end{slide}

\begin{slide}{\ns 代数体上のグレブナー基底計算}

\underline{定理}

$F = \Q[\alpha_1,\ldots,\alpha_l] = \Q[T]/I$  ($T=\{t_1,\ldots,t_l\}$)

$I=\langle m_1(t_1),\ldots,m_l(t_1,\ldots,t_l)\rangle$

$J =\langle B \rangle \subset R = F[x_1,\ldots,x_n]$ : $R$ の真のイデアル

$<$ : $R$ の項順序

$<_F$ : $\Q[X]$ 上で $<$ に等しく, $X >> T$ であるブロック順序

$B_F = B \cup \{m_1,\ldots,m_l\}$ 

$G_F = \langle B_F\rangle$ の  $<_F$ に関するグレブナー基底

$\Rightarrow$ $G=(G_F \setminus \Q[T]) \bmod I$ は $J$ の $<$ に関するグレブナー基底
\end{slide}

\begin{slide}{\ns monic 化のために S-多項式が増える}

定理により, $F$ 上のグレブナー基底計算は $\Q$ 上のそれに帰着

実行を観察すると, 生成される中間基底の頭項の $t$ 変数がだんだん消滅 

$\Rightarrow$ 頭係数の逆元計算を S-多項式と単項簡約で実行

$\Rightarrow$ S-多項式の数が増大している

弊害 : 不適切な順序で S-多項式が処理される可能性も増える.
 (不必要な係数膨張の可能性)
\end{slide}

\begin{slide}{\ns 正規形を monic 化}

\begin{itemize}
\item 通常の処理

$S(f,g) \tmred{G} h \neq 0$ ならば, $G \leftarrow G \cup \{h\}$

\item 変更後の処理

$S(f,g) \tmred{G} h(x,t) \neq 0$ ならば, 
$h(x,\alpha)$ を monic 化したもの
$\tilde{h}(x,\alpha)$ を作り,
$G \leftarrow G \cup \{\tilde{h}(x,t)\}$
\end{itemize}

このような変更を行っても $G_F$ が計算できることはあきらか

\end{slide}

\begin{slide}{\ns trace アルゴリズム}

$\bmod p$ でのtrace アルゴリズムの続行に必要なこと

\begin{itemize}
\item $\cdots$ $\Q$ 上の簡約化にあらわれる分母が $p$ で割り切れない

\item 正規形の頭係数が $p$ で割り切れない
\end{itemize}

$\Rightarrow$ monic 化に $p$ で割れる分母があらわれない, と緩められる

(あらかじめイデアルの生成元の一つであったと考えればよい)

\underline{他の実現方法}

$\overline{I}=I \bmod p$ が根基イデアル

$\Rightarrow$ $GF(p)[t]/\overline{I}$ は有限体の直和

$I_p$ : $I$ の係数を $\Q_{<p>}=\{a/b\,|\, a, b \in Z, p \not{|} b\}$
に制限

$\phi$ : $I_p$ からある直和成分への射影

としてもよい

$\Rightarrow$ 有限体上の trace 計算の手間を減らせる可能性がある.
\end{slide}

\begin{slide}{\ns Risa/Asir 上での実装 : 逐次代数拡大}

{\tt Alg} : ボディ部が再帰表現多項式 (既存)

{\tt DAlg} : ボディ部が分散表現多項式 (新規) -- Alg から変換
\begin{verbatim}
typedef struct oDAlg {
        short id;
        char nid;
        char pad;
        struct oDP *nm;  /* 実際には整数係数 */
        struct oQ *dn;   /* 実際には整数 */
} *DAlg;
\end{verbatim}
代数的数としては {\tt nm/dn} : 分母を通分して {\tt dn} とする.

他に, 簡約用に拡大体データを構造体として保持

{\tt set\_field()} で設定できる.
\end{slide}

\begin{slide}{\ns Risa/Asir 上での実装 : グレブナー基底計算}

\begin{itemize}
\item {\tt nd\_gr} および {\tt nd\_gr\_trace} を改造

入力 + 最小多項式に対し実行 + 正規形の monic 化

入力は {\tt Alg} 型を係数に含んでよい (要 monic 化)

\item 内部表現

代数的数は, 元の多項式変数と同等, 正規化計算は有理数体上で
$\Rightarrow$ 係数の content 除去が自動的に適用される.

\item monic 化

monic 化の際にのみ, 本来の係数が代数的数 ({\tt DAlg}型) と
して取り出され, 逆元計算などが行われる.

\item weight

代数的数に対応するweight を 0 に設定 $\Rightarrow$ sugar を
適正にするため
\end{itemize}
\end{slide}

\begin{slide}{\ns 他の実装法}

\underline{代数的数を完全に係数として扱う}

係数に関して簡約化および逆元計算を行う

自然な実装と言える.

content 除去に相当する方法を新たに考案する必要
があり, 今後の課題.
\end{slide}

\begin{slide}{\ns 計算の例}

$\langle \sqrt{2}x^2+(\sqrt{2}+\sqrt{3})xy+\sqrt{3}y^2-\sqrt{3},(\sqrt{2}-2\sqrt{3})x^2+2\sqrt{3}xy+2\sqrt{2}x^2+\sqrt{2}+\sqrt{3}\rangle$ のグレブナー計算
\begin{verbatim}
[0] S2=newalg(x^2-2);
(#0)
[1] S3=newalg(x^2-3);
(#1)
[2] F1=S2*x^2+(S2+S3)*x*y+S3*y^2-S3$
F2=(S2-2*S3)*x^2+2*S3*x*y+2*S2*x^2+S2+S3]$
[3] nd_gr_trace([F1,F2],[x,y],1,1,2);
[90*y^4+(-21*#0*#1-246)*y^2+(16*#0*#1+144),
20*x+(15*#0*#1-60)*y^3+(-7*#0*#1+83)*y]
\end{verbatim}
\end{slide}

\begin{slide}{\ns 実験 : 単根添加}

{\small
\begin{eqnarray*}
Cyc&=&\{f_1,f_2,f_3,f_4,f_5,f_6,f_7\}\\
f_1&=&\omega c_5c_4c_3c_2c_1c_0-1\\
f_2&=&(((((c_5+\omega )c_4+\omega c_5)c_3+\omega c_5c_4)c_2+\omega c_5c_4c_3)c_1+\omega c_5c_4c_3c_2)c_0+\omega c_5c_4c_3c_2c_1\\
f_3&=&((((c_4+\omega )c_3+\omega c_5)c_2+\omega c_5c_4)c_1+\omega c_5c_4c_3)c_0+c_5c_4c_3c_2c_1+\omega c_5c_4c_3c_2\\
f_4&=&(((c_3+\omega )c_2+\omega c_5)c_1+\omega c_5c_4)c_0+c_4c_3c_2c_1+c_5c_4c_3c_2+\omega c_5c_4c_3\\
f_5&=&((c_2+\omega )c_1+\omega c_5)c_0+c_3c_2c_1+c_4c_3c_2+c_5c_4c_3+\omega c_5c_4\\
f_6&=&(c_1+\omega )c_0+c_2c_1+c_3c_2+c_4c_3+c_5c_4+\omega c_5\\
f_7&=&c_0+c_1+c_2+c_3+c_4+c_5+\omega
\end{eqnarray*}}
$Cyc$: cyclic-7 の $c_6$ に 1 の原始 7 乗根 $\omega$ を代入

\underline{$\Q(\omega)$ 上での GB 計算}: 斉次化 trace アルゴリズムにより 22 秒
(monic 化に 2.2 秒 (逆元計算 0.2秒))

\underline{最小多項式を添加して $\Q$ 上で計算} : 220 秒


\end{slide}

\begin{slide}{\ns 実験 : 2 根添加}
{\small
\begin{eqnarray*}
Cap&=&\{f_1,f_2,f_3,f_4\}\\
f_1&=&(2ty-2)x-(\alpha+\beta)zy^2-z\\
f_2&=&2\beta\alpha^4zx^3+(4ty+\beta)x^2+(4zy^2+4z)x+2ty^3-10y^2-10ty+2\alpha^2+\beta^2\\
f_3&=&(t^2-1)x+(\beta\alpha^4+\beta^3\alpha^3)tzy-2z\\
f_4&=&(-z^2+4t^2+\beta\alpha+2\beta^3)zx+(4tz^2+2t^3-10t)y+4z^2-10t^2+\beta\alpha^3\\
m_1&=&u^7-7u+3\\
m_2&=&u^6+\alpha u^5+\alpha^2u^4+\alpha^3u^3+\alpha^4u^2+\alpha^5u+\alpha^6-7
\end{eqnarray*}}
$Cap$ : $Caprasse$ [SYMBDATA] の係数をランダムに代数的数に置き換えた

$\alpha$, $\beta$ : $t^7-7t+3$ の 2 根

\underline{$\Q(\alpha,\beta)$ 上での GB 計算} : 斉次化 trace アルゴリズムで 589 秒
(monic 化 36 秒)

\underline{$\Q$ 上での計算} : 1 時間待っても終了しない.
\end{slide}

\begin{slide}{\ns 実験 : 3 根添加}

$f(x)=x^7-7x+3$ の最小分解体 $F$ は 3 根添加で実現される (既出).

$f(x)$ の $F$ 上因数分解に現れる, $F$ 上の 2 つの 2 次式の
GCD 計算 (GCD は 1 次式) グレブナー基底で計算する.

\underline{$F$ 上の GB 計算} : 0.8 秒 (逆元計算 1 回分が大部分)

\underline{$\Q$ 上で計算} : 60 秒
	
\end{slide}

\begin{slide}{\ns おわりに}

\begin{itemize}
\item DCGB との関係

佐藤ら [SATO01] による DCGB との比較

\item change of ordering, RUR 

FGLM や RUR の計算の代数体上への拡張

(代数体上? or 有理数体上?)

\item 代数体演算の実装の効率化

代数体の表現を {\tt DP} から, より効率よい
実装に変更する

\item Dynamic evaluation

必ずしも既約でない多項式による拡大を許す

$\Rightarrow$ 逆元計算に失敗すれば, 係数環が分解できる.
\end{itemize}

\end{slide}

\begin{slide}{\ns 文献}

[HOEIJ02] M.v. Hoeij, M. Monagan, A Modular GCD algorithm over Number Fields presented with Multiple Extensions. Proc. ISSAC'02 (2002), 109-116.

[NORO96] 野呂, 逐次代数拡大体上での 1 変数多項式の GCD について. 数理研講究録 920 (1996), 1-8.

[SATO01] Y. Sato, A. Suzuki,  Discrete Comprehensive Gr\"obner Bases.
Proc. ISSAC'01 (2001), 292-296.

[SYMBDATA] {\tt http://www.SymbolicData.org}.
\end{slide}

%\begin{slide}{\ns }
%\end{slide}

\end{document}