My Project  UNKNOWN_GIT_VERSION
Functions
tropicalTraversal.cc File Reference
#include "bbcone.h"
#include "groebnerCone.h"
#include "tropicalCurves.h"
#include "std_wrapper.h"
#include "Singular/ipshell.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

◆ checkNecessaryGroebnerFlips()

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

Definition at line 113 of file tropicalTraversal.cc.

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 }

◆ checkNecessaryTropicalFlips()

std::vector<bool> checkNecessaryTropicalFlips ( const groebnerCones tropicalVariety,
const groebnerCones workingList,
const gfan::ZVector &  interiorPoint,
const gfan::ZMatrix &  normalVectors 
)

Definition at line 7 of file tropicalTraversal.cc.

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 }

◆ 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 141 of file tropicalTraversal.cc.

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 }

◆ 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 52 of file tropicalTraversal.cc.

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 }
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
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:1900
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
id_Delete
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
Definition: simpleideals.cc:113
groebnerCone::getPolynomialIdeal
ideal getPolynomialIdeal() const
Definition: groebnerCone.h:62
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
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:26
groebnerCone
Definition: groebnerCone.h:27
Print
#define Print
Definition: emacs.cc:79
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:381
tropicalVariety
BOOLEAN tropicalVariety(leftv res, leftv args)
Definition: tropicalVariety.cc:41
printlevel
int printlevel
Definition: febase.cc:35
interiorPointsOfFacets
gfan::ZMatrix interiorPointsOfFacets(const gfan::ZCone &zc, const std::set< gfan::ZVector > &exceptThese)
Definition: bbcone.cc:1847
raysOfTropicalStar
gfan::ZMatrix raysOfTropicalStar(ideal I, const ring r, const gfan::ZVector &u, const tropicalStrategy *currentStrategy)
Definition: tropicalCurves.cc:240
groebnerCone::getPolyhedralCone
gfan::ZCone getPolyhedralCone() const
Definition: groebnerCone.h:64
groebnerCone::isTrivial
bool isTrivial() const
Definition: groebnerCone.h:69
tropicalStrategy
Definition: tropicalStrategy.h:36