\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\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\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} \title{\bf Risa/Asir 上の新グレブナー基底計算パッケージについて} %\slideCaption{Risa/Asir 上の新グレブナー基底計算パッケージについて} \author{{\bf\Large 野呂 正行\\ 神戸大学理学部数学科}} %\date{\bf\Large June 21, 2002} %\date{\bf\Large Nov. 26, 2003} \date{\bf\Large Dec. 18, 2003} \begin{document} \setlength{\parskip}{10pt} \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}{新パッケージ開発の経緯} グレブナー基底計算の効率 : アルゴリズムと同時に, 実装, データ構造にも大きく 依存 分散表現多項式 {\tt DP} : 単項式 {\tt MP} の linked list {\tt MP} : 指数ベクトル {\tt DL} をポインタでもつ {\tt DL} : 32bit 整数配列 (1 要素 32bit で固定) \vskip 1cm \begin{tabular}{cc} \begin{minipage}{.5\hsize} \baselineskip 0.5in \begin{verbatim} typedef struct oMP { struct oDL *dl; P c; struct oMP *next; } *MP; \end{verbatim} \end{minipage} & \begin{minipage}{.5\hsize} \baselineskip 0.5in \begin{verbatim} typedef struct oDL { int td; int d[1]; } *DL; \end{verbatim} \end{minipage} \end{tabular} \end{slide} \begin{slide}{Singular との比較} Singular 2-0-4 \begin{itemize} \item 有限体上で高速 基本的アルゴリズムは Asir と同じ. 論文によると, geobucket, 可変長指数ベクトル, 効率よい メモリ管理 etc. を実装 \item 有理数体上でも高速 gmp を整数演算に使用 $\Rightarrow$ Asir の bignum より, 大きい数では速い \end{itemize} \end{slide} \begin{slide}{負けっぱなしはくやしい$\ldots$} ほぼ完全に 0 から書く (できれば) オリジナルな工夫を入れたい $\Rightarrow$ (試行錯誤をさんざんやった)結果として, geobucket, 可変長指数ベクトルは実装 状況に応じた 2 種類の多項式表現 (リスト or 配列) の切替え 正規化計算における reducer 探しにハッシュを利用 関数のインライン, unrolling の多用 \end{slide} \begin{slide}{効率化の工夫 --- geobucket} 多項式を, 配列 $g$で持つ $g[i]$ には, 項数が, 高々 $b^i$ の多項式が入る 多項式は, $g[i]$ 全部の和 項数が $l$ ($b^(i-1) < l \le b^i$) の多項式 $p$ を $g$ に 足す場合 \begin{enumerate} \item $p \leftarrow g[i]+p$ \item もし $p$ の長さが $b^i$ より大なら, $g[i]=0$, $i\leftarrow i+1$, 1. へ. さもなくば, $g[i] \leftarrow p$ として終了 \end{enumerate} 効果 : 多数の和の計算において, 比較演算を減らす \end{slide} \begin{slide}{効率化の工夫 --- 可変長指数ベクトル} 例えば, $f(x_1,x_2,x_3,x_4)$ の各変数の指数が 256 以下なら, 指数ベクトルは 32 bit に 4 つ入る. \begin{tabular}{|c|c|c|c|} \hline $e_1$ & $e_2$ & $e_3$ & $e_4$ \\ \hline \end{tabular} 指数の和 : 32bit 整数の和 指数の比較 : 辞書式なら, 32bit 整数の大きさの比較 逆辞書式なら, あらかじめ逆順に詰める. \end{slide} \begin{slide}{効率化の工夫 --- 配列による多項式の保持} 基本操作 : $f-mg$ ($m$ は単項式) $f-(mg)$ : geobucket $mg$ : $g$ の表現により, 効率が異なる 試行錯誤の結果 : $g$ が, メモリ上に一次元的に表現されていると高速 $g$ は中間基底 $\Rightarrow$ 中間基底のみ, 配列表現 $mg$ 自身は, 加算にまわるので, linked list がよい \end{slide} \begin{slide}{効率化の工夫 --- 関数のインライン化, unrolling} 大物を片付けると, 小物が目につく 小物 : 指数ベクトルの操作 (和, 差, 比較, divisibility) 実験で比較しながら, したほうがよいものをインライン, unrolling \end{slide} \begin{slide}{効率化の工夫 --- reducer サーチのハッシュ化} 項 t を割り切る中間基底 $g_t$ のサーチも問題となった $g_t$ は, 古い基底から順に探す $\Rightarrow$ あれば一意的 $\Rightarrow$ ハッシュ表 $H$ は, $t$ のハッシュ値 $h(t)$ に対し, $H[h(t)]$ に $(t,g_t)$ を登録する. $t$ が与えられたら, $H[h(t)]$ を探し, みつかったら $g_t$ を使う. なければ $g_t$ を通常の方法でさがし, あれば $H[h(t)]$ に 登録 \end{slide} \begin{slide}{効率化の工夫 --- 斉次の場合の効率化} \begin{itemize} \item 一般の場合 : 途中で interreduction しない \item 斉次の場合 : してよい 頭項は変化しない 得られた中間基底は実は簡約グレブナー基底のうち, 現次数までのすべて $\Rightarrow$ 0 に正規化された S-poly は, interreduction 後も 0 に行く \end{itemize} \end{slide} \begin{slide}{効率化の工夫 --- メモリ管理} 比較的小さいメモリ領域が繰り返し必要となる $\Rightarrow$ 毎回 {\tt GC\_malloc()} は重すぎ $\Rightarrow$ GC からもらったメモリを, 自前で フリーリスト管理 \end{slide} \begin{slide}{各部の詳細 --- ドライバ} \begin{itemize} \item {\tt nd\_gr} 有限体, 有理数体係数など, すべてに対応する. \item {\tt nd\_gr\_trace} 有理数体専用. trace アルゴリズムを実行する. 斉次化を利用するよう指定が可能 \item {\tt nd\_f4} 有限体専用 $F_4$ 実装. 時間, 空間双方に関する効率化 を目指した実装 \end{itemize} \end{slide} \begin{slide}{各部の詳細 --- 指数ベクトルの長さ変更} \begin{itemize} \item あふれ 多項式 $f$ $\Rightarrow$ 最大指数ベクトル $M_f$ を対応 \item $x^E f$ $E+M_f$ があふれをおこすかどうか調べる \item チェックが必要な場所 S-poly 計算, 正規化における, 単項式 $\times$ reducer の計算 \end{itemize} \end{slide} \begin{slide}{各部の詳細 --- その他} \begin{itemize} \item 中間基底をディスク上に置き, demand loading 既存機能と同じスイッチを使う. ({\tt dp\_gr\_flags()}). \item content 除去 default で行う. 頭係数が 2 倍の bit 長になったら content 除去 \end{itemize} \end{slide} \begin{slide}{性能 --- 有限体上での cyclic-$n$ } \vskip 1cm \begin{tabular}{c||c|c|c|c} $n$ & {\tt nd\_gr} & Singular & {\tt nd\_f4} & {\tt dp\_gr\_mod\_main} \\ \hline 7 & 5.1 & 5.0 & 1.8 & 17 \\ 8 & 124 & 135 & 34 & 564 \\ 9 & 27810 & 29725 & 3951 & --- \\ \end{tabular} \end{slide} \begin{slide}{性能 --- 有限体上でのベンチマーク } \vskip 1cm \begin{tabular}{c||c|c|c} & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline dl & 5.9 & 4.9 &4.0 \\ eco10 & 7.1 & 10 &3.1 \\ eco11 & 63 & 106 &23 \\ eco12 & 507 & 1012 &198 \\ extcyc6 & 11 & 9.4 &4.1 \\ extcyc7 & 1813 & 1283 &447 \\ f855 & 3.6 & 3.4 &2.5 \\ filter9 & 0.28 & 0.80 &3.2 \\ hairer2 & 5.9 & 3.8 &4.5 \\ hairer3 & 11 & 35 &* \end{tabular} \end{slide} \begin{slide}{性能 --- 有限体上でのベンチマーク } \vskip 1cm \begin{tabular}{c||c|c|c} & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline hcyclic7 & 6.5 & 4.8 &3.1 \\ hcyclic8 & 213 & 163 &82 \\ hf744 & 1.1 & 1.1 &1.6 \\ hf855 & 25 & 25 &17 \\ ilias13 & 11 & 8.4 &6.0\\ ilias\_k\_2 & 3.1 & 2.7 &1.1\\ ilias\_k\_3 & 4.4 & 2.9 &1.2 \\ katsura10 & 285 & 218 &80 \\ katsura8 & 4.1 & 3.3 &1.3 \\ katsura9 & 35 & 29 &11 \\ \end{tabular} \end{slide} \begin{slide}{性能 --- 有限体上でのベンチマーク } \vskip 1cm \begin{tabular}{c||c|c|c} & {\tt nd\_gr} & Singular & {\tt nd\_f4} \\ \hline noon7 & 4.4 & 1.8 &13 \\ noon8 & 35 & 18 &220 \\ pinchon1 & 3.6 & 1.0 &7.6 \\ rbpl & 1.0 & 0.89 &1.2 \\ redcyc7 & 3.5 & 3.3 &1.2 \\ redeco10 & 2.8 & 2.3 &1.3 \\ redeco11 & 24 & 18 &12 \\ redeco12 & 177 & 134 &74 \\ reimer6 & 11 & 32 &10 \\ reimer7 & 4000 & 4108 & 956 \\ virasoro & 1.8 & 1.4 & 0.65 \end{tabular} \end{slide} \begin{slide}{今後の予定} \begin{itemize} \item 有理関数体上のグレブナー基底計算 \item 有理数体上の $F_4$ 計算 \item tangent cone アルゴリズム, 標準基底 \end{itemize} \end{slide} %\begin{slide}{} %\end{slide} \end{document}