My Project
Loading...
Searching...
No Matches
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
7std::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
113std::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}
std::pair< gfan::ZMatrix, gfan::ZMatrix > interiorPointsAndNormalsOfFacets(const gfan::ZCone zc, const std::set< gfan::ZVector > &exceptThesePoints, const bool onlyLowerHalfSpace)
Definition: bbcone.cc:1853
gfan::ZMatrix interiorPointsOfFacets(const gfan::ZCone &zc, const std::set< gfan::ZVector > &exceptThese)
Definition: bbcone.cc:1799
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
const tropicalStrategy * getTropicalStrategy() const
Definition: groebnerCone.h:66
gfan::ZCone getPolyhedralCone() const
Definition: groebnerCone.h:64
bool isTrivial() const
Definition: groebnerCone.h:69
ideal getPolynomialIdeal() const
Definition: groebnerCone.h:62
ring getPolynomialRing() const
Definition: groebnerCone.h:63
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...
void deletePolynomialData()
Definition: groebnerCone.h:53
bool isValuationTrivial() const
bool restrictToLowerHalfSpace() const
returns true, if valuation non-trivial, false otherwise
#define Print
Definition: emacs.cc:80
int j
Definition: facHensel.cc:110
VAR int printlevel
Definition: febase.cc:36
implementation of the class groebnerCone
std::set< groebnerCone, groebnerCone_compare > groebnerCones
Definition: groebnerCone.h:24
gfan::ZFan * groebnerFan(const tropicalStrategy currentStrategy)
Definition: groebnerFan.cc:28
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
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
ideal gfanlib_satStd_wrapper(ideal I, ring r, tHomog h=testHomog)
Definition: std_wrapper.cc:124
gfan::ZMatrix raysOfTropicalStar(ideal I, const ring r, const gfan::ZVector &u, const tropicalStrategy *currentStrategy)
groebnerCones groebnerTraversal(const groebnerCone startingCone)
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)
BOOLEAN tropicalVariety(leftv res, leftv args)