Changeset a3c7bd in git


Ignore:
Timestamp:
Apr 14, 2016, 2:26:19 PM (7 years ago)
Author:
dere <dkifle16@…>
Branches:
(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
Children:
9c3bb425bf8416386333a0071b1a9580567e8f91
Parents:
3a81956cd2be104798726e5412f0b2a5205a9f64
Message:
fix: typo and delete commented procedures
File:
1 edited

Legend:

Unmodified
Added
Removed
  • Singular/LIB/nfmodsyz.lib

    r3a8195 ra3c7bd  
    1111
    1212OVERVIEW:
    13   A library for computing the syzygy module of a given submodule I over an
    14   algebraic number field Q(t), where t is an algebraic number, using modular methods.
    15   For the case Q(t)=Q, that is, t is an element of Q, we compute, following
    16   [1], the syzygy module of I as follows: For I submodule of A^m with A = Q[X],
    17   as described in [1], we first choose sufficiently large set of primes P and compute
    18   the reduced Groebner basis of the syzygy module of I_p, for each p in P, in parallel.
    19   We then use the Chinese remainder algorithm and rational reconstruction to obtain the syzygy
    20   module of I over Q. For the case t is not in Q, we compute, following [2], the syzygy module
    21   of I as follows:
    22   Let f be the minimal polynomial of t. For I, I' submodules in A^m with A = Q(t)[X],
    23   (Q[t]/<f>)[X] respectively, we map I to I' via the map sending t to t + <f>. We first
     13  A library for computing the syzygy module of a given submodule I in a polynomial ring
     14  over an algebraic number field Q(t), where t is an algebraic number, using modular methods.
     15  For the case Q(t)=Q, that is, where t is an element of Q, we compute, following
     16  [1], the syzygy module of I as follows: For a submodule I of A^m with A = Q[X], we first
     17  choose a sufficiently large set of primes P and compute the reduced Groebner basis of the
     18  syzygy module of I_p, for each p in P, in parallel. We then use the Chinese remainder
     19  algorithm and rational reconstruction to obtain the syzygy module of I over Q.
     20  For the case where t is not in Q, we compute, following [2], the syzygy module of I as
     21  follows:
     22  Let f be the minimal polynomial of t. For a submodule I in A^m with A = Q(t)[X], we map I
     23  to a submodule I' in A^m with A = (Q[t]/<f>)[X] via the map sending t to t + <f>. We first
    2424  choose a prime p such that f has at least two factors in characteristic p. For each
    2525  factor f_{i,p} of f_p:= (f mod p), we set I'_{i,p} := (I'_p mod f_{i,p}). We then
     
    2828  remaindering for polynomials. As described in [2], the procedure is repeated for many primes
    2929  p, where we compute the G_p in parallel until the number of primes is sufficiently large to
    30   recover the correct generating set for the syzygy module G' of I' which is also a generating
    31   set for the syzygy module of I.
     30  recover the correct generating set for the syzygy module G' of I' which is, considered over
     31  Q(t), also a generating set for the syzygy module of I.
    3232
    3333REFERENCES:
     
    3535      J. Symb. Comp. 35, 403-419 (2003).
    3636  [2] D. Boku, W. Decker, C. Fieker, and A. Steenpass. Groebner bases over algebraic
    37       number fields. In Proceedings of the 2015 International Workshop on Parallel
     37      number fields. In: Proceedings of the 2015 International Workshop on Parallel
    3838      Symb. Comp. PASCO'15, pages 16-24 (2015).
    3939
     
    349349{
    350350    /*
    351      * test if the set 'result' generates the syzygy module of args[1]
    352      * in characteristic zero
     351     * test if the set generating 'result' also generates the syzygy module
     352     * of args[1] in characteristic zero
    353353     */
    354354    def Ls = basering;
     
    404404{
    405405    /*
    406      * test if the set 'result' generates the syzygy module of args[1]
    407      * in characteristic zero
     406     * test if the set  generating 'result' also generates the syzygy module
     407     * of args[1] in characteristic zero
    408408     */
    409409    module M=args[1];
     
    427427{
    428428     /*
    429       * This procedure makes the first test in positive characteristic to verify whether the
    430       * set 'result' generates the submodule args[1]. Note that this test works only over Z_p
     429      * This procedure performs the first test in positive characteristic to
     430      * verify whether the set generating 'result' also generates the syzygy
     431      * module of the submodule args[1]. Note that this test works only
     432      * over Z_p
    431433      */
    432434     def br = basering;
     
    474476{
    475477     /*
    476       * This procedure makes the first test in positive characteristic to verify whether the
    477       * set 'result' generates the submodule args[1]. Note that this test works only over
    478       * Z_p(t) where t is an algebraic number which is not Z_p.
     478      * This procedure performs the first test in positive characteristic to
     479      * verify whether the set generating 'result' also generates the syzygy
     480      * module of args[1]. Note that this test works only over Z_p(t) where
     481      * t is an algebraic number which is not in Z_p.
    479482     */
    480483
     
    618621     intvec opt = option(get);
    619622     option(redSB);
    620      option(returnSB); // forces the procedure to return std of syz(I)
     623     option(returnSB);
     624     /*------ if these options are set, the Singular command syz returns the
     625      reduced Groebner basis of I ---------------------------------------*/
    621626
    622627     // apply modular command from modular.lib
     
    708713                [y-x,y2],
    709714                [x2-xy, ax-y];
    710     M1 = nfmodSyz(M1);
    711     M1;
     715    nfmodSyz(M1);
    712716    ring r2 = (0,a),(x,y,z),(dp,c);
    713717    minpoly = (a3+a+1);
     
    715719                [y2+(a)*z+(a),(a+3)*z3+(-a)*x2],
    716720                [-xz+(a2+3)*yz,xy+(a2)*z];
    717     M2 = nfmodSyz(M2);
    718     M2;
     721    nfmodSyz(M2);
    719722    ring r3=0,(x,y),dp; // ring without parameter
    720723    module M3 = [x2 + y, xy], [-7y, 2x], [x2-y, 0];
    721     M3=nfmodSyz(M3);
    722     M3;
     724    nfmodSyz(M3);
    723725    ring r4=0,(x,y),(c,dp); // ring without parameter
    724726    module M4 = [xy, x-y],
     
    726728                [- 7y, 2x],
    727729                [x2-y, 0];
    728     M4 = nfmodSyz(M4);
    729     M4;
    730 }
    731 
    732 /*
    733 ////////////////////////////////////////////////////////////////////////////////
    734 
    735 //-------------nfmodSyz--old--version-----------------------------------
    736 
    737 static proc ret_indx(matrix M, int rp)
    738 {
    739      int i,j,sc;
    740      for(j=1;j<=ncols(M);j++)
    741      {
    742          sc=re_indx(M, rp, j,sc);
    743          if(j>sc)
    744          {
    745              return(sc);
    746              break;
    747          }
    748      }
    749 }
    750 
    751 ////////////////////////////////////////////////////////////////////////////////
    752 
    753 static proc re_indx(matrix M, int rp, int j, int sc)
    754 {
    755      int i;
    756      if(M[1,j]!=0)
    757      {
    758          return(sc);
    759      }
    760      else
    761      {
    762           for(i=2;i<=rp; i++)
    763           {
    764              if(M[i,j]!=0)
    765              {
    766                  return(sc);
    767                  break;
    768              }
    769           }
    770           return(j);
    771      }
    772 }
    773 
    774 ////////////////////////////////////////////////////////////////////////////////
    775 
    776 proc syzMod(def I, list #)
    777 {
    778      // compute the syzygy module of a given submodule
    779 
    780      int i,j, s1,s2,s,k1,k2, i1,i2,i_I,j_I,i_3, tmp;
    781      if(size(#)>0)
    782      {
    783          tmp = #[1]; // in this case, the procedure returns the reduced Groebner basis of
    784                      // I which may partitioned to 2x2 block matrix
    785      }
    786      module sy;
    787      module N = transpose(I),freemodule(ncols(I));
    788      N= transpose(N);
    789      matrix M = nfmodStd(N); // nfmodStd
    790      i1 = ncols(M);
    791      i2 = nrows(M);
    792      i_I = ncols(I);
    793      j_I = nrows(I);
    794      i_3 = i2-i_I; // rows of zeros
    795      j = ret_indx(M,j_I);
    796      i = i_I; // i is nrows of syz module
    797      if(j==0)
    798      {
    799          i = 0;
    800      }
    801 
    802      if(i==0)
    803      {
    804          if(tmp)
    805          {
    806              matrix T[i_I][i1] = M[(i_3+1)..i2,1..i1];
    807              matrix G[i_3][i1] = M[1..i_3,1..i1];
    808              list L = module([0]), module(G), T;
    809              return(L);
    810          }
    811          return(module([0]));
    812      }
    813 
    814      if(!tmp)
    815      {
    816          matrix V[i][j] = M[(i_3+1)..i2,1..j];
    817          sy = V;
    818          return(sy);
    819      }
    820      else
    821      {
    822              matrix V[i][j] = M[(i_3+1)..i2,1..j];
    823              matrix T[i_I][i1-j] = M[(i_3+1)..i2,(j+1)..i1];
    824              matrix G[i_3][i1-j] = M[1..i_3,(j+1)..i1];
    825              list L = module(V), module(G), T;
    826              return(L);
    827      }
    828 }
    829 
     730    nfmodSyz(M4);
     731}
     732
Note: See TracChangeset for help on using the changeset viewer.