Changeset 1593911 in git

Timestamp:

Aug 16, 2019, 2:41:16 PM (4 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', '828514cf6e480e4bafc26df99217bf2a1ed1ef45')

Children:

c8b65d77e75cfce24c257822df19be0d1113e110

Parents:

61805653a98bcb59b2ce76a4d538b2fb05459e28d9e5b0a9e2ca74ac8fcf60a83f008cc393d9278d

git-author:

Hans Schoenemann <hannes@mathematik.uni-kl.de>2019-08-16 14:41:16+02:00

git-committer:

GitHub <noreply@github.com>2019-08-16 14:41:16+02:00

Message:

Merge pull request #948 from kabouzeid/stable

lpGkDim in dynamic module

Files:

• Singular/LIB/fpaprops.lib (modified) (3 diffs)
• Singular/LIB/tropical.lib (modified) (40 diffs)
• Singular/dyn_modules/freealgebra/freealgebra.cc (modified) (5 diffs)
• Singular/iparith.cc (modified) (13 diffs)
• Singular/ipshell.cc (modified) (8 diffs)
• Tst/Letterplace.lst (modified) (2 diffs)
• Tst/Manual/letterplace_std.res.gz.uu (modified) (1 diff)
• Tst/Manual/letterplace_std.stat (modified) (1 diff)
• Tst/Manual/letterplace_std.tst (modified) (2 diffs)
• Tst/Manual/lpGkDim.res.gz.uu (added)
• Tst/Manual/lpGkDim.stat (added)
• Tst/Manual/lpGkDim.tst (added)
• Tst/Manual/lpLmDivisible.res.gz.uu (added)
• Tst/Manual/lpLmDivisible.stat (added)
• Tst/Manual/lpLmDivisible.tst (added)
• libpolys/polys/shiftop.cc (modified) (4 diffs)

Singular/LIB/fpaprops.lib

@@ -26 +26 @@
   lpIsSemiPrime(<GB>);    check whether A/<LM(GB)> is semi-prime
   lpIsPrime(<GB>);        check whether A/<LM(GB)> is prime
-  lpGkDim(<GB>);          compute the Gelfand Kirillov dimension of A/<GB>
   lpGlDimBound(<GB>);     compute an upper bound for the global dimension of A/<GB>
   lpSubstitute();         substitute a variable with polynomials (ring homomorphism)
@@ -43 +42 @@
     example lpIsSemiPrime;
     example lpIsPrime;
-    example lpGkDim;
     example lpGlDimBound;
     example lpSubstitute;
@@ -877 +875 @@
 }
 
-proc lpGkDim(ideal G)
-"USAGE: lpGkDim(G); G an ideal in a letterplace ring
-RETURN: int
-PURPOSE: Determines the Gelfand Kirillov dimension of A/<G>
-       -1 means positive infinite
-ASSUME: - basering is a Letterplace ring
-      - G is a Groebner basis
-"
-{
-  G = lead(G);
-  G = simplify(G, 2+4+8);
-
-  // check special case 1
-  int l = 0;
-  for (int i = 1; i <= size(G); i++) {
-    // find the max degree in G
-    int d = deg(G[i]);
-    if (d > l) {
-      l = d;
-    }
-
-    // also if G is the whole ring return minus infinity
-    if (leadmonom(G[i]) == 1) {
-      ERROR("GK-Dim not defined for 0-ring")
-    }
-    kill d;
-  } kill i;
-  // if longest word has length 1, or G is the zero ideal, we handle it as a special case
-  if (l == 1 || size(G) == 0) {
-    int n = lpVarBlockSize(basering); // variable count
-    int k = size(G);
-    if (k == n) { // V = {1} no edges
-      return(0);
-    }
-    if (k == n-1) { // V = {1} with loop
-      return(1);
-    }
-    if (k <= n-2) { // V = {1} with more than one loop
-      return(-1);
-    }
-  }
-
-  dbprint("computing Ufnarovskii graph");
-  intmat UG = lpUfGraph(G);
-  if (printlevel >= voice + 1) {
-    UG;
-  }
-
-  // check special case 2
-  intmat zero[nrows(UG)][ncols(UG)];
-  if (UG == zero) {
-    return (0);
-  }
-
-  // check special case 3
-  dbprint("topological sorting of Ufnarovskii graph");
-  UG = topologicalSort(UG);
-  if (printlevel >= voice + 1) {
-    UG;
-  }
-
-  dbprint("check if Ufnarovskii graph is DAG");
-  if (imIsUpRightTriangle(UG)) {
-    UG = eliminateZerosUpTriangle(UG);
-    if (ncols(UG) == 0 || nrows(UG) == 0) { // when the diagonal was zero
-      return (0)
-    }
-    dbprint("DAG detected, using URTNZD growth alg");
-    return(UfGraphURTNZDGrowth(UG));
-  }
-
-  // otherwise count cycles in the Ufnarovskij Graph
-  dbprint("not a DAG, using regular growth alg");
-  return(UfGraphGrowth(UG));
-}
-example
-{
-  "EXAMPLE:"; echo = 2;
-  ring r = 0,(x,y,z),dp;
-  def R = freeAlgebra(r, 5); // constructs a Letterplace ring
-  R;
-  setring R; // sets basering to Letterplace ring
-  ideal I = z;//an example of infinite GK dimension
-  lpGkDim(I);
-  I = x,y,z; // gkDim = 0
-  lpGkDim(I);
-  I = x*y, x*z, z*y, z*z;//gkDim = 2
-  lpGkDim(I);
-  ideal G = y*x - x*y, z*x - x*z, z*y - y*z; G = std(G);
-  G;
-  lpGkDim(G); // 3, as expected for K[x,y,z]
-}
+// lpGkDim now implemented in dynamic module
+/* proc lpGkDim(ideal G) */
+/* "USAGE: lpGkDim(G); G an ideal in a letterplace ring */
+/* RETURN: int */
+/* PURPOSE: Determines the Gelfand Kirillov dimension of A/<G> */
+/*        -1 means positive infinite */
+/* ASSUME: - basering is a Letterplace ring */
+/*       - G is a Groebner basis */
+/* " */
+/* { */
+/*   G = lead(G); */
+/*   G = simplify(G, 2+4+8); */
+
+/*   // check special case 1 */
+/*   int l = 0; */
+/*   for (int i = 1; i <= size(G); i++) { */
+/*     // find the max degree in G */
+/*     int d = deg(G[i]); */
+/*     if (d > l) { */
+/*       l = d; */
+/*     } */
+
+/*     // also if G is the whole ring return minus infinity */
+/*     if (leadmonom(G[i]) == 1) { */
+/*       ERROR("GK-Dim not defined for 0-ring") */
+/*     } */
+/*     kill d; */
+/*   } kill i; */
+/*   // if longest word has length 1, or G is the zero ideal, we handle it as a special case */
+/*   if (l == 1 || size(G) == 0) { */
+/*     int n = lpVarBlockSize(basering); // variable count */
+/*     int k = size(G); */
+/*     if (k == n) { // V = {1} no edges */
+/*       return(0); */
+/*     } */
+/*     if (k == n-1) { // V = {1} with loop */
+/*       return(1); */
+/*     } */
+/*     if (k <= n-2) { // V = {1} with more than one loop */
+/*       return(-1); */
+/*     } */
+/*   } */
+
+/*   dbprint("computing Ufnarovskii graph"); */
+/*   intmat UG = lpUfGraph(G); */
+/*   if (printlevel >= voice + 1) { */
+/*     UG; */
+/*   } */
+
+/*   // check special case 2 */
+/*   intmat zero[nrows(UG)][ncols(UG)]; */
+/*   if (UG == zero) { */
+/*     return (0); */
+/*   } */
+
+/*   // check special case 3 */
+/*   dbprint("topological sorting of Ufnarovskii graph"); */
+/*   UG = topologicalSort(UG); */
+/*   if (printlevel >= voice + 1) { */
+/*     UG; */
+/*   } */
+
+/*   dbprint("check if Ufnarovskii graph is DAG"); */
+/*   if (imIsUpRightTriangle(UG)) { */
+/*     UG = eliminateZerosUpTriangle(UG); */
+/*     if (ncols(UG) == 0 || nrows(UG) == 0) { // when the diagonal was zero */
+/*       return (0) */
+/*     } */
+/*     dbprint("DAG detected, using URTNZD growth alg"); */
+/*     return(UfGraphURTNZDGrowth(UG)); */
+/*   } */
+
+/*   // otherwise count cycles in the Ufnarovskij Graph */
+/*   dbprint("not a DAG, using regular growth alg"); */
+/*   return(UfGraphGrowth(UG)); */
+/* } */
+/* example */
+/* { */
+/*   "EXAMPLE:"; echo = 2; */
+/*   ring r = 0,(x,y,z),dp; */
+/*   def R = freeAlgebra(r, 5); // constructs a Letterplace ring */
+/*   R; */
+/*   setring R; // sets basering to Letterplace ring */
+/*   ideal I = z;//an example of infinite GK dimension */
+/*   lpGkDim(I); */
+/*   I = x,y,z; // gkDim = 0 */
+/*   lpGkDim(I); */
+/*   I = x*y, x*z, z*y, z*z;//gkDim = 2 */
+/*   lpGkDim(I); */
+/*   ideal G = y*x - x*y, z*x - x*z, z*y - y*z; G = std(G); */
+/*   G; */
+/*   lpGkDim(G); // 3, as expected for K[x,y,z] */
+/* } */
 
 proc lpGlDimBound(ideal G)

Singular/LIB/tropical.lib

@@ -338 +338 @@
   // we change to a ring where the variables have names t and x(1),...,x(n)
   def ALTERRING=basering;
+  list RL=ringlist(ALTERRING);
   if (nvars(basering)==2)
   {
-    execute("ring BASERING=("+charstr(ALTERRING)+"),(t,x(1)),("+ordstr(ALTERRING)+");");
+    RL[2]=list("t","x(1)");
+    ring BASERING = ring(RL);
   }
   else
   {
-    execute("ring BASERING=("+charstr(ALTERRING)+"),(t,x(1.."+string(nvars(ALTERRING)-1)+")),("+ordstr(ALTERRING)+");");
+    list V = "t";
+    for (int ii = nvars(ALTERRING)-1; ii > 0; ii--)
+    {
+      V[ii+1] = "x("+string(ii)+")";
+    }
+    RL[2]=V;
+    ring BASERING = ring(RL);
   }
   map altphi=ALTERRING,maxideal(1);
@@ -466 +474 @@
   // for this, unfortunately, t has to be the last variable !!!
   ideal variablen;
+  list RL=ringlist(basering);
   for (j=2;j<=nvars(basering);j++)
   {
     variablen=variablen+var(j);
-  }
-  execute("ring GRUNDRING=("+charstr(basering)+"),("+string(variablen)+",t),(dp("+string(nvars(basering)-1)+"),lp(1));");
+    RL[2][j-1]=RL[2][j];
+  }
+  RL[2][size(RL[2])]="t";
+  RL[3]=list(list("dp",1:(nvars(basering)-1)),list("lp",1));
+  ring GRUNDRING = ring(RL);
+  list RL=ringlist(GRUNDRING);
+  list VARIABLEN;
   ideal variablen;
   for (j=1;j<=nvars(basering)-1;j++)
   {
     variablen=variablen+var(j);
+    VARIABLEN[j]=RL[2][j];
   }
   map GRUNDPHI=BASERING,t,variablen;
@@ -497 +512 @@
   if (iszerodim==0) // do so only if is_dim_zero is not set
   {
-    execute("ring QUOTRING=("+charstr(basering)+",t),("+string(variablen)+"),dp;");
+    RL=ringlist(basering);
+    RL[1]=list(RL[1],list("t"),list(list("lp",1)),ideal(0));
+    RL[2]=VARIABLEN;
+    RL[3]=list(list("dp",1:size(VARIABLEN)));
+    ring QUOTRING = ring(RL);
     ideal i=groebner(imap(GRUNDRING,i));
     int dd=dim(i);
@@ -573 +592 @@
         // from LIFTRING are present,
         // and where also the variables of CUTDOWNRING live
-        execute("ring REPLACEMENTRING=("+charstr(LIFTRING)+"),("+varstr(CUTDOWNRING)+"),dp;");
+        list RL=ringlist(LIFTRING);
+        list RL2=ringlist(CUTDOWNRING);
+        RL[2]=RL2[2];
+        RL[3]=list(list("dp",1:nvars(CUTDOWNRING)));
+        ring REPLACEMENTRING = ring(RL);
         list repl=imap(CUTDOWNRING,repl); // get the replacement rules
                                           // from CUTDOWNRING
@@ -1069 +1092 @@
       poly mp=minpoly;
       def OLDRING=basering;
-      execute("ring NEWRING=0,("+varstr(basering)+","+parstr(basering)+"),ds;");
+      list RL=ringlist(OLDRING);
+      RL[2]=RL[2]+RL[1][2];
+      RL[1]=RL[1][1];
+      RL[3]=list(list("ds",1:size(RL[2])));
+      ring NEWRING=ring(RL);
       ideal I=imap(OLDRING,mp),imap(OLDRING,f);
     }
@@ -1717 +1744 @@
     {
       string polynomstring=string(f);
-      execute("ring drawring=(0,"+parstr(basering)+"),("+varstr(basering)+"),dp;");
+      list RL=ringlist(basering);
+      RL[1][1]=0;
+      RL[3]=list(list("dp",1:nvars(basering)));
+      ring drawring = ring(RL);
       execute("poly f="+polynomstring+";");
     }
@@ -2637 +2667 @@
   // THIS IS NOT DOCUMENTED FOR THE GENERAL USER!!!!
   def BASERING=basering;
+  list RL=ringlist(BASERING);
+  list VARIABLEN;
   int j;
   if (size(#)>0)
@@ -2642 +2674 @@
     // we first have to move the variable t to the front again
     ideal variablen=var(nvars(basering));
+    VARIABLEN[1]=RL[2][nvars(basering)];
     for (j=1;j<nvars(basering);j++)
     {
       variablen=variablen+var(j);
+      VARIABLEN[j+1]=RL[2][j];
     }
   }
@@ -2650 +2684 @@
   {
     ideal variablen=maxideal(1);
+    VARIABLEN=RL[2];
   }
   // we want to homogenise the ideal i ....
-  execute("ring HOMOGRING=("+charstr(basering)+"),(@s,"+string(variablen)+"),dp;");
+  RL=ringlist(basering);
+  RL[2]=list("@s")+RL[2];
+  RL[3]=list(list("dp",1:size(RL[2])));
+  ring HOMOGRING = ring(RL);
   ideal i=homog(std(imap(BASERING,i)),@s);
   // ... and compute a standard basis with
@@ -2667 +2705 @@
   }
   intmat O=weightVectorToOrderMatrix(whomog);
-  execute("ring WEIGHTRING=("+charstr(basering)+"),("+varstr(basering)+"),(M("+string(O)+"));");
+  list RL=ringlist(basering);
+  RL[3]=list(list("M",O));
+  ring WEIGHTRING = ring(RL);
   // map i to the new ring and compute a GB of i, then dehomogenise i,
   // so that we can be sure, that the
@@ -2674 +2714 @@
   // compute the w-initial ideal with the help of the procedure tInitialForm;
   setring BASERING;
-  execute("ring COMPINIRING=("+charstr(basering)+"),("+string(variablen)+"),dp;");
+  RL[2]=VARIABLEN;
+  RL[3]=list(list("dp",1:size(VARIABLEN)));
+  ring COMPINIRING = ring(RL);
   ideal i=imap(WEIGHTRING,i);
   ideal ini;
@@ -2711 +2753 @@
   def BASERING=basering;
   intmat O=weightVectorToOrderMatrix(w);
-  execute("ring INITIALRING=("+charstr(BASERING)+"),("+varstr(basering)+"),M("+string(O)+");");
+  list RL=ringlist(basering);
+  RL[3]=list(list("M",O));
+  ring INITIALRING = ring(RL);
   poly f=imap(BASERING,f);
   int GRAD=deg(f);
@@ -2784 +2828 @@
   def BASERING=basering;
   intmat O=weightVectorToOrderMatrix(w);
-  execute("ring INITIALRING=("+charstr(BASERING)+"),("+varstr(basering)+"),M("+string(O)+");");
+  list RL=ringlist(BASERING);
+  RL[3]=list(list("M",O));
+  ring INITIALRING = ring(RL);
   ideal i=imap(BASERING,i);
   i=std(i);
@@ -2834 +2880 @@
   }
   def BASERING=basering;
-  execute("ring PARAMETERRING=("+string(char(basering))+"),("+parstr(basering)+"),ds;");
+  ring PARAMETERRING = create_ring("("+string(char(basering))+")", "("+parstr(basering)+")", "ds");
   poly den=imap(BASERING,den);
   poly num=imap(BASERING,num);
@@ -3493 +3539 @@
 {
   def BASERING=basering;
-  execute("ring RADRING=("+charstr(basering)+"),(@T,"+varstr(basering)+"),(dp(1),"+ordstr(basering)+");");
+  list RL=ringlist(BASERING);
+  RL[2]=list("@T")+RL[2];
+  RL[3]=list(list("dp",1:1))+RL[3];
+  ring RADRING = ring(RL);
   ideal I=ideal(imap(BASERING,i))+ideal(1-@T*imap(BASERING,f));
   if (reduce(1,std(I))==0)
@@ -3644 +3693 @@
   CHARAKTERISTIK=CHARAKTERISTIK[1..size(CHARAKTERISTIK)-2];
   def BASERING=basering;
-  execute("ring INITIALRING=("+CHARAKTERISTIK+"),("+varstr(basering)+"),("+ordstr(basering)+");");
+  ring INITIALRING = create_ring("("+CHARAKTERISTIK+")", "("+varstr(basering)+")", "("+ordstr(basering)+")");
   list l=solve(imap(BASERING,i));
   l;
@@ -3952 +4001 @@
   }
   def BASERING=basering;
-  execute("ring QUOTRING=("+charstr(basering)+",t),("+string(variablen)+"),dp;");
+  ring QUOTRING = create_ring("("+charstr(basering)+",t)", "("+string(variablen)+")", "dp");
   ideal i=subst(imap(BASERING,i),var(j-1),t^(-wj)*var(j-1));
   for (k=1;k<=size(i);k++)
@@ -4007 +4056 @@
   list erglini;
   list ergl;
+  list VARIABLEN;
+  list RL=ringlist(BASERING);
   for (j1=1;j1<=nvars(basering)-1;j1++)
   {
@@ -4013 +4064 @@
     product=product*var(j1); // make product of all variables
                              // (needed for the initial-monomial-check later
-  }
-  execute("ring QUOTRING=("+charstr(basering)+",t),("+string(variablen)+"),dp;");
+    VARIABLEN[j1]=RL[2][j1];
+  }
+  RL[1]=list(RL[1],list("t"),list(list("lp",1:1)),ideal(0));
+  RL[2]=VARIABLEN;
+  RL[3]=list(list("dp",1:size(VARIABLEN)));
+  ring QUOTRING = ring(RL);
   setring BASERING;
   // change to quotring where we want to compute the primary decomposition of i
@@ -4201 +4256 @@
         variablen=0;
         j2=0;
+        VARIABLEN=list();
         for(j1=1;j1<=nvars(basering)-1;j1++)
         {
@@ -4214 +4270 @@
             variablen=variablen+var(j1); // read the set of remaining variables
                                          // (needed to make quotring later)
+            VARIABLEN=VARIABLEN+list(RL[2][j1]);
           }
         }
         // return pideal, the initial and the list ergl which tells us
         // which variables we replaced by which form
-        execute("ring BASERINGLESS1=("+charstr(BASERING)+"),("+string(variablen)+",t),(dp("+string(ncols(variablen))+"),lp(1));");
+        RL=ringlist(BASERING);
+        RL[2]=VARIABLEN+list("t");
+        RL[3]=list(list("dp",1:size(VARIABLEN)),list("lp",1:1));
+        ring BASERINGLESS1 = ring(RL);
         ideal i=imap(BASERING,pideal);
         ideal ini=imap(BASERING,pini); //ideal ini2=tInitialIdeal(i,wvecp,1);
@@ -4295 +4355 @@
   }
   setring BASERING;
-  execute("ring BASERINGLESS2=("+charstr(BASERING)+"),("+string(variablen)+",t),(dp("+string(ncols(variablen))+"),lp(1));");
+  ring BASERINGLESS2 = create_ring(ringlist(BASERING)[1], "("+string(variablen)+",t)", "(dp("+string(ncols(variablen))+"),lp(1))", "no_minpoly");
   // using the 0/1-vector which tells us which variables belong
   // to the set of smallest entries of wvec
@@ -4643 +4703 @@
   if ((numberdeletedvariables>0) and (anzahlvariablen>1)) // if only t remains,
   { // all true variables are gone
-    execute("ring NEURING=("+charstr(basering)+"),("+string(variablen)+"),(dp("+string(size(variablen)-1)+"),lp(1));");
+    ring NEURING = create_ring(ringlist(basering)[1], "("+string(variablen)+")", "(dp("+string(size(variablen)-1)+"),lp(1))", "no_minpoly");
     ideal i=imap(BASERING,i);
     ideal gesamt_m=imap(BASERING,gesamt_m);
@@ -4659 +4719 @@
     {
       // pass to a ring which has variables which are suitable for gfan
-      execute("ring GFANRING=("+charstr(basering)+"),(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z),dp;");
+      ring GFANRING = create_ring(ringlist(basering)[1], "(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z)", "dp", "no_minpoly");
       ideal phiideal=b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z;
       phiideal[nvars(PREGFANRING)]=a; // map t to a
@@ -4829 +4889 @@
     else
     {
-      execute("ring PARARing=("+charstr(basering)+"),t,ls;");
+      ring PARARing = create_ring(ringlist(basering)[1], "t", "ls", "no_minpoly");
     }
     ideal PARA; // will contain the parametrisation
@@ -4917 +4977 @@
     variablen=variablen+var(j);
   }
-  execute("ring INITIALRING=("+charstr(basering)+"),("+string(variablen)+"),dp;");
+  ring INITIALRING = create_ring(ringlist(basering)[1], "("+string(variablen)+")", "dp", "no_minpoly");
   ideal ini=imap(BASERING,ini);
   // compute the associated primes of the initialideal
@@ -5160 +5220 @@
   if (anzahlvariablen<nvars(basering))
   {
-    execute("ring TINRING=("+charstr(basering)+","+string(Parameter)+"),("+string(variablen)+"),dp;");
+    ring TINRING = create_ring("("+charstr(basering)+","+string(Parameter)+")", "("+string(variablen)+")", "dp");
   }
   else
   {
-    execute("ring TINRING=("+charstr(basering)+"),("+string(variablen)+"),dp;");
+    ring TINRING = create_ring(ringlist(basering)[1], "("+string(variablen)+")", "dp", "no_minpoly");
   }
   ideal tin=imap(BASERING,tin);
@@ -5185 +5245 @@
   string PMet=string(par(1));
   def BASERING=basering;
-  execute("ring r=0,"+PMet+",ls;");
+  ring r = create_ring(0, PMet, "ls");
   execute("poly denomi="+denom+";");
   execute("poly numer="+num+";");
@@ -5543 +5603 @@
     if (size(#)>0) // noAbs was used
     {
-      execute("ring NOQRing=("+string(char(LIFTRing))+"),("+varstr(basering)+","+parstr(LIFTRing)+"),dp;");
+      ring NOQRing = create_ring("("+string(char(LIFTRing))+")", "("+varstr(basering)+","+parstr(LIFTRing)+")", "dp");
       execute("qring TESTRing=std("+#[1]+");");
       ideal i=imap(BASERING,i);
@@ -5551 +5611 @@
       setring LIFTRing;
       poly mp=minpoly;
-      execute("ring TESTRing=("+charstr(LIFTRing)+"),("+varstr(BASERING)+"),dp;");
+      ring TESTRing = create_ring(ringlist(LIFTRing)[1], "("+varstr(BASERING)+")", "dp", "no_minpoly");
       minpoly=number(imap(LIFTRing,mp));
       ideal i=imap(BASERING,i);
@@ -5718 +5778 @@
         {
           // pass to a ring which has variables which are suitable for gfan
-          execute("ring GFANRING=("+string(char(basering))+"),(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z),dp;");
+          ring GFANRING = create_ring(string(char(basering)), "(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z)", "dp");
           ideal phiideal=b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z;
           phiideal[nvars(PREGFANRING)]=a; // map t to a
@@ -5934 +5994 @@
         if (anzahlvariablen<nvars(basering))
         {
-          execute("ring PARARing=("+string(char(basering))+",@a),t,ls;");
+          ring PARARing = create_ring("("+string(char(basering))+",@a)", "t", "ls");
           minpoly=number(imap(PREGFANRING,m));
         }
         else
         {
-          execute("ring PARARing=("+charstr(basering)+"),t,ls;");
+          ring PARARing = create_ring(ringlist(basering)[1], "t", "ls", "no_minpoly");
         }
         ideal PARA; // will contain the parametrisation
@@ -6200 +6260 @@
         else
         {
-          execute("ring SATURATERING=("+charstr(basering)+"),("+varstr(basering)+"),("+ordstr(basering)+");");
+          ring SATURATERING = create_ring(ringlist(basering)[1], "("+varstr(basering)+")", "("+ordstr(basering)+")", "no_minpoly");
           ideal i=imap(BASERING,i);
           export(i);
@@ -6308 +6368 @@
   def BASERING=basering;
   string tvar=string(var(nvars(basering)));
+  list RL_BASERING=ringlist(BASERING);
+  list TVAR=RL_BASERING[2];
   int j,k,l; // indices
   // store the weighted degrees of the elements of i in an integer vector
@@ -6334 +6396 @@
   // collect the true variables x_1,...,x_n plus @a, if it is defined in BASERING
   ideal variablen;
+  list VARIABLEN;
+  list RL=ringlist(basering);
   for (j=1;j<=nvars(basering)-1;j++)
   {
     variablen=variablen+var(j);
+    VARIABLEN[j]=RL[2][j];
   }
   // move to a polynomial ring with global monomial ordering
   // - the variable t is superflous,
   // the variable @a is not if it was already present
-  execute("ring INITIALRING=("+charstr(basering)+"),("+string(variablen)+"),dp;");
+  RL[2]=VARIABLEN;
+  RL[3]=list(list("dp",1:size(VARIABLEN)));
+  ring INITIALRING = ring(RL);
   ideal ini=imap(BASERING,ini);
   // compute the minimal associated primes of the
@@ -6357 +6424 @@
   }
   list extensionringlist; // contains the rings which are to be returned
+  list RL;
   for (j=1;j<=size(maximalideals);j++)
   {
@@ -6363 +6431 @@
     // if some of the maximal ideals needs a field extension,
     // then everything will live in this ring
+    RL=ringlist(BASERING);
     if ((maximalideals[j][1]!=0) and (nvars(BASERING)==anzahlvariablen))
     {
       // define the extension ring which contains
       // the new variable @a, if it is not yet present
-      execute("ring EXTENSIONRING=("+charstr(BASERING)+"),("+string(imap(BASERING,variablen))+",@a,"+tvar+"),(dp("+string(anzahlvariablen-1)+"),dp(1),lp(1));");
+      RL[2]=VARIABLEN+list("@a")+TVAR;
+      RL[3]=list(list("dp",1:(anzahlvariablen-1)),list("dp",1:1),list("lp",1:1));
+      ring EXTENSIONRING = ring(RL);
       // phi maps x_i to x_i, @a to @a (if present in the ring),
       // and the additional variable
@@ -6378 +6449 @@
     else // @a was already present in the BASERING or no
     { // field extension is necessary
-      execute("ring EXTENSIONRING=("+charstr(BASERING)+"),("+varstr(BASERING)+"),("+ordstr(BASERING)+");");
+      ring EXTENSIONRING = ring(RL);
       // phi maps x_i to x_i, @a to @a (if present in the ring),
       // and the additional variable
@@ -7255 +7326 @@
 {
   def BASERING=basering;
-  execute("ring INTERRING=0,("+varstr(basering)+"),("+ordstr(basering)+");");
+  ring INTERRING = create_ring(0, "("+varstr(basering)+")", "("+ordstr(basering)+")");
   poly n=imap(BASERING,n);
-  execute("ring REALRING=(real,50,100),("+varstr(basering)+"),("+ordstr(basering)+");");
+  ring REALRING = create_ring("(real,50,100)", "("+varstr(basering)+")", "("+ordstr(basering)+")");
   map phi=INTERRING,maxideal(1);
   string s=string(phi(n));
@@ -7873 +7944 @@
   {
     def BASERING=basering;
-    execute("ring TRING="+string(char(BASERING))+",t,ds;");
+    ring TRING = create_ring(string(char(BASERING)), "t", "ds");
     poly hn=imap(BASERING,hn);
     poly c4=imap(BASERING,c4);

Singular/dyn_modules/freealgebra/freealgebra.cc

@@ -1 +1 @@
 #include "Singular/libsingular.h"
+#include <vector>
 
 #ifdef HAVE_SHIFTBBA
@@ -84 +85 @@
 }
 
+static BOOLEAN p_LPDivisibleBy(ideal I, poly p, ring r)
+{
+  for(int i = 0; i < IDELEMS(I); i++)
+  {
+    if (p_LPDivisibleBy(I->m[i], p, r))
+    {
+      return TRUE;
+    }
+  }
+  return FALSE;
+}
+
 static BOOLEAN lpLmDivides(leftv res, leftv h)
 {
@@ -101 +114 @@
     poly q=(poly)h->next->Data();
     res->rtyp = INT_CMD;
-    for(int i=0;i<IDELEMS(I);i++)
-    {
-      if (p_LPDivisibleBy(I->m[i],q, currRing))
-      {
-        res->data=(void*)(long)1;
-        return FALSE;
-      }
-    }
-    res->data=(void*)(long)0;
+    res->data=(void*)(long) p_LPDivisibleBy(I, q, currRing);
     return FALSE;
   }
@@ -128 +133 @@
   else return TRUE;
 }
+
+static void _computeStandardWords(ideal words, int n, ideal M, int& last)
+{
+  if (n <= 0){
+    words->m[0] = pOne();
+    last = 0;
+    return;
+  }
+
+  _computeStandardWords(words, n - 1, M, last);
+
+  int nVars = currRing->isLPring;
+
+  for (int j = nVars - 1; j >= 0; j--)
+  {
+    for (int i = last; i >= 0; i--)
+    {
+      int index = (j * (last + 1)) + i;
+
+      if (words->m[i] != NULL)
+      {
+        if (j > 0) {
+          words->m[index] = pCopy(words->m[i]);
+        }
+
+        int varOffset = ((n - 1) * nVars) + 1;
+        pSetExp(words->m[index], varOffset + j, 1);
+        pSetm(words->m[index]);
+        pTest(words->m[index]);
+
+        if (p_LPDivisibleBy(M, words->m[index], currRing))
+        {
+          pDelete(&words->m[index]);
+          words->m[index] = NULL;
+        }
+      }
+    }
+  }
+
+  last = nVars * last + nVars - 1;
+}
+
+static ideal computeStandardWords(int n, ideal M)
+{
+  int nVars = currRing->isLPring;
+
+  int maxElems = 1;
+  for (int i = 0; i < n; i++) // maxElems = nVars^n
+    maxElems *= nVars;
+  ideal words = idInit(maxElems);
+  int last;
+  _computeStandardWords(words, n, M, last);
+  idSkipZeroes(words);
+  return words;
+}
+
+// NULL if graph is undefined
+static intvec* ufnarovskiGraph(ideal G)
+{
+  long l = 0;
+  for (int i = 0; i < IDELEMS(G); i++)
+    l = si_max(pTotaldegree(G->m[i]), l);
+  l--;
+  if (l <= 0)
+  {
+    WerrorS("Ufnarovski graph not implemented for l <= 0");
+    return NULL;
+  }
+  int lV = currRing->isLPring;
+
+  ideal standardWords = computeStandardWords(l, G);
+
+  int n = IDELEMS(standardWords);
+  intvec* UG = new intvec(n, n, 0);
+  for (int i = 0; i < n; i++)
+  {
+    for (int j = 0; j < n; j++)
+    {
+      poly v = standardWords->m[i];
+      poly w = standardWords->m[j];
+
+      // check whether v*x1 = x2*w (overlap)
+      bool overlap = true;
+      for (int k = 1; k <= (l - 1) * lV; k++)
+      {
+        if (pGetExp(v, k + lV) != pGetExp(w, k)) {
+          overlap = false;
+          break;
+        }
+      }
+
+      if (overlap)
+      {
+        // create the overlap
+        poly p = pMult(pCopy(v), p_LPVarAt(w, l, currRing));
+
+        // check whether the overlap is normal
+        bool normal = true;
+        for (int k = 0; k < IDELEMS(G); k++)
+        {
+          if (p_LPDivisibleBy(G->m[k], p, currRing))
+          {
+            normal = false;
+            break;
+          }
+        }
+
+        if (normal)
+        {
+          IMATELEM(*UG, i + 1, j + 1) = 1;
+        }
+      }
+    }
+  }
+  return UG;
+}
+
+static std::vector<int> countCycles(const intvec* _G, int v, std::vector<int> path, std::vector<BOOLEAN> visited, std::vector<BOOLEAN> cyclic, std::vector<int> cache)
+{
+  intvec* G = ivCopy(_G); // modifications must be local
+
+  if (cache[v] != -2) return cache; // value is already cached
+
+  visited[v] = TRUE;
+  path.push_back(v);
+
+  int cycles = 0;
+  for (int w = 0; w < G->cols(); w++)
+  {
+    if (IMATELEM(*G, v + 1, w + 1)) // edge v -> w exists in G
+    {
+      if (!visited[w])
+      { // continue with w
+        cache = countCycles(G, w, path, visited, cyclic, cache);
+        if (cache[w] == -1)
+        {
+          cache[v] = -1;
+          return cache;
+        }
+        cycles = si_max(cycles, cache[w]);
+      }
+      else
+      { // found new cycle
+        int pathIndexOfW = -1;
+        for (int i = path.size() - 1; i >= 0; i--) {
+          if (cyclic[path[i]] == 1) { // found an already cyclic vertex
+            cache[v] = -1;
+            return cache;
+          }
+          cyclic[path[i]] = TRUE;
+
+          if (path[i] == w) { // end of the cycle
+            assume(IMATELEM(*G, v + 1, w + 1) != 0);
+            IMATELEM(*G, v + 1, w + 1) = 0; // remove edge v -> w
+            pathIndexOfW = i;
+            break;
+          } else {
+            assume(IMATELEM(*G, path[i - 1] + 1, path[i] + 1) != 0);
+            IMATELEM(*G, path[i - 1] + 1, path[i] + 1) = 0; // remove edge vi-1 -> vi
+          }
+        }
+        assume(pathIndexOfW != -1); // should never happen
+        for (int i = path.size() - 1; i >= pathIndexOfW; i--) {
+          cache = countCycles(G, path[i], path, visited, cyclic, cache);
+          if (cache[path[i]] == -1)
+          {
+            cache[v] = -1;
+            return cache;
+          }
+          cycles = si_max(cycles, cache[path[i]] + 1);
+        }
+      }
+    }
+  }
+  cache[v] = cycles;
+
+  delete G;
+  return cache;
+}
+
+// -1 is infinity
+static int graphGrowth(const intvec* G)
+{
+  // init
+  int n = G->cols();
+  std::vector<int> path;
+  std::vector<BOOLEAN> visited;
+  std::vector<BOOLEAN> cyclic;
+  std::vector<int> cache;
+  visited.resize(n, FALSE);
+  cyclic.resize(n, FALSE);
+  cache.resize(n, -2);
+
+  // get max number of cycles
+  int cycles = 0;
+  for (int v = 0; v < n; v++)
+  {
+    cache = countCycles(G, v, path, visited, cyclic, cache);
+    if (cache[v] == -1)
+      return -1;
+    cycles = si_max(cycles, cache[v]);
+  }
+  return cycles;
+}
+
+// -1 is infinity, -2 is error
+static int gkDim(const ideal _G)
+{
+  if (rField_is_Ring(currRing)) {
+      WerrorS("GK-Dim not implemented for rings");
+      return -2;
+  }
+
+  for (int i=IDELEMS(_G)-1;i>=0; i--)
+  {
+    if (pGetComp(_G->m[i]) != 0)
+    {
+      WerrorS("GK-Dim not implemented for modules");
+      return -2;
+    }
+  }
+
+  ideal G = id_Head(_G, currRing); // G = LM(G) (and copy)
+  idSkipZeroes(G); // remove zeros
+  id_DelLmEquals(G, currRing); // remove duplicates
+
+  // get the max deg
+  long maxDeg = 0;
+  for (int i = 0; i < IDELEMS(G); i++)
+  {
+    maxDeg = si_max(maxDeg, pTotaldegree(G->m[i]));
+
+    // also check whether G = <1>
+    if (pIsConstantComp(G->m[i]))
+    {
+      WerrorS("GK-Dim not defined for 0-ring");
+      return -2;
+    }
+  }
+
+  // early termination if G \subset X
+  if (maxDeg <= 1)
+  {
+    int lV = currRing->isLPring;
+    if (IDELEMS(G) == lV) // V = {1} no edges
+      return 0;
+    if (IDELEMS(G) == lV - 1) // V = {1} with loop
+      return 1;
+    if (IDELEMS(G) <= lV - 2) // V = {1} with more than one loop
+      return -1;
+  }
+
+  intvec* UG = ufnarovskiGraph(G);
+  if (errorreported || UG == NULL) return -2;
+  return graphGrowth(UG);
+}
+
+
+static BOOLEAN lpGkDim(leftv res, leftv h)
+{
+  const short t[]={1,IDEAL_CMD};
+  if (iiCheckTypes(h,t,1))
+  {
+    assumeStdFlag(h);
+    ideal G = (ideal) h->Data();
+    res->rtyp = INT_CMD;
+    res->data = (void*)(long) gkDim(G);
+    if (errorreported) return TRUE;
+    return FALSE;
+  }
+  else return TRUE;
+}
 #endif
 
@@ -138 +415 @@
   p->iiAddCproc("freealgebra.so","lpLmDivides",FALSE,lpLmDivides);
   p->iiAddCproc("freealgebra.so","lpVarAt",FALSE,lpVarAt);
+  p->iiAddCproc("freealgebra.so","lpGkDim",FALSE,lpGkDim);
+
   p->iiAddCproc("freealgebra.so","stest",TRUE,stest);
   p->iiAddCproc("freealgebra.so","btest",TRUE,btest);

Singular/iparith.cc

@@ -1023 +1023 @@
       }
       res->data = (char *)(pp_Mult_qq( a, b, currRing));
-      pNormalize((poly)res->data);
       return FALSE;
     }
@@ -1036 +1035 @@
     }
     res->data = (char *)(pMult( a, b));
-    pNormalize((poly)res->data);
     return jjOP_REST(res,u,v);
   }
@@ -1051 +1049 @@
   }
   res->data = (char *)(pMult( a, b));
-  pNormalize((poly)res->data);
   return jjOP_REST(res,u,v);
 }
@@ -1057 +1054 @@
 {
   res->data = (char *)idMult((ideal)u->Data(),(ideal)v->Data());
-  id_Normalize((ideal)res->data,currRing);
   if ((v->next!=NULL) || (u->next!=NULL))
     return jjOP_REST(res,u,v);
@@ -1106 +1102 @@
   ideal I= (ideal)mp_MultP((matrix)u->CopyD(MATRIX_CMD),p,currRing);
   if (r>0) I->rank=r;
-  id_Normalize(I,currRing);
   res->data = (char *)I;
   return FALSE;
@@ -1116 +1111 @@
   ideal I= (ideal)pMultMp(p,(matrix)v->CopyD(MATRIX_CMD),currRing);
   if (r>0) I->rank=r;
-  id_Normalize(I,currRing);
   res->data = (char *)I;
   return FALSE;
@@ -1125 +1119 @@
   poly p=pNSet(n);
   res->data = (char *)mp_MultP((matrix)u->CopyD(MATRIX_CMD),p,currRing);
-  id_Normalize((ideal)res->data,currRing);
   return FALSE;
 }
@@ -1135 +1128 @@
 {
   res->data = (char *)mp_MultI((matrix)u->CopyD(MATRIX_CMD),(int)(long)v->Data(),currRing);
-  id_Normalize((ideal)res->data,currRing);
   return FALSE;
 }
@@ -1152 +1144 @@
      return TRUE;
   }
-  id_Normalize((ideal)res->data,currRing);
   if ((v->next!=NULL) || (u->next!=NULL))
     return jjOP_REST(res,u,v);
@@ -1167 +1158 @@
      return TRUE;
   }
-  id_Normalize((ideal)res->data,currRing);
   if ((v->next!=NULL) || (u->next!=NULL))
     return jjOP_REST(res,u,v);
@@ -1317 +1307 @@
     }
   }
-  id_Normalize((ideal)mm,currRing);
   res->data=(char *)mm;
   return FALSE;
@@ -3974 +3963 @@
 
 /// Return the denominator of the input number
-/// NOTE: the input number is normalized as a side effect
 static BOOLEAN jjDENOMINATOR(leftv res, leftv v)
 {
-  number n = reinterpret_cast<number>(v->Data());
+  number n = reinterpret_cast<number>(v->CopyD());
   res->data = reinterpret_cast<void*>(n_GetDenom(n, currRing->cf));
+  n_Delete(&n,currRing);
   return FALSE;
 }
 
 /// Return the numerator of the input number
-/// NOTE: the input number is normalized as a side effect
 static BOOLEAN jjNUMERATOR(leftv res, leftv v)
 {
-  number n = reinterpret_cast<number>(v->Data());
+  number n = reinterpret_cast<number>(v->CopyD());
   res->data = reinterpret_cast<void*>(n_GetNumerator(n, currRing->cf));
+  n_Delete(&n,currRing);
   return FALSE;
 }
@@ -4529 +4518 @@
   else
   {
+    nNormalize(pGetCoeff(p));
     res->data=(char *)nCopy(pGetCoeff(p));
   }

Singular/ipshell.cc

@@ -1692 +1692 @@
         case ringorder_Ds:
         case ringorder_lp:
+        case ringorder_rp:
+        case ringorder_ls:
           for(;j>=0; j--) (*iv)[j]=1;
           break;
@@ -2205 +2207 @@
         case ringorder_Ds:
         case ringorder_lp:
+        case ringorder_ls:
+        case ringorder_rp:
           for(;j>=0; j--) (*iv)[j]=1;
           break;
@@ -2399 +2403 @@
         {
           ch=TRUE;
-          Warn("name conflict var(%d) and var(%d): `%s`, rename to `@%s`",i+1,j+1,R->names[i],R->names[i]);
+          Warn("name conflict var(%d) and var(%d): `%s`, rename to `@%s`in >>%s<<\nin %s:%d",i+1,j+1,R->names[i],R->names[i],my_yylinebuf,currentVoice->filename,yylineno);
           omFree(R->names[j]);
           R->names[j]=(char *)omAlloc(2+strlen(R->names[i]));
@@ -2414 +2418 @@
       if (strcmp(rParameter(R)[i],R->names[j])==0)
       {
-        Warn("name conflict par(%d) and var(%d): `%s`, renaming the VARIABLE to `@@(%d)`",i+1,j+1,R->names[j],i+1);
+        Warn("name conflict par(%d) and var(%d): `%s`, rename the VARIABLE to `@@(%d)`in >>%s<<\nin %s:%d",i+1,j+1,R->names[j],i+1,my_yylinebuf,currentVoice->filename,yylineno);
 //        omFree(rParameter(R)[i]);
 //        rParameter(R)[i]=(char *)omAlloc(10);
@@ -2532 +2536 @@
           continue;
         }
-        if ((vv->m[1].Typ()!=INTVEC_CMD) && (vv->m[1].Typ()!=INT_CMD))
+        if ((vv->m[1].Typ()!=INTVEC_CMD) && (vv->m[1].Typ()!=INT_CMD)
+        && (vv->m[1].Typ()!=INTMAT_CMD))
         {
           PrintS(lString(vv));
@@ -2562 +2567 @@
         intvec *iv;
         if (vv->m[1].Typ()==INT_CMD)
-          iv=new intvec((int)(long)vv->m[1].Data(),(int)(long)vv->m[1].Data());
+        {
+          int l=si_max(1,(int)(long)vv->m[1].Data());
+          iv=new intvec(l);
+          for(int i=0;i<l;i++) (*iv)[i]=1;
+        }
         else
-          iv=ivCopy((intvec*)vv->m[1].Data()); //assume INTVEC
+          iv=ivCopy((intvec*)vv->m[1].Data()); //assume INTVEC/INTMAT
         int iv_len=iv->length();
         if (iv_len==0)
         {
-          Werror("empty intvec for ordering %d (%s)",j_in_R,rSimpleOrdStr(R->order[j_in_R]));
+          Werror("empty intvec for ordering %d (%s)",j_in_R+1,rSimpleOrdStr(R->order[j_in_R]));
           return TRUE;
+        }
+        if (R->order[j_in_R]==ringorder_M)
+        {
+          if (vv->m[1].rtyp==INTMAT_CMD) iv->makeVector();
+          iv_len=iv->length();
         }
         if ((R->order[j_in_R]!=ringorder_s)
@@ -2620 +2634 @@
              R->wvhdl[j_in_R] =( int *)omAlloc((iv->length())*sizeof(int));
              for (i=0; i<iv->length();i++) R->wvhdl[j_in_R][i]=(*iv)[i];
-             R->block1[j_in_R]=si_max(R->block0[j_in_R],R->block0[j_in_R]+(int)sqrt((double)(iv->length()-1)));
+             R->block1[j_in_R]=si_max(R->block0[j_in_R],R->block0[j_in_R]+(int)sqrt((double)(iv->length())));
              if (R->block1[j_in_R]>R->N)
              {
-               WerrorS("ordering matrix too big");
-               return TRUE;
+               R->block1[j_in_R]=R->N;
              }
              break;
@@ -2636 +2649 @@
            case ringorder_Dp:
            case ringorder_rp:
+             #if 0
+             for (i=0; i<iv_len;i++)
+             {
+               if (((*iv)[i]!=1)&&(iv_len!=1))
+               {
+                 iv->show(1);
+                 Warn("ignore weight %d for ord %d (%s) at pos %d\n>>%s<<",
+                   (*iv)[i],j_in_R+1,rSimpleOrdStr(R->order[j_in_R]),i+1,my_yylinebuf);
+                 break;
+               }
+             }
+             #endif // break absfact.tst
              break;
            case ringorder_S:

Tst/Letterplace.lst

@@ -9 +9 @@
 Manual/makeLetterplaceRing.tst
 Manual/serreRelations.tst
+Manual/lpGkDim.tst
 Manual/lpKDim.tst
 Manual/lpMonomialPrinting.tst
@@ -18 +19 @@
 Manual/lpSickleDim.tst
 Manual/lpHilbert.tst
+Manual/lpLmDivisible.tst

Tst/Manual/letterplace_std.res.gz.uu

@@ -1 @@
-begin 640 letterplace_std.res.gz
-M'XL(",KG3EP"`VQE='1E<G!L86-E7W-T9"YR97,`39%=:X,P%(;O_16'L@N-
-M6HS6?B`&-GIC&;MH=S>DZ$Q%$%<T97&_?B?1-KT0S7N>]SD$3Y_[[`,`*(/W
-M[`T68A#+MBD7">#7N>D:83N)I=[`&+1<"-Y?V^*;GP=1+3O^NQQ$(:S3K`EG
-MS:7GO"XGTV,8,>B;KH8>4@@\6WJC]^=X^ZLA5@R:3D#%:^R?RY];5R$;&R!F
-M.+S`$5.UXK6M>=D7=N_%CH'6#`8N]*JC23?HKGC10H9E7Y+1WY"1C&Y$))$>
-M8$"DCP\936=[[QRP@Q>VLZ<U.P:'Q#I\T3S5#N/$,,S3,%0RS"*BM7Y(U9%(
-M5T,:BZ:N6GW'W3OF&VRE;-L@F@(TT%T4S&,-Q'F*T327RK&)J8'7]`E=Y^GX
-:.,YWH0'3_UO]R]M@4R=YL?X!*I4F?1H"````
+begin 644 letterplace_std.res.gz
+M'XL("(6:P5P"`VQE='1E<G!L86-E7W-T9"YR97,`?9M)CQQ7=H7W^A6)AA=4
+M)9/]Y@$""=CHC0##"[4!+PR"D%IL@3`A-ZAJN.A?[^][.41&RG:SR:J,C'C#
+M'<XY][[0G__U3]__R^%PB.\.__S]/QW^\/S;\YO/GW[ZPW<'?OOPZ==/SZ^^
+M_>X;?Q[>O3M\_OC\_/'+WS[_^)>/'WY[_OG-KQ__Z\UOSS\^?_/GRS#I,LQ?
+MOWS\^,M/YY%N7^9WA]OOY<WACW\\Q-OG^N;PY=.OOQR^'-X>PNM7+Z^_OO[O
+M;U__Z6_;T^W=X=.OSX>?/_["V!]^^L^___HS]];MAOZ.+_]Z^(&K3O^/GW_Y
+M^-.7'U]]>5V_W6X:[PZ_?7Q>4_VP79V,_?/''S\?ON?AT\O3UU-_^OKT]9B?
+M7IY>7A^X\/1RXN_3U]LS,3#2\\^OOF?P#_\>W[]=]V[/<C&]?YN2#W$M/ZW'
+M3RGZ\>GEN&Y:M^7SLTYQO?UXO>VTW58<;81\OL`(<>9P^7K=4-^_Y=+Y^Q?'
+MZ#5N-[=X=VM[__;K[>-U0W%S3TQO#O_QZ?/GPY=MOWAO7=K,%LO=$W4Y-!U>
+M_>5#^1`_]`__]NWMN_;@W/+Z);]^2:]?XL[%\?_TX*%O+HR;"U_]<'=YY\.7
+M\O123JD^^4LZO40_MB=_YM-</]/1?^/KZP`IO%F/Y6/,Y\>.,:U?HD]X[5C6
+MSW0L<?T2<<]YZ#7@-E1DJ'R9:CV0SO<]3HF98[^LD;4F?SJV]VYW949;7[DP
+M1SJ5\TXNPY[W=S=L.3\0C^7R?5X_X\U8J3X$[_]Z^SF$+ZNZS%BO]Y1PNXD`
+M_G]V>P[=VS:OVSNE<-U$#Y<Q4]@&K;=GN".4BR-BS1=7M'&9K,U^=@9>*9>)
+M4[L,?LHU]8N[N;@-WV[#EU,,Y;+B4POILJI69[]N=8[-(OW]VXLM7$\[_[Z>
+M8)C;IW3JN5X_^-@@>Z^/I>,XW^0":VG;$#WTN`U1T\5&ES$F0!':>8BUQ+,)
+MUL)C#+%=/[*6,OKV.:VOT^US/(YXGG49M<7;TC3&V%9WS#&GZQ(*^1#JO"TI
+MGV*/:6SK-V'R''&W\1@PV"PUS5+JN"[>!3/43".%=K>+%FLI+2^C7/>29BJY
+MQQI&O]L1M@FAII%3'MN^8LRM])##V+:71J^ISG&YMJ*'SS-D]Q.NFR4B9RZU
+MS%KNKA)!O0V6V6>K=Y9H?;("K%QJV&(`>*^ML8;&WMKF/2Q39PTAY=IRBR7O
+M+$3^I8EY&/*\E?.R0XJ)*(KE9C2V5]H8/5RNK:440IRU5+DC7Q&NQL"(;=GA
+M8C&"*T2R(:;M3I!DY-GQQ643:^8Z6IACYK;9*^:<:HYSC+39"V\';FR]I;2%
+M3,R#_Y41YYV]VFRY,U>;H]P%T)AQAC"P52WWUB+YR+DY8\._<6<L$(D8"?F<
+MO&L/!&&]>F=M@$?CN/,VL[04Q[;R08"5?-GS\G+K>*;,;<6X%K*=,6_I>6I`
+MR`C8<4L*N``KP\1Q/G@55#1!KWA9XVW!QRL&^GM.=_8`P>ZL0++O4TD)D*^D
+MM,)MS&U4MASG-G#JZ3Z*<]L2^93;V&8]$I5AF]:L?IA7+(ZCW.82?6>,F]-/
+M/?;1YMT$^+GWDK9)B$ARIN>[B7+'Q"6T'<A%D/EE[W(@EU`C&\CK-$:.;<9:
+M6Z@DPIP]D"*D[(B%9,Q`36XY\Q5I"T;DVMEZ!YQS:9&'"K?WF+N.G#,!?J&G
+M`D3-.@K)`*!Q>V2241%8D5L8O>78Y^9@EP_Q1+)_Q#1[6T;C]R98Y9);SZ.)
+M9&#9#(/L9)S0B/Y!6(]&?O)P9@*P35T7@9G.K;!A"8XVB4A`@[LZN2@DECJE
+MJE!J9<*"OF.8IP=C#8W501/7`W;-+-*QTQGB2(5,`.58@_B5&""Q3]AAEIXG
+MN.=T3,@"@"H`(X*R';0DU3/VJ0#Q&(VX8W23E^6'EA/_!Y=PP[Q;#P1!G`'P
+MV"E6`!1W]3'88\/>G9]I1%"X59W+2C)3L^8$6'`#:^BES0*MUL9204?2D;\%
+MS,^%=8VN=1TKUH&I6FM:-F'D#.#?>VM1$RA4E_')C5HR[I9$V";C8%C,R@\P
+M5EH`P0AAAAQR2A\U@.O\PW:ADXRQ(+H\(K[!:Z7@8)<6ZL)WJ`ZD;C@]CHX[
+M'KT$E1.-F+LG8P,[81<,/J8AD(UQ.$1S`XS$WB1(6V%K$UMW8")%PWU@UTF:
+MM0XY5L)5VFFAL[`4!3@@`<O"Z2'=+0&=HYWG\@CXB^NF&8(WV>FH8",6Q_O,
+MBI_X-;$9K`W]L"-0O/!L-1%U!+\V/)M8C\MJ5;$!-Z?6.DO#V&7320L,)K@^
+M_5+@GZ0!ZU4*P"9E5)['_CD!*?H:N!\XC]C(F1!FSY.O8&"BA"S6WVR0_&Q5
+M_612:\FA9]BW:19B?TC=R0I-102$8W0-#&T3F4F?+&P@R4A`HQ<;X!?N`E.R
+MWC'N!EDHSQ("U03E<7U*Z!)_"(DDV^,V2"3D\1`!"5DTPA()'1R46!DQ,0FI
+M9!2!4PF^QL*U,P:K&$4'D7GZ&C1)4Y0B>DD%MDD*8XD63.1$FL*_P,#<@'ZQ
+M,Z,:[`1$(+0#""6DX",`E#P#N=AMJ@0^:&-DLV?"04$@@I*5$'X3,[0\L:[8
+M@=>)=9`<__`K2[P/MJ-I6;KN-FF;F8_Q"!C2!(@FW)L0`L6,N0PPD!N4LI,0
+M;2*ANBSP''#)\DFS5*,X&8TPC(>7^'(78<U<CGU],;4AT$\D:$CF"\0O.U#5
+M%%P'@$<A.)%C9#>X1'*;'F"*#(&A15RB3$!FV7UYCLAM;1=7)$,?XAAX0)BP
+M6>*)U;-R2&C9:.`<S15<#R.X(3"B+G@-?!X(59`_*6V5S6"`/H>(,!(H60G0
+M1SQ)43P!`,'.:.P4,8`T9$`21H'"MX._6%#EHSYCL5"`6%Z!#O:#";#41*CB
+M=@`N+\1LFP*Z:%"(Q`2%T/$`[F%F8D/,DD.'XV,9890L5<G581)/0TNC,!$A
+M0(@"=9`XM<K00R-L$F7%*C?#F=*G4@SH(=:7*@8S`3R(12)GFR#Q9)!!OFM$
+MK,YFY)(B72:V$PB3X'T!;#B71G=H2,DA36$$H%4&Z`(FR!.0&18OH.B:*:KM
+M)6T`D5QIV(TM:?61F#EI0LR][*(I"-^Q"\O5LY'*HP*W5A=G:B!/9>FBFP@J
+MJ6GEA'PH$V(:HH(1V340RPB$%?LWA%451755PBX8EX29ZE)2J6DEXM[L@6Z)
+M<ZXT,1A=SV"=:RB7Q?.$J%A#L0`^=F-:<,-NKI[AB-9X5^1=0G`)<T8%++$T
+M*V07C$9.F;":7;*"V]FGJ*&"P+RZ-G>1&D2>IB!&A%"[J-W&S7SGXK2[?5P)
+M`I,_I#ZDO7@WFG,@(-L$*8%R-#J!719[2JOJ4Q:FR[+B40D!WHZXBVYJ_6J8
+M9=2`'*-\3*"JA@`-V`H,I;)JJYX3^P!*XHD_X$%<0"5U)05=5=[TL(_JZ<#D
+M#,8DMC*A,M43A!N7*=I0%UB7[['A5'Z1/<:,FY$QUK:C;%BL3Z#].'9PR_=#
+MDJ+<<H6)VX/@Q542!D0J:J71634$!2@AUJO[!=]A60:>HI[215%2DSO<$_B)
+MU;)FY3<Y9LFO"I0XAGEMH%"5`M8D(J;+`!HN9R.&5-3VXCE[[^JC0A@NG173
+M7K)!YZ23#,ENDH\"D^#,7(^:'/(*!L1:Q<B49YS"!4P9.!!P,+P)*V`@[$?X
+M'7A2J<FZ-PM:/>&37>21JCLF+93ZQ,#>M]1C(%W8>0,!1:"4O?E,/7-XAT-4
+MZ*0SYJGY<87EVG2Z5.Y'TFDW,9FR(UV*.B[U/3L1SB7]+F_KM3.5K@VUL),,
+MIYWK*>WJR&$W%?`)(>R)D!3(Z7$J2CO<0L"1@.U^0UB3E"%]VV:1<Q,D+[8U
+MQK<R\=S!@6@(55@1Y']@J(!T4RFKRLO>02@'Z'ZIY#9W^Q*NSYH.L5/B;H?P
+M-Y[M%!GZ+.W"U`X>J3:L8@I_XN.N*5\)2`M452<%ZC+`Q!6DG::@T!">JGAC
+MX0;[5B43Z$-Z6OU1Z5B2P3)AZV*L/AYU#)@'0`U[5UUZ+-(!P('X@7:[VF/`
+M*@H<N%T%"7\.R9OTQTO@L6*P[)$V.**CH;#6H^I^S$/&HMRFM)Y,:TJ-*3P.
+M>-$R/%N:!.OHN9)615UVB6-O`#XN2TC8HF*9"R)@EFH:(TG(<Z#0\CJ[(7-?
+M!0Q9<'M73"W*(.4W\#OW.9@2MK0;H![%S(IKUJBEE`=P3+;,0.=9NJ('B`5K
+M3<S!DK*J&G6H`,ICKV.M8?F#D[(=2="9C014ET6ZX`*1*_PLNN4NV$$>LT@M
+MX!"4D(T[0!#^PO-C[#$5C2<ARCOL&&X05_DX5//$,W^3YL;=[#XJS6$/=DJ=
+M3*A,:^!0UK0I+PVSAU/L/&U,8#0L;$_4VHNB@=#&/%6%!6:`KG9;F:$9<NS)
+M-:L4+#&E-,.8*=OOD-3F`R2/69@"QR%^W;Z*4,ECX3T7!C,-,I4$M=XR@PF3
+MJ3C0N)`WL]UZE.<^.RED`2'C*`497GD(`K/`G@4.C6Z?UT*""\D,(G/D/$J!
+M060B/^ZSYZ3JGM3G2E>7C:.P*CIH29YH!XNOIZUCPE5/(*I!,)-J=:XQ49;I
+M=BKEN`K_9J\\:R\$,J)O552&"RJ(@"$(<>O4Q,/^$W)`_"`(L2XXT"Q)RXYQ
+MCGQM/5<M0]0'D-LB'"MO##[TZKI0;"(4R\-ASXC?[%OR$.,C[IN1N],D3&I)
+M$VV.V8<8]JG($(3):I4`\(5457@!%DMGD?#3F@63&^!(2RQDVN]`=2`SFMZU
+MH]/-OZY$D[J#+5_W7RQPK95'7(+6=+1,*VJN;&;*^4BX/>O$U4QB3>1L,1-9
+M)EQAL4IY;$.(/+=D!SN()]/.LH`%HP6ROPT['$/9!6*4':8/ZY]IK82P#+8<
+MA)!L/X3`L@"F9,R6L/C2>@;!OJI8U,>P[]A+,IR&9QR_Y]Q)GJ@LF_V49M$"
+M('@Z`/:8R>A_0955)&LFH@PG0DTM61!X[%+LU)2['$DGE)#-$C*[NEI[&>AY
+M_)Y5KU9X^B"N8JO9=XJB6%!!>7F6M)T6K(8R<TNOEBK]7'_WU2JP4*"2M@T"
+MN!JZ:LJN23PU(*V3[#9'V66;!SX=]&``#6^P%GLL"+.V0H.PP&CV.P1P:DA,
+MD>6)8FM^/E8#1PJS8D=`65C2@G%K&78)>]J$`A%;//<);4TFZ<CZ&;EIJ470
+MC+WXMY-"=@X?E"BC(I],CK9+U1I6RM4U,M$P0;D-@;=*:3M/81UGW646Q*L4
+MM1PN%D3^0]2**-PN/(##:?41VUD*H#^:#:YY[BR9+3L64CQ;6;95./*\>HRL
+MA#'4$X`)&=.:-9O\:)K!;-VZ`>"DH*;LLJ&UYQY+)@*DK>82HEQXI<PS/(07
+MA!%Q9)-V!35,!+DB!5;Y296-.A-;'@2\ZD$*MB'7XU(9=OQM/Q0S5?FF7X/I
+MVUBY=9\B0^LF0ZK9H\W](7]R0$BNWANJ`9=*]+)KM0\*S`Y(RC86O]O]P]'6
+M,LF:<+:[$/?`!5JV4B)S$>6V(FQJF2[=0Z4RUZ$!WY?UM1TATK#V^V&2ASCV
+MC(!BS6B!BPA)(CO`G^6GU4C5`,Y#<25/*ZQV+&>_)Q(+V`O):T:N)"OV$.<Z
+M5$1\>E06Z[GC1P3./:<=53?$;;1)G"WF;`1FR1HW$M/=DPCD!`A"/LJ,P5)]
+M7^W@Y>$)!F%FL`7//Z.%%[N$(:.)K@9824S!F^P-CC!VZ815A'1@4>YP%7V=
+M2`ZC:X%T#PLVH&RN-`NB9NH_%,S8TA!6`MB#MS`%.>QS1J-&38L:I`2)-A'#
+MRDD(K>ZJE'+JUF%RL(<7LK?M9'&,8AS&M518.E&("^N\>G4^[-L]\,ZJH2TI
+M04)E.:1),G@VQ?KF.CM)'L?7:4_8O)+^U['HGF3(QVZ%HTH%$J+-3//$+N-<
+MR[,Q2;9:*`\)@F3!ACD^5HAY-0"MZ:T@SPT5NWVV04$F]!S;UCC5>C\JU>\B
+MKQR'66^OT1,#6*\D-:1GH"TLQ>LF]'5,\DXKNRP2:E7^"#P"=O35(E7HV21C
+M+=D/4_6^FD^YQ7WZV+!H]M64'JS6(R(!TJ[I-#FG:AZ,QV!$8M]E7SS9L4EJ
+M@&J,*Z`!GF0G14PEXFQAJV;K.HYX**"4SW-U1DP9/![M$())=L3SVC"?F@HF
+MIO!0)/5U@"'"P5R>`F'V2*+*@MU.$(R.S\[UR%U/8>6'HJ18M\65`U-.)S7!
+M=)Z-UD8L;`JUR2.$NV;S6;0M5K3!UST'P?C8S?K:E5"KJK7Q0]=V5GEU7\='
+MJPQ<7-8)F!W5J`?-C&K&>MCFN=HZ?JMN-;:'7J8G)AY46#^LW@II*K$&+6`A
+ME06]8JWKBCR.W#<DLHT?,M>QLZAG7QZ@-G"QNXW"8E_2YC?!%ZS<'R/?ON.0
+M6O4<&(+-TC)CL7_JV52XO0.QNA7$6;:YM1I"VA6`)[B0':7>!]9Z30"+-OO&
+MJPG!DC"(Y,W6QI(C^?[]'VR%I"!NL`Q.46MT6\68T$.H%'9ZC80G2CWHZ[8T
+M@5,%E<?"\/:2^3LU!OYU3[]E%O+`3BY%`F+0MO4>OX^^*^-K"D5)7%=7&4'?
+M[=81"WE7CQ^[M=.TUP=T*M@]EF$J]FHEW/=A=TJV(8I:E7$]&$I*Y2DNXT"D
+MSKZMXIF@*;].[:VK;0_F:M_?&CF8S[NPP@]](0%TX'FF;F?E'M58M]K>;?L&
+MC"?[1$J,ZY"^VAHD*0PJ#<93+<7R&#;Y_=MDZ6@_&HI.ZYV.?-?>0TUE6_2K
+MB-U>M5HV(!IL+TA[1-C802D)'X0`0-]@F#N.!RM-`_4E1(-8&_M*ERJ=`GJ]
+MI:"<\HR^A'T8-"6^0$CP]O;0'[?[RG:M>E=K?=^R!%ILI)`2+L%CMOWA()K#
+M5R;.YZQJWX?^A_6D?9YI+G3Q]J&%`8(4@<1""'JW/9_;PSD\P(H_@F=3MH`,
+MI_Y8(&7?&/2]C(`-2EGD9^MJLU6^+&AFNS*6@G;@+=,7RN9[^>#!B3TZSQ*#
+M?09[AKM$]]!%\*VK11I\=6.%9]@E>%N]KFH_76S'2YX!SM5GN<OKXALDI:PF
+M%^'AV6%:DGG'6D<T</)PRY<P1"R+R+EO<I[6D9HZT$;\ZH#AG=+W[<X,UGM0
+MC?.(>JM\*'L=D.Y;Q$L\V;2P%S4\(O>4I(Z]3$)R$AH`RRCKZ-?"CRR=H<;]
+M&7[R#).5@8V>QK3S09Q=\=SW^;GTFKTEK>$A>5WHC._K^)V0\5TC]8:"M?K6
+M&+!5[G7[N98<RKF\R@3/VV"6<BXX\SU2K;,<9X8]H(5U4K;/5IPH>J));3MV
+M:\75JMDGK?U(6[(.(JEY,&^IM]-!Z6B1%ZR75EFL\BG3PY2=V(I'SSN'[1.%
+M.`+)/*^E['M(>-,W7SP78\;I>S1S[@^KCE!=]_P(`0*5K^X^(I'@VY]*+#%?
+M/9+R;1!%DIH_UOTK(=E>D3RU#NK7^Y&RU_"ECWV[?V3?5%CUJ:]LV,FK=E9'
+M?1"X^-M^H\=;S5/7ZBM0OGB!-?>.O[Z7W+8WRE-_L_X;!/_[@K__]BI^^]T_
++?/,_T)H[0:XP````
 `
 end

Tst/Manual/letterplace_std.stat

@@ -1 @@
-1 >> tst_memory_0 :: 1548675018:4114, 64 bit:4.1.1:x86_64-Linux:nepomuck:331856
-1 >> tst_memory_1 :: 1548675018:4114, 64 bit:4.1.1:x86_64-Linux:nepomuck:2150160
-1 >> tst_memory_2 :: 1548675018:4114, 64 bit:4.1.1:x86_64-Linux:nepomuck:2191264
-1 >> tst_timer_1 :: 1548675018:4114, 64 bit:4.1.1:x86_64-Linux:nepomuck:6
+1 >> tst_memory_0 :: 1556191877:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:20013576
+1 >> tst_memory_1 :: 1556191877:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:21011760
+1 >> tst_memory_2 :: 1556191877:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:21068800
+1 >> tst_timer_1 :: 1556191877:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:22

Tst/Manual/letterplace_std.tst

@@ -1 +1 @@
 LIB "tst.lib"; tst_init();
 LIB "freegb.lib";
+
+// 1
 ring r = 0,(x,y,z),Dp;
 int degree_bound = 5;
@@ -6 +8 @@
 setring R;
 ideal I = -x*y-7*y*y+3*x*x, x*y*x-y*x*y;
-ideal J = std(I);
-J;
+std(I);
+
+kill r;
+kill R;
+
+// 2 (c_4_1_7_W)
+ring r = 0,(x4,x3,x2,x1),Dp;
+def R = freeAlgebra(r, 7);
+setring(R);
+ideal I = x4*x4-25*x4*x2-x1*x4-6*x1*x3-9*x1*x2+x1*x1,
+x4*x3+13*x4*x2+12*x4*x1-9*x3*x4+4*x3*x2+41*x3*x1-7*x1*x4-x1*x2,
+x3*x3-9*x3*x2+2*x1*x4+x1*x1,
+17*x4*x2-5*x2*x2-41*x1*x4,
+x2*x2-13*x2*x1-4*x1*x3+2*x1*x2-x1*x1,
+x2*x1+4*x1*x2-3*x1*x1;
+std(I);
+
 tst_status(1);$

libpolys/polys/shiftop.cc

@@ -13 +13 @@
  * -> wait until the new interface is released
 */
-#define SHIFT_MULT_COMPAT_MODE
+#define SHIFT_MULT_COMPAT_MODE // ncHilb.lib still relies on it
 
 #ifdef SHIFT_MULT_DEBUG
@@ -756 +756 @@
 BOOLEAN _p_LPLmDivisibleByNoComp(poly a, poly b, const ring r)
 {
-  if(p_LmIsConstantComp(a, r))
-    return TRUE;
 #ifdef SHIFT_MULT_COMPAT_MODE
   a = p_Head(a, r);
@@ -764 +762 @@
   p_mLPunshift(b, r);
 #endif
-  int i = (r->N / r->isLPring) - p_LastVblock(a, r);
-  do {
-    int j = r->N - (i * r->isLPring);
+  for (int i = (r->N / r->isLPring) - p_LastVblock(a, r); i >= 0; i--)
+  {
     bool divisible = true;
-    do
+    for (int j = r->N - (i * r->isLPring); j >= 0; j--)
     {
       if (p_GetExp(a, j, r) > p_GetExp(b, j + (i * r->isLPring), r))
@@ -775 +772 @@
         break;
       }
-      j--;
-    }
-    while (j);
+    }
     if (divisible) return TRUE;
-    i--;
-  }
-  while (i > -1);
+  }
 #ifdef SHIFT_MULT_COMPAT_MODE
   p_Delete(&a, r);