%$OpenXM: OpenXM/doc/compalg/bib.tex,v 1.4 2001/02/27 08:07:24 noro Exp $
\begin{thebibliography}{99}
\bibitem{ABBOTT}
Abbott, J.A. et al, Factorisation of Polynomials: Old Ideas and Recent Results.
Trends in Computer Algebra (LNCS 296), 81-91.

\bibitem{ADAMS}
Adams, W., Loustaunau, P., An Introduction to Gr\"bner Bases. Graduate
Strudies in Mathematics, Vol. 3., AMS (1994).

\bibitem{ABRW}
Alonso, M. E., Becker, E., Roy, M. F., W\"ormann, T., Zeros,
Multiplicities and Idempotents for Zerodimensinal Systems.
Proc. MEGA94, Birkh\"auser (1996).

\bibitem{BW}
Becker, T., Weispfenning, V., Gr\"obner Bases. GTM 141, Springer-Verlag(1993).

\bibitem{BERL}
Berlekamp, E.R., Factoring Polynomials over Large Finite Fields.
Math. Comp. 24 (1970), 713-735.

\bibitem{GC}
Boehm, H.,Weiser, M., Garbage Collection in an Uncooperative Environment.
Software Practice \& Experience(September 1988), 807-820.

{\tt http://reality.sgi.com/boehm\_mti/gc.html}

\bibitem{BUCH}
Buchberger, B., Ein algorithmisches Kriterium {f\"ur} die
{L\"osbarkeit} eines algebraischen Geichungssystems. Aequ. Math. 4/3
(1970), 374-383.

\bibitem{CZ}
Cantor, D.G., Zassenhaus, H., On Algorithms for Factoring
Polynomials over Finite Fields.
Math. Comp. 36 (1981), 587-592.

\bibitem{WALK}
Collart, M. et al, Converting Bases with the Gr\"obner Walk.
J. Symb. Comp. 24/3/4(1997), 465-469.

\bibitem{COX}
Cox, D., Little, J., O'Shea, D., Ideals, Varieties, and Algorithms. 
UTM, Springer-Verlag (1992).

\bibitem{COX2}
Cox, D., Little, J., O'Shea, D., Using Algebraic Geometry.
GTM 185, Springer-Verlag (1998).

\bibitem{DAV}
Davenport, J.H. et al, Computer Algebra. Academic Press (1988).

\bibitem{DIXON}
Dixon, J. D., Exact Solution of Linear Equations Using P-Adic Expansions.
Numerische Mathematik {\bf 40} (1982), 137-141.

\bibitem{EISEN}
Eisenbud, D., Commutative Algebra with a View Toward Algebraic Geometry.
GTM 150, Springer-Verlag (1995).

\bibitem{FGLM}
Faug\`ere, J.C., Gianni, P., Lazard, D., Mora, T., Efficient
Computation of Zero-dimensional Gr\"obnerr Bases by Change of Ordering. J. 
Symb. Comp. 16/4(1993), 329-344.

\bibitem{F}
Faug\`ere, J.C.,
A new efficient algorithm for computing Groebner bases  ($F_4$),
Journal of Pure and Applied Algebra (139) 1-3 (1999), 61-88.

\bibitem{GEB}
Gebauer, R., M\"oller, H.M., On an installation of Buchberger's algorithm.
J. Symb. Comp. 6/2/3(1989), 275-286.

\bibitem{GEDDES}
Geddes, K.O. et al., Algorithms for Computer Algebra.
Kluwer Academic Publishers, Boston (1992).

\bibitem{GEL}
Gel'fond, A.O., Transcendental and Algebraic Numbers. New York, Dover (1960).

\bibitem{GTZ}
Gianni, P., Trager, B., Zacharias, G., Gr\"obner bases and primary
decomposition of polynomial ideals. J. Symb. Comp. 6/2,3(1988), 149-167.

\bibitem{SUGAR}
Giovini, A., Mora, T., Nielsi, G., Robbiano, L., Traverso, C., ``One
sugar cube, please'' OR Selection strategies in the Buchberger
algorithm.  Proc. ISSAC '91, 49-54.

\bibitem{HOEIJ}
van Hoeij, M., Factoring polynomials and the knapsack problem.
To appear in Journal of Number Theory. The preprint is available
from {\tt http://euclid.math.fsu.edu/\verb+~+hoeij/papers.html}.

\bibitem{KR}
カーニハン, B.W., リッチー, D.M., プログラミング言語 C 第 2 版. 
共立出版 (1989).

\bibitem{KNUTH}
Knuth, D.E., The Art of Computer Programming, Vol. 2. 
Seminumerical Algorithms, 2nd ed. Addison-Wesley (1981).

\bibitem{LENSTRA}
Lenstra, A.K., Lenstra, H.W., Lob\'asz, Factoring polynomials with
rational coefficients, Math, Ann. 261 (1982), 515-534.

\bibitem{SUB}
Loos, R., Generalized Polynomial Remainder Sequences.
Computing, Suppl. 4 (1982), 115-137.

\bibitem{MIG}
Mignotte, M., Mathematics for Computer Algebra.
Springer-Verlag (1982).

\bibitem{YUN}
Moses, J., Yun, D.Y.Y., The EZ GCD Algorithm, Proc. ACM Annual
Conf. (1973), 159-166.

\bibitem{NAGAO}
永尾汎, 代数学. 
新数学講座 4, 朝倉書店 (1983).

\bibitem{REP}
Noro, M., J. McKay,
Computation of replicable functions on Risa/Asir.
Proc. PASCO'97, ACM Press (1997), 130-138.

\bibitem{NS}
Noro, M. et al, Asir.

{\tt ftp://archives.cs.ehime-u.ac.jp/pub/asir2000}

\bibitem{NT}
Noro, M., Takeshima, T., Risa/Asir --- A Computer Algebra system.
Proc. ISSAC'92, ACM Press(1992), 387-396.

\bibitem{NY}
Noro, M., Yokoyama, K., New methods for the change-of-ordering in Gr\"obner
basis computation. Research Report ISIS-RR-95-8E, FUJITSU LABS, ISIS
(1995).

\bibitem{NY2} 
Noro, M., Yokoyama, K., A Modular Method to Compute the
Rational Univariate Representation of Zero-Dimensional Ideals.
J. Symb. Comp. {\bf 28}/1 (1999), 243-263.

\bibitem{OAKU}
大阿久俊則, グレブナ基底と線型偏微分方程式系 (計算代数解析入門).
上智大学数学講究録 No. 38 (1994).

\bibitem{ROBBIANO}
Robbiano, L., Term orderings on the polynomial ring. Proc. EUROCAL'85 (LNCS 204), 513-517.

\bibitem{SASAKI}
佐々木建昭, 数式処理. 情報処理叢書 7, 情報処理学会 (1981). 

\bibitem{SY}
Shimoyama, T., Yokoyaka, K., Localization and Primary Decomposition of
Polynomial ideals. J. Symb. Comp. 22(1996), 247-277.

\bibitem{TAKAGI}
高木貞治, 初等整数論講義 第 2 版. 共立出版 (1971).

\bibitem{TAKAGI2}
高木貞治, 代数学講義 改訂新版. 共立出版 (1965).

\bibitem{GMP} 
Torbj\"orn et al, GNU MP library. Free Software Foundation (1996).

{\tt http://www.fsf.org/software/gmp/gmp.html}

\bibitem{TRAGER} 
Trager, B.M., Algebraic Factoring and Rational Function Integration.
Proc. SYMSAC 76, 219-226.

\bibitem{TRAV}
Traverso, C., Gr\"obner trace algorithms. Proc. ISSAC '88 (LNCS 358), 125-138.

\bibitem{WANG}
Wang, P.S., An Improved Multivariate Polynomial Factoring Algorithm.
Math. Comp. 32(1978), 1215-1231.

\bibitem{WANG2}
Wang, P.S. et al, p-adic Reconstruction of Rational Numbers.
SIGSAM Bulletin 16(1982), 2-3.

\bibitem{SQFR}
Wang, P.S., Trager, B.M., New Algorithms for Polynomial Square-Free Decomposition over the Integers. 
SIAM J. Comp. 8(1979), 300-305.

\bibitem{BMOD}
Weber, K., The Accelerated Integer GCD Algorithm. ACM Transactions on Mathematic
al Software, Vol. 21, No. 1 (1995), 111-122.

\bibitem{SYMP}
吉田春夫, シンプレクティック数値解法.
数理科学, 33, 6 (1995), 27-46.

\bibitem{ZASS}
Zassenhaus, H., On Hensel Factorization I.
J. Number Theory 1 (1969), 291-311.
\end{thebibliography}

本講では, 予備知識として, 線形代数および代数学の基礎的な内容を仮定して
いる. 後者に関しては, 具体的には群, 環, 体などの代数系に関する基礎的事
項, 特に体の拡大およびイデアルに関する知識を持っていることが望まし
い. 例えば \cite{NAGAO} などを薦める. \cite{KNUTH} は, 数, 多項式に関
するさまざまなアルゴリズムが詳細かつ正確に解説されていて, 辞書的に使え
る. \cite{DAV}\cite{GEDDES}\cite{SASAKI} は計算機代数の教科
書. \cite{ADAMS}\cite{BW}\cite{COX}\cite{COX2}\cite{EISEN}\cite{OAKU} 
はグレブナ基底あるいは可換代数に関する教科書. \cite{KR} は C 言語の標
準的な解説書である.

以下, 各章に関し, 参考書, 論文を挙げながら簡単に振り返る. 

\noi
第 2 章:

ここで述べたのは, CPU および C 言語に関する最低限のことがらである. CPU 
に関しては, 文字通り CPU 毎にマニュアルが存在するが, 興味のある方は, 
例えば Pentium などのマニュアルを眺めてみてはどうだろうか. C 言語に関
しては数え切れない程の解説書があるが, 筆者は \cite{KR}の他には, 何らか
のフリーソフトウェアのソースコードを読むことをお勧めする. 特に, {\tt
gmp} \cite{GMP} は第 3 章で述べたアルゴリズムおよびより進んだアルゴリズ
ムが実装されており, 参考になると思う.

\noi
第 3 章:

ここで最も理解しにくいのは除算アルゴリズムであろう. 各補題の証明は
省略してあるので, 練習問題として解いてみれば除算アルゴリズムの仕組み
がよく分かると思う. これらは全て \cite{KNUTH} に証明がある. 
整数 GCD についてなにも述べなかったが, Euclid 互除法の他に binary
GCD アルゴリズムとよばれるタイプのアルゴリズムがあり, 倍精度整数除算
を用いないため高速に実行できる. これに関してはやはり \cite{KNUTH}
に解説されている. また, 最近このタイプのアルゴリズムをさらに進化
させたものが提案されている. これについては \cite{BMOD} 参照. 

\noi
第 4 章:

多項式を C などの高級言語で表現し, その演算を記述してみることは, 
プログラミングのよい練習になる. その際に問題となるのが, 不要になった
メモリ領域の開放に関することである. C 言語ではこれはプログラマの
責任であるが, これを手作業で行うことは, 開放し忘れによるメモリリーク, 
あるいは不適切な開放など, 重大かつ見つけにくいバグの原因となり易い. 
これを防ぐために, \cite{GC} で, 自動ガーベッジコレクタ付きのメモリ
管理が提案された. これはフリーなサブルーチンライブラリとして利用
できる. この章では, 多項式乗算の高速アルゴリズムとして Karatsuba 法
のみを取り上げたが, 高次 (数十次以上) の多項式の乗算が多く必要な場合
には FFT アルゴリズムが有効な場合もある. これについては \cite{KNUTH}
を参照. 

\noi
第 5 章:

ここで述べられていることのうち, 互除法に関することは Euclid 環において
成り立つ. また, 終結式については, その重要性にもかかわらず, 一般的な
代数学の講義などで詳しく扱われることは少ないと思われる. \cite{TAKAGI2}
などで勉強してみてほしい. 

\noi
第 6 章:

ここで扱われている内容は, 計算機代数研究における一つのハイライトとも言
えるものである. 特に, 有限体上の多項式因数分解は, 楕円曲線暗号などへの
直接の応用もあり, 現在も活発に研究されている. また, 有理数体上の因数分
解も, 数学における実験ツールとして計算機代数システムを用いる場合に大変
有効な機能である. この章の内容のうち, 有限体, 有理数体上の一変数多項式
の因数分解に関しては \cite{KNUTH}, 多変数多項式の因数分解に関しては
\cite{SASAKI} あるいは \cite{GEDDES} を参照. なお, アルゴリズム 
\ref{zassenhaus} は 分解される多項式の次数 $n$ に関して最悪計算量が 
$O(2^n)$ となるが, LLL アルゴリズム を用いる多項式時間アルゴリズムが 
\cite{LENSTRA} により提案されている. ただしこのアルゴリズムは実用的と
はいえず, 一般にはアルゴリズム \ref{zassenhaus}が用いられてきた. ごく
最近, 異なる観点から LLL アルゴリズムを用いる方法が \cite{HOEIJ} 
により提案された. この方法は, これまでの方法では事実上分解が不可能だっ
た多項式を効率よく分解するなど, 実用的にも優れていることが報告されてい
る.

\noi
第 7 章, 第 8 章:

ここでは, グレブナ基底, Buchberger アルゴリズムおよびそれらの応用につ
いてごく基本的なことがらのみに限定して述べている. 詳しくは,
\cite{COX} \cite{COX2} を参照. 特に \cite{COX2} は代数幾何, 可換代数
の研究のためのツールとなるアルゴリズムについて, グレブナ基底に限らない
最近の成果も含めて幅広く記述されている. 

\noi
第 9 章:

ここでは, 理論上も応用上も重要なイデアルの準素分解について概説している. 
アルゴリズムはさまざまな部品から成っており, それらの説明については, 
\cite{BW} を参照. なお, ここで述べたのとは異なる準素分解アルゴリズムが
\cite{SY} で提案されており, Risa/Asir に実装されている. 

\noi
第 10 章, 第 11 章:

これらの章はやや特殊な内容を扱っており, グレブナ基底計算をツールとして
用いる場合には特に意識する必要はない. しかし, それを単なる便利なブラッ
クボックスと考えると, ちょっとした問題でもすぐに計算が破綻してしまうこ
とは知っておく必要がある. 任意入力からのグレブナ基底計算については, 最
近提案された $F_4$ アルゴリズム \cite{F} が有力であるが, まだ汎用計算
機代数システムなどには実装されていないようである. また, change of
ordering については, ここで述べた方法の他に Gr\"obner walk と呼ばれる方法が 
\cite{WALK} で提案されている. modular change of orderingおよび modular
RUR は Risa/Asir に実装されている.