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
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();
15 gfan::ZVector bigInteriorPoint = 1000*interiorPoint;
16 for (int i=0; i<k; 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
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 */
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());
84 sigma.getPolynomialRing(),
85 interiorPoint,
86 sigma.getTropicalStrategy());
87 id_Delete(&inISTD,sigma.getPolynomialRing());
88
90 for (int j=0; j<normalVectors.getHeight(); j++)
91 {
92 if (needToFlip[j])
93 {
94 groebnerCone neighbour = sigma.flipCone(interiorPoint,normalVectors[j]);
96 }
97 }
98 }
99 finishedInteriorPoints.insert(interiorPoint);
100 }
101
102 sigma.deletePolynomialData();
103 workingList.erase(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
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
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);
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]);
173 }
175 }
176
177 sigma.deletePolynomialData();
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
ListItem< T > * first
Definition ftmpl_list.h:54
void insert(const T &)
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
gfan::ZFan * groebnerFan(const tropicalStrategy currentStrategy)
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)
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)