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