1 #include "traverser_groebnerfan.h"
2 #include <iostream>
3 #include "division.h"
4 #include "wallideal.h"
5 #include "groebnerengine.h"
6 #include "tropical2.h"
7 #include "log.h"
8 #include "division.h"
9 #include "buchberger.h"
10
groebnerBasisWithFullDimensionalIntersection(PolynomialSet g,PolyhedralCone const & c)11 PolynomialSet groebnerBasisWithFullDimensionalIntersection(PolynomialSet g, PolyhedralCone const &c)
12 {
13 IntegerVector v=c.getRelativeInteriorPoint();
14 IntegerVectorList l=c.generatorsOfSpan();
15 l.push_front(v);
16 MatrixTermOrder T(l);
17 buchberger(&g,T);
18 return g;
19 }
20
21
GroebnerFanTraverser(PolynomialSet const & groebnerBasis_)22 GroebnerFanTraverser::GroebnerFanTraverser(PolynomialSet const &groebnerBasis_):
23 ConeTraverser(groebnerBasis_.getRing().getNumberOfVariables()),
24 groebnerBasis(groebnerBasis_),
25 theCone(groebnerBasis_.getRing().getNumberOfVariables()),
26 theRestrictingCone(groebnerBasis_.getRing().getNumberOfVariables()),
27 isHomogeneous(false),
28 isKnownToBeComplete(false)
29 {
30 n=groebnerBasis_.getRing().getNumberOfVariables();
31 d=n;
32 updatePolyhedralCone();
33 //cerr<<"DIMIMIMiM"<<d<<endl;
34 }
35
GroebnerFanTraverser(PolynomialSet const & groebnerBasis_,PolyhedralCone const & restrictingCone)36 GroebnerFanTraverser::GroebnerFanTraverser(PolynomialSet const &groebnerBasis_, PolyhedralCone const &restrictingCone):
37 ConeTraverser(groebnerBasis_.getRing().getNumberOfVariables()),
38 groebnerBasis(groebnerBasis_),
39 theCone(groebnerBasis_.getRing().getNumberOfVariables()),
40 theRestrictingCone(restrictingCone),
41 isHomogeneous(false),
42 isKnownToBeComplete(false)
43 {
44 d=theRestrictingCone.dimension();
45 n=groebnerBasis_.getRing().getNumberOfVariables();
46 updatePolyhedralCone();
47
48 isHomogeneous=theCone.linealitySpace().containsPositiveVector();
49 //d=n;
50 //cerr<<"DIMIMIMiM"<<d<<endl;
51 }
52
updatePolyhedralCone()53 void GroebnerFanTraverser::updatePolyhedralCone()
54 {
55 // IntegerVectorList empty;
56 // theCone=PolyhedralCone::polyhedralConeWithKnownImpliedEquations(fastNormals(wallInequalities(groebnerBasis)),empty,n);
57 // theCone=PolyhedralCone(fastNormals(wallInequalities(groebnerBasis)),empty,n);
58 // theCone=PolyhedralCone(fastNormals(algebraicTest(wallInequalities(groebnerBasis),groebnerBasis)),empty,n);
59
60 IntegerVectorList inequalities=fastNormals(wallInequalities(groebnerBasis));
61 IntegerVectorList inequalities2=theRestrictingCone.getHalfSpaces();
62 inequalities.splice(inequalities.begin(),inequalities2);
63 theCone=PolyhedralCone::polyhedralConeWithKnownImpliedEquations(inequalities,theRestrictingCone.getEquations(),n);
64 // theCone=intersection(theCone,theRestrictingCone);
65 theCone.canonicalize();
66
67 /* if(theCone.dimension()!=d)
68 {
69 cerr<<"WARNING THIS CONE HAS THE WRONG DIMENSION!"<<endl;
70
71 cerr<<"d"<<d<<"n"<<n;
72
73 AsciiPrinter P(Stderr);
74 theRestrictingCone.print(&P);
75 assert(0);
76 }*/
77 }
78
changeCone(IntegerVector const & ridgeVector,IntegerVector const & rayVector)79 void GroebnerFanTraverser::changeCone(IntegerVector const &ridgeVector, IntegerVector const &rayVector)
80 {
81 assert(theCone.contains(ridgeVector));
82 if(theRestrictingCone.isFullSpace())
83 {
84 //Notice that changeCone might be called even when no change is needed
85 //This happens when we go to a ridge, but there is nothing to be done
86 //In that case we return to the facet that we came from.
87 //The call to changeCone should be interpreted as go to ridge, then cone back
88 //to the facet in direction rayVector.
89 {
90 IntegerVectorList l=wallInequalities(groebnerBasis);
91 bool testPerformed=false;
92 for(IntegerVectorList::const_iterator i=l.begin();i!=l.end();i++)
93 if(dotLong(*i,ridgeVector)==0)
94 {
95 if(dotLong(rayVector,*i)>=0)return;//<<--------------------
96 testPerformed=true;break;
97 }
98 assert(testPerformed);
99 }
100 // groebnerBasis=flip(groebnerBasis,-rayVector);
101 {
102 IntegerVectorList m;
103 m.push_back(ridgeVector);
104 m.push_back(rayVector);
105 MatrixTermOrder T(m);
106 groebnerBasis=flip(groebnerBasis,-rayVector,&T);
107 }
108 }
109 else
110 {
111 PolynomialSet ridgeIdealOld=initialFormsAssumeMarked(groebnerBasis,ridgeVector);
112 WeightReverseLexicographicTermOrder T(rayVector);
113 PolynomialSet ridgeIdeal=GE_groebnerBasis(ridgeIdealOld,T,true,false);
114 PolynomialSet g2(groebnerBasis.getRing());
115 for(PolynomialSet::const_iterator j=ridgeIdeal.begin();j!=ridgeIdeal.end();j++)
116 g2.push_back(divisionLift(*j, ridgeIdealOld, groebnerBasis, T));
117 groebnerBasis=GE_autoReduce(g2);
118 }
119 updatePolyhedralCone();
120 }
121
link(IntegerVector const & ridgeVector)122 IntegerVectorList GroebnerFanTraverser::link(IntegerVector const &ridgeVector)
123 {
124 IntegerVectorList ret;
125 IntegerVector v=theCone.link(ridgeVector).getUniquePoint();
126
127 ret.push_back(v);
128
129 if(isKnownToBeComplete)
130 {
131 ret.push_back(-v);
132 return ret;
133 }
134
135 if(!theRestrictingCone.containsRelatively(ridgeVector))return ret;
136
137 // If the ideal is known to be homogeneous in a positive grading then we don't have to make the following test
138 // Furthermore, for restricted traversals the following test test the ridge for having a positive vector - another definitions of flipability would be to check the lifting of the ridge to the full space.
139 if(isHomogeneous)
140 {
141 // debug<<"FDSFADFA-------------------------------\n";
142 ret.push_back(-v);
143 return ret;
144 }
145 {
146 PolyhedralCone temp=theCone.faceContaining(ridgeVector);
147 if(temp.containsPositiveVector())ret.push_back(-v);
148 //cerr<<"THIS NEEDS TO BE FIXED!!!\n";
149 // ret.push_back(-v);
150 }
151 return ret;
152 }
153
refToPolyhedralCone()154 PolyhedralCone & GroebnerFanTraverser::refToPolyhedralCone()
155 {
156 return theCone;
157 }
158
refToGroebnerBasisRepresentation()159 PolynomialSet &GroebnerFanTraverser::refToGroebnerBasisRepresentation()
160 {
161 return groebnerBasis;
162 }
163
setIsKnownToBeComplete(bool complete)164 void GroebnerFanTraverser::setIsKnownToBeComplete(bool complete)
165 {
166 isKnownToBeComplete=complete;
167 }
168