Changeset edb60f in git for dyn_modules/callgfanlib/initialReduction.cc

Timestamp:

Dec 2, 2013, 3:29:46 PM (9 years ago)

Author:

Yue Ren <ren@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')

Children:

88c726094b0406a43f64b51105e892d707306874

Parents:

528fa78d82d2bc9d49f41d3dbb87afea0e1697e2

git-author:

Yue Ren <ren@mathematik.uni-kl.de>2013-12-02 15:29:46+01:00

git-committer:

Yue Ren <ren@mathematik.uni-kl.de>2015-02-06 13:47:02+01:00

Message:

new: reduceInitially(ideal I, const number p, poly g)

File:

• dyn_modules/callgfanlib/initialReduction.cc (modified) (4 diffs)

dyn_modules/callgfanlib/initialReduction.cc

@@ -95 +95 @@
 
 /***
- * Returns, if it exists, a pointer to the first term in g
- * that is divisible by (the leading monomial of) m or, if it does not exist, the NULL pointer
- * If g is homogeneous in x with the same degree as m,
+ * returns, if it exists, a pointer to the first term in g
+ * that is divisible by (the leading monomial of) m or, if it does not exist, the NULL pointer.
+ * if g is homogeneous in x with the same degree as m,
  * then it returns the first term with the same monomial in x as m,
  * if the t-degree of the term is higher than the t-degree of m, or NULL otherwise.
@@ -196 +196 @@
 /***
  * reduces I initially with respect to itself and with respect to p-t.
+ * also sorts the generators of I with respect to the leading monomials in descending order.
  * assumes that I is generated by elements which are homogeneous in x of the same degree.
  **/
 bool reduceInitially(ideal I, const number p)
 {
-  sortByLeadmonom(I); int i,j;
+  poly cache; int i,j,n=IDELEMS(I);
+  do
+  {
+    j=0;
+    for (i=1; i<n; i++)
+    {
+      if (pLmCmp(I->m[i-1],I->m[i])<0)
+      {
+        cache=I->m[i-1];
+        I->m[i-1]=I->m[i];
+        I->m[i]=cache;
+        j = i;
+      }
+    }
+    n=j;
+  } while(n);
   for (i=1; i<IDELEMS(I); i++)
     if (pReduce(I->m[i],p)) return true;
@@ -230 +246 @@
     if ((v != NULL) && (v->Typ() == NUMBER_CMD))
     {
-      ideal I = (ideal) u->CopyD();
-      number p = (number) v->CopyD();
+      ideal I; number p;
       omUpdateInfo();
       Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
+      I = (ideal) u->CopyD();
+      p = (number) v->CopyD();
       (void) reduceInitially(I,p);
+      id_Delete(&I,currRing);
+      n_Delete(&p,currRing->cf);
       omUpdateInfo();
       Print("usedBytesAfter=%ld\n",om_Info.UsedBytes);
+      I = (ideal) u->CopyD();
+      p = (number) v->CopyD();
+      (void) reduceInitially(I,p);
       n_Delete(&p,currRing->cf);
       res->rtyp = IDEAL_CMD;
@@ -246 +268 @@
 }
 #endif //NDEBUG
+
+
+/***
+ * inserts g into I and reduces I with respect to itself and p-t
+ * assumes that I was already sorted and initially reduced in the first place
+ **/
+bool reduceInitially(ideal I, const number p, poly g)
+{
+  pEnlargeSet(&(I->m),IDELEMS(I),1);
+  IDELEMS(I)++; int i,j,k;
+  for (j=IDELEMS(I)-1; j>0; j--)
+  {
+    if (pLmCmp(I->m[j-1],g)<0)
+      I->m[j] = I->m[j-1];
+    else
+    {
+      I->m[j] = g;
+      break;
+    }
+  }
+  if (j<1) I->m[0] = g;
+
+  /***
+   * the first pass. removing terms with the same monomials in x as lt(g_i) out of g_j for i<j
+   * removing terms with the same monomials in x as lt(g_j) out of g_k for j<k
+   **/
+  for (i=0; i<j; i++)
+    if (reduceInitially(I->m[j], I->m[i]) && pReduce(I->m[j],p)) return true;
+  for (k=j+1; k<IDELEMS(I); k++)
+    if (reduceInitially(I->m[k], I->m[j]) && pReduce(I->m[k],p)) return true;
+
+  /***
+   * the second pass. removing terms divisible by lt(g_j) and lt(g_k) out of g_i for i<j<k
+   * removing terms divisible by lt(g_k) out of g_j for j<k
+   **/
+  for (i=0; i<j; i++)
+    for (k=j; k<IDELEMS(I); k++)
+      if (reduceInitially(I->m[i], I->m[k]) && pReduce(I->m[i],p)) return true;
+  for (k=j+1; k<IDELEMS(I); k++)
+    if (reduceInitially(I->m[j],I->m[k]) && pReduce(I->m[j],p)) return true;
+
+  return false;
+}
+
+
+#ifndef NDEBUG
+BOOLEAN reduceInitially2(leftv res, leftv args)
+{
+  leftv u = args;
+  if ((u != NULL) && (u->Typ() == IDEAL_CMD))
+  {
+    leftv v = u->next;
+    if ((v != NULL) && (v->Typ() == NUMBER_CMD))
+    {
+      leftv w = v->next;
+      if ((w != NULL) && (w->Typ() == POLY_CMD))
+      {
+        ideal I; number p; poly g;
+        omUpdateInfo();
+        Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
+        I = (ideal) u->CopyD();
+        p = (number) v->CopyD();
+        g = (poly) w->CopyD();
+        (void) reduceInitially(I,p,g);
+        id_Delete(&I,currRing);
+        n_Delete(&p,currRing->cf);
+        omUpdateInfo();
+        Print("usedBytesAfter=%ld\n",om_Info.UsedBytes);
+        I = (ideal) u->CopyD();
+        p = (number) v->CopyD();
+        g = (poly) w->CopyD();
+        (void) reduceInitially(I,p,g);
+        n_Delete(&p,currRing->cf);
+        res->rtyp = IDEAL_CMD;
+        res->data = (char*) I;
+        return FALSE;
+      }
+    }
+  }
+  return TRUE;
+}
+#endif //NDEBUG