Changeset 79893d5 in git


Ignore:
Timestamp:
Oct 24, 2018, 7:19:23 PM (6 years ago)
Author:
Viktor Levandovskyy <levandov@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
ccef1eb6e20089e5cfa874a24ecd7214396997a6
Parents:
b6b95b3bfd0ae62f05831baf6e66e376305769b4
Message:
levandov: major adaptation to the new Letterplace interface
File:
1 edited

Legend:

Unmodified
Added
Removed

  • Singular/LIB/ncHilb.lib

    rb6b95b3 r79893d5  
    33category="Noncommutative algebra";
    44info="
    5 LIBRARY:  ncHilb.lib: A library for computing graded and multi-graded Hilbert
    6                       series of non-commutative algebras. It also computes
    7                       the truncated Hilbert series of the algebras whose Hilbert
     5LIBRARY:  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
    88                      series are possibly not rational or unknown.
    99
    1010AUTHOR:   Sharwan K. Tiwari   shrawant@gmail.com
    1111          Roberto La Scala
    12 
     12                  Viktor Levandovskyy (adaptation to the new Letterplace release)
     13                 
    1314REFERENCES:
    14           La Scala R.: Monomial right ideals and the Hilbert series of
    15           non-commutative modules, J. of Symb. Comp. (2016).
    16 
    17           La Scala R., Tiwari Sharwan K.: Multigraded Hilbert Series of
    18           noncommutative modules, https://arxiv.org/abs/1705.01083.
     15          La Scala R.: Monomial right ideals and the Hilbert series of non-commutative modules,
     16                  Journal of Symbolic Computation (2016).
     17
     18          La Scala R., Tiwari Sharwan K.: Multigraded Hilbert Series of noncommutative modules, https://arxiv.org/abs/1705.01083.
    1919
    2020PROCEDURES:
    21           nchilb(L,d,#); Hilbert series of a non-commutative algebra
    22           rcolon(L, w, d); Right colon ideal of a two-sided monomial ideal
    23                            with respect to a monomial w
     21          fpahilb(L,d,#); Hilbert series of a non-commutative algebra
     22          rcolon(I, w, d); Right colon ideal of a two-sided monomial ideal with respect to a monomial w
    2423
    2524";
    … …  
    2726LIB "freegb.lib";
    2827
    29 proc nchilb(list L_wp, int d, list #)
    30 "USAGE:  nchilb(list of relations, an integer, optional);
    31          L is a list of modules (each module represents a free-polynomial),
    32          d is an integer for the degree bound (maximal total degree of
    33          polynomials of the generating set of the input ideal),
    34          #[]=1, computation for non-finitely generated regular ideals,
    35          #[]=2, computation of multi-graded Hilbert series,
    36          #[]=tdeg, for obtaining the truncated Hilbert series up to the
    37               total degree tdeg-1 (tdeg should be > 2), and
    38 
    39          #[]=string(p), to print the details about the orbit and system of
    40              equations. Let the orbit is O_I = {T_{w_1}(I),...,T_{w_r}(I)}
    41              ($w_i\in W$), where we assume that if T_{w_i}(I)=T_{w_i'}(I)$
    42              for some $w'_i\in W$, then $deg(w_i)\leq deg(w'_i)$.
    43              Then, it prints words description of orbit: w_1,...,w_r.
    44              It also prints the maximal degree and the cardinality of
    45              \sum_j R(w_i, b_j) corresponding to each w_i, where {b_j} is a
    46              basis of I. Moreover, it also prints the linear system (for the
    47              information about adjacency matrix) and its solving time.
    48 
    49 NOTE  : A Groebner basis of two-sided ideal of the input should be given in a
    50         special form. This form is a list of modules, where each generator
    51         of every module represents a monomial times a coefficient in the free
    52         associative algebra. The first entry, in each generator, represents a
    53         coefficient and every next entry is a variable.
    54 
    55         Ex: module p1=[1,y,z],[-1,z,y], represents the poly y*z-z*y;
    56             module p2=[1,x,z,x],[-1,z,x,z], represents the poly x*z*x-z*x*z
    57         for more details about the input, see examples.
    58 EXAMPLE: example nchilb; shows an example "
    59 {
    60     if (d<1)
    61     {
    62       ERROR("bad degree bound");
    63     }
    64 
    65     def save = basering;
     28proc fpahilb(ideal I, list #)
     29"USAGE: fpahilb(I[, L]), ideal I, optional list L
     30PURPOSE: compute Hilbert series of a non-commutative algebra, presented by I
     31RETURN: nothing (prints data out)
     32ASSUME: basering is a Letterplace ring, I is given via its Groebner basis
     33NOTE: the appearance of following values among the optional arguments triggers the following:
     34@* 1: computation for non-finitely generated regular ideals,
     35@* 2: computation of multi-graded Hilbert series,
     36@* N>2: computation of truncated Hilbert series up to degree N-1, and
     37@* nonempty string: the details about the orbit and system of equations will be printed.
     38
     39Let 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)}
     40for some @code{w'_i\in W}, then @code{deg(w_i)\leq deg(w'_i)} follows.
     41Then the description of orbit in the form @code{w_1,...,w_r} will be printed.
     42It also prints the maximal degree and the cardinality of @code{\sum_j R(w_i, b_j)} corresponding to each @code{w_i},
     43where @code{{b_j}} is a basis of I.
     44Moreover, it also prints the linear system (for the information about adjacency matrix).
     45
     46EXAMPLE: example fpahilb; shows an example "
     47{
     48        if (attrib(@R, "isLetterplaceRing")==0)
     49        {
     50      ERROR("Basering should be Letterplace ring");
     51        }
     52        def save = basering;
    6653    int sz=size(#);
    67     int lV=nvars(save);
     54    int lV=attrib(save,"uptodeg");
    6855    int ig=0;
    6956    int mgrad=0;
    … …  
    10693          else
    10794          {
    108             ERROR("error: only int 1,2 and >2 are allowed as
    109             optional parameters");
     95            ERROR("error: only int 1,2 and >2 are allowed as optional parameters");
    11096          }
    11197        }
    … …  
    115101    if( i <= sz)
    116102    {
    117       ERROR("error:only int 1,2, >2, and a string are allowed as
    118        optional parameters");
    119     }
    120     if(tdeg==0)
    121     {def R = makeLetterplaceRing(2*d);}
    122     else
    123     {def R = makeLetterplaceRing(2*(tdeg-1));}
    124     setring R;
    125     ideal I;
    126     poly p;
    127     poly q=0;
    128     // convert list L_wp of free-poly to letterPlace-poly format
    129     setring save;
    130     module M;
    131     int j,k,sw,sm,slm;
    132     vector w;
    133     poly pc=0;
    134     intvec v;
    135     slm = size(L_wp);              // number of polys in the given ideal
    136     for (i=1; i<=slm; i++)
    137     {
    138         M  = L_wp[i];
    139         sm = ncols(M);            // number of words in the free-poly M
    140         for (j=1; j<=sm; j++)
    141         {
    142             w  = M[j];
    143             sw = size(w);
    144             for (k=2; k<=sw; k++)
    145             {
    146               v[k-1]=rvar(w[k]);
    147             }
    148             pc=w[1];
    149             setring R;
    150             p=imap(save,pc);
    151             for (k=2; k<=sw; k++)
    152             {
    153               p=p*var(v[k-1]+(k-2)*lV);
    154             }
    155             q=q+p;
    156             setring save;
    157         }
    158         setring R;
    159         I = I,q; //lp-polynomial added to I
    160         q=0;   //ready for the next polynomial
    161         setring save;
    162     }
    163     setring R;
    164     I=simplify(I,2);
    165     ideal J_lm;
     103      ERROR("error:only int 1,2, >2, and a string are allowed as optional parameters");
     104    }
     105    /* new: truncation should be < than degbound */
     106        if (tdeg> lV)
     107        {
     108       ERROR("unappropriate degree bound");
     109        }
     110    ideal J_lm = I;
    166111    for(i=1;i<=size(I);i++)
    167112    {
    … …  
    170115    //compute the Hilbert series
    171116    if(odp == "")
    172     {system("nc_hilb", J_lm, lV, ig, mgrad,tdeg);}
     117    {
     118      system("nc_hilb", J_lm, lV, ig, mgrad,tdeg);
     119        }
    173120    else
    174     {system("nc_hilb", J_lm, lV, ig, mgrad,tdeg, odp);}
     121    {
     122      system("nc_hilb", J_lm, lV, ig, mgrad,tdeg, odp);
     123        }
    175124}
    176125
    … …  
    178127{
    179128"EXAMPLE:"; echo = 2;
    180 
    181     ring r=0,(X,Y,Z),dp;
    182     module p1 =[1,Y,Z];             //represents the poly Y*Z
    183     module p2 =[1,Y,Z,X];          //represents the poly Y*Z*X
    184     module p3 =[1,Y,Z,Z,X,Z];
    185     module p4 =[1,Y,Z,Z,Z,X,Z];
    186     module p5 =[1,Y,Z,Z,Z,Z,X,Z];
    187     module p6 =[1,Y,Z,Z,Z,Z,Z,X,Z];
    188     module p7 =[1,Y,Z,Z,Z,Z,Z,Z,X,Z];
    189     module p8 =[1,Y,Z,Z,Z,Z,Z,Z,Z,X,Z];
    190     list l1=list(p1,p2,p3,p4,p5,p6,p7,p8);
    191     nchilb(l1,10);
    192 
    193     ring r=0,(x,y,z),dp;
    194 
    195     module p1=[1,y,z],[-1,z,y];               //y*z-z*y
    196     module p2=[1,x,z,x],[-1,z,x,z];           // x*z*x-z*x*z
    197     module p3=[1,x,z,z,x,z],[-1,z,x,z,z,x];   // x*z^2*x*z-z*x*z^2*x
    198     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
    199     list l2=list(p1,p2,p3,p4);
    200 
    201     nchilb(l2,6,1); //third argument '1' is for non-finitely generated case
    202 
    203     ring r=0,(a,b),dp;
    204     module p1=[1,a,a,a];
    205     module p2=[1,a,b,b];
    206     module p3=[1,a,a,b];
    207 
    208     list l3=list(p1,p2,p3);
    209     nchilb(l3,5,2);//third argument '2' is to compute multi-graded HS
     129  ring r=0,(X,Y,Z),dp;
     130  def R = makeLetterplaceRing(10); setring R;
     131  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);
     133  kill R;
     134       
     135  ring r2=0,(x,y,z),dp;
     136  def R2 = makeLetterplaceRing(11); setring R2;
     137  ideal I = y*z-z*y, x*z*x-z*x*z, x*z^2*x*z-z*x*z^2*x, x*z^3*x*z-z*x*z^2*x^2;
     138  ideal J = std(I); // compute a Groebner basis up to degree 11
     139  // inspecting J we see that this is a homogeneous Groebner basis
     140  // 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
    210146
    211147    ring r=0,(x,y,z),dp;
    … …  
    252188}
    253189
     190// overhauled by VL
     191proc rcolon(ideal I, poly W)
     192"USAGE:  rcolon(I,w,d); ideal I, poly w
     193RETURNS: ideal
     194ASSUME: - basering is a Letterplace ring
     195- W is a monomial
     196- I is a monomial ideal
     197PURPOSE: compute a right colon ideal of I by a monomial w
     198NOTE: Output is the set of generators, which should be added to I
     199EXAMPLE: 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 }
     216example
     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/*
     228proc nchilb(list L_wp, int d, list #)
     229"USAGE: fpahilb(I, d[, L]), ideal I, int d, optional list L
     230PURPOSE: compute Hilbert series of a non-commutative algebra
     231ASSUME:
     232NOTE: 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.
     238Let 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)$
     239for some $w'_i\in W$, then $deg(w_i)\leq deg(w'_i)$.
     240Then, it prints words description of orbit: w_1,...,w_r.
     241It also prints the maximal degree and the cardinality of \sum_j R(w_i, b_j) corresponding to each w_i,
     242where {b_j} is a basis of I.
     243Moreover, it also prints the linear system (for the information about adjacency matrix) and its solving time.
     244
     245NOTE  : 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.
     254EXAMPLE: 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
     373example
     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}
     449*/
     450
     451/*
     452// orig version of the procedure
    254453proc rcolon(list L_wp, module W, int d)
    255454"USAGE:  rcolon(list of relations, a monomial, an integer);
    … …  
    351550    rcolon(l1,w,10);
    352551}
    353 
     552*/
Note: See TracChangeset for help on using the changeset viewer.