[BACK]Return to dagb-noro.tex CVS log [TXT][DIR] Up to [local] / OpenXM / doc / Papers

Annotation of OpenXM/doc/Papers/dagb-noro.tex, Revision 1.3

1.3     ! noro        1: % $OpenXM: OpenXM/doc/Papers/dagb-noro.tex,v 1.2 2001/10/04 04:12:29 noro Exp $
1.1       noro        2: \setlength{\parskip}{10pt}
                      3:
                      4: \begin{slide}{}
1.2       noro        5: \begin{center}
                      6: \fbox{\large Part I : Overview and history of Risa/Asir}
                      7: \end{center}
                      8: \end{slide}
                      9:
                     10: \begin{slide}{}
1.1       noro       11: \fbox{A computer algebra system Risa/Asir}
                     12:
                     13: \begin{itemize}
                     14: \item Old style software for polynomial computation
                     15:
                     16: \begin{itemize}
                     17: \item Domain specification is not necessary prior to computation
                     18: \item automatic conversion of inputs into internal canonical forms
                     19: \end{itemize}
                     20:
                     21: \item User language with C-like syntax
                     22:
                     23: \begin{itemize}
                     24: \item No type declaration of variables
                     25: \item Builtin debugger for user programs
                     26: \end{itemize}
                     27:
                     28: \item Open source
                     29:
                     30: \begin{itemize}
                     31: \item Whole source tree is available via CVS
                     32: \end{itemize}
                     33:
1.2       noro       34: \item OpenXM ((Open message eXchange protocol for Mathematics) interface
1.1       noro       35:
                     36: \begin{itemize}
                     37: \item As a client : can call procedures on other OpenXM servers
                     38: \item As a server : offers all its functionalities to OpenXM clients
                     39: \item As a library : OpenXM functionality is available via subroutine calls
                     40: \end{itemize}
                     41: \end{itemize}
                     42: \end{slide}
                     43:
                     44: \begin{slide}{}
                     45: \fbox{Major functionalities}
                     46:
                     47: \begin{itemize}
                     48: \item Fundamental polynomial arithmetics
                     49:
                     50: \begin{itemize}
                     51: \item Internal form of a polynomial : recursive representaion or distributed
                     52: representation
                     53: \end{itemize}
                     54:
                     55: \item Polynomial factorization
                     56:
                     57: \begin{itemize}
                     58: \item Univariate factorization over the rationals, algebraic number fields and various finite fields
                     59:
                     60: \item Multivariate factorization over the rationals
                     61: \end{itemize}
                     62:
                     63: \item Groebner basis computation
                     64:
                     65: \begin{itemize}
1.2       noro       66: \item Buchberger and $F_4$ [Faug\'ere] algorithm
1.1       noro       67:
1.2       noro       68: \item Change of ordering/RUR [Rouillier] of 0-dimensional ideals
1.1       noro       69:
                     70: \item Primary ideal decomposition
                     71:
                     72: \item Computation of $b$-function
                     73: \end{itemize}
                     74:
1.2       noro       75: \item PARI [PARI] library interface
1.1       noro       76:
                     77: \item Paralell distributed computation under OpenXM
                     78: \end{itemize}
                     79: \end{slide}
                     80:
                     81: \begin{slide}{}
                     82: \fbox{History of development : ---1994}
                     83:
                     84: \begin{itemize}
                     85: \item --1989
                     86:
                     87: Several subroutines were developed for a Prolog program.
                     88:
                     89: \item 1989--1992
                     90:
                     91: \begin{itemize}
1.2       noro       92: \item Reconfigured as Risa/Asir with a parser and Boehm's conservative GC [Boehm]
1.1       noro       93:
                     94: \item Developed univariate and multivariate factorizers over the rationals.
                     95: \end{itemize}
                     96:
                     97: \item 1992--1994
                     98:
                     99: \begin{itemize}
1.2       noro      100: \item Started implementation of Buchberger algorithm
1.1       noro      101:
1.2       noro      102: Written in user language $\Rightarrow$ rewritten in C (by Murao)
                    103:
                    104: $\Rightarrow$ trace lifting [Traverso]
1.1       noro      105:
                    106: \item Univariate factorization over algebraic number fields
                    107:
                    108: Intensive use of successive extension, non-squarefree norms
                    109: \end{itemize}
                    110: \end{itemize}
                    111:
                    112: \end{slide}
                    113:
                    114: \begin{slide}{}
                    115: \fbox{History of development : 1994-1996}
                    116:
                    117: \begin{itemize}
1.2       noro      118: \item Free distribution of binary versions from Fujitsu
1.1       noro      119:
                    120: \item Primary ideal decomposition
                    121:
                    122: \begin{itemize}
1.2       noro      123: \item Shimoyama-Yokoyama algorithm [SY]
1.1       noro      124: \end{itemize}
                    125:
                    126: \item Improvement of Buchberger algorithm
                    127:
                    128: \begin{itemize}
                    129: \item Trace lifting+homogenization
                    130:
                    131: \item Omitting check by compatible prime
                    132:
                    133: \item Modular change of ordering, Modular RUR
                    134:
1.2       noro      135: These are joint works with Yokoyama [NY]
1.1       noro      136: \end{itemize}
                    137: \end{itemize}
                    138:
                    139: \end{slide}
                    140:
                    141: \begin{slide}{}
                    142: \fbox{History of development : 1996-1998}
                    143:
                    144: \begin{itemize}
                    145: \item Distributed compuatation
                    146:
                    147: \begin{itemize}
                    148: \item A prototype of OpenXM
                    149: \end{itemize}
                    150:
                    151: \item Improvement of Buchberger algorithm
                    152:
                    153: \begin{itemize}
                    154: \item Content reduction during nomal form computation
                    155:
                    156: \item Its parallelization by the above facility
                    157:
1.2       noro      158: \item Computation of odd order replicable functions [Noro]
1.1       noro      159:
                    160: Risa/Asir : it took 5days to compute a DRL basis ({\it McKay})
                    161:
1.2       noro      162: Faug\`ere FGb : computation of the DRL basis 53sec
1.1       noro      163: \end{itemize}
                    164:
                    165:
                    166: \item Univariate factorization over large finite fields
                    167:
                    168: \begin{itemize}
                    169: \item To implement Schoof-Elkies-Atkin algorithm
                    170:
1.2       noro      171: Counting rational points on elliptic curves
1.1       noro      172:
1.2       noro      173: --- not free But related functions are freely available
1.1       noro      174: \end{itemize}
                    175: \end{itemize}
                    176:
                    177: \end{slide}
                    178:
                    179: \begin{slide}{}
                    180: \fbox{History of development : 1998-2000}
                    181: \begin{itemize}
                    182: \item OpenXM
                    183:
                    184: \begin{itemize}
                    185: \item OpenXM specification was written by Noro and Takayama
                    186:
1.2       noro      187: Borrowed idea on encoding, phrase book from OpenMath [OpenMath]
                    188:
1.1       noro      189: \item Functions for distributed computation were rewritten
                    190: \end{itemize}
                    191:
                    192: \item Risa/Asir on Windows
                    193:
                    194: \begin{itemize}
                    195: \item Requirement from a company for which Noro worked
                    196:
                    197: Written in Visual C++
                    198: \end{itemize}
                    199:
                    200: \item Test implementation of $F_4$
                    201:
                    202: \begin{itemize}
1.2       noro      203: \item Implemented according to [Faug\`ere]
                    204:
1.1       noro      205: \item Over $GF(p)$ : pretty good
                    206:
                    207: \item Over the rationals : not so good except for {\it McKay}
                    208: \end{itemize}
                    209: \end{itemize}
                    210: \end{slide}
                    211:
                    212: \begin{slide}{}
                    213: \fbox{History of development : 2000-current}
                    214: \begin{itemize}
                    215: \item The source code is freely available
                    216:
                    217: \begin{itemize}
1.2       noro      218: \item Noro moved from Fujitsu to Kobe university
1.1       noro      219:
1.2       noro      220: Started Kobe branch [Risa/Asir]
1.1       noro      221: \end{itemize}
                    222:
1.2       noro      223: \item OpenXM [OpenXM]
1.1       noro      224:
                    225: \begin{itemize}
                    226: \item Revising the specification : OX-RFC100, 101, (102)
                    227:
1.2       noro      228: \item OX-RFC102 : communications between servers via MPI
1.1       noro      229: \end{itemize}
                    230:
1.3     ! noro      231: \item Weyl algebra
1.1       noro      232:
                    233: \begin{itemize}
1.2       noro      234: \item Buchberger algorithm [Takayama]
1.1       noro      235:
1.3     ! noro      236: \item $b$-function computation [Oaku]
1.1       noro      237:
                    238: Minimal polynomial computation by modular method
                    239: \end{itemize}
                    240: \end{itemize}
                    241:
                    242: \end{slide}
                    243:
                    244: \begin{slide}{}
                    245: \fbox{Status of each component --- Factorizer}
                    246:
                    247: \begin{itemize}
                    248: \item 10 years ago
                    249:
                    250: its performace was fine compared with existing software
1.2       noro      251: like REDUCE, Mathematica.
1.1       noro      252:
                    253: \item 4 years ago
                    254:
                    255: Univarate factorization over algebraic number fields was
                    256: still fine because of some tricks on factoring polynomials
                    257: derived from norms.
                    258:
                    259: \item Current
                    260:
                    261: Multivariate : not so bad
                    262:
                    263: Univariate : completely obsolete by M. van Hoeij's new algorithm
1.2       noro      264: [Hoeij]
1.1       noro      265: \end{itemize}
                    266:
                    267: \end{slide}
                    268:
                    269: \begin{slide}{}
                    270: \fbox{Status of each component --- Groebner basis related functions}
                    271:
                    272: \begin{itemize}
                    273: \item 8 years ago
                    274:
                    275: The performace was poor with only the sugar strategy.
                    276:
                    277: \item 7 years ago
                    278:
                    279: Rather fine with trace lifting but Faug\`ere's (old)Gb was more
                    280: efficient.
                    281:
                    282: Homogenization+trace lifting made it possible to compute
                    283: wider range of Groebner bases.
                    284:
                    285: \item 4 years ago
                    286:
                    287: Modular RUR was comparable with Rouillier's implementation.
                    288:
                    289: \item Current
                    290:
                    291: FGb seems much more efficient than our $F_4$ implementation.
                    292:
1.3     ! noro      293: Singular [Singular] is also several times
1.1       noro      294: faster than Risa/Asir, because Singular seems to have efficient
                    295: monomial and polynomial representation.
                    296:
                    297: \end{itemize}
                    298: \end{slide}
                    299:
                    300: \begin{slide}{}
1.2       noro      301: \fbox{OpenXM}
                    302:
                    303: \begin{itemize}
                    304: \item An environment for parallel distributed computation
                    305:
                    306: Both for interactive, non-interactive environment
                    307:
                    308: \item Message passing
                    309:
                    310: OX (OpenXM) message : command and data
                    311:
                    312: \item Hybrid command execution
                    313:
                    314: \begin{itemize}
                    315: \item Stack machine command
                    316:
                    317: push, pop, function execution, $\ldots$
                    318:
                    319: \item accepts its own command sequences
                    320:
                    321: {\tt execute\_string} --- easy to use
                    322: \end{itemize}
                    323:
                    324: \item Data is represented as CMO
                    325:
                    326: CMO (Common Mathematical Object format)
                    327:
                    328: --- Serialized representation of mathematical object
                    329:
                    330: {\sl Integer32}, {\sl Cstring}, {\sl List}, {\sl ZZ}, $\ldots$
                    331: \end{itemize}
                    332: \end{slide}
                    333:
                    334:
                    335: \begin{slide}{}
                    336: \fbox{OpenXM and OpenMath}
                    337:
                    338: \begin{itemize}
                    339: \item OpenMath
                    340:
                    341: \begin{itemize}
                    342: \item A standard for representing mathematical objects
                    343:
                    344: \item CD (Content Dictionary) : assigns semantics to symbols
                    345:
                    346: \item Phrasebook : convesion between internal and OpenMath objects.
                    347:
                    348: \item Encoding : format for actual data exchange
                    349: \end{itemize}
                    350:
                    351: \item OpenXM
                    352:
                    353: \begin{itemize}
                    354: \item Specification for encoding and exchanging messages
                    355:
                    356: \item It also specifies behavior of servers and session management
                    357: \end{itemize}
                    358:
                    359: \end{itemize}
                    360: \end{slide}
                    361:
                    362: \begin{slide}{}
                    363: \fbox{OpenXM server interface in Risa/Asir}
                    364:
                    365: \begin{itemize}
                    366: \item TCP/IP stream
                    367:
                    368: \begin{itemize}
                    369: \item Launcher
                    370:
                    371: A client executes a launcher on a host.
                    372:
                    373: The launcher launches a server on the same host.
                    374:
                    375: \item Server
                    376:
                    377: A server reads from the descriptor 3, write to the descriptor 4.
                    378:
                    379: \end{itemize}
                    380:
                    381: \item Subroutine call
                    382:
                    383: Risa/Asir subroutine library provides interfaces corresponding to
                    384: pushing and popping data and executing stack commands.
                    385: \end{itemize}
                    386: \end{slide}
                    387:
                    388: \begin{slide}{}
                    389: \fbox{OpenXM client interface in Risa/Asir}
                    390:
                    391: \begin{itemize}
                    392: \item Primitive interface functions
                    393:
                    394: Pushing and popping data, sending commands etc.
                    395:
                    396: \item Convenient functions
                    397:
                    398: Launching servers, calling remote functions,
                    399:  interrupting remote executions etc.
                    400:
                    401: \item Parallel distributed computation is easy
                    402:
                    403: Simple parallelization is practically important
                    404:
                    405: Competitive computation is easily realized
                    406: \end{itemize}
                    407: \end{slide}
                    408:
                    409:
                    410: %\begin{slide}{}
                    411: %\fbox{CMO = Serialized representation of mathematical object}
                    412: %
                    413: %\begin{itemize}
                    414: %\item primitive data
                    415: %\begin{eqnarray*}
                    416: %\mbox{Integer32} &:& ({\tt CMO\_INT32}, {\sl int32}\ \mbox{n}) \\
                    417: %\mbox{Cstring}&:& ({\tt CMO\_STRING},{\sl int32}\,  \mbox{ n}, {\sl string}\, \mbox{s}) \\
                    418: %\mbox{List} &:& ({\tt CMO\_LIST}, {\sl int32}\, len, ob[0], \ldots,ob[m-1])
                    419: %\end{eqnarray*}
                    420: %
                    421: %\item numbers and polynomials
                    422: %\begin{eqnarray*}
                    423: %\mbox{ZZ}         &:& ({\tt CMO\_ZZ},{\sl int32}\, {\rm f}, {\sl byte}\, \mbox{a[1]}, \ldots
                    424: %{\sl byte}\, \mbox{a[$|$f$|$]} ) \\
                    425: %\mbox{Monomial32}&:& ({\tt CMO\_MONOMIAL32}, n, \mbox{e[1]}, \ldots, \mbox{e[n]}, \mbox{Coef}) \\
                    426: %\mbox{Coef}&:& \mbox{ZZ} | \mbox{Integer32} \\
                    427: %\mbox{Dpolynomial}&:& ({\tt CMO\_DISTRIBUTED\_POLYNOMIAL},\\
                    428: %                  & & m, \mbox{DringDefinition}, \mbox{Monomial32}, \ldots)\\
                    429: %\mbox{DringDefinition}
                    430: %                  &:& \mbox{DMS of N variables} \\
                    431: %                  & & ({\tt CMO\_RING\_BY\_NAME}, name) \\
                    432: %                  & & ({\tt CMO\_DMS\_GENERIC}) \\
                    433: %\end{eqnarray*}
                    434: %\end{itemize}
                    435: %\end{slide}
                    436: %
                    437: %\begin{slide}{}
                    438: %\fbox{Stack based communication}
                    439: %
                    440: %\begin{itemize}
                    441: %\item Data arrived a client
                    442: %
                    443: %Pushed to the stack
                    444: %
                    445: %\item Result
                    446: %
                    447: %Pushd to the stack
                    448: %
                    449: %Written to the stream when requested by a command
                    450: %
                    451: %\item The reason why we use the stack
                    452: %
                    453: %\begin{itemize}
                    454: %\item Stack = I/O buffer for (possibly large) objects
                    455: %
                    456: %Multiple requests can be sent before their exection
                    457: %
                    458: %A server does not get stuck in sending results
                    459: %\end{itemize}
                    460: %\end{itemize}
                    461: %\end{slide}
                    462:
                    463: \begin{slide}{}
                    464: \fbox{Executing functions on a server (I) --- {\tt SM\_executeFunction}}
                    465:
                    466: \begin{enumerate}
                    467: \item (C $\rightarrow$ S) Arguments are sent in binary encoded form.
                    468: \item (C $\rightarrow$ S) The number of aruments is sent as {\sl Integer32}.
                    469: \item (C $\rightarrow$ S) A function name is sent as {\sl Cstring}.
                    470: \item (C $\rightarrow$ S) A command {\tt SM\_executeFunction} is sent.
                    471: \item The result is pushed to the stack.
                    472: \item (C $\rightarrow$ S) A command {\tt SM\_popCMO} is sent.
                    473: \item (S $\rightarrow$ C) The result is sent in binary encoded form.
                    474: \end{enumerate}
                    475:
                    476: $\Rightarrow$ Communication is fast, but functions for binary data
                    477: conversion are necessary.
                    478: \end{slide}
                    479:
                    480: \begin{slide}{}
                    481: \fbox{Executing functions on a server (II) --- {\tt SM\_executeString}}
                    482:
                    483: \begin{enumerate}
                    484: \item (C $\rightarrow$ S) A character string represeting a request in a server's
                    485: user language is sent as {\sl Cstring}.
                    486: \item (C $\rightarrow$ S) A command {\tt SM\_executeString} is sent.
                    487: \item The result is pushed to the stack.
                    488: \item (C $\rightarrow$ S) A command {\tt SM\_popString} is sent.
                    489: \item (S $\rightarrow$ C) The result is sent in readable form.
                    490: \end{enumerate}
                    491:
                    492: $\Rightarrow$ Communication may be slow, but the client parser may be
                    493: enough to read the result.
                    494: \end{slide}
                    495:
                    496: \begin{slide}{}
                    497: \fbox{Example of distributed computation --- $F_4$ vs. $Buchberger$ }
                    498:
                    499: \begin{verbatim}
                    500: /* competitive Gbase computation over GF(M) */
                    501: /* Cf. A.28 in SINGULAR Manual */
                    502: /* Process list is specified as an option : grvsf4(...|proc=P) */
                    503: def grvsf4(G,V,M,O)
                    504: {
                    505:   P = getopt(proc);
                    506:   if ( type(P) == -1 ) return dp_f4_mod_main(G,V,M,O);
                    507:   P0 = P[0]; P1 = P[1]; P = [P0,P1];
                    508:   map(ox_reset,P);
                    509:   ox_cmo_rpc(P0,"dp_f4_mod_main",G,V,M,O);
                    510:   ox_cmo_rpc(P1,"dp_gr_mod_main",G,V,0,M,O);
                    511:   map(ox_push_cmd,P,262); /* 262 = OX_popCMO */
                    512:   F = ox_select(P); R = ox_get(F[0]);
                    513:   if ( F[0] == P0 ) { Win = "F4"; Lose = P1;}
                    514:   else { Win = "Buchberger"; Lose = P0; }
                    515:   ox_reset(Lose); /* simply resets the loser */
                    516:   return [Win,R];
                    517: }
                    518: \end{verbatim}
                    519: \end{slide}
                    520:
                    521: \begin{slide}{}
                    522: \fbox{References}
                    523:
                    524: [Bernardin] L. Bernardin, On square-free factorization of
                    525: multivariate polynomials over a finite field, Theoretical
                    526: Computer Science 187 (1997), 105-116.
                    527:
                    528: [Boehm] {\tt http://www.hpl.hp.com/personal/Hans\_Boehm/gc}
                    529:
                    530: [Faug\`ere] J.C. Faug\`ere,
                    531: A new efficient algorithm for computing Groebner bases  ($F_4$),
                    532: Journal of Pure and Applied Algebra (139) 1-3 (1999), 61-88.
                    533:
                    534: [Hoeij] M. van Heoij, Factoring polynomials and the knapsack problem,
                    535: to appear in Journal of Number Theory (2000).
                    536:
                    537: [NY] M. Noro, K. Yokoyama,
                    538: A Modular Method to Compute the Rational Univariate
                    539: Representation of Zero-Dimensional Ideals.
                    540: J. Symb. Comp. {\bf 28}/1 (1999), 243-263.
                    541:
1.3     ! noro      542: [Oaku] T. Oaku, Algorithms for $b$-functions, restrictions and algebraic
        !           543: local cohomology groups of $D$-modules.
        !           544: Advancees in Applied Mathematics, 19 (1997), 61-105.
        !           545: \end{slide}
        !           546:
        !           547: \begin{slide}{}
        !           548:
1.2       noro      549: [OpenMath] {\tt http://www.openmath.org}
                    550:
                    551: [OpenXM] {\tt http://www.openxm.org}
                    552:
                    553: [PARI] {\tt http://www.parigp-home.de}
                    554:
                    555: [Risa/Asir] {\tt http://www.math.kobe-u.ac.jp/Asir/asir.html}
                    556:
                    557: [Rouillier] F. Rouillier,
                    558: R\'esolution des syst\`emes z\'ero-dimensionnels.
                    559: Doctoral Thesis(1996), University of Rennes I, France.
                    560:
1.3     ! noro      561: [SY] T. Shimoyama, K. Yokoyama, Localization and Primary Decomposition of Polynomial Ideals.  J. Symb. Comp. {\bf 22} (1996), 247-277.
        !           562:
        !           563: [Singular] {\tt http://www.singular.uni-kl.de}
        !           564:
1.2       noro      565: [Traverso] C. Traverso, \gr trace algorithms. Proc. ISSAC '88 (LNCS 358), 125-138.
                    566:
                    567: \end{slide}
                    568:
                    569: \begin{slide}{}
                    570: \begin{center}
                    571: \fbox{\large Part II : Algorithms and implementations in Risa/Asir}
                    572: \end{center}
                    573: \end{slide}
                    574:
                    575: \begin{slide}{}
1.1       noro      576: \fbox{Ground fields}
                    577:
                    578: \begin{itemize}
                    579: \item The rational number field
                    580: \item Algebraic number fields
                    581:
                    582: represented by successive extensions
                    583: \item Finite fields
                    584: \begin{itemize}
                    585: \item $GF(p)$ ($p<2^{30}$); represented by a single word
                    586: \item $GF(p^n)$ ($p^n < 2^{20}$); represented by a primitive root
                    587: \item $GF(2^n)$; represented by a bit string
                    588: \item $GF(p)$ ($p$ : arbitrary prime)
                    589: \item $GF(p^n)$ ($p$ : arbitrary odd prime)
                    590: \end{itemize}
                    591:
                    592: \item Real and complex number fields
                    593:
                    594: \begin{itemize}
                    595: \item Double float
                    596: \item PARI bigfloat
                    597: \end{itemize}
                    598:
                    599: \end{itemize}
                    600: \end{slide}
                    601:
                    602: \begin{slide}{}
                    603: \fbox{Polynomial factorization}
                    604: \begin{itemize}
                    605: \item Univariate factorization
                    606:
                    607: \begin{itemize}
                    608: \item Over the rationals
                    609:
                    610: Berlekamp-Zassenhaus
                    611:
                    612: (classical; knapsack has not yet implemented)
                    613:
                    614: \item Over algebraic number fields
                    615:
                    616: Trager's algorithm + some improvement
                    617:
                    618: \item Over finite fieds
                    619:
                    620: DDF + Cantor-Zassenhaus; FFT for large finite fields
                    621: \end{itemize}
                    622:
                    623: \item Multivariate factorization
                    624:
                    625: \begin{itemize}
                    626: \item Over the rationals
                    627:
                    628: Classical EZ algorithm
                    629:
1.2       noro      630: \item Over small finite fieds
                    631:
                    632: Modified Bernardin's square free algorithm [Bernardin],
1.1       noro      633:
1.2       noro      634: possibly Hensel lifting over extension fields
1.1       noro      635: \end{itemize}
                    636:
                    637: \end{itemize}
                    638: \end{slide}
                    639:
                    640: \begin{slide}{}
                    641: \fbox{Groebner basis computation --- Buchberger algorithm}
                    642: \begin{itemize}
                    643: \item Polynomial rings
                    644: \begin{itemize}
                    645: \item Over finite fields
                    646:
                    647: Any finite field is available as a ground field
                    648:
                    649: \item Over the rationals
                    650:
                    651: Guess of a groebner basis by detecting zero reduction by modular computation
                    652: + check (trace lifting)
                    653:
                    654: Homogenization+guess+dehomogenization+check
                    655: \end{itemize}
                    656:
1.3     ! noro      657: \item Weyl Algebra
1.1       noro      658:
                    659: \begin{itemize}
                    660: \item Groebner basis of a left ideal
                    661:
1.2       noro      662: Key : an efficient implementation of Leibniz rule
1.1       noro      663: \end{itemize}
                    664:
                    665: \end{itemize}
                    666: \end{slide}
                    667:
                    668: \begin{slide}{}
                    669: \fbox{$F_4$ algorithm}
                    670: \begin{itemize}
                    671: \item Over small finite fields ($GF(p)$, $p < 2^{30}$)
                    672: \begin{itemize}
1.2       noro      673: \item More efficient than our Buchberger algorithm implementation
1.1       noro      674:
                    675: but less efficient than FGb by Faugere
                    676: \end{itemize}
                    677:
                    678: \item Over the rationals
                    679:
                    680: \begin{itemize}
                    681: \item Very naive implementation
                    682:
1.2       noro      683: Modular computation + CRT + Checking the result at each degree
                    684:
1.1       noro      685: \item Less efficient than Buchberger algorithm
                    686:
1.2       noro      687: except for one example (={\it McKay})
1.1       noro      688: \end{itemize}
                    689:
                    690: \end{itemize}
                    691: \end{slide}
                    692:
                    693: \begin{slide}{}
1.2       noro      694: \fbox{Change of ordering for zero-dimensional ideals}
1.1       noro      695:
                    696: \begin{itemize}
                    697: \item Any ordering to lex ordering
                    698:
                    699: \begin{itemize}
                    700: \item Modular change of ordering
                    701:
                    702: Guess of the support by modular FGLM
                    703:
                    704: + solving linear systems by Hensel lifting
                    705:
                    706: \end{itemize}
                    707:
                    708: \item RUR (generalized shape lemma)
                    709:
                    710: \begin{itemize}
                    711: \item Modular RUR (only implemented on the shape base case)
                    712:
                    713: Almost the same as modular change of ordering
                    714: \end{itemize}
                    715:
                    716: \end{itemize}
                    717: \end{slide}
                    718:
                    719: \begin{slide}{}
                    720: \fbox{Primary decomposition --- Shimoyama-Yokoyama algorithm}
                    721:
                    722: \begin{itemize}
                    723: \item Only implemented over the rationals
                    724:
                    725: Finite field version will soon be available
                    726:
                    727: \item Pseudo primary ideal
                    728:
                    729: An ideal whose radical is prime
                    730:
                    731: \item Prime decomp. of the radical $\Rightarrow$ pseudo primary decomp.
                    732:
                    733: \item Extraction of embedded components
                    734:
                    735: \end{itemize}
                    736:
                    737: \end{slide}
                    738:
                    739: \begin{slide}{}
                    740: \fbox{Computation of $b$-function}
                    741:
1.3     ! noro      742: $D=K\langle x,\partial \rangle$ : Weyl algebra
1.1       noro      743:
                    744: $b(s)$ : a polynomial of the smallest degree s.t.
                    745: there exists $P(s) \in D[s]$, $P(s)f^{s+1}=b(s)f^s$
                    746:
                    747: $b(s)$ : $b$-function of a polynomial $f$
                    748:
                    749: $\Rightarrow$ $b(s)$ can be computed by Oaku's algorithm
                    750:
                    751: On Risa/Asir : $b(s)$ is computed by
                    752:
                    753: A groebner basis $\Rightarrow$ guess of $\deg(b(s))$ by modular
                    754: computation $\Rightarrow$ solving a linear system
                    755: \end{slide}
                    756:
                    757: \begin{slide}{}
                    758: \fbox{Interface to PARI library}
                    759:
                    760: \begin{itemize}
                    761: \item Data conversion
                    762:
                    763: \begin{itemize}
                    764:
                    765: \item Only primitive data can be passed to PARI
                    766:
                    767: Rational number, bignum, bigfloat, polynomial,
                    768: vector, matrix
                    769:
                    770: \item Results are converted to Risa objects
                    771:
                    772: \end{itemize}
                    773:
                    774: \item Evaluation of transcendental functions
                    775:
                    776: \begin{itemize}
                    777: \item Most of univariate functions in PARI can be
                    778: evaluated by {\tt eval()}
                    779: \end{itemize}
                    780:
                    781: \item Calling PARI functions
                    782:
                    783: \begin{itemize}
                    784: \item One can call PARI functions by {\tt pari({\it parifunction},{\it args})}
                    785:
                    786: The knapsack factorization is available via {\tt pari(factor,{\it poly})}
                    787: \end{itemize}
                    788: \end{itemize}
                    789: \end{slide}
                    790:
                    791: \begin{slide}{}
                    792: \end{slide}
                    793:
                    794: \begin{slide}{}
                    795: \end{slide}
                    796:
                    797: \begin{slide}{}
                    798: \end{slide}
                    799:
                    800: \begin{slide}{}
                    801: \end{slide}
                    802:

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>