Changeset 30fb427 in git

Timestamp:

Aug 5, 1998, 1:40:58 PM (26 years ago)

Author:

Thomas Siebert <siebert@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

0e3e6f4a4d841a9a31f2a0c9f797ac572094c852

Parents:

d950c52d07929c4629546c9ad477819d8410ffb3

Message:

*** empty log message ***


git-svn-id: file:///usr/local/Singular/svn/trunk@2429 2c84dea3-7e68-4137-9b89-c4e89433aadc

File:

• Singular/syz1.cc (modified) (25 diffs)

Singular/syz1.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: syz1.cc,v 1.30 1998-06-30 14:48:20 obachman Exp $ */
+/* $Id: syz1.cc,v 1.31 1998-08-05 11:40:58 siebert Exp $ */
 /*
 * ABSTRACT: resolutions
@@ -1036 +1036 @@
 }
 
-/*3
-* reduces all pairs of degree deg in the module index
-* put the reduced generators to the resolvente which contains
-* the truncated kStd 
-*/
-static void syRedNextPairs(SSet nextPairs, syStrategy syzstr,
-               int howmuch, int index)
-{
-  int i=howmuch-1,j,k=IDELEMS(syzstr->res[index]);
-  int ks=IDELEMS(syzstr->res[index+1]),kk,l,ll;
+//#define OLD_PAIR_ORDER
+#ifdef OLD_PAIR_ORDER
+static intvec* syLinStrat(SSet nextPairs, syStrategy syzstr,
+                          int howmuch, int index)
+{
+  int i=howmuch-1,i1=0,l,ll;
   int ** Fin=syzstr->Firstelem;
   int ** Hin=syzstr->Howmuch;
   int ** bin=syzstr->backcomponents;
-  number coefgcd,n;
   ideal o_r=syzstr->orderedRes[index+1];
-  polyset redset=syzstr->orderedRes[index]->m;
-  poly p=NULL,q;
+  intvec *result=new intvec(howmuch+1);
   BOOLEAN isDivisible;
   SObject tso;
 
-  if ((nextPairs==NULL) || (howmuch==0)) return;
-  while ((k>0) && (syzstr->res[index]->m[k-1]==NULL)) k--;
-  while ((ks>0) && (syzstr->res[index+1]->m[ks-1]==NULL)) ks--;
   while (i>=0)
   {
@@ -1080 +1071 @@
       }
     }
-    if (!isDivisible)
-    {
-      tso.p = 
+    if (isDivisible)
+    {
+      syDeletePair(&nextPairs[i]);
+      //crit++;
+    }
+    else
+    {
+      nextPairs[i].p =
         sySPoly(tso.p1, tso.p2,tso.lcm);
+      (*result)[i1] = i+1;
+      i1++;
+    }
+    i--;
+  }
+  return result;
+}
+#else
+static intvec* syLinStrat(SSet nextPairs, syStrategy syzstr,
+                          int howmuch, int index)
+{
+  int i=howmuch-1,i1=0,i2,i3,l,ll;
+  int ** Fin=syzstr->Firstelem;
+  int ** Hin=syzstr->Howmuch;
+  int ** bin=syzstr->backcomponents;
+  ideal o_r=syzstr->orderedRes[index+1];
+  intvec *result=new intvec(howmuch+1);
+  intvec *spl=new intvec(howmuch,1,-1);
+  BOOLEAN isDivisible;
+  SObject tso;
+
+  while (i>=0)
+  {
+    tso = nextPairs[i];
+    isDivisible = FALSE;
+    if (syzstr->res[index+1]!=NULL)
+    {
+      l = Fin[index][pGetComp(tso.lcm)]-1;
+      if (l>=0)
+      {
+        ll = l+Hin[index][pGetComp(tso.lcm)];
+        while ((l<ll) && (!isDivisible))
+        {
+          if (o_r->m[l]!=NULL)
+          {
+            isDivisible = isDivisible || 
+              pDivisibleBy2(o_r->m[l],tso.lcm);
+          }
+          l++;
+        }
+      }
+    }
+    if (isDivisible)
+    {
+      syDeletePair(&nextPairs[i]);
+      //crit++;
+    }
+    else
+    {
+      nextPairs[i].p = 
+        sySPoly(tso.p1, tso.p2,tso.lcm);
+      (*spl)[i] = pLength(nextPairs[i].p);
+    }
+    i--;
+  }
+//Print("\n");Print("Laengenvektor: ");spl->show(1,1);Print("\n");
+  i3 = 0;
+  loop
+  {
+    i2 = -1;
+    for (i1=0;i1<howmuch;i1++)
+    {
+      if (i2==-1) 
+      {
+        if ((*spl)[i1]!=-1)
+        {
+          i2 = i1;
+        }
+      }
+      else
+      {
+        if (((*spl)[i1]>=0) && ((*spl)[i1]<(*spl)[i2]))
+        {
+          i2 = i1;
+        }
+      }
+    }
+    if (i2>=0)
+    {
+      (*result)[i3] = i2+1;
+      (*spl)[i2] = -1;
+      i3++;
+    }
+    else
+    {
+      break;
+    }
+  }
+  return result;
+}
+#endif
+/*3
+* reduces all pairs of degree deg in the module index
+* put the reduced generators to the resolvente which contains
+* the truncated kStd 
+*/
+static void syRedNextPairs(SSet nextPairs, syStrategy syzstr,
+               int howmuch, int index)
+{
+  int i,j,k=IDELEMS(syzstr->res[index]);
+  int ks=IDELEMS(syzstr->res[index+1]),kk,l,ll;
+  int ** Fin=syzstr->Firstelem;
+  int ** Hin=syzstr->Howmuch;
+  int ** bin=syzstr->backcomponents;
+  number coefgcd,n;
+  polyset redset=syzstr->orderedRes[index]->m;
+  poly p=NULL,q;
+  intvec *spl1=new intvec(howmuch+1);
+  SObject tso;
+
+  if ((nextPairs==NULL) || (howmuch==0)) return;
+  while ((k>0) && (syzstr->res[index]->m[k-1]==NULL)) k--;
+  while ((ks>0) && (syzstr->res[index+1]->m[ks-1]==NULL)) ks--;
+  spl1 = syLinStrat(nextPairs,syzstr,howmuch,index);
+//Print("\n");Print("Ordnungsvektor: ");spl1->show(1,1);Print("\n");
+  i=0;
+  while ((*spl1)[i]>0)
+  {
+    tso = nextPairs[(*spl1)[i]-1];
+    if ((tso.p1!=NULL) && (tso.p2!=NULL))
+    {
       coefgcd = 
-        nGcd(pGetCoeff(tso.p1),pGetCoeff(tso.p1));
+        nGcd(pGetCoeff(tso.p1),pGetCoeff(tso.p2));
       tso.syz = pHead(tso.lcm);
       pSetm(tso.syz);
@@ -1232 +1349 @@
       ks++;
       p = NULL;
-      nextPairs[i] = tso;
-    }
-    else
-    {
-      syDeletePair(&nextPairs[i]);
-      //crit++;
-    }
-    i--;
-  }
+      nextPairs[(*spl1)[i]-1] = tso;
+    }
+    i++;
+  }
+  delete spl1;
 } 
 
@@ -1437 +1550 @@
           {
             pDelete(&(nPm[j1]));
-            break;
+            //break;
           }
         }
@@ -1502 +1615 @@
 }
 
+/*2
+* tail reduction for the LaScala algorithm
+* takes care of the special ordering
+*/
 static void sySyzTail(syStrategy syzstr, int index, int newEl)
 {
@@ -1819 +1936 @@
 }
 
+/*3
+* deletes a resolution
+*/
 void syKillComputation(syStrategy syzstr)
 {
@@ -1935 +2055 @@
 }
 
+/*3
+* read out the Betti numbers from resolution
+* (if not LaScala calls the traditional Betti procedure)
+*/
 intvec * syBettiOfComputation(syStrategy syzstr)
 {
@@ -1986 +2110 @@
 }
 
+/*3
+* computes the allocated length of the resolution
+*/
 int syLength(syStrategy syzstr)
 {
@@ -1991 +2118 @@
 }
 
+/*3
+* computes the real length of the resolution
+*/
 int sySize(syStrategy syzstr)
 {
@@ -2008 +2138 @@
 }
 
+/*3
+* computes the cohomological dimension of res[1]
+*/
 int syDim(syStrategy syzstr)
 {
@@ -2040 +2173 @@
 }
 
+/*3
+* copies the resolution (by increment the reference counter)
+*/
 syStrategy syCopy(syStrategy syzstr)
 {
@@ -2047 +2183 @@
 }
 
+/*2
+* local print procedure used in syPrint
+*/
 static void syPrintEmptySpaces(int i)
 {
@@ -2056 +2195 @@
 }
 
+/*2
+* local print procedure used in syPrint
+*/
 static void syPrintEmptySpaces1(int i)
 {
@@ -2065 +2207 @@
 }
 
+/*2
+* local print procedure used in syPrint
+*/
 static int syLengthInt(int i)
 {
@@ -2078 +2223 @@
 }
 
+/*3
+* prints the resolution as sequence of free modules
+*/
 void syPrint(syStrategy syzstr)
 {
@@ -2169 +2317 @@
 }
 
+/*2
+* divides out the weight monomials (given by the Schreyer-ordering)
+* fronm the LaScala-resolution
+*/
 static resolvente syReorder(resolvente res,int length,
         syStrategy syzstr,BOOLEAN toCopy=TRUE,resolvente totake=NULL)
@@ -2231 +2383 @@
 }
 
+/*3
+* converts a resolution into a list of modules
+*/
 lists syConvRes(syStrategy syzstr)
 {
@@ -2269 +2424 @@
 }
 
+/*3
+* converts a list of modules into a resolution
+*/
 syStrategy syConvList(lists li)
 {
@@ -2286 +2444 @@
 }
 
+/*3
+* converts a list of modules into a minimal resolution
+*/
 syStrategy syForceMin(lists li)
 {
@@ -2302 +2463 @@
 }
 
+/*2
+* deleting all monomials the component of which correspond
+* to non-minimal generators
+*/
 static poly syStripOut(poly p,intvec * toStrip)
 {
@@ -2323 +2488 @@
 }
 
-static poly syMinimizeP(poly toMin,syStrategy syzstr,int pNum,int index,
+static poly syMinimizeP(int toMin,syStrategy syzstr,intvec * ordn,int index,
                         intvec * toStrip)
 {
-  int i,j,tc,lastin,newin=pNum-1;
-  poly p,pp=pCopy(toMin),q=NULL,tq,pisN;
+  int ii=0,i,j,tc;
+  poly p,pp,q=NULL,tq,pisN;
   SSet sPairs=syzstr->resPairs[index];
-
+  poly tempStripped=NULL;
+
+  pp=pCopy(syzstr->res[index+1]->m[toMin]);
   pp = syStripOut(pp,toStrip);
-  while (newin>=0)
-  {
-    lastin = newin;
-    while ((newin>=0) && (sPairs[lastin].order==sPairs[newin].order))
-      newin--;
-//Print("Hier lastin:%d newin:%d\n",lastin,newin);
-    for (i=newin+1;i<=lastin;i++)
-    {
-      if (sPairs[i].isNotMinimal!=NULL)
-      {
-        pisN = sPairs[i].isNotMinimal;
-        tc = pGetComp(pisN);
-        p = pp;
-        while (p!=NULL)
-        {
-          if (pGetComp(p)==tc)
-          {
-            tq = pInit();
-            for(j=pVariables; j>0; j--)
-              pSetExp(tq,j, pGetExp(p,j)-pGetExp(pisN,j));
-            pSetComp(tq, 0);
-            pSetCoeff0(tq,nDiv(pGetCoeff(p),pGetCoeff(pisN)));
-            pGetCoeff(tq) = nNeg(pGetCoeff(tq));
-            q = syAdd(q,syStripOut(syMultT1(syzstr->res[index+1]->m[sPairs[i].syzind],tq),toStrip));
-          }  
-          pIter(p);
-        }
-        if (q!=NULL)
-        {
-          pp = syAdd(pp,q);
-          q = NULL;
-        }
-      }
-    }
+  while ((ii<ordn->length()) && ((*ordn)[ii]!=-1) && (sPairs[(*ordn)[ii]].syzind!=toMin))
+  {
+    ii++;
+  }
+  while (ii>=0)
+  {
+    i = (*ordn)[ii];
+    if (sPairs[i].isNotMinimal!=NULL)
+    {
+      tempStripped = syStripOut(pCopy(syzstr->res[index+1]->m[sPairs[i].syzind]),toStrip);
+      pisN = sPairs[i].isNotMinimal;
+      tc = pGetComp(pisN);
+      p = pp;
+      while (p!=NULL)
+      {
+        if (pGetComp(p)==tc)
+        {
+          tq = pInit();
+          for(j=pVariables; j>0; j--)
+            pSetExp(tq,j, pGetExp(p,j)-pGetExp(pisN,j));
+          pSetComp(tq, 0);
+          pSetCoeff0(tq,nDiv(pGetCoeff(p),pGetCoeff(pisN)));
+          pGetCoeff(tq) = nNeg(pGetCoeff(tq));
+          q = syAdd(q,syMultT1(tempStripped,tq));
+        }  
+        pIter(p);
+      }
+      if (q!=NULL)
+      {
+        pp = syAdd(pp,q);
+        q = NULL;
+      }
+      pDelete(&tempStripped);
+    }
+    ii--;
   }
   return pp;
@@ -2435 +2603 @@
 }
 
+static intvec * syOrdPairs(SSet sPairs, int length)
+{
+  intvec * result=new intvec(length,1,-1);
+  int i,j=0,k=-1,l,ii;
+
+  loop
+  {
+    l = -1;
+    for(i=0;i<length;i++)
+    {
+      if (sPairs[i].syzind>k)
+      {
+        if (l==-1)
+        {
+          l = sPairs[i].syzind;
+          ii = i;
+        }
+        else
+        {
+          if (sPairs[i].syzind<l) 
+          {
+            l = sPairs[i].syzind;
+            ii = i;
+          }
+        }
+      }
+    }
+    if (l==-1) break;
+    (*result)[j] = ii;
+    j++;
+    k = l;
+  } 
+  return result;
+}
+
 static resolvente syReadOutMinimalRes(syStrategy syzstr, 
            BOOLEAN computeStd=FALSE)
 {
-  intvec * Strip;
+  intvec * Strip, * ordn;
   resolvente tres=(resolvente)Alloc0((syzstr->length+1)*sizeof(ideal));
   sip_sring tmpR;
@@ -2449 +2652 @@
     return tres;
   }
-  int i,j,l,index,o1,ii,i1;
+  int i,j,l,index,ii,i1;
   poly p;
   ideal rs;
@@ -2496 +2699 @@
       tres[index+1] = idInit(IDELEMS(syzstr->res[index+1]),syzstr->res[index+1]->rank);
       i1 = (*syzstr->Tl)[index];
+      ordn = syOrdPairs(sPairs,i1);
       for (i=0;i<i1;i++)
       {
         if ((sPairs[i].isNotMinimal==NULL) && (sPairs[i].lcm!=NULL))
         {
-          o1 = sPairs[i].order;
-          ii = i;
-          while ((ii<i1) && (sPairs[ii].lcm!=NULL) && (sPairs[ii].order==o1))
-            ii++;
           l = sPairs[i].syzind;
           tres[index+1]->m[l] =
-            syMinimizeP(syzstr->res[index+1]->m[l],syzstr,ii,index,Strip);
+            syMinimizeP(l,syzstr,ordn,index,Strip);
         }
       }