Changeset 08b7c2a in git

Timestamp:

Feb 4, 2015, 11:29:46 PM (9 years ago)

Author:

Yue Ren <ren@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

7cb46755d168b8a6622fc01364fe4ca055f20f4b

Parents:

7723d00a58aba67b90f5f607a5018d386f4f8465

git-author:

Yue Ren <ren@mathematik.uni-kl.de>2015-02-04 23:29:46+01:00

git-committer:

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

Message:

chg: removed redundant witness computations

Location:

Singular/dyn_modules/gfanlib

Files:

• groebnerCone.cc (modified) (1 diff)
• tropicalCurves.cc (modified) (4 diffs)
• tropicalStrategy.cc (modified) (2 diffs)
• tropicalStrategy.h (modified) (1 diff)
• tropicalTraversal.cc (modified) (6 diffs)

Singular/dyn_modules/gfanlib/groebnerCone.cc

@@ -408 +408 @@
     if (currentStrategy->restrictToLowerHalfSpace() && R[i][0].sign()==0)
       continue;
-    poly s = currentStrategy->checkInitialIdealForMonomial(I,r,R[i]);
-    if (s==NULL)
-    {
-      p_Delete(&s,r);
+    std::pair<poly,int> s = currentStrategy->checkInitialIdealForMonomial(I,r,R[i]);
+    if (s.first==NULL)
+    {
+      if (s.second<0)
+        // if monomial was initialized, delete it
+        p_Delete(&s.first,r);
       return R[i];
     }

Singular/dyn_modules/gfanlib/tropicalCurves.cc

@@ -147 +147 @@
 
     ideal inIsSTD = gfanlib_kStd_wrapper(inIs,s,isHomog);
+    id_Delete(&inIs,s);
     ideal ininIs = initial(inIsSTD,s,w,W);
 
-    poly mons = currentStrategy->checkInitialIdealForMonomial(ininIs,s,w);
-    if (mons!=NULL)
+    std::pair<poly,int> mons = currentStrategy->checkInitialIdealForMonomial(ininIs,s);
+
+    if (mons.first!=NULL)
     {
       poly gs;
-      if (pNext(mons)==NULL)
-        gs = witness(mons,inIsSTD,ininIs,s);
+      if (mons.second>=0)
+        // cheap way out, ininIsSTD already contains a monomial in its generators
+        gs = inIsSTD->m[mons.second];
       else
-        gs = p_Copy(mons,s);
+        // compute witness
+        gs = witness(mons.first,inIsSTD,ininIs,s);
+
       C = intersect(C,tropicalVarietySortedByDimension(gs,s,currentStrategy),d);
       nMapFunc mMap = n_SetMap(s->cf,r->cf);
@@ -162 +167 @@
       idInsertPoly(inI,gr);
       k++;
-      p_Delete(&mons,s);
-      p_Delete(&gs,s);
-      zc = C.begin();
-      // gfan::ZFan* zf = toFanStar(C);
-      // std::cout << zf->toString(2+4+8+128) << std::endl;
-      // delete zf;
-      id_Delete(&inIs,s);
+
+      if (mons.second<0)
+      {
+        // if necessary, cleanup mons and gs
+        p_Delete(&mons.first,s);
+        p_Delete(&gs,s);
+      }
+      // cleanup rest, reset zc
       id_Delete(&inIsSTD,s);
       id_Delete(&ininIs,s);
       rDelete(s);
+      zc = C.begin();
     }
     else
     {
-      id_Delete(&inIs,s);
+      // cleanup remaining data of first stage
       id_Delete(&inIsSTD,s);
       id_Delete(&ininIs,s);
@@ -190 +197 @@
 
         inIsSTD = gfanlib_kStd_wrapper(inIs,s,isHomog);
+        id_Delete(&inIs,s);
         ininIs = initial(inIsSTD,s,wNeg,W);
 
-        mons = currentStrategy->checkInitialIdealForMonomial(ininIs,s,wNeg);
-        if (mons!=NULL)
+        mons = currentStrategy->checkInitialIdealForMonomial(ininIs,s);
+        if (mons.first!=NULL)
         {
           poly gs;
-          if (pNext(mons)==NULL)
-            gs = witness(mons,inIsSTD,ininIs,s);
+          if (mons.second>=0)
+            // cheap way out, ininIsSTD already contains a monomial in its generators
+            gs = inIsSTD->m[mons.second];
           else
-            gs = p_Copy(mons,s);
+            // compute witness
+            gs = witness(mons.first,inIsSTD,ininIs,s);
+
           C = intersect(C,tropicalVarietySortedByDimension(gs,s,currentStrategy),d);
           nMapFunc mMap = n_SetMap(s->cf,r->cf);
@@ -205 +216 @@
           idInsertPoly(inI,gr);
           k++;
-          p_Delete(&mons,s);
-          p_Delete(&gs,s);
+
+          if (mons.second<0)
+          {
+            // if necessary, cleanup mons and gs
+            p_Delete(&mons.first,s);
+            p_Delete(&gs,s);
+          }
+          // reset zc
           zc = C.begin();
-          // gfan::ZFan* zf = toFanStar(C);
-          // std::cout << zf->toString();
-          // delete zf;
         }
         else
           zc++;
-        id_Delete(&inIs,s);
+        // cleanup remaining data of second stage
         id_Delete(&inIsSTD,s);
         id_Delete(&ininIs,s);

Singular/dyn_modules/gfanlib/tropicalStrategy.cc

@@ -456 +456 @@
 }
 
-poly tropicalStrategy::checkInitialIdealForMonomial(const ideal I, const ring r, const gfan::ZVector w) const
-{
+std::pair<poly,int> tropicalStrategy::checkInitialIdealForMonomial(const ideal I, const ring r, const gfan::ZVector &w) const
+{
+  // quick check whether I already contains an ideal
   int k = idSize(I);
   for (int i=0; i<k; i++)
@@ -463 +464 @@
     poly g = I->m[i];
     if (pNext(g)==NULL && (isValuationTrivial() || n_IsOne(p_GetCoeff(g,r),r->cf)))
-    {
-      poly monomial = p_Copy(g,r);
-      return monomial;
-    }
-  }
-  // prepend extra weight for homogeneity
-  // switch to residue field if valuation is non trivial
-  ring rShortcut = getShortcutRingPrependingWeight(r,w);
-
-  // compute the initial ideal and map it into the constructed ring
-  // if switched to residue field, remove possibly 0 elements
-  ideal inI = initial(I,r,w);
-  ideal inIShortcut = idInit(k);
-  nMapFunc intoShortcut = n_SetMap(r->cf,rShortcut->cf);
-  for (int i=0; i<k; i++)
-    inIShortcut->m[i] = p_PermPoly(inI->m[i],NULL,r,rShortcut,intoShortcut,NULL,0);
-  if (isValuationNonTrivial())
-    idSkipZeroes(inIShortcut);
+      return std::pair<poly,int>(g,i);
+  }
+
+  ring rShortcut;
+  ideal inIShortcut;
+  if (w.size()>0)
+  {
+    // if needed, prepend extra weight for homogeneity
+    // switch to residue field if valuation is non trivial
+    rShortcut = getShortcutRingPrependingWeight(r,w);
+
+    // compute the initial ideal and map it into the constructed ring
+    // if switched to residue field, remove possibly 0 elements
+    ideal inI = initial(I,r,w);
+    inIShortcut = idInit(k);
+    nMapFunc intoShortcut = n_SetMap(r->cf,rShortcut->cf);
+    for (int i=0; i<k; i++)
+      inIShortcut->m[i] = p_PermPoly(inI->m[i],NULL,r,rShortcut,intoShortcut,NULL,0);
+    if (isValuationNonTrivial())
+      idSkipZeroes(inIShortcut);
+    id_Delete(&inI,r);
+  }
+  else
+  {
+    rShortcut = r;
+    inIShortcut = I;
+  }
 
   // check initial ideal for monomial and
   // if it exsists, return a copy of the monomial in the input ring
   poly p = checkForMonomialViaSuddenSaturation(inIShortcut,rShortcut);
-  poly monomial = NULL; int n = rVar(r);
+  poly monomial = NULL;
   if (p!=NULL)
   {
     monomial=p_One(r);
-    for (int i=1; i<=n; i++)
+    for (int i=1; i<=rVar(r); i++)
       p_SetExp(monomial,i,p_GetExp(p,i,rShortcut),r);
     p_Delete(&p,rShortcut);
   }
-  id_Delete(&inI,r);
-  id_Delete(&inIShortcut,rShortcut);
-  rDelete(rShortcut);
-  return monomial;
+
+
+  if (w.size()>0)
+  {
+    // if needed, cleanup
+    id_Delete(&inIShortcut,rShortcut);
+    rDelete(rShortcut);
+  }
+  return std::pair<poly,int>(monomial,-1);
 }
 

Singular/dyn_modules/gfanlib/tropicalStrategy.h

@@ -306 +306 @@
    * In both cases returns a monomial, if it contains one, returns NULL otherwise.
    **/
-  poly checkInitialIdealForMonomial(const ideal I, const ring r, const gfan::ZVector w=0) const;
+  std::pair<poly,int> checkInitialIdealForMonomial(const ideal I, const ring r, const gfan::ZVector &w=0) const;
 
   /**

Singular/dyn_modules/gfanlib/tropicalTraversal.cc

@@ -48 +48 @@
   workingList.insert(startingCone);
   const tropicalStrategy* currentStrategy=startingCone.getTropicalStrategy();
-  // std::cout << "starting traversal" << std::endl;
   while(!workingList.empty())
   {
@@ -54 +53 @@
      * Pick an element the working list and compute interior points on its facets
      */
-    // std::cout << "picking cone and computing interior facet points..." << std::endl;
     groebnerCone sigma=*(workingList.begin());
     gfan::ZMatrix interiorPoints = interiorPointsOfFacets(sigma.getPolyhedralCone());
@@ -67 +65 @@
       {
         ideal inI = initial(sigma.getPolynomialIdeal(),sigma.getPolynomialRing(),interiorPoint);
-        // std::cout << "picking interiorPoint and computing rays of tropical star..." << std::endl;
         gfan::ZMatrix normalVectors = raysOfTropicalStar(inI,
                                                          sigma.getPolynomialRing(),
@@ -74 +71 @@
         id_Delete(&inI,sigma.getPolynomialRing());
 
-        // std::cout << "checking for th neccessity to flip..." << std::endl;
         std::vector<bool> needToFlip = checkNecessaryFlips(tropicalVariety,workingList,interiorPoint,normalVectors);
         for (int j=0; j<normalVectors.getHeight(); j++)
@@ -80 +76 @@
           if (needToFlip[j])
           {
-            // std::cout << "flipping cone..." << std::endl;
             groebnerCone neighbour = sigma.flipCone(interiorPoint,normalVectors[j]);
             workingList.insert(neighbour);
@@ -114 +109 @@
     tropicalVariety.insert(sigma);
     workingList.erase(sigma);
-    // std::cout << "tropicalVariety.size():" << tropicalVariety.size() << std::endl;
-    // std::cout << "workingList.size():" << workingList.size() << std::endl;
+    std::cout << "tropicalVariety.size():" << tropicalVariety.size() << std::endl;
+    std::cout << "workingList.size():" << workingList.size() << std::endl;
   }
   return tropicalVariety;