tropicalTraversal.cc
Go to the documentation of this file.
1 #include <bbcone.h>
2 #include <groebnerCone.h>
3 #include <tropicalCurves.h>
4 #include <std_wrapper.h>
5 
6 std::vector<bool> checkNecessaryTropicalFlips(const groebnerCones &tropicalVariety, const groebnerCones &workingList,
7  const gfan::ZVector &interiorPoint, const gfan::ZMatrix &normalVectors)
8 {
9  int k = normalVectors.getHeight();
10  std::vector<bool> needToFlip(k,true);
11 
12  int n = normalVectors.getWidth();
13  gfan::ZMatrix testVectors(k,n);
14  gfan::ZVector bigInteriorPoint = 1000*interiorPoint;
15  for (int i=0; i<k; i++)
16  testVectors[i] = bigInteriorPoint+normalVectors[i];
17 
18  for (groebnerCones::iterator sigma = tropicalVariety.begin(); sigma!=tropicalVariety.end(); sigma++)
19  {
20  if (sigma->contains(interiorPoint))
21  {
22  for (int i=0; i<k; i++)
23  {
24  if (needToFlip[i] && sigma->contains(testVectors[i]))
25  {
26  needToFlip[i] = false;
27  break;
28  }
29  }
30  }
31  }
32 
33  for (groebnerCones::iterator sigma = workingList.begin(); sigma!=workingList.end(); sigma++)
34  {
35  if (sigma->contains(interiorPoint))
36  {
37  for (int i=0; i<k; i++)
38  {
39  if (needToFlip[i] && sigma->contains(testVectors[i]))
40  {
41  needToFlip[i] = false;
42  break;
43  }
44  }
45  }
46  }
47 
48  return needToFlip;
49 }
50 
52 {
54  if (startingCone.isTrivial())
55  {
56  return tropicalVariety;
57  }
58 
59  groebnerCones workingList;
60  workingList.insert(startingCone);
61  const tropicalStrategy* currentStrategy=startingCone.getTropicalStrategy();
62  std::set<gfan::ZVector> finishedInteriorPoints;
63  while(!workingList.empty())
64  {
65  /**
66  * Pick an element the working list and compute interior points on its facets
67  */
68  groebnerCone sigma=*(workingList.begin());
69  gfan::ZMatrix interiorPoints = interiorPointsOfFacets(sigma.getPolyhedralCone(),finishedInteriorPoints);
70 
71  for (int i=0; i<interiorPoints.getHeight(); i++)
72  {
73  /**
74  * For each interior point, compute the rays of the tropical star in that point
75  */
76  gfan::ZVector interiorPoint = interiorPoints[i];
77  if (!(currentStrategy->restrictToLowerHalfSpace() && interiorPoint[0].sign()==0))
78  {
79  ideal inI = initial(sigma.getPolynomialIdeal(),sigma.getPolynomialRing(),interiorPoint);
80  ideal inISTD = gfanlib_satStd_wrapper(inI,sigma.getPolynomialRing());
81  id_Delete(&inI,sigma.getPolynomialRing());
82  gfan::ZMatrix normalVectors = raysOfTropicalStar(inISTD,
83  sigma.getPolynomialRing(),
84  interiorPoint,
85  sigma.getTropicalStrategy());
86  id_Delete(&inISTD,sigma.getPolynomialRing());
87 
88  std::vector<bool> needToFlip = checkNecessaryTropicalFlips(tropicalVariety,workingList,interiorPoint,normalVectors);
89  for (int j=0; j<normalVectors.getHeight(); j++)
90  {
91  if (needToFlip[j])
92  {
93  groebnerCone neighbour = sigma.flipCone(interiorPoint,normalVectors[j]);
94  workingList.insert(neighbour);
95  }
96  }
97  }
98  finishedInteriorPoints.insert(interiorPoint);
99  }
100 
101  sigma.deletePolynomialData();
102  workingList.erase(sigma);
103  tropicalVariety.insert(sigma);
104  if (printlevel > 0)
105  Print("cones finished: %lu cones in working list: %lu\n",
106  (unsigned long)tropicalVariety.size(), (unsigned long)workingList.size());
107  }
108  return tropicalVariety;
109 }
110 
111 
112 std::vector<bool> checkNecessaryGroebnerFlips(const groebnerCones &groebnerFan, const groebnerCones &workingList,
113  const gfan::ZMatrix &interiorPoints)
114 {
115  int k = interiorPoints.getHeight();
116  std::vector<bool> needToFlip(k,true);
117 
118  for (groebnerCones::iterator sigma = groebnerFan.begin(); sigma!=groebnerFan.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  for (groebnerCones::iterator sigma = workingList.begin(); sigma!=workingList.end(); sigma++)
128  {
129  for (int i=0; i<k; i++)
130  {
131  if (needToFlip[i] && sigma->contains(interiorPoints[i]))
132  needToFlip[i] = false;
133  }
134  }
135 
136  return needToFlip;
137 }
138 
139 
141 {
142  const tropicalStrategy* currentStrategy = startingCone.getTropicalStrategy();
143 
145  groebnerCones workingList;
146  workingList.insert(startingCone);
147  std::set<gfan::ZVector> finishedInteriorPoints;
148  bool onlyLowerHalfSpace = !currentStrategy->isValuationTrivial();
149 
150  while(!workingList.empty())
151  {
152  /**
153  * Pick a maximal Groebner cone from the working list
154  * and compute interior points on its facets as well as outer facet normals
155  */
156  groebnerCone sigma=*(workingList.begin());
157  workingList.erase(workingList.begin());
158 
159  std::pair<gfan::ZMatrix,gfan::ZMatrix> interiorPointsAndOuterFacetNormals = interiorPointsAndNormalsOfFacets(sigma.getPolyhedralCone(), finishedInteriorPoints, onlyLowerHalfSpace);
160  gfan::ZMatrix interiorPoints = interiorPointsAndOuterFacetNormals.first;
161  gfan::ZMatrix outerFacetNormals = interiorPointsAndOuterFacetNormals.second;
162  std::vector<bool> needToFlip = checkNecessaryGroebnerFlips(groebnerFan,workingList, interiorPoints);
163 
164  for (int i=0; i<interiorPoints.getHeight(); i++)
165  {
166  gfan::ZVector interiorPoint = interiorPoints[i];
167 
168  if (needToFlip[i]==true)
169  {
170  groebnerCone neighbour = sigma.flipCone(interiorPoint,outerFacetNormals[i]);
171  workingList.insert(neighbour);
172  }
173  finishedInteriorPoints.insert(interiorPoints[i]);
174  }
175 
176  sigma.deletePolynomialData();
177  groebnerFan.insert(sigma);
178  if (printlevel > 0)
179  Print("cones finished: %lu cones in working list: %lu\n",
180  (unsigned long)groebnerFan.size(), (unsigned long)workingList.size());
181  }
182  return groebnerFan;
183 }
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:1757
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)
ideal gfanlib_satStd_wrapper(ideal I, ring r, tHomog h=testHomog)
Definition: std_wrapper.cc:124
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:1703
ideal getPolynomialIdeal() const
Definition: groebnerCone.h:63