Changeset bc947c9 in git

Timestamp:

Apr 25, 2019, 7:55:05 PM (4 years ago)

Author:

Karim Abou Zeid <karim23697@…>

Branches:

(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')

Children:

7ea5de9643c52c85381a5d31f1c56130fc656ff9

Parents:

1a4a5cca1fc236a8841234e826efbd00bbc02b4c

Message:

Improve ufnarovskiGraph performance

Files:

• Singular/dyn_modules/freealgebra/freealgebra.cc (modified) (6 diffs)
• libpolys/polys/shiftop.cc (modified) (3 diffs)

Singular/dyn_modules/freealgebra/freealgebra.cc

@@ -81 +81 @@
 }
 
+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)
 {
@@ -98 +110 @@
     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;
   }
@@ -124 +128 @@
   }
   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;
 }
 
@@ -140 +199 @@
   int lV = currRing->isLPring;
 
-  ideal words = idMaxIdeal(l);
-  ideal standardWords = kNF(G, currRing->qideal, words);
-  idSkipZeroes(standardWords);
+  ideal standardWords = computeStandardWords(l, G);
 
   int n = IDELEMS(standardWords);
@@ -278 +335 @@
 
 // -1 is infinity, -2 is error
-static int id_LPGkDim(const ideal _G)
+static int gkDim(const ideal _G)
 {
   if (rField_is_Ring(currRing)) {
@@ -338 +395 @@
     ideal G = (ideal) h->Data();
     res->rtyp = INT_CMD;
-    res->data = (void*)(long) id_LPGkDim(G);
+    res->data = (void*)(long) gkDim(G);
     if (errorreported) return TRUE;
     return FALSE;

libpolys/polys/shiftop.cc

@@ -718 +718 @@
 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);
@@ -726 +724 @@
   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))
@@ -737 +734 @@
         break;
       }
-      j--;
-    }
-    while (j);
+    }
     if (divisible) return TRUE;
-    i--;
-  }
-  while (i > -1);
+  }
 #ifdef SHIFT_MULT_COMPAT_MODE
   p_Delete(&a, r);