Changeset 44d34b6 in git

Timestamp:

Feb 1, 2015, 10:01:06 PM (9 years ago)

Author:

Yue Ren <ren@…>

Branches:

(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')

Children:

f16226e1d8662eca29be06420a230cd92d756ff3

Parents:

670e639535c5bd70580255e59bdb06627c71b9f1

git-author:

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

git-committer:

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

Message:

chg: possible speedup?

Location:

Singular/dyn_modules/gfanlib

Files:

• tropicalCurves.cc (modified) (11 diffs)
• tropicalCurves.h (modified) (1 diff)
• tropicalVarietyOfPolynomials.cc (modified) (2 diffs)
• tropicalVarietyOfPolynomials.h (modified) (1 diff)

Singular/dyn_modules/gfanlib/tropicalCurves.cc

@@ -10 +10 @@
 #include <tropicalStrategy.h>
 #include <tropicalVarietyOfPolynomials.h>
+#include <tropicalCurves.h>
 #include <set>
 #ifndef NDEBUG
@@ -20 +21 @@
  * and throws away those of lower dimension than d.
  **/
-static std::set<gfan::ZCone> intersect(const std::set<gfan::ZCone> setA,
-                                       const std::set<gfan::ZCone> setB,
-                                       int d=0)
+static ZConesSortedByDimension intersect(const ZConesSortedByDimension &setA,
+                                         const ZConesSortedByDimension &setB,
+                                         int d=0)
 {
   if (setA.empty())
@@ -28 +29 @@
   if (setB.empty())
     return setA;
-  std::set<gfan::ZCone> setAB;
-  for (std::set<gfan::ZCone>::iterator coneOfA=setA.begin(); coneOfA!=setA.end(); coneOfA++)
-  {
-    for (std::set<gfan::ZCone>::iterator coneOfB=setB.begin(); coneOfB!=setB.end(); coneOfB++)
+  ZConesSortedByDimension setAB;
+  for (ZConesSortedByDimension::iterator coneOfA=setA.begin(); coneOfA!=setA.end(); coneOfA++)
+  {
+    for (ZConesSortedByDimension::iterator coneOfB=setB.begin(); coneOfB!=setB.end(); coneOfB++)
     {
       gfan::ZCone coneOfIntersection = gfan::intersection(*coneOfA,*coneOfB);
@@ -111 +112 @@
  * the initial ideal inI with respect to it, computes the star of the tropical variety in u.
  **/
-std::set<gfan::ZCone> tropicalStar(ideal &inI, const ring &r, const gfan::ZVector &u,
-                                   const tropicalStrategy* currentStrategy)
+ZConesSortedByDimension tropicalStar(ideal inI, const ring r, const gfan::ZVector &u,
+                                     const tropicalStrategy* currentStrategy)
 {
   int k = idSize(inI);
@@ -119 +120 @@
   /* Compute the common refinement over all tropical varieties
    * of the polynomials in the generating set */
-  std::set<gfan::ZCone> C = tropicalVariety(inI->m[0],r,currentStrategy);
+  ZConesSortedByDimension C = tropicalVarietySortedByDimension(inI->m[0],r,currentStrategy);
   for (int i=1; i<k; i++)
-    C = intersect(C,tropicalVariety(inI->m[i],r,currentStrategy),d);
+    C = intersect(C,tropicalVarietySortedByDimension(inI->m[i],r,currentStrategy),d);
 
   /* Cycle through all maximal cones of the refinement.
@@ -153 +154 @@
       // std::cout << "computing witness in tropical star!" << std::endl;
       poly gs = witness(mons,inIsSTD,ininIs,s);
-      C = intersect(C,tropicalVariety(gs,s,currentStrategy),d);
+      C = intersect(C,tropicalVarietySortedByDimension(gs,s,currentStrategy),d);
       nMapFunc mMap = n_SetMap(s->cf,r->cf);
       poly gr = p_PermPoly(gs,NULL,s,r,mMap,NULL,0);
@@ -192 +193 @@
         {
           poly gs = witness(mons,inIsSTD,ininIs,s);
-          C = intersect(C,tropicalVariety(gs,s,currentStrategy),d);
+          C = intersect(C,tropicalVarietySortedByDimension(gs,s,currentStrategy),d);
           nMapFunc mMap = n_SetMap(s->cf,r->cf);
           poly gr = p_PermPoly(gs,NULL,s,r,mMap,NULL,0);
@@ -219 +220 @@
 
 
-gfan::ZMatrix raysOfTropicalStar(ideal I, const ring r, const gfan::ZVector u, const tropicalStrategy* currentStrategy)
-{
-  std::set<gfan::ZCone> C = tropicalStar(I,r,u,currentStrategy);
+gfan::ZMatrix raysOfTropicalStar(ideal I, const ring r, const gfan::ZVector &u, const tropicalStrategy* currentStrategy)
+{
+  ZConesSortedByDimension C = tropicalStar(I,r,u,currentStrategy);
   // gfan::ZFan* zf = toFanStar(C);
   // std::cout << zf->toString();
@@ -228 +229 @@
   if (!currentStrategy->restrictToLowerHalfSpace())
   {
-    for (std::set<gfan::ZCone>::iterator zc=C.begin(); zc!=C.end(); zc++)
+    for (ZConesSortedByDimension::iterator zc=C.begin(); zc!=C.end(); zc++)
     {
       assume(zc->dimensionOfLinealitySpace()+1 == zc->dimension());
@@ -237 +238 @@
   else
   {
-    for (std::set<gfan::ZCone>::iterator zc=C.begin(); zc!=C.end(); zc++)
+    for (ZConesSortedByDimension::iterator zc=C.begin(); zc!=C.end(); zc++)
     {
       assume(zc->dimensionOfLinealitySpace()+2 == zc->dimension());
@@ -266 +267 @@
       tropicalStrategy currentCase(inI,currRing);
       gfan::ZVector* v = bigintmatToZVector(u);
-      std::set<gfan::ZCone> C = tropicalStar(inI,currRing,*v,&currentCase);
+      ZConesSortedByDimension C = tropicalStar(inI,currRing,*v,&currentCase);
       id_Delete(&inI,currRing);
       delete u;
       delete v;
-      res->rtyp = fanID;
-      res->data = (char*) toFanStar(C);
+      res->rtyp = NONE;
+      res->data = NULL;
+      // res->rtyp = fanID;
+      // res->data = (char*) toFanStar(C);
       return FALSE;
     }

Singular/dyn_modules/gfanlib/tropicalCurves.h

@@ -6 +6 @@
 #include <libpolys/polys/monomials/p_polys.h>
 #include <tropicalStrategy.h>
+#include <tropicalVarietyOfPolynomials.h>
 
-std::set<gfan::ZCone> tropicalStar(const ideal I, const ring r, const gfan::ZVector u,
-                                   const tropicalStrategy* currentStrategy);
-gfan::ZMatrix raysOfTropicalStar(ideal I, const ring r, const gfan::ZVector u,
+ZConesSortedByDimension tropicalStar(const ideal I, const ring r, const gfan::ZVector &u,
+                                     const tropicalStrategy* currentStrategy);
+gfan::ZMatrix raysOfTropicalStar(ideal I, const ring r, const gfan::ZVector &u,
                                  const tropicalStrategy* currentStrategy);
 

Singular/dyn_modules/gfanlib/tropicalVarietyOfPolynomials.cc

@@ -5 +5 @@
 
 #include <tropicalStrategy.h>
+#include <tropicalVarietyOfPolynomials.h>
 
 #ifndef NDEBUG
@@ -22 +23 @@
   int n = rVar(r);
   std::set<gfan::ZCone> tropVar;
+  if (g && g->next)
+  {
+    int* expv = (int*) omAlloc((n+1)*sizeof(int));
+    gfan::ZMatrix exponents = gfan::ZMatrix(0,n);
+    for (poly s=g; s; pIter(s))
+    {
+      p_GetExpV(s,expv,r);
+      gfan::ZVector zv = intStar2ZVector(n,expv);
+      exponents.appendRow(intStar2ZVector(n,expv));
+    }
+    omFreeSize(expv,(n+1)*sizeof(int));
+
+    int l = exponents.getHeight();
+    gfan::ZVector lowerHalfSpaceCondition = gfan::ZVector(n);
+    lowerHalfSpaceCondition[0] = -1;
+    for (int i=0; i<l; i++)
+    {
+      for (int j=i+1; j<l; j++)
+      {
+        gfan::ZMatrix equation = gfan::ZMatrix(0,n);
+        equation.appendRow(exponents[i]-exponents[j]);
+        gfan::ZMatrix inequalities = gfan::ZMatrix(0,n);
+        if (currentCase->restrictToLowerHalfSpace())
+          inequalities.appendRow(lowerHalfSpaceCondition);
+        for (int k=0; k<l; k++)
+          if (k!=i && k!=j) inequalities.appendRow(exponents[i]-exponents[k]);
+        gfan::ZCone zc = gfan::ZCone(inequalities,equation);
+        if (zc.dimension()>=n-1)
+        {
+          zc.canonicalize();
+          tropVar.insert(zc);
+        }
+      }
+    }
+  }
+  return tropVar;
+}
+
+ZConesSortedByDimension tropicalVarietySortedByDimension(const poly g, const ring r, const tropicalStrategy* currentCase)
+{
+  int n = rVar(r);
+  ZConesSortedByDimension tropVar;
   if (g && g->next)
   {

Singular/dyn_modules/gfanlib/tropicalVarietyOfPolynomials.h

@@ -13 +13 @@
 #endif
 
+struct ZConeCompareDimensionFirst
+{
+  bool operator() (const gfan::ZCone &zc, const gfan::ZCone &zd) const
+    {
+      int n = zc.dimension();
+      int m = zd.dimension();
+      if (n==m)
+        return zc<zd;
+      else
+        return n<m;
+    }
+};
+
+typedef std::set<gfan::ZCone,ZConeCompareDimensionFirst> ZConesSortedByDimension;
+
 std::set<gfan::ZCone> tropicalVariety(const poly g, const ring r, const tropicalStrategy* currentCase);
+ZConesSortedByDimension tropicalVarietySortedByDimension(const poly g, const ring r, const tropicalStrategy* currentCase);
 
 #ifndef NDEBUG