Changeset 7f5789 in git for Singular

Timestamp:

Jan 18, 2020, 10:59:58 PM (4 years ago)

Author:

Karim Abou Zeid <karim23697@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

c417af59af93bdad5278db69f84585a318ee2ba5

Parents:

da6d43a81ee1ba91b8ecae7bb3a89f608e66b354

git-author:

Karim Abou Zeid <karim23697@gmail.com>2020-01-18 22:59:58+01:00

git-committer:

Karim Abou Zeid <karim23697@gmail.com>2020-01-18 23:05:58+01:00

Message:

Fix fpaprops for ncgen and add tests

Location:

Singular

Files:

• LIB/fpaprops.lib (modified) (9 diffs)
• LIB/freegb.lib (modified) (2 diffs)
• attrib.cc (modified) (3 diffs)
• dyn_modules/freealgebra/freealgebra.cc (modified) (5 diffs)

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;
 };
@@ -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 = lpUfGraph(G)[1];
 
   // check special case 2
@@ -311 +310 @@
   }
 
-  list VUG = lpUfGraph(G, 1);
+  list VUG = lpUfGraph(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 = lpUfGraph(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 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); */
+/* } */
 
 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 = lpUfGraph(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

@@ -191 +191 @@
 
 // NULL if graph is undefined
-static intvec* ufnarovskiGraph(ideal G)
+static intvec* ufnarovskiGraph(ideal G, ideal &standardWords)
 {
   long l = 0;
@@ -204 +204 @@
   int lV = currRing->isLPring;
 
-  ideal standardWords = computeStandardWords(l, G);
+  standardWords = computeStandardWords(l, G);
 
   int n = IDELEMS(standardWords);
@@ -251 +251 @@
 }
 
+static BOOLEAN lpUfGraph(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)
 {
@@ -392 +418 @@
   }
 
-  intvec* UG = ufnarovskiGraph(G);
+  ideal standardWords;
+  intvec* UG = ufnarovskiGraph(G, standardWords);
   if (errorreported || UG == NULL) return -2;
   return graphGrowth(UG);
@@ -423 +450 @@
   p->iiAddCproc("freealgebra.so","lpVarAt",FALSE,lpVarAt);
   p->iiAddCproc("freealgebra.so","lpGkDim",FALSE,lpGkDim);
+  p->iiAddCproc("freealgebra.so","lpUfGraph",FALSE,lpUfGraph);
 
   p->iiAddCproc("freealgebra.so","stest",TRUE,stest);