Changeset 5c73a12 in git


Ignore:
Timestamp:
Oct 26, 2018, 8:19:17 PM (5 years ago)
Author:
Viktor Levandovskyy <levandov@…>
Branches:
(u'spielwiese', '4a9821a93ffdc22a6696668bd4f6b8c9de3e6c5f')
Children:
ff2859da961f6b00a7d13ed9f691781672d9fe3d
Parents:
7a968b28061d6ecc758e202406876a8d29dad211
Message:
more changes, not yet stable
File:
1 edited

Legend:

Unmodified
Added
Removed

  • Singular/LIB/ncHilb.lib

    r7a968b r5c73a12  
    11//////////////////////////////////////////////////////////////////////////////
    22version="version nc_hilb.lib 4.1.1.0 Dec_2017 "; // $Id$
    3 category="Noncommutative algebra";
     3category="Noncommutative";
    44info="
    5 LIBRARY:  fpahilb.lib: A library for computing graded and multi-graded Hilbert
    6                       series of general non-commutative algebras (available via Letterplace).
    7                                           It also computes the truncated Hilbert series of the algebras whose Hilbert
    8                       series are possibly not rational or unknown.
     5LIBRARY:  fpahilb.lib: Computation of graded and multi-graded Hilbert series of non-commutative algebras (Letterplace).
    96
    107AUTHOR:   Sharwan K. Tiwari   shrawant@gmail.com
    … …  
    1815          La Scala R., Tiwari Sharwan K.: Multigraded Hilbert Series of noncommutative modules, https://arxiv.org/abs/1705.01083.
    1916
     17KEYWORDS: finitely presented algebra; infinitely presented algebra; graded Hilbert series; multi-graded Hilbert series;
     18                 
    2019PROCEDURES:
    2120          fpahilb(L,d,#); Hilbert series of a non-commutative algebra
    … …  
    3635@* N>2: computation of truncated Hilbert series up to degree N-1, and
    3736@* nonempty string: the details about the orbit and system of equations will be printed.
    38 
    3937Let the orbit be @code{O_I = {T_{w_1}(I),...,T_{w_r}(I)} ($w_i\in W$)}, where we assume that if @code{T_{w_i}(I)=T_{w_i'}(I)}
    4038for some @code{w'_i\in W}, then @code{deg(w_i)\leq deg(w'_i)} follows.
    … …  
    4341where @code{{b_j}} is a basis of I.
    4442Moreover, it also prints the linear system (for the information about adjacency matrix).
    45 
    4643EXAMPLE: example fpahilb; shows an example "
    4744{
    48         if (attrib(@R, "isLetterplaceRing")==0)
     45        if (attrib(basering, "isLetterplaceRing")==0)
    4946        {
    5047      ERROR("Basering should be Letterplace ring");
    … …  
    5855    string odp="";
    5956    int i;
    60     for(i=sz ;i >= 1; i--)
     57    for(i=sz; i >= 1; i--)
    6158    {
    6259      if(typeof(#[i])=="string")
    … …  
    7269    }
    7370    i=1;
    74 //only one optional parameter (for printing the details) is allowed as a string.
    75     while(typeof(#[i])=="int" && i<=sz)
    76     {
    77       if(#[i] == 1 && ig==0)
     71// VL: changing the old "only one optional parameter (for printing the details) is allowed as a string."
     72    while( (typeof(#[i])=="int") && (i<=sz) )
     73    {
     74      if( (#[i] == 1) && (ig==0) )
    7875      {
    7976        ig = 1;
    … …  
    8178      else
    8279      {
    83         if(#[i] == 2 && mgrad==0)
     80        if ( (#[i] == 2) && (mgrad==0) )
    8481        {
    8582          mgrad = 2;
    … …  
    8784        else
    8885        {
    89           if(#[i] > 2 && tdeg==0)
     86          if ( (#[i] > 2) && (tdeg==0) )
    9087          {
    9188            tdeg = #[i];
    … …  
    103100      ERROR("error:only int 1,2, >2, and a string are allowed as optional parameters");
    104101    }
    105     /* new: truncation should be < than degbound */
    106         if (tdeg> lV)
     102    /* new: truncation should be < than degbound/2 */
     103        if (tdeg > lV div 2 + 1)
    107104        {
    108        ERROR("unappropriate degree bound");
     105       ERROR("degree bound is too high");
    109106        }
    110107    ideal J_lm = I;
    … …  
    130127  def R = makeLetterplaceRing(10); setring R;
    131128  ideal I = Y*Z, Y*Z*X, Y*Z*Z*X, Y*Z*Z*Z*X, Y*Z*Z*Z*Z*X, Y*Z*Z*Z*Z*Z*X, Y*Z*Z*Z*Z*Z*Z*X, Y*Z*Z*Z*Z*Z*Z*Z*X;
    132   nchilb(I,10);
     129  fpahilb(I,5);
    133130  kill R;
    134131       
    … …  
    139136  // inspecting J we see that this is a homogeneous Groebner basis
    140137  // which is potentially infinite, i.e. J is not finitely generated
    141   nchilb(I,6,1); //third argument '1' is for non-finitely generated case
    142 
    143   ring r=0,(a,b),dp;
    144   ideal I = a^3, a*b^2, a^2*b;
    145   nchilb(l3,5,2); //third argument '2' is to compute multi-graded Hilbert series
     138  fpahilb(J,5,1,2,"p"); // '1' i for non-finitely generated case, string to print details
     139  //'5' here is to compute the truncated HS up to degree 5.
     140  //'2' is to compute multi-graded Hilbert series
     141  fpahilb(J,3,1,"p");
     142}
     143
     144// overhauled by VL
     145proc rcolon(ideal I, poly W)
     146"USAGE:  rcolon(I,w); ideal I, poly w
     147RETURNS: ideal
     148ASSUME: - basering is a Letterplace ring
     149- W is a monomial
     150- I is a monomial ideal
     151PURPOSE: compute a right colon ideal of I by a monomial w
     152NOTE: Output is the set of generators, which should be added to I
     153EXAMPLE: example rcolon; shows an example"
     154{
     155        int lV =  attrib(R,"isLetterplaceRing"); //nvars(save);
     156        if (lV == 0)
     157        {
     158      ERROR("Basering must be a Letterplace ring");
     159        }
     160    poly wc = leadmonom(W);
     161        ideal II = lead(I);
     162    ideal J = system("rcolon", II, wc, lV);
     163    // VL: printlevel here? before only printing was there, no output
     164        return(J);
     165 }
     166example
     167{
     168"EXAMPLE:"; echo = 2;
     169  ring r=0,(X,Y,Z),dp;
     170  def R = makeLetterplaceRing(10); setring R;
     171  ideal I = Y*Z, Y*Z*X, Y*Z*Z*X, Y*Z*Z*Z*X, Y*Z*Z*Z*Z*X, Y*Z*Z*Z*Z*Z*X, Y*Z*Z*Z*Z*Z*Z*X, Y*Z*Z*Z*Z*Z*Z*Z*X;
     172  poly w = Y;
     173  ideal J = rcolon(I,w);
     174  J; // new generators, which need to be added to I
     175}
     176
     177
     178/*
     179proc nchilb(list L_wp, int d, list #)
     180"USAGE: fpahilb(I, d[, L]), ideal I, int d, optional list L
     181PURPOSE: compute Hilbert series of a non-commutative algebra
     182ASSUME:
     183NOTE: d is an integer for the degree bound (maximal total degree of
     184         polynomials of the generating set of the input ideal),
     185#[]=1, computation for non-finitely generated regular ideals,
     186#[]=2, computation of multi-graded Hilbert series,
     187#[]=tdeg, for obtaining the truncated Hilbert series up to the total degree tdeg-1 (tdeg should be > 2), and
     188#[]=string(p), to print the details about the orbit and system of equations.
     189Let the orbit is O_I = {T_{w_1}(I),...,T_{w_r}(I)} ($w_i\in W$), where we assume that if T_{w_i}(I)=T_{w_i'}(I)$
     190for some $w'_i\in W$, then $deg(w_i)\leq deg(w'_i)$.
     191Then, it prints words description of orbit: w_1,...,w_r.
     192It also prints the maximal degree and the cardinality of \sum_j R(w_i, b_j) corresponding to each w_i,
     193where {b_j} is a basis of I.
     194Moreover, it also prints the linear system (for the information about adjacency matrix) and its solving time.
     195
     196NOTE  : A Groebner basis of two-sided ideal of the input should be given in a
     197        special form. This form is a list of modules, where each generator
     198        of every module represents a monomial times a coefficient in the free
     199        associative algebra. The first entry, in each generator, represents a
     200        coefficient and every next entry is a variable.
     201
     202        Ex: module p1=[1,y,z],[-1,z,y], represents the poly y*z-z*y;
     203            module p2=[1,x,z,x],[-1,z,x,z], represents the poly x*z*x-z*x*z
     204        for more details about the input, see examples.
     205EXAMPLE: example nchilb; shows an example "
     206{
     207    if (d<1)
     208    {
     209      ERROR("bad degree bound");
     210    }
     211
     212    def save = basering;
     213    int sz=size(#);
     214    int lV=nvars(save);
     215    int ig=0;
     216    int mgrad=0;
     217    int tdeg=0;
     218    string odp="";
     219    int i;
     220    for(i=sz ;i >= 1; i--)
     221    {
     222      if(typeof(#[i])=="string")
     223      {
     224        if(#[i]!="")
     225        {
     226          odp = "p";
     227        }
     228        # = delete(#,i);
     229        sz = sz-1;
     230        break;
     231      }
     232    }
     233    i=1;
     234//only one optional parameter (for printing the details) is allowed as a string.
     235    while(typeof(#[i])=="int" && i<=sz)
     236    {
     237      if(#[i] == 1 && ig==0)
     238      {
     239        ig = 1;
     240      }
     241      else
     242      {
     243        if(#[i] == 2 && mgrad==0)
     244        {
     245          mgrad = 2;
     246        }
     247        else
     248        {
     249          if(#[i] > 2 && tdeg==0)
     250          {
     251            tdeg = #[i];
     252          }
     253          else
     254          {
     255            ERROR("error: only int 1,2 and >2 are allowed as
     256            optional parameters");
     257          }
     258        }
     259      }
     260      i = i + 1;
     261    }
     262    if( i <= sz)
     263    {
     264      ERROR("error:only int 1,2, >2, and a string are allowed as
     265       optional parameters");
     266    }
     267    if(tdeg==0)
     268    {def R = makeLetterplaceRing(2*d);}
     269    else
     270    {def R = makeLetterplaceRing(2*(tdeg-1));}
     271    setring R;
     272    ideal I;
     273    poly p;
     274    poly q=0;
     275    // convert list L_wp of free-poly to letterPlace-poly format
     276    setring save;
     277    module M;
     278    int j,k,sw,sm,slm;
     279    vector w;
     280    poly pc=0;
     281    intvec v;
     282    slm = size(L_wp);              // number of polys in the given ideal
     283    for (i=1; i<=slm; i++)
     284    {
     285        M  = L_wp[i];
     286        sm = ncols(M);            // number of words in the free-poly M
     287        for (j=1; j<=sm; j++)
     288        {
     289            w  = M[j];
     290            sw = size(w);
     291            for (k=2; k<=sw; k++)
     292            {
     293              v[k-1]=rvar(w[k]);
     294            }
     295            pc=w[1];
     296            setring R;
     297            p=imap(save,pc);
     298            for (k=2; k<=sw; k++)
     299            {
     300              p=p*var(v[k-1]+(k-2)*lV);
     301            }
     302            q=q+p;
     303            setring save;
     304        }
     305        setring R;
     306        I = I,q; //lp-polynomial added to I
     307        q=0;   //ready for the next polynomial
     308        setring save;
     309    }
     310    setring R;
     311    I=simplify(I,2);
     312    ideal J_lm;
     313    for(i=1;i<=size(I);i++)
     314    {
     315        J_lm[i]=leadmonom(I[i]);
     316    }
     317    //compute the Hilbert series
     318    if(odp == "")
     319    {system("nc_hilb", J_lm, lV, ig, mgrad,tdeg);}
     320    else
     321    {system("nc_hilb", J_lm, lV, ig, mgrad,tdeg, odp);}
     322}
     323
     324example
     325{
     326"EXAMPLE:"; echo = 2;
     327
     328    ring r=0,(X,Y,Z),dp;
     329    module p1 =[1,Y,Z];             //represents the poly Y*Z
     330    module p2 =[1,Y,Z,X];          //represents the poly Y*Z*X
     331    module p3 =[1,Y,Z,Z,X,Z];
     332    module p4 =[1,Y,Z,Z,Z,X,Z];
     333    module p5 =[1,Y,Z,Z,Z,Z,X,Z];
     334    module p6 =[1,Y,Z,Z,Z,Z,Z,X,Z];
     335    module p7 =[1,Y,Z,Z,Z,Z,Z,Z,X,Z];
     336    module p8 =[1,Y,Z,Z,Z,Z,Z,Z,Z,X,Z];
     337    list l1=list(p1,p2,p3,p4,p5,p6,p7,p8);
     338    nchilb(l1,10);
     339
     340    ring r=0,(x,y,z),dp;
     341
     342    module p1=[1,y,z],[-1,z,y];               //y*z-z*y
     343    module p2=[1,x,z,x],[-1,z,x,z];           // x*z*x-z*x*z
     344    module p3=[1,x,z,z,x,z],[-1,z,x,z,z,x];   // x*z^2*x*z-z*x*z^2*x
     345    module p4=[1,x,z,z,z,x,z];[-1,z,x,z,z,x,x]; // x*z^3*x*z-z*x*z^2*x^2
     346    list l2=list(p1,p2,p3,p4);
     347
     348    nchilb(l2,6,1); //third argument '1' is for non-finitely generated case
     349
     350    ring r=0,(a,b),dp;
     351    module p1=[1,a,a,a];
     352    module p2=[1,a,b,b];
     353    module p3=[1,a,a,b];
     354
     355    list l3=list(p1,p2,p3);
     356    nchilb(l3,5,2);//third argument '2' is to compute multi-graded HS
    146357
    147358    ring r=0,(x,y,z),dp;
    … …  
    187398    //'11' is to compute the truncated HS up to degree 10.
    188399}
    189 
    190 // overhauled by VL
    191 proc rcolon(ideal I, poly W)
    192 "USAGE:  rcolon(I,w,d); ideal I, poly w
    193 RETURNS: ideal
    194 ASSUME: - basering is a Letterplace ring
    195 - W is a monomial
    196 - I is a monomial ideal
    197 PURPOSE: compute a right colon ideal of I by a monomial w
    198 NOTE: Output is the set of generators, which should be added to I
    199 EXAMPLE: example rcolon; shows an example"
    200 {
    201     if (d<1)
    202     {
    203        ERROR("bad degree bound");
    204     }
    205         int lV =  attrib(R,"isLetterplaceRing"); //nvars(save);
    206         if (lV == 0)
    207         {
    208       ERROR("Basering must be a Letterplace ring");
    209         }
    210     poly wc = leadmonom(W);
    211         ideal II = lead(I);
    212     ideal J = system("rcolon", II, wc, lV);
    213     // VL: printlevel here? before only printing was there, no output
    214         return(J);
    215  }
    216 example
    217 {
    218 "EXAMPLE:"; echo = 2;
    219   ring r=0,(X,Y,Z),dp;
    220   poly w = Y;
    221   ideal I = Y*Z, Y*Z*X, Y*Z*Z*X, Y*Z*Z*Z*X, Y*Z*Z*Z*Z*X, Y*Z*Z*Z*Z*Z*X, Y*Z*Z*Z*Z*Z*Z*X, Y*Z*Z*Z*Z*Z*Z*Z*X;
    222   ideal J = rcolon(I,w,10);
    223   J; // new generators, which need to be added to I
    224 }
    225 
    226 
    227 /*
    228 proc nchilb(list L_wp, int d, list #)
    229 "USAGE: fpahilb(I, d[, L]), ideal I, int d, optional list L
    230 PURPOSE: compute Hilbert series of a non-commutative algebra
    231 ASSUME:
    232 NOTE: d is an integer for the degree bound (maximal total degree of
    233          polynomials of the generating set of the input ideal),
    234 #[]=1, computation for non-finitely generated regular ideals,
    235 #[]=2, computation of multi-graded Hilbert series,
    236 #[]=tdeg, for obtaining the truncated Hilbert series up to the total degree tdeg-1 (tdeg should be > 2), and
    237 #[]=string(p), to print the details about the orbit and system of equations.
    238 Let the orbit is O_I = {T_{w_1}(I),...,T_{w_r}(I)} ($w_i\in W$), where we assume that if T_{w_i}(I)=T_{w_i'}(I)$
    239 for some $w'_i\in W$, then $deg(w_i)\leq deg(w'_i)$.
    240 Then, it prints words description of orbit: w_1,...,w_r.
    241 It also prints the maximal degree and the cardinality of \sum_j R(w_i, b_j) corresponding to each w_i,
    242 where {b_j} is a basis of I.
    243 Moreover, it also prints the linear system (for the information about adjacency matrix) and its solving time.
    244 
    245 NOTE  : A Groebner basis of two-sided ideal of the input should be given in a
    246         special form. This form is a list of modules, where each generator
    247         of every module represents a monomial times a coefficient in the free
    248         associative algebra. The first entry, in each generator, represents a
    249         coefficient and every next entry is a variable.
    250 
    251         Ex: module p1=[1,y,z],[-1,z,y], represents the poly y*z-z*y;
    252             module p2=[1,x,z,x],[-1,z,x,z], represents the poly x*z*x-z*x*z
    253         for more details about the input, see examples.
    254 EXAMPLE: example nchilb; shows an example "
    255 {
    256     if (d<1)
    257     {
    258       ERROR("bad degree bound");
    259     }
    260 
    261     def save = basering;
    262     int sz=size(#);
    263     int lV=nvars(save);
    264     int ig=0;
    265     int mgrad=0;
    266     int tdeg=0;
    267     string odp="";
    268     int i;
    269     for(i=sz ;i >= 1; i--)
    270     {
    271       if(typeof(#[i])=="string")
    272       {
    273         if(#[i]!="")
    274         {
    275           odp = "p";
    276         }
    277         # = delete(#,i);
    278         sz = sz-1;
    279         break;
    280       }
    281     }
    282     i=1;
    283 //only one optional parameter (for printing the details) is allowed as a string.
    284     while(typeof(#[i])=="int" && i<=sz)
    285     {
    286       if(#[i] == 1 && ig==0)
    287       {
    288         ig = 1;
    289       }
    290       else
    291       {
    292         if(#[i] == 2 && mgrad==0)
    293         {
    294           mgrad = 2;
    295         }
    296         else
    297         {
    298           if(#[i] > 2 && tdeg==0)
    299           {
    300             tdeg = #[i];
    301           }
    302           else
    303           {
    304             ERROR("error: only int 1,2 and >2 are allowed as
    305             optional parameters");
    306           }
    307         }
    308       }
    309       i = i + 1;
    310     }
    311     if( i <= sz)
    312     {
    313       ERROR("error:only int 1,2, >2, and a string are allowed as
    314        optional parameters");
    315     }
    316     if(tdeg==0)
    317     {def R = makeLetterplaceRing(2*d);}
    318     else
    319     {def R = makeLetterplaceRing(2*(tdeg-1));}
    320     setring R;
    321     ideal I;
    322     poly p;
    323     poly q=0;
    324     // convert list L_wp of free-poly to letterPlace-poly format
    325     setring save;
    326     module M;
    327     int j,k,sw,sm,slm;
    328     vector w;
    329     poly pc=0;
    330     intvec v;
    331     slm = size(L_wp);              // number of polys in the given ideal
    332     for (i=1; i<=slm; i++)
    333     {
    334         M  = L_wp[i];
    335         sm = ncols(M);            // number of words in the free-poly M
    336         for (j=1; j<=sm; j++)
    337         {
    338             w  = M[j];
    339             sw = size(w);
    340             for (k=2; k<=sw; k++)
    341             {
    342               v[k-1]=rvar(w[k]);
    343             }
    344             pc=w[1];
    345             setring R;
    346             p=imap(save,pc);
    347             for (k=2; k<=sw; k++)
    348             {
    349               p=p*var(v[k-1]+(k-2)*lV);
    350             }
    351             q=q+p;
    352             setring save;
    353         }
    354         setring R;
    355         I = I,q; //lp-polynomial added to I
    356         q=0;   //ready for the next polynomial
    357         setring save;
    358     }
    359     setring R;
    360     I=simplify(I,2);
    361     ideal J_lm;
    362     for(i=1;i<=size(I);i++)
    363     {
    364         J_lm[i]=leadmonom(I[i]);
    365     }
    366     //compute the Hilbert series
    367     if(odp == "")
    368     {system("nc_hilb", J_lm, lV, ig, mgrad,tdeg);}
    369     else
    370     {system("nc_hilb", J_lm, lV, ig, mgrad,tdeg, odp);}
    371 }
    372 
    373 example
    374 {
    375 "EXAMPLE:"; echo = 2;
    376 
    377     ring r=0,(X,Y,Z),dp;
    378     module p1 =[1,Y,Z];             //represents the poly Y*Z
    379     module p2 =[1,Y,Z,X];          //represents the poly Y*Z*X
    380     module p3 =[1,Y,Z,Z,X,Z];
    381     module p4 =[1,Y,Z,Z,Z,X,Z];
    382     module p5 =[1,Y,Z,Z,Z,Z,X,Z];
    383     module p6 =[1,Y,Z,Z,Z,Z,Z,X,Z];
    384     module p7 =[1,Y,Z,Z,Z,Z,Z,Z,X,Z];
    385     module p8 =[1,Y,Z,Z,Z,Z,Z,Z,Z,X,Z];
    386     list l1=list(p1,p2,p3,p4,p5,p6,p7,p8);
    387     nchilb(l1,10);
    388 
    389     ring r=0,(x,y,z),dp;
    390 
    391     module p1=[1,y,z],[-1,z,y];               //y*z-z*y
    392     module p2=[1,x,z,x],[-1,z,x,z];           // x*z*x-z*x*z
    393     module p3=[1,x,z,z,x,z],[-1,z,x,z,z,x];   // x*z^2*x*z-z*x*z^2*x
    394     module p4=[1,x,z,z,z,x,z];[-1,z,x,z,z,x,x]; // x*z^3*x*z-z*x*z^2*x^2
    395     list l2=list(p1,p2,p3,p4);
    396 
    397     nchilb(l2,6,1); //third argument '1' is for non-finitely generated case
    398 
    399     ring r=0,(a,b),dp;
    400     module p1=[1,a,a,a];
    401     module p2=[1,a,b,b];
    402     module p3=[1,a,a,b];
    403 
    404     list l3=list(p1,p2,p3);
    405     nchilb(l3,5,2);//third argument '2' is to compute multi-graded HS
    406 
    407     ring r=0,(x,y,z),dp;
    408     module p1=[1,x,z,y,z,x,z];
    409     module p2=[1,x,z,x];
    410     module p3=[1,x,z,y,z,z,x,z];
    411     module p4=[1,y,z];
    412     module p5=[1,x,z,z,x,z];
    413 
    414     list l4=list(p1,p2,p3,p4,p5);
    415     nchilb(l4,7,"p"); //third argument "p" is to print the details
    416                      // of the orbit and system
    417 
    418     ring r=0,(x,y,z),dp;
    419 
    420     module p1=[1,y,z,z];
    421     module p2=[1,y,y,z];
    422     module p3=[1,x,z,z];
    423     module p4=[1,x,z,y];
    424     module p5=[1,x,y,z];
    425     module p6=[1,x,y,y];
    426     module p7=[1,x,x,z];
    427     module p8=[1,x,x,y];
    428     module p9=[1,y,z,y,z];
    429     module p10=[1,y,z,x,z];
    430     module p11=[1,y,z,x,y];
    431     module p12=[1,x,z,x,z];
    432     module p13=[1,x,z,x,y];
    433     module p14=[1,x,y,x,z];
    434     module p15=[1,x,y,x,y];
    435     module p16=[1,y,z,y,x,z];
    436     module p17=[1,y,z,y,x,y];
    437     module p18=[1,y,z,y,y,x,z];
    438     module p19=[1,y,z,y,y,x,y];
    439     module p20=[1,y,z,y,y,y,x,z];
    440     module p21=[1,y,z,y,y,y,x,y];
    441 
    442     list l5=list(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,
    443     p14,p15,p16,p17,p18,p19,p20,p21);
    444     nchilb(l5,7,1,2,"p");
    445 
    446     nchilb(l5,7,1,2,11,"p");
    447     //'11' is to compute the truncated HS up to degree 10.
    448 }
    449400*/
    450401
Note: See TracChangeset for help on using the changeset viewer.