Return to bib.tex CVS log

Up to [local] / OpenXM / doc / compalg

Annotation of OpenXM/doc/compalg/bib.tex, Revision 1.3

1.3     ! noro        1: %$OpenXM$
1.1       noro        2: \begin{thebibliography}{99}
                      3: \bibitem{ABBOTT}
                      4: Abbott, J.A. et al, Factorisation of Polynomials: Old Ideas and Recent Results.
                      5: Trends in Computer Algebra (LNCS 296), 81-91.
                      6:
                      7: \bibitem{ADAMS}
                      8: Adams, W., Loustaunau, P., An Introduction to Gr\"bner Bases. Graduate
                      9: Strudies in Mathematics, Vol. 3., AMS (1994).
                     10:
                     11: \bibitem{ABRW}
                     12: Alonso, M. E., Becker, E., Roy, M. F., W\"ormann, T., Zeros,
                     13: Multiplicities and Idempotents for Zerodimensinal Systems.
                     14: Proc. MEGA94, Birkh\"auser (1996).
                     15:
                     16: \bibitem{BW}
                     17: Becker, T., Weispfenning, V., Gr\"obner Bases. GTM 141, Springer-Verlag(1993).
                     18:
                     19: \bibitem{BERL}
                     20: Berlekamp, E.R., Factoring Polynomials over Large Finite Fields.
                     21: Math. Comp. 24 (1970), 713-735.
                     22:
                     23: \bibitem{GC}
                     24: Boehm, H.,Weiser, M., Garbage Collection in an Uncooperative Environment.
                     25: Software Practice \& Experience(September 1988), 807-820.
                     26:
                     27: {\tt http://reality.sgi.com/boehm\_mti/gc.html}
                     28:
                     29: \bibitem{BUCH}
                     30: Buchberger, B., Ein algorithmisches Kriterium {f\"ur} die
                     31: {L\"osbarkeit} eines algebraischen Geichungssystems. Aequ. Math. 4/3
                     32: (1970), 374-383.
                     33:
                     34: \bibitem{CZ}
                     35: Cantor, D.G., Zassenhaus, H., On Algorithms for Factoring
                     36: Polynomials over Finite Fields.
                     37: Math. Comp. 36 (1981), 587-592.
                     38:
                     39: \bibitem{WALK}
                     40: Collart, M. et al, Converting Bases with the Gr\"obner Walk.
                     41: J. Symb. Comp. 24/3/4(1997), 465-469.
                     42:
                     43: \bibitem{COX}
                     44: Cox, D., Little, J., O'Shea, D., Ideals, Varieties, and Algorithms.
                     45: UTM, Springer-Verlag (1992).
                     46:
                     47: \bibitem{COX2}
                     48: Cox, D., Little, J., O'Shea, D., Using Algebraic Geometry.
                     49: GTM 185, Springer-Verlag (1998).
                     50:
                     51: \bibitem{DAV}
                     52: Davenport, J.H. et al, Computer Algebra. Academic Press (1988).
                     53:
                     54: \bibitem{DIXON}
                     55: Dixon, J. D., Exact Solution of Linear Equations Using P-Adic Expansions.
                     56: Numerische Mathematik {\bf 40} (1982), 137-141.
                     57:
                     58: \bibitem{EISEN}
                     59: Eisenbud, D., Commutative Algebra with a View Toward Algebraic Geometry.
                     60: GTM 150, Springer-Verlag (1995).
                     61:
                     62: \bibitem{FGLM}
                     63: Faug\`ere, J.C., Gianni, P., Lazard, D., Mora, T., Efficient
                     64: Computation of Zero-dimensional Gr\"obnerr Bases by Change of Ordering. J.
                     65: Symb. Comp. 16/4(1993), 329-344.
                     66:
                     67: \bibitem{F}
                     68: Faug\`ere, J.C.,
                     69: A new efficient algorithm for computing Groebner bases  ($F_4$),
                     70: Journal of Pure and Applied Algebra (139) 1-3 (1999), 61-88.
                     71:
                     72: \bibitem{GEB}
                     73: Gebauer, R., M\"oller, H.M., On an installation of Buchberger's algorithm.
                     74: J. Symb. Comp. 6/2/3(1989), 275-286.
                     75:
                     76: \bibitem{GEDDES}
                     77: Geddes, K.O. et al., Algorithms for Computer Algebra.
                     78: Kluwer Academic Publishers, Boston (1992).
                     79:
                     80: \bibitem{GEL}
                     81: Gel'fond, A.O., Transcendental and Algebraic Numbers. New York, Dover (1960).
                     82:
                     83: \bibitem{GTZ}
                     84: Gianni, P., Trager, B., Zacharias, G., Gr\"obner bases and primary
                     85: decomposition of polynomial ideals. J. Symb. Comp. 6/2,3(1988), 149-167.
                     86:
                     87: \bibitem{SUGAR}
                     88: Giovini, A., Mora, T., Nielsi, G., Robbiano, L., Traverso, C., ``One
                     89: sugar cube, please'' OR Selection strategies in the Buchberger
                     90: algorithm.  Proc. ISSAC '91, 49-54.
                     91:
                     92: \bibitem{KR}
                     93: $B%+!<%K%O%s(B, B.W., $B%j%C%A!<(B, D.M., $B%W%m%0%i%_%s%08@8l(B C $BBh(B 2 $BHG(B.
                     94: $B6&N)=PHG(B (1989).
                     95:
                     96: \bibitem{KNUTH}
                     97: Knuth, D.E., The Art of Computer Programming, Vol. 2.
                     98: Seminumerical Algorithms, 2nd ed. Addison-Wesley (1981).
                     99:
                    100: \bibitem{SUB}
                    101: Loos, R., Generalized Polynomial Remainder Sequences.
                    102: Computing, Suppl. 4 (1982), 115-137.
                    103:
                    104: \bibitem{MIG}
                    105: Mignotte, M., Mathematics for Computer Algebra.
                    106: Springer-Verlag (1982).
                    107:
                    108: \bibitem{YUN}
                    109: Moses, J., Yun, D.Y.Y., The EZ GCD Algorithm, Proc. ACM Annual
                    110: Conf. (1973), 159-166.
                    111:
                    112: \bibitem{NAGAO}
                    113: $B1JHxHF(B, $BBe?t3X(B.
                    114: $B?7?t3X9V:B(B 4, $BD+AR=qE9(B (1983).
                    115:
                    116: \bibitem{REP}
                    117: Noro, M., J. McKay,
                    118: Computation of replicable functions on Risa/Asir.
                    119: Proc. PASCO'97, ACM Press (1997), 130-138.
                    120:
                    121: \bibitem{NS}
1.2       noro      122: Noro, M. et al, Asir.
1.1       noro      123:
                    124: {\tt ftp://archives.cs.ehime-u.ac.jp/pub/asir2000}
                    125:
                    126: \bibitem{NT}
                    127: Noro, M., Takeshima, T., Risa/Asir --- A Computer Algebra system.
                    128: Proc. ISSAC'92, ACM Press(1992), 387-396.
                    129:
                    130: \bibitem{NY}
                    131: Noro, M., Yokoyama, K., New methods for the change-of-ordering in Gr\"obner
                    132: basis computation. Research Report ISIS-RR-95-8E, FUJITSU LABS, ISIS
                    133: (1995).
                    134:
                    135: \bibitem{NY2}
                    136: Noro, M., Yokoyama, K., A Modular Method to Compute the
                    137: Rational Univariate Representation of Zero-Dimensional Ideals.
                    138: J. Symb. Comp. {\bf 28}/1 (1999), 243-263.
                    139:
                    140: \bibitem{OAKU}
                    141: $BBg0$5W=SB'(B, $B%0%l%V%J4pDl$H@~7?JPHyJ,J}Dx<07O(B ($B7W;;Be?t2r@OF~Lg(B).
                    142: $B>eCRBg3X?t3X9V5fO?(B No. 38 (1994).
                    143:
                    144: \bibitem{ROBBIANO}
                    145: Robbiano, L., Term orderings on the polynomial ring. Proc. EUROCAL'85 (LNCS 204), 513-517.
                    146:
                    147: \bibitem{SASAKI}
                    148: $B:4!9LZ7z><(B, $B?t<0=hM}(B. $B>pJs=hM}AQ=q(B 7, $B>pJs=hM}3X2q(B (1981).
                    149:
                    150: \bibitem{SY}
                    151: Shimoyama, T., Yokoyaka, K., Localization and Primary Decomposition of
                    152: Polynomial ideals. J. Symb. Comp. 22(1996), 247-277.
                    153:
                    154: \bibitem{TAKAGI}
                    155: $B9bLZDg<#(B, $B=iEy@0?tO@9V5A(B $BBh(B 2 $BHG(B. $B6&N)=PHG(B (1971).
                    156:
                    157: \bibitem{TAKAGI2}
                    158: $B9bLZDg<#(B, $BBe?t3X9V5A(B $B2~D{?7HG(B. $B6&N)=PHG(B (1965).
                    159:
                    160: \bibitem{GMP}
                    161: Torbj\"orn et al, GNU MP library. Free Software Foundation (1996).
                    162:
                    163: {\tt http://www.fsf.org/software/gmp/gmp.html}
                    164:
                    165: \bibitem{TRAGER}
                    166: Trager, B.M., Algebraic Factoring and Rational Function Integration.
                    167: Proc. SYMSAC 76, 219-226.
                    168:
                    169: \bibitem{TRAV}
                    170: Traverso, C., Gr\"obner trace algorithms. Proc. ISSAC '88 (LNCS 358), 125-138.
                    171:
                    172: \bibitem{WANG}
                    173: Wang, P.S., An Improved Multivariate Polynomial Factoring Algorithm.
                    174: Math. Comp. 32(1978), 1215-1231.
                    175:
                    176: \bibitem{WANG2}
                    177: Wang, P.S. et al, p-adic Reconstruction of Rational Numbers.
                    178: SIGSAM Bulletin 16(1982), 2-3.
                    179:
                    180: \bibitem{SQFR}
                    181: Wang, P.S., Trager, B.M., New Algorithms for Polynomial Square-Free Decomposition over the Integers.
                    182: SIAM J. Comp. 8(1979), 300-305.
                    183:
                    184: \bibitem{BMOD}
                    185: Weber, K., The Accelerated Integer GCD Algorithm. ACM Transactions on Mathematic
                    186: al Software, Vol. 21, No. 1 (1995), 111-122.
                    187:
                    188: \bibitem{SYMP}
                    189: $B5HED=UIW(B, $B%7%s%W%l%/%F%#%C%/?tCM2rK!(B.
                    190: $B?tM}2J3X(B, 33, 6 (1995), 27-46.
                    191:
                    192: \bibitem{ZASS}
                    193: Zassenhaus, H., On Hensel Factorization I.
                    194: J. Number Theory 1 (1969), 291-311.
                    195: \end{thebibliography}
                    196:
                    197: $BK\9V$G$O(B, $BM=HwCN<1$H$7$F(B, $B@~7ABe?t$*$h$SBe?t3X$N4pACE*$JFbMF$r2>Dj$7$F(B
                    198: $B$$$k(B. $B8e<T$K4X$7$F$O(B, $B6qBNE*$K$O72(B, $B4D(B, $BBN$J$I$NBe?t7O$K4X$9$k4pACE*;v(B
                    199: $B9`(B, $BFC$KBN$N3HBg$*$h$S%$%G%"%k$K4X$9$kCN<1$r;}$C$F$$$k$3$H$,K>$^$7(B
                    200: $B$$(B. $BNc$($P(B \cite{NAGAO} $B$J$I$rA&$a$k(B. \cite{KNUTH} $B$O(B, $B?t(B, $BB?9`<0$K4X(B
                    201: $B$9$k$5$^$6$^$J%"%k%4%j%:%`$,>\:Y$+$D@53N$K2r@b$5$l$F$$$F(B, $B<-=qE*$K;H$((B
                    202: $B$k(B. \cite{DAV}\cite{GEDDES}\cite{SASAKI} $B$O7W;;5!Be?t$N652J(B
                    203: $B=q(B. \cite{ADAMS}\cite{BW}\cite{COX}\cite{COX2}\cite{EISEN}\cite{OAKU}
                    204: $B$O%0%l%V%J4pDl$"$k$$$O2D49Be?t$K4X$9$k652J=q(B. \cite{KR} $B$O(B C $B8@8l$NI8(B
                    205: $B=`E*$J2r@b=q$G$"$k(B.
                    206:
                    207: $B0J2<(B, $B3F>O$K4X$7(B, $B;29M=q(B, $BO@J8$r5s$2$J$,$i4JC1$K?6$jJV$k(B.
                    208:
                    209: \noi
                    210: $BBh(B 2 $B>O(B:
                    211:
                    212: $B$3$3$G=R$Y$?$N$O(B, CPU $B$*$h$S(B C $B8@8l$K4X$9$k:GDc8B$N$3$H$,$i$G$"$k(B. CPU
                    213: $B$K4X$7$F$O(B, $BJ8;zDL$j(B CPU $BKh$K%^%K%e%"%k$,B8:_$9$k$,(B, $B6=L#$N$"$kJ}$O(B,
                    214: $BNc$($P(B Pentium $B$J$I$N%^%K%e%"%k$rD/$a$F$_$F$O$I$&$@$m$&$+(B. C $B8@8l$K4X(B
                    215: $B$7$F$O?t$(@Z$l$J$$Dx$N2r@b=q$,$"$k$,(B, $BI.<T$O(B \cite{KR}$B$NB>$K$O(B, $B2?$i$+(B
                    216: $B$N%U%j!<%=%U%H%&%'%"$N%=!<%9%3!<%I$rFI$`$3$H$r$*4+$a$9$k(B. $BFC$K(B, {\tt
                    217: gmp} \cite{GMP} $B$OBh(B 3 $B>O$G=R$Y$?%"%k%4%j%:%`$*$h$S$h$j?J$s$@%"%k%4%j%:(B
                    218: $B%`$,<BAu$5$l$F$*$j(B, $B;29M$K$J$k$H;W$&(B.
                    219:
                    220: \noi
                    221: $BBh(B 3 $B>O(B:
                    222:
                    223: $B$3$3$G:G$bM}2r$7$K$/$$$N$O=|;;%"%k%4%j%:%`$G$"$m$&(B. $B3FJdBj$N>ZL@$O(B
                    224: $B>JN,$7$F$"$k$N$G(B, $BN}=,LdBj$H$7$F2r$$$F$_$l$P=|;;%"%k%4%j%:%`$N;EAH$_(B
                    225: $B$,$h$/J,$+$k$H;W$&(B. $B$3$l$i$OA4$F(B \cite{KNUTH} $B$K>ZL@$,$"$k(B.
                    226: $B@0?t(B GCD $B$K$D$$$F$J$K$b=R$Y$J$+$C$?$,(B, Euclid $B8_=|K!$NB>$K(B binary
1.2       noro      227: GCD $B%"%k%4%j%:%`$H$h$P$l$k%?%$%W$N%"%k%4%j%:%`$,$"$j(B, $BG\@:EY@0?t=|;;(B
                    228: $B$rMQ$$$J$$$?$a9bB.$K<B9T$G$-$k(B. $B$3$l$K4X$7$F$O$d$O$j(B \cite{KNUTH}
1.1       noro      229: $B$K2r@b$5$l$F$$$k(B. $B$^$?(B, $B:G6a$3$N%?%$%W$N%"%k%4%j%:%`$r$5$i$K?J2=(B
                    230: $B$5$;$?$b$N$,Ds0F$5$l$F$$$k(B. $B$3$l$K$D$$$F$O(B \cite{BMOD} $B;2>H(B.
                    231:
                    232: \noi
                    233: $BBh(B 4 $B>O(B:
                    234:
                    235: $BB?9`<0$r(B C $B$J$I$N9b5i8@8l$GI=8=$7(B, $B$=$N1i;;$r5-=R$7$F$_$k$3$H$O(B,
                    236: $B%W%m%0%i%_%s%0$N$h$$N}=,$K$J$k(B. $B$=$N:]$KLdBj$H$J$k$N$,(B, $BITMW$K$J$C$?(B
                    237: $B%a%b%jNN0h$N3+J|$K4X$9$k$3$H$G$"$k(B. C $B8@8l$G$O$3$l$O%W%m%0%i%^$N(B
                    238: $B@UG$$G$"$k$,(B, $B$3$l$r<j:n6H$G9T$&$3$H$O(B, $B3+J|$7K:$l$K$h$k%a%b%j%j!<%/(B,
                    239: $B$"$k$$$OITE,@Z$J3+J|$J$I(B, $B=EBg$+$D8+$D$1$K$/$$%P%0$N860x$H$J$j0W$$(B.
                    240: $B$3$l$rKI$0$?$a$K(B, \cite{GC} $B$G(B, $B<+F0%,!<%Y%C%8%3%l%/%?IU$-$N%a%b%j(B
                    241: $B4IM}$,Ds0F$5$l$?(B. $B$3$l$O%U%j!<$J%5%V%k!<%A%s%i%$%V%i%j$H$7$FMxMQ(B
                    242: $B$G$-$k(B. $B$3$N>O$G$O(B, $BB?9`<0>h;;$N9bB.%"%k%4%j%:%`$H$7$F(B Karatsuba $BK!(B
                    243: $B$N$_$r<h$j>e$2$?$,(B, $B9b<!(B ($B?t==<!0J>e(B) $B$NB?9`<0$N>h;;$,B?$/I,MW$J>l9g(B
                    244: $B$K$O(B FFT $B%"%k%4%j%:%`$,M-8z$J>l9g$b$"$k(B. $B$3$l$K$D$$$F$O(B \cite{KNUTH}
                    245: $B$r;2>H(B.
                    246:
                    247: \noi
                    248: $BBh(B 5 $B>O(B:
                    249:
                    250: $B$3$3$G=R$Y$i$l$F$$$k$3$H$N$&$A(B, $B8_=|K!$K4X$9$k$3$H$O(B Euclid $B4D$K$*$$$F(B
                    251: $B@.$jN)$D(B. $B$^$?(B, $B=*7k<0$K$D$$$F$O(B, $B$=$N=EMW@-$K$b$+$+$o$i$:(B, $B0lHLE*$J(B
                    252: $BBe?t3X$N9V5A$J$I$G>\$7$/07$o$l$k$3$H$O>/$J$$$H;W$o$l$k(B. \cite{TAKAGI2}
                    253: $B$J$I$GJY6/$7$F$_$F$[$7$$(B.
                    254:
                    255: \noi
                    256: $BBh(B 6 $B>O(B:
                    257:
                    258: $B$3$3$G07$o$l$F$$$kFbMF$O(B, $B7W;;5!Be?t8&5f$K$*$1$k0l$D$N%O%$%i%$%H$H$b8@(B
                    259: $B$($k$b$N$G$"$k(B. $BFC$K(B, $BM-8BBN>e$NB?9`<00x?tJ,2r$O(B, $BBJ1_6J@~0E9f$J$I$X$N(B
                    260: $BD>@\$N1~MQ$b$"$j(B, $B8=:_$b3hH/$K8&5f$5$l$F$$$k(B. $B$^$?(B, $BM-M}?tBN>e$N0x?tJ,(B
                    261: $B2r$b(B, $B?t3X$K$*$1$k<B83%D!<%k$H$7$F7W;;5!Be?t%7%9%F%`$rMQ$$$k>l9g$KBgJQ(B
                    262: $BM-8z$J5!G=$G$"$k(B. $B$3$N>O$NFbMF$N$&$A(B, $BM-8BBN(B, $BM-M}?tBN>e$N0lJQ?tB?9`<0(B
                    263: $B$N0x?tJ,2r$K4X$7$F$O(B \cite{KNUTH}, $BB?JQ?tB?9`<0$N0x?tJ,2r$K4X$7$F$O(B
                    264: \cite{SASAKI} $B$"$k$$$O(B \cite{GEDDES} $B$r;2>H(B.
                    265:
                    266: \noi
                    267: $BBh(B 7 $B>O(B, $BBh(B 8 $B>O(B:
                    268:
                    269: $B$3$3$G$O(B, $B%0%l%V%J4pDl(B, Buchberger $B%"%k%4%j%:%`$*$h$S$=$l$i$N1~MQ$K$D(B
                    270: $B$$$F$4$/4pK\E*$J$3$H$,$i$N$_$K8BDj$7$F=R$Y$F$$$k(B. $B>\$7$/$O(B,
                    271: \cite{COX} \cite{COX2} $B$r;2>H(B. $BFC$K(B \cite{COX2} $B$OBe?t4v2?(B, $B2D49Be?t(B
                    272: $B$N8&5f$N$?$a$N%D!<%k$H$J$k%"%k%4%j%:%`$K$D$$$F(B, $B%0%l%V%J4pDl$K8B$i$J$$(B
                    273: $B:G6a$N@.2L$b4^$a$FI}9-$/5-=R$5$l$F$$$k(B.
                    274:
                    275: \noi
                    276: $BBh(B 9 $B>O(B:
                    277:
                    278: $B$3$3$G$O(B, $BM}O@>e$b1~MQ>e$b=EMW$J%$%G%"%k$N=`AGJ,2r$K$D$$$F35@b$7$F$$$k(B.
                    279: $B%"%k%4%j%:%`$O$5$^$6$^$JItIJ$+$i@.$C$F$*$j(B, $B$=$l$i$N@bL@$K$D$$$F$O(B,
                    280: \cite{BW} $B$r;2>H(B. $B$J$*(B, $B$3$3$G=R$Y$?$N$H$O0[$J$k=`AGJ,2r%"%k%4%j%:%`$,(B
                    281: \cite{SY} $B$GDs0F$5$l$F$*$j(B, Risa/Asir $B$K<BAu$5$l$F$$$k(B.
                    282:
                    283: \noi
                    284: $BBh(B 10 $B>O(B, $BBh(B 11 $B>O(B:
                    285:
                    286: $B$3$l$i$N>O$O$d$dFC<l$JFbMF$r07$C$F$*$j(B, $B%0%l%V%J4pDl7W;;$r%D!<%k$H$7$F(B
                    287: $BMQ$$$k>l9g$K$OFC$K0U<1$9$kI,MW$O$J$$(B. $B$7$+$7(B, $B$=$l$rC1$J$kJXMx$J%V%i%C%/(B
                    288: $B%\%C%/%9$H9M$($k$H(B, $B$A$g$C$H$7$?LdBj$G$b$9$0$K7W;;$,GKC>$7$F$7$^$&$3$H(B
                    289: $B$OCN$C$F$*$/I,MW$,$"$k(B. $BG$0UF~NO$+$i$N%0%l%V%J4pDl7W;;$K$D$$$F$O(B,
                    290: $B:G6aDs0F$5$l$?(B $F_4$ $B%"%k%4%j%:%`(B \cite{F} $B$,M-NO$G$"$k$,(B, $B$^$@(B
                    291: $BHFMQ7W;;5!Be?t%7%9%F%`$J$I$K$O<BAu$5$l$F$$$J$$$h$&$G$"$k(B.
                    292: $B$^$?(B, change of ordering $B$K$D$$$F$O(B, $B$3$3$G=R$Y$?J}K!$NB>$K(B
                    293: \cite{WALK} $B$G0[$J$kJ}K!$,Ds0F$5$l$F$$$k(B. modular change of ordering
                    294: $B$*$h$S(B modular RUR $B$O(B Risa/Asir $B$K<BAu$5$l$F$$$k(B.
                    295: