Changeset 3d391f4 in git

Timestamp:

Jan 30, 2020, 11:58:50 PM (4 years ago)

Author:

Karim Abou Zeid <karim23697@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

636fa5455e699fa8c0a820dd60e00a059f96f8efbbc88372fd4d9c3bc704e6afef375197fdd09810

Parents:

928d43353be8cce56dabc86bd3b35ebd48f1cdd0ed01f112cee60b9d71fdcff8400dab5c67a23882

Message:

Merge branch 'reduce_fix' into stable

Files:

• Singular/LIB/fpaprops.lib (modified) (10 diffs)
• Singular/LIB/freegb.lib (modified) (2 diffs)
• Singular/attrib.cc (modified) (3 diffs)
• Singular/dyn_modules/freealgebra/freealgebra.cc (modified) (10 diffs)
• Tst/Letterplace.lst (modified) (1 diff)
• Tst/Manual/lpGlDimBound.res.gz.uu (added)
• Tst/Manual/lpGlDimBound.stat (added)
• Tst/Manual/lpGlDimBound.tst (added)
• Tst/Manual/lpIsPrime.res.gz.uu (added)
• Tst/Manual/lpIsPrime.stat (added)
• Tst/Manual/lpIsPrime.tst (added)
• Tst/Manual/lpIsSemiPrime.res.gz.uu (added)
• Tst/Manual/lpIsSemiPrime.stat (added)
• Tst/Manual/lpIsSemiPrime.tst (added)
• Tst/Manual/lpNoetherian.res.gz.uu (added)
• Tst/Manual/lpNoetherian.stat (added)
• Tst/Manual/lpNoetherian.tst (added)
• Tst/Manual/lpUfnarovskiGraph.res.gz.uu (added)
• Tst/Manual/lpUfnarovskiGraph.stat (added)
• Tst/Manual/lpUfnarovskiGraph.tst (added)
• kernel/GBEngine/kutil.cc (modified) (1 diff)
• libpolys/polys/shiftop.cc (modified) (2 diffs)
• libpolys/polys/shiftop.h (modified) (1 diff)

Singular/LIB/fpaprops.lib

@@ -28 +28 @@
   lpGlDimBound(<GB>);     compute an upper bound for the global dimension of A/<GB>
   lpSubstitute();         substitute a variable with polynomials (ring homomorphism)
-  lpUfGraph(<GB>);        constructs the Ufnarovskij graph for <LM(GB)>
   lpCalcSubstDegBound(); utility for lpSubstitute
 ";
@@ -44 +43 @@
     example lpGlDimBound;
     example lpSubstitute;
-    example lpUfGraph;
     example lpCalcSubstDegBound;
 };
@@ -83 +81 @@
     // also if G is the whole ring
     if (leadmonom(G[i]) == 1) {
-      ERROR("noetherianity not defined for 0-ring")
+      ERROR("Noetherianity not defined for 0-ring")
     }
     kill d;
@@ -90 +88 @@
   if (l == 1) {
     int n = lpVarBlockSize(basering); // variable count
+    int ncgenCount = lpNcgenCount(basering);
     int k = size(G);
-    if (k == n) { // only the field left
+    if (k == n - ncgenCount) { // only the field left
       return(3); // every field is noetherian
     }
-    if (k == n-1) { // V = {1} with loop
+    if (k == n - ncgenCount - 1) { // V = {1} with loop
       return(3);
     }
-    if (k <= n-2) { // V = {1} with more than one loop
+    if (k <= n ncgenCount - 2) { // V = {1} with more than one loop
       return(0);
     }
   }
 
-  intmat UG = lpUfGraph(G);
+  intmat UG = lpUfnarovskiGraph(G)[1];
 
   // check special case 2
@@ -311 +310 @@
   }
 
-  list VUG = lpUfGraph(G, 1);
+  list VUG = lpUfnarovskiGraph(G);
   intmat UG = VUG[1]; // the Ufnarovskij graph
   ideal V = VUG[2]; // the vertices of UG (standard words with length = l-1)
@@ -419 +418 @@
   }
 
-  list VUG = lpUfGraph(G, 1);
+  list VUG = lpUfnarovskiGraph(G);
   intmat UG = VUG[1]; // the Ufnarovskij graph
   ideal V = VUG[2]; // the vertices of UG (standard words with length = l-1)
@@ -726 +725 @@
 }
 
-proc lpUfGraph(ideal G, list #)
-"USAGE: lpUfGraph(G); G a set of monomials in a letterplace ring.
-RETURN: intmat or list
-NOTE: lpUfGraph(G); returns intmat. lpUfGraph(G,1); returns list L with L[1] an intmat and L[2] an ideal.
-      The intmat is the Ufnarovskij Graph and the ideal contains the vertices.
-PURPOSE: Constructs the Ufnarovskij graph induced by G
-      the adjacency matrix of the Ufnarovskij graph induced by G
-ASSUME: - basering is a Letterplace ring
-      - G are the leading monomials of a Groebner basis
-"
-{
-  dbprint("computing maxDeg");
-  int l = maxDeg(G);
-  if (l - 1 == 0) {
-    // TODO: how should the graph look like when l - 1 = 0 ?
-    ERROR("Ufnarovskij graph not implemented for l = 1");
-  }
-  int lV = lpVarBlockSize(basering);
-  // TODO: what if l <= 0?
-  dbprint("computing standard words");
-  ideal SW = lpStandardWords(G, l - 1); // vertices
-  int n = ncols(SW);
-  dbprint("n = " + string(n));
-  intmat UG[n][n]; // Ufnarovskij graph
-  for (int i = 1; i <= n; i++) {
-    for (int j = 1; j <= n; j++) {
-      dbprint("Ufnarovskii graph: " + string((i-1)*n + j) + "/" + string(n*n) + " entries");
-      // [Studzinski page 76]
-      poly v = SW[i];
-      poly w = SW[j];
-      intvec v_overlap;
-      intvec w_overlap;
-      if (l - 1 > 1) {
-        v_overlap = leadexp(v);
-        w_overlap = leadexp(w);
-        v_overlap = v_overlap[(lV+1) .. (l-1)*lV];
-        w_overlap = w_overlap[1 .. (l-2)*lV];
-      }
-      if (v_overlap == w_overlap && !lpLmDivides(G, v * lpVarAt(w, l - 1))) {
-        UG[i,j] = 1;
-      }
-      kill v; kill w; kill v_overlap; kill w_overlap;
-    } kill j;
-  } kill i;
-  if (size(#) > 0) {
-    if (typeof(#[1]) == "int") {
-      if (#[1] != 0) {
-        list ret = UG;
-        ret[2] = SW; // the vertices
-        return (ret);
-      }
-    }
-  }
-  return (UG);
-}
-example
-{
-  "EXAMPLE:"; echo = 2;
-  ring r = 0,(x,y,z),dp;
-  def R = freeAlgebra(r, 5); // constructs a Letterplace ring
-  setring R; // sets basering to Letterplace ring
-  ideal I = x*y, x*z, z*y, z*z;
-  lpUfGraph(I);
-  lpUfGraph(I,1);
-}
+// Ufnarovskii graph is now implemented in the dynamic module (freeAlgebra.cc)
+/* proc lpUfnarovskiGraph(ideal G, list #) */
+/* "USAGE: lpUfnarovskiGraph(G); G a set of monomials in a letterplace ring. */
+/* RETURN: intmat or list */
+/* NOTE: lpUfnarovskiGraph(G); returns intmat. lpUfnarovskiGraph(G,1); returns list L with L[1] an intmat and L[2] an ideal. */
+/*       The intmat is the Ufnarovskij Graph and the ideal contains the vertices. */
+/* PURPOSE: Constructs the Ufnarovskij graph induced by G */
+/*       the adjacency matrix of the Ufnarovskij graph induced by G */
+/* ASSUME: - basering is a Letterplace ring */
+/*       - G are the leading monomials of a Groebner basis */
+/* " */
+/* { */
+/*   dbprint("computing maxDeg"); */
+/*   int l = maxDeg(G); */
+/*   if (l - 1 == 0) { */
+/*     // TODO: how should the graph look like when l - 1 = 0 ? */
+/*     ERROR("Ufnarovskij graph not implemented for l = 1"); */
+/*   } */
+/*   int lV = lpVarBlockSize(basering); */
+/*   // TODO: what if l <= 0? */
+/*   dbprint("computing standard words"); */
+/*   ideal SW = lpStandardWords(G, l - 1); // vertices */
+/*   int n = ncols(SW); */
+/*   dbprint("n = " + string(n)); */
+/*   intmat UG[n][n]; // Ufnarovskij graph */
+/*   for (int i = 1; i <= n; i++) { */
+/*     for (int j = 1; j <= n; j++) { */
+/*       dbprint("Ufnarovskii graph: " + string((i-1)*n + j) + "/" + string(n*n) + " entries"); */
+/*       // [Studzinski page 76] */
+/*       poly v = SW[i]; */
+/*       poly w = SW[j]; */
+/*       intvec v_overlap; */
+/*       intvec w_overlap; */
+/*       if (l - 1 > 1) { */
+/*         v_overlap = leadexp(v); */
+/*         w_overlap = leadexp(w); */
+/*         v_overlap = v_overlap[(lV+1) .. (l-1)*lV]; */
+/*         w_overlap = w_overlap[1 .. (l-2)*lV]; */
+/*       } */
+/*       if (v_overlap == w_overlap && !lpLmDivides(G, v * lpVarAt(w, l - 1))) { */
+/*         UG[i,j] = 1; */
+/*       } */
+/*       kill v; kill w; kill v_overlap; kill w_overlap; */
+/*     } kill j; */
+/*   } kill i; */
+/*   if (size(#) > 0) { */
+/*     if (typeof(#[1]) == "int") { */
+/*       if (#[1] != 0) { */
+/*         list ret = UG; */
+/*         ret[2] = SW; // the vertices */
+/*         return (ret); */
+/*       } */
+/*     } */
+/*   } */
+/*   return (UG); */
+/* } */
+/* example */
+/* { */
+/*   "EXAMPLE:"; echo = 2; */
+/*   ring r = 0,(x,y,z),dp; */
+/*   def R = freeAlgebra(r, 5); // constructs a Letterplace ring */
+/*   setring R; // sets basering to Letterplace ring */
+/*   ideal I = x*y, x*z, z*y, z*z; */
+/*   lpUfnarovskiGraph(I); */
+/*   lpUfnarovskiGraph(I,1); */
+/* } */
 
 static proc maxDeg(ideal G)
@@ -833 +833 @@
     return (words); // no standard words
   }
-  int lV = lpVarBlockSize(basering); // variable count
+  int nVars = lpVarBlockSize(basering) - lpNcgenCount(basering); // variable count
   list prevWords = ivStandardWords(G, length - 1);
   list words;
-  for (int i = 1; i <= lV; i++) {
+  for (int i = 1; i <= nVars; i++) {
     for (int j = 1; j <= size(prevWords); j++) {
       intvec word = prevWords[j];
@@ -919 +919 @@
 
 /*   dbprint("computing Ufnarovskii graph"); */
-/*   intmat UG = lpUfGraph(G); */
+/*   intmat UG = lpUfnarovskiGraph(G)[1]; */
 /*   if (printlevel >= voice + 1) { */
 /*     UG; */
@@ -1002 +1002 @@
   if (size(G1) > 0) {
     while (size(G1) > 0) {
-      if (lpVarBlockSize(R) > 1) {
+      if (lpVarBlockSize(R) - lpNcgenCount(R) > 1) {
         def @R = R - string(G1[1]);
         R = @R;

Singular/LIB/freegb.lib

@@ -26 +26 @@
 lpDegBound(R);                   returns the degree bound of a letterplace ring
 lpVarBlockSize(R);               returns the size of the letterplace blocks
+lpNcgenCount(R);                 returns the number of ncgen variables
 lpDivision(f,I);                 two-sided division with remainder
 lpGBPres2Poly(L,I);              reconstructs a polynomial from the output of lpDivision
@@ -1004 +1005 @@
   def R = freeAlgebra(r, 7);
   isFreeAlgebra(R);
+}
+
+proc lpNcgenCount(def R)
+"USAGE:  lpNcgenCount(R); R a letterplace ring
+RETURN:  int
+PURPOSE: returns the number of ncgen variables in the letterplace ring.
+EXAMPLE: example ncgenCount; shows examples
+"
+{
+  return(attrib(R, "ncgenCount"));
+}
+example
+{
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x,y,z),dp;
+  def R = freeAlgebra(r, 7, 10);
+  lpNcgenCount(R); // should be 10
 }
 

Singular/attrib.cc

@@ -259 +259 @@
       #ifdef HAVE_SHIFTBBA
       PrintS("attr:isLetterplaceRing, type int\n");
+      PrintS("attr:ncgenCount, type int\n");
       #endif
 
@@ -331 +332 @@
     res->data=(void *)(long)(((ring)v->Data())->isLPring);
   }
+  else if ((strcmp(name,"ncgenCount")==0)
+  &&(/*v->Typ()*/t==RING_CMD))
+  {
+    res->rtyp=INT_CMD;
+    res->data=(void *)(long)(((ring)v->Data())->LPncGenCount);
+  }
 #endif
   else
@@ -436 +443 @@
     }
   }
+  else if ((strcmp(name,"ncgenCount")==0)
+  &&(/*v->Typ()*/t==RING_CMD))
+  {
+    if (c->Typ()==INT_CMD)
+      ((ring)v->Data())->LPncGenCount=(int)(long)c->Data();
+    else
+    {
+      WerrorS("attribute `ncgenCount` must be int");
+      return TRUE;
+    }
+  }
 #endif
   else

Singular/dyn_modules/freealgebra/freealgebra.cc

@@ -136 +136 @@
 static void _computeStandardWords(ideal words, int n, ideal M, int& last)
 {
+  // assume <M> != <1>
   if (n <= 0){
     words->m[0] = pOne();
@@ -144 +145 @@
   _computeStandardWords(words, n - 1, M, last);
 
-  int nVars = currRing->isLPring;
+  int nVars = currRing->isLPring - currRing->LPncGenCount;
 
   for (int j = nVars - 1; j >= 0; j--)
@@ -158 +159 @@
         }
 
-        int varOffset = ((n - 1) * nVars) + 1;
+        int varOffset = ((n - 1) * currRing->isLPring) + 1;
         pSetExp(words->m[index], varOffset + j, 1);
         pSetm(words->m[index]);
@@ -177 +178 @@
 static ideal computeStandardWords(int n, ideal M)
 {
-  int nVars = currRing->isLPring;
+  int nVars = currRing->isLPring - currRing->LPncGenCount;
 
   int maxElems = 1;
@@ -190 +191 @@
 
 // NULL if graph is undefined
-static intvec* ufnarovskiGraph(ideal G)
+static intvec* ufnarovskiGraph(ideal G, ideal &standardWords)
 {
   long l = 0;
@@ -203 +204 @@
   int lV = currRing->isLPring;
 
-  ideal standardWords = computeStandardWords(l, G);
+  standardWords = computeStandardWords(l, G);
 
   int n = IDELEMS(standardWords);
@@ -250 +251 @@
 }
 
+static BOOLEAN lpUfnarovskiGraph(leftv res, leftv h)
+{
+  const short t[]={1,IDEAL_CMD};
+  if (iiCheckTypes(h,t,1))
+  {
+    ideal I = (ideal) h->Data();
+    res->rtyp = LIST_CMD;
+
+    ideal standardWords;
+    intvec* graph = ufnarovskiGraph(I, standardWords);
+
+    lists li=(lists)omAllocBin(slists_bin);
+    li->Init(2);
+    li->m[0].rtyp=INTMAT_CMD;
+    li->m[1].rtyp=IDEAL_CMD;
+    li->m[0].data=graph;
+    li->m[1].data=standardWords;
+
+    res->data = li;
+
+    if (errorreported) return TRUE;
+    return FALSE;
+  }
+  else return TRUE;
+}
+
 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)
 {
@@ -353 +380 @@
       return -2;
     }
+    if (pGetNCGen(_G->m[i]) != 0)
+    {
+      WerrorS("GK-Dim not implemented for bi-modules");
+      return -2;
+    }
   }
 
@@ -377 +409 @@
   {
     int lV = currRing->isLPring;
-    if (IDELEMS(G) == lV) // V = {1} no edges
+    int ncGenCount = currRing->LPncGenCount;
+    if (IDELEMS(G) == lV - ncGenCount) // V = {1} no edges
       return 0;
-    if (IDELEMS(G) == lV - 1) // V = {1} with loop
+    if (IDELEMS(G) == lV - ncGenCount - 1) // V = {1} with loop
       return 1;
-    if (IDELEMS(G) <= lV - 2) // V = {1} with more than one loop
+    if (IDELEMS(G) <= lV - ncGenCount - 2) // V = {1} with more than one loop
       return -1;
   }
 
-  intvec* UG = ufnarovskiGraph(G);
+  ideal standardWords;
+  intvec* UG = ufnarovskiGraph(G, standardWords);
   if (errorreported || UG == NULL) return -2;
   return graphGrowth(UG);
@@ -416 +450 @@
   p->iiAddCproc("freealgebra.so","lpVarAt",FALSE,lpVarAt);
   p->iiAddCproc("freealgebra.so","lpGkDim",FALSE,lpGkDim);
+  p->iiAddCproc("freealgebra.so","lpUfnarovskiGraph",FALSE,lpUfnarovskiGraph);
 
   p->iiAddCproc("freealgebra.so","stest",TRUE,stest);

Tst/Letterplace.lst

@@ -11 +11 @@
 
 Manual/lpGkDim.tst
+Manual/lpNoetherian.tst
+Manual/lpIsPrime.tst
+Manual/lpIsSemiPrime.tst
+Manual/lpGlDimBound.tst
 Manual/lpKDim.tst
 Manual/lpKDimCheck.tst
+Manual/lpUfnarovskiGraph.tst
 Manual/lpMonomialBasis.tst
 Manual/lpSickleDim.tst

kernel/GBEngine/kutil.cc

@@ -9374 +9374 @@
 void enterSBbaShift (LObject &p,int atS,kStrategy strat, int atR)
 {
+  enterSBba(p, atS, strat, atR);
+
   int maxPossibleShift = p_mLPmaxPossibleShift(p.p, strat->tailRing);
   for (int i = maxPossibleShift; i > 0; i--)
   {
+
     LObject qq;
     qq.p = pLPCopyAndShiftLM(p.p, i); // don't use Set() because it'll test the poly order
     qq.shift = i;
     strat->initEcart(&qq); // initEcartBBA sets length, pLength, FDeg and ecart
+    int atS = posInS(strat, strat->sl, qq.p, qq.ecart); // S needs to stay sorted because this is for example assumed when searching S later
     enterSBba(qq, atS, strat, -1);
   }
-  enterSBba(p, atS, strat, atR);
 }
 #endif

libpolys/polys/shiftop.cc

@@ -613 +613 @@
 }
 
+BOOLEAN _p_mLPNCGenValid(poly p, const ring r)
+{
+  if (p == NULL) return TRUE;
+  int *e=(int *)omAlloc((r->N+1)*sizeof(int));
+  p_GetExpV(p,e,r);
+  int b = _p_mLPNCGenValid(e, r);
+  omFreeSize((ADDRESS) e, (r->N+1)*sizeof(int));
+  return b;
+}
+
 BOOLEAN _p_mLPNCGenValid(int *mExpV, const ring r)
 {
@@ -634 +644 @@
   }
   return TRUE;
+}
+
+int p_GetNCGen(poly p, const ring r)
+{
+  if (p == NULL) return 0;
+  assume(_p_mLPNCGenValid(p, r));
+
+  int lV = r->isLPring;
+  int degbound = r->N/lV;
+  int ncGenCount = r->LPncGenCount;
+  for (int i = 1; i <= degbound; i++)
+  {
+    for (int j = i*lV; j > (i*lV - ncGenCount); j--)
+    {
+      if (p_GetExp(p, j, r))
+      {
+        return j - i*lV + ncGenCount;
+      }
+    }
+  }
+  return 0;
 }
 

libpolys/polys/shiftop.h

@@ -55 +55 @@
 BOOLEAN _p_LPLmDivisibleByNoComp(poly a, poly b, const ring r);
 
+BOOLEAN _p_mLPNCGenValid(poly p, const ring r);
 BOOLEAN _p_mLPNCGenValid(int *mExpV, const ring r);
 
 poly p_LPVarAt(poly p, int pos, const ring r);
+
+#define pGetNCGen(p) p_GetNCGen(p, currRing)
+int p_GetNCGen(poly p, const ring r);
 
 #define pLPSubst(p, n, e) p_LPSubst(p, n, e, r)