Functions
tropicalTraversal.cc File Reference
#include <bbcone.h>
#include <groebnerCone.h>
#include <tropicalCurves.h>

Go to the source code of this file.

Functions

std::vector< bool > checkNecessaryTropicalFlips (const groebnerCones &tropicalVariety, const groebnerCones &workingList, const gfan::ZVector &interiorPoint, const gfan::ZMatrix &normalVectors)
 
groebnerCones tropicalTraversalMinimizingFlips (const groebnerCone startingCone)
 
std::vector< bool > checkNecessaryGroebnerFlips (const groebnerCones &groebnerFan, const groebnerCones &workingList, const gfan::ZMatrix &interiorPoints)
 
groebnerCones groebnerTraversal (const groebnerCone startingCone)
 

Function Documentation

std::vector<bool> checkNecessaryGroebnerFlips ( const groebnerCones groebnerFan,
const groebnerCones workingList,
const gfan::ZMatrix &  interiorPoints 
)

Definition at line 103 of file tropicalTraversal.cc.

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 }
gfan::ZFan * groebnerFan(const tropicalStrategy currentStrategy)
Definition: groebnerFan.cc:28
int k
Definition: cfEzgcd.cc:93
int i
Definition: cfEzgcd.cc:123
std::vector<bool> checkNecessaryTropicalFlips ( const groebnerCones tropicalVariety,
const groebnerCones workingList,
const gfan::ZVector &  interiorPoint,
const gfan::ZMatrix &  normalVectors 
)

Definition at line 5 of file tropicalTraversal.cc.

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 }
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
int k
Definition: cfEzgcd.cc:93
BOOLEAN tropicalVariety(leftv res, leftv args)
int i
Definition: cfEzgcd.cc:123
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 131 of file tropicalTraversal.cc.

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 }
const tropicalStrategy * getTropicalStrategy() const
Definition: groebnerCone.h:67
#define Print
Definition: emacs.cc:83
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::ZFan * groebnerFan(const tropicalStrategy currentStrategy)
Definition: groebnerFan.cc:28
gfan::ZCone getPolyhedralCone() const
Definition: groebnerCone.h:65
std::pair< gfan::ZMatrix, gfan::ZMatrix > interiorPointsAndNormalsOfFacets(const gfan::ZCone zc, const std::set< gfan::ZVector > &exceptThesePoints, const bool onlyLowerHalfSpace)
Definition: bbcone.cc:1674
std::set< groebnerCone, groebnerCone_compare > groebnerCones
Definition: groebnerCone.h:24
void deletePolynomialData()
Definition: groebnerCone.h:54
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
bool isValuationTrivial() const
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 44 of file tropicalTraversal.cc.

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 }
const tropicalStrategy * getTropicalStrategy() const
Definition: groebnerCone.h:67
#define Print
Definition: emacs.cc:83
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...
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
gfan::ZCone getPolyhedralCone() const
Definition: groebnerCone.h:65
std::set< groebnerCone, groebnerCone_compare > groebnerCones
Definition: groebnerCone.h:24
void deletePolynomialData()
Definition: groebnerCone.h:54
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)
ideal getPolynomialIdeal() const
Definition: groebnerCone.h:63
int i
Definition: cfEzgcd.cc:123
bool isTrivial() const
Definition: groebnerCone.h:70
bool restrictToLowerHalfSpace() const
returns true, if valuation non-trivial, false otherwise
ring getPolynomialRing() const
Definition: groebnerCone.h:64
int printlevel
Definition: febase.cc:42
gfan::ZMatrix raysOfTropicalStar(ideal I, const ring r, const gfan::ZVector &u, const tropicalStrategy *currentStrategy)
gfan::ZMatrix interiorPointsOfFacets(const gfan::ZCone &zc, const std::set< gfan::ZVector > &exceptThese)
Definition: bbcone.cc:1620