tropicalTraversal.cc
Go to the documentation of this file.
1 #include <bbcone.h>
2 #include <groebnerCone.h>
3 #include <tropicalCurves.h>
4 
5 std::vector<bool> checkNecessaryTropicalFlips(const groebnerCones &tropicalVariety, const groebnerCones &workingList,
6  const gfan::ZVector &interiorPoint, const gfan::ZMatrix &normalVectors)
7 {
8  int k = normalVectors.getHeight();
9  std::vector<bool> needToFlip(k,true);
10 
11  int n = normalVectors.getWidth();
12  gfan::ZMatrix testVectors(k,n);
13  gfan::ZVector bigInteriorPoint = 1000*interiorPoint;
14  for (int i=0; i<k; i++)
15  testVectors[i] = bigInteriorPoint+normalVectors[i];
16 
17  for (groebnerCones::iterator sigma = tropicalVariety.begin(); sigma!=tropicalVariety.end(); sigma++)
18  {
19  if (sigma->contains(interiorPoint))
20  {
21  for (int i=0; i<k; i++)
22  {
23  if (needToFlip[i] && sigma->contains(testVectors[i]))
24  needToFlip[i] = false;
25  }
26  }
27  }
28 
29  for (groebnerCones::iterator sigma = workingList.begin(); sigma!=workingList.end(); sigma++)
30  {
31  if (sigma->contains(interiorPoint))
32  {
33  for (int i=0; i<k; i++)
34  {
35  if (needToFlip[i] && sigma->contains(testVectors[i]))
36  needToFlip[i] = false;
37  }
38  }
39  }
40 
41  return needToFlip;
42 }
43 
45 {
47  if (startingCone.isTrivial())
48  {
49  return tropicalVariety;
50  }
51 
52  groebnerCones workingList;
53  workingList.insert(startingCone);
54  const tropicalStrategy* currentStrategy=startingCone.getTropicalStrategy();
55  std::set<gfan::ZVector> finishedInteriorPoints;
56  while(!workingList.empty())
57  {
58  /**
59  * Pick an element the working list and compute interior points on its facets
60  */
61  groebnerCone sigma=*(workingList.begin());
62  gfan::ZMatrix interiorPoints = interiorPointsOfFacets(sigma.getPolyhedralCone(),finishedInteriorPoints);
63 
64  for (int i=0; i<interiorPoints.getHeight(); i++)
65  {
66  /**
67  * For each interior point, compute the rays of the tropical star in that point
68  */
69  gfan::ZVector interiorPoint = interiorPoints[i];
70  if (!(currentStrategy->restrictToLowerHalfSpace() && interiorPoint[0].sign()==0))
71  {
72  ideal inI = initial(sigma.getPolynomialIdeal(),sigma.getPolynomialRing(),interiorPoint);
73  gfan::ZMatrix normalVectors = raysOfTropicalStar(inI,
74  sigma.getPolynomialRing(),
75  interiorPoint,
76  sigma.getTropicalStrategy());
77  id_Delete(&inI,sigma.getPolynomialRing());
78 
79  std::vector<bool> needToFlip = checkNecessaryTropicalFlips(tropicalVariety,workingList,interiorPoint,normalVectors);
80  for (int j=0; j<normalVectors.getHeight(); j++)
81  {
82  if (needToFlip[j])
83  {
84  groebnerCone neighbour = sigma.flipCone(interiorPoint,normalVectors[j]);
85  workingList.insert(neighbour);
86  }
87  }
88  }
89  finishedInteriorPoints.insert(interiorPoint);
90  }
91 
92  sigma.deletePolynomialData();
93  workingList.erase(sigma);
94  tropicalVariety.insert(sigma);
95  if (printlevel > 0)
96  Print("cones finished: %lu cones in working list: %lu\n",
97  (unsigned long)tropicalVariety.size(), (unsigned long)workingList.size());
98  }
99  return tropicalVariety;
100 }
101 
102 
103 std::vector<bool> checkNecessaryGroebnerFlips(const groebnerCones &groebnerFan, const groebnerCones &workingList,
104  const gfan::ZMatrix &interiorPoints)
105 {
106  int k = interiorPoints.getHeight();
107  std::vector<bool> needToFlip(k,true);
108 
109  for (groebnerCones::iterator sigma = groebnerFan.begin(); sigma!=groebnerFan.end(); sigma++)
110  {
111  for (int i=0; i<k; i++)
112  {
113  if (needToFlip[i] && sigma->contains(interiorPoints[i]))
114  needToFlip[i] = false;
115  }
116  }
117 
118  for (groebnerCones::iterator sigma = workingList.begin(); sigma!=workingList.end(); sigma++)
119  {
120  for (int i=0; i<k; i++)
121  {
122  if (needToFlip[i] && sigma->contains(interiorPoints[i]))
123  needToFlip[i] = false;
124  }
125  }
126 
127  return needToFlip;
128 }
129 
130 
132 {
133  const tropicalStrategy* currentStrategy = startingCone.getTropicalStrategy();
134 
136  groebnerCones workingList;
137  workingList.insert(startingCone);
138  std::set<gfan::ZVector> finishedInteriorPoints;
139  bool onlyLowerHalfSpace = !currentStrategy->isValuationTrivial();
140 
141  while(!workingList.empty())
142  {
143  /**
144  * Pick a maximal Groebner cone from the working list
145  * and compute interior points on its facets as well as outer facet normals
146  */
147  groebnerCone sigma=*(workingList.begin());
148  workingList.erase(workingList.begin());
149 
150  std::pair<gfan::ZMatrix,gfan::ZMatrix> interiorPointsAndOuterFacetNormals = interiorPointsAndNormalsOfFacets(sigma.getPolyhedralCone(), finishedInteriorPoints, onlyLowerHalfSpace);
151  gfan::ZMatrix interiorPoints = interiorPointsAndOuterFacetNormals.first;
152  gfan::ZMatrix outerFacetNormals = interiorPointsAndOuterFacetNormals.second;
153  std::vector<bool> needToFlip = checkNecessaryGroebnerFlips(groebnerFan,workingList, interiorPoints);
154 
155  for (int i=0; i<interiorPoints.getHeight(); i++)
156  {
157  gfan::ZVector interiorPoint = interiorPoints[i];
158 
159  if (needToFlip[i]==true)
160  {
161  groebnerCone neighbour = sigma.flipCone(interiorPoint,outerFacetNormals[i]);
162  workingList.insert(neighbour);
163  }
164  finishedInteriorPoints.insert(interiorPoints[i]);
165  }
166 
167  sigma.deletePolynomialData();
168  groebnerFan.insert(sigma);
169  if (printlevel > 0)
170  Print("cones finished: %lu cones in working list: %lu\n",
171  (unsigned long)groebnerFan.size(), (unsigned long)workingList.size());
172  }
173  return groebnerFan;
174 }
gfan::ZCone getPolyhedralCone() const
Definition: groebnerCone.h:65
bool isTrivial() const
Definition: groebnerCone.h:70
#define Print
Definition: emacs.cc:83
ring getPolynomialRing() const
Definition: groebnerCone.h:64
gfan::ZFan * groebnerFan(const tropicalStrategy currentStrategy)
Definition: groebnerFan.cc:28
std::vector< bool > checkNecessaryTropicalFlips(const groebnerCones &tropicalVariety, const groebnerCones &workingList, const gfan::ZVector &interiorPoint, const gfan::ZMatrix &normalVectors)
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
int k
Definition: cfEzgcd.cc:93
std::pair< gfan::ZMatrix, gfan::ZMatrix > interiorPointsAndNormalsOfFacets(const gfan::ZCone zc, const std::set< gfan::ZVector > &exceptThesePoints, const bool onlyLowerHalfSpace)
Definition: bbcone.cc:1716
groebnerCones groebnerTraversal(const groebnerCone startingCone)
std::set< groebnerCone, groebnerCone_compare > groebnerCones
Definition: groebnerCone.h:24
const tropicalStrategy * getTropicalStrategy() const
Definition: groebnerCone.h:67
void deletePolynomialData()
Definition: groebnerCone.h:54
groebnerCones tropicalTraversalMinimizingFlips(const groebnerCone startingCone)
poly initial(const poly p, const ring r, const gfan::ZVector w)
Returns the initial form of p with respect to w.
Definition: initial.cc:32
bool isValuationTrivial() const
int j
Definition: myNF.cc:70
BOOLEAN tropicalVariety(leftv res, leftv args)
bool restrictToLowerHalfSpace() const
returns true, if valuation non-trivial, false otherwise
int i
Definition: cfEzgcd.cc:123
implementation of the class groebnerCone
std::vector< bool > checkNecessaryGroebnerFlips(const groebnerCones &groebnerFan, const groebnerCones &workingList, const gfan::ZMatrix &interiorPoints)
int printlevel
Definition: febase.cc:42
gfan::ZMatrix raysOfTropicalStar(ideal I, const ring r, const gfan::ZVector &u, const tropicalStrategy *currentStrategy)
groebnerCone flipCone(const gfan::ZVector &interiorPoint, const gfan::ZVector &facetNormal) const
Given an interior point on the facet and the outer normal factor on the facet, returns the adjacent g...
gfan::ZMatrix interiorPointsOfFacets(const gfan::ZCone &zc, const std::set< gfan::ZVector > &exceptThese)
Definition: bbcone.cc:1662
ideal getPolynomialIdeal() const
Definition: groebnerCone.h:63