Functions
tropicalTraversal.h File Reference
#include <groebnerCone.h>

Go to the source code of this file.

Functions

groebnerCones tropicalTraversalMinimizingFlips (const groebnerCone startingCone)
 
groebnerCones tropicalTraversal (const groebnerCone startingCone)
 
groebnerCones groebnerTraversal (const groebnerCone startingCone)
 

Function Documentation

◆ groebnerTraversal()

groebnerCones groebnerTraversal ( const groebnerCone  startingCone)

Pick a maximal Groebner cone from the working list and compute interior points on its facets as well as outer facet normals

Definition at line 140 of file tropicalTraversal.cc.

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
#define Print
Definition: emacs.cc:83
gfan::ZFan * groebnerFan(const tropicalStrategy currentStrategy)
Definition: groebnerFan.cc:28
std::pair< gfan::ZMatrix, gfan::ZMatrix > interiorPointsAndNormalsOfFacets(const gfan::ZCone zc, const std::set< gfan::ZVector > &exceptThesePoints, const bool onlyLowerHalfSpace)
Definition: bbcone.cc:1757
std::set< groebnerCone, groebnerCone_compare > groebnerCones
Definition: groebnerCone.h:24
const tropicalStrategy * getTropicalStrategy() const
Definition: groebnerCone.h:67
void deletePolynomialData()
Definition: groebnerCone.h:54
bool isValuationTrivial() const
int i
Definition: cfEzgcd.cc:123
std::vector< bool > checkNecessaryGroebnerFlips(const groebnerCones &groebnerFan, const groebnerCones &workingList, const gfan::ZMatrix &interiorPoints)
int printlevel
Definition: febase.cc:42
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...

◆ tropicalTraversal()

groebnerCones tropicalTraversal ( const groebnerCone  startingCone)

◆ tropicalTraversalMinimizingFlips()

groebnerCones tropicalTraversalMinimizingFlips ( const groebnerCone  startingCone)

Pick an element the working list and compute interior points on its facets

For each interior point, compute the rays of the tropical star in that point

Definition at line 51 of file tropicalTraversal.cc.

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 }
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
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
std::set< groebnerCone, groebnerCone_compare > groebnerCones
Definition: groebnerCone.h:24
const tropicalStrategy * getTropicalStrategy() const
Definition: groebnerCone.h:67
void deletePolynomialData()
Definition: groebnerCone.h:54
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
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
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