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