My Project  UNKNOWN_GIT_VERSION
tropicalStrategy.h
Go to the documentation of this file.
1 #ifndef GFANLIB_TROPICALSTRATEGY_H
2 #define GFANLIB_TROPICALSTRATEGY_H
3 
4 #include "gfanlib/gfanlib_vector.h"
5 #include "gfanlib/gfanlib_zcone.h"
6 #include "polys/simpleideals.h"
7 #include "kernel/ideals.h" // for idElem
9 #include "containsMonomial.h"
10 #include "flip.h"
11 #include "initial.h"
12 #include "witness.h"
13 
14 #ifndef SING_NDEBUG
15 
16 #include "Singular/ipshell.h" // for isPrime(int i)
17 #include "adjustWeights.h"
18 #include "ppinitialReduction.h"
19 
20 #endif
21 
22 /** \file
23  * implementation of the class tropicalStrategy
24  *
25  * tropicalStrategy is a class that contains information relevant for
26  * computing tropical varieties that is dependent on the valuation of the coefficient field.
27  * It represents the mutable part of an overall framework that is capable of
28  * computing tropical varieties both over coefficient fields without valuation and
29  * with valuation (currently: only p-adic valuation over rational numbers)
30  */
31 
32 typedef gfan::ZVector (*wAdjAlg1)(gfan::ZVector);
33 typedef gfan::ZVector (*wAdjAlg2)(gfan::ZVector,gfan::ZVector);
34 typedef bool (*redAlg)(ideal,ring,number);
35 
37 {
38 private:
39  /**
40  * polynomial ring over a field with valuation
41  */
43  /**
44  * input ideal, assumed to be a homogeneous prime ideal
45  */
47  /**
48  * the expected Dimension of the polyhedral output,
49  * i.e. the dimension of the ideal if valuation trivial
50  * or the dimension of the ideal plus one if valuation non-trivial
51  * (as the output is supposed to be intersected with a hyperplane)
52  */
54  /**
55  * the homogeneity space of the Grobner fan
56  */
57  gfan::ZCone linealitySpace;
58  /**
59  * polynomial ring over the valuation ring extended by one extra variable t
60  */
62  /**
63  * preimage of the input ideal under the map that sends t to the uniformizing parameter
64  */
66  /**
67  * uniformizing parameter in the valuation ring
68  */
70  /**
71  * polynomial ring over the residue field
72  */
74 
75  /**
76  * true if valuation non-trivial, false otherwise
77  */
79 
80  /**
81  * A function such that:
82  * Given weight w, returns a strictly positive weight u such that an ideal satisfying
83  * the valuation-sepcific homogeneity conditions is weighted homogeneous with respect to w
84  * if and only if it is homogeneous with respect to u
85  */
86  gfan::ZVector (*weightAdjustingAlgorithm1) (const gfan::ZVector &w);
87  /**
88  * A function such that:
89  * Given strictly positive weight w and weight v,
90  * returns a strictly positive weight u such that on an ideal that is weighted homogeneous
91  * with respect to w the weights u and v coincide
92  */
93  gfan::ZVector (*weightAdjustingAlgorithm2) (const gfan::ZVector &v, const gfan::ZVector &w);
94  /**
95  * A function that reduces the generators of an ideal I so that
96  * the inequalities and equations of the Groebner cone can be read off.
97  */
98  bool (*extraReductionAlgorithm) (ideal I, ring r, number p);
99 
100  ring copyAndChangeCoefficientRing(const ring r) const;
101  ring copyAndChangeOrderingWP(const ring r, const gfan::ZVector &w, const gfan::ZVector &v) const;
102  ring copyAndChangeOrderingLS(const ring r, const gfan::ZVector &w, const gfan::ZVector &v) const;
103 
104  /**
105  * if valuation non-trivial, checks whether the generating system contains p-t
106  * otherwise returns true
107  */
108  bool checkForUniformizingBinomial(const ideal I, const ring r) const;
109 
110  /**
111  * if valuation non-trivial, checks whether the genearting system contains p
112  * otherwise returns true
113  */
114  bool checkForUniformizingParameter(const ideal inI, const ring r) const;
115  int findPositionOfUniformizingBinomial(const ideal I, const ring r) const;
116  void putUniformizingBinomialInFront(ideal I, const ring r, const number q) const;
117 
118 public:
119 
120  /**
121  * Constructor for the trivial valuation case
122  */
123  tropicalStrategy(const ideal I, const ring r, const bool completelyHomogeneous=true, const bool completeSpace=true);
124  /**
125  * Constructor for the non-trivial valuation case
126  * p is the uniformizing parameter of the valuation
127  */
128  tropicalStrategy(const ideal J, const number p, const ring s);
129  /**
130  * copy constructor
131  */
132  tropicalStrategy(const tropicalStrategy& currentStrategy);
133 
134 
135  /**
136  * destructor
137  */
139  /**
140  * assignment operator
141  **/
142  tropicalStrategy& operator=(const tropicalStrategy& currentStrategy);
143 
144  bool isValuationTrivial() const
145  {
146  bool b = (uniformizingParameter==NULL);
147  return b;
148  }
150  {
151  bool b = (uniformizingParameter!=NULL);
152  return b;
153  }
154 
155  /**
156  * returns the polynomial ring over the field with valuation
157  */
158  ring getOriginalRing() const
159  {
161  return originalRing;
162  }
163 
164  /**
165  * returns the input ideal over the field with valuation
166  */
167  ideal getOriginalIdeal() const
168  {
170  return originalIdeal;
171  }
172 
173  /**
174  * returns the polynomial ring over the valuation ring
175  */
176  ring getStartingRing() const
177  {
179  return startingRing;
180  }
181 
182  /**
183  * returns the input ideal
184  */
185  ideal getStartingIdeal() const
186  {
188  return startingIdeal;
189  }
190 
192  {
193  return rVar(startingRing);
194  }
195 
196  /**
197  * returns the expected Dimension of the polyhedral output
198  */
200  {
201  return expectedDimension;
202  }
203 
204  /**
205  * returns the uniformizing parameter in the valuation ring
206  */
208  {
210  return uniformizingParameter;
211  }
212 
213  ring getShortcutRing() const
214  {
216  return shortcutRing;
217  }
218 
219  /**
220  * returns the homogeneity space of the preimage ideal
221  */
222  gfan::ZCone getHomogeneitySpace() const
223  {
224  return linealitySpace;
225  }
226 
227  /**
228  * returns true, if v is contained in the homogeneity space; false otherwise
229  */
230  bool homogeneitySpaceContains(const gfan::ZVector &v) const
231  {
232  return linealitySpace.contains(v);
233  }
234 
235  /**
236  * returns true, if valuation non-trivial, false otherwise
237  */
239  {
240  return onlyLowerHalfSpace;
241  }
242 
243  /**
244  * Given weight w, returns a strictly positive weight u such that an ideal satisfying
245  * the valuation-sepcific homogeneity conditions is weighted homogeneous with respect to w
246  * if and only if it is homogeneous with respect to u
247  */
248  gfan::ZVector adjustWeightForHomogeneity(gfan::ZVector w) const
249  {
250  return this->weightAdjustingAlgorithm1(w);
251  }
252 
253  /**
254  * Given strictly positive weight w and weight v,
255  * returns a strictly positive weight u such that on an ideal that is weighted homogeneous
256  * with respect to w the weights u and v coincide
257  */
258  gfan::ZVector adjustWeightUnderHomogeneity(gfan::ZVector v, gfan::ZVector w) const
259  {
260  return this->weightAdjustingAlgorithm2(v,w);
261  }
262 
263  gfan::ZVector negateWeight(const gfan::ZVector &w) const
264  {
265  gfan::ZVector wNeg(w.size());
266 
267  if (this->isValuationNonTrivial())
268  {
269  wNeg[0]=w[0];
270  for (unsigned i=1; i<w.size(); i++)
271  wNeg[i]=w[i];
272  }
273  else
274  wNeg = -w;
275 
276  return wNeg;
277  }
278 
279  /**
280  * If valuation trivial, returns a copy of r with a positive weight prepended,
281  * such that any ideal homogeneous with respect to w is homogeneous with respect to that weight.
282  * If valuation non-trivial, changes the coefficient ring to the residue field.
283  */
284  ring getShortcutRingPrependingWeight(const ring r, const gfan::ZVector &w) const;
285 
286  /**
287  * reduces the generators of an ideal I so that
288  * the inequalities and equations of the Groebner cone can be read off.
289  */
290  bool reduce(ideal I, const ring r) const;
291 
292  void pReduce(ideal I, const ring r) const;
293 
294  /**
295  * If given w, assuming w is in the Groebner cone of the ordering on r
296  * and I is a standard basis with respect to that ordering,
297  * checks whether the initial ideal of I with respect to w contains a monomial.
298  * If no w is given, assuming that I is already an initial form of some ideal,
299  * checks whether I contains a monomial.
300  * In both cases returns a monomial, if it contains one, returns NULL otherwise.
301  **/
302  std::pair<poly,int> checkInitialIdealForMonomial(const ideal I, const ring r, const gfan::ZVector &w=0) const;
303 
304  /**
305  * given generators of the initial ideal, computes its standard basis
306  */
307  ideal computeStdOfInitialIdeal(const ideal inI, const ring r) const;
308 
309  /**
310  * suppose w a weight in maximal groebner cone of >
311  * suppose I (initially) reduced standard basis w.r.t. > and inI initial forms of its elements w.r.t. w
312  * suppose inJ elements of initial ideal that are homogeneous w.r.t w
313  * returns J elements of ideal whose initial form w.r.t. w are inI
314  * in particular, if w lies also inthe maximal groebner cone of another ordering >'
315  * and inJ is a standard basis of the initial ideal w.r.t. >'
316  * then the returned J will be a standard baiss of the ideal w.r.t. >'
317  */
318  ideal computeWitness(const ideal inJ, const ideal inI, const ideal I, const ring r) const;
319 
320  ideal computeLift(const ideal inJs, const ring s, const ideal inIr, const ideal Ir, const ring r) const;
321 
322  /**
323  * given an interior point of a groebner cone
324  * computes the groebner cone adjacent to it
325  */
326  std::pair<ideal,ring> computeFlip(const ideal Ir, const ring r, const gfan::ZVector &interiorPoint, const gfan::ZVector &facetNormal) const;
327 };
328 
329 #endif
tropicalStrategy::originalIdeal
ideal originalIdeal
input ideal, assumed to be a homogeneous prime ideal
Definition: tropicalStrategy.h:46
tropicalStrategy::isValuationTrivial
bool isValuationTrivial() const
Definition: tropicalStrategy.h:144
tropicalStrategy::pReduce
void pReduce(ideal I, const ring r) const
Definition: tropicalStrategy.cc:430
tropicalStrategy::adjustWeightForHomogeneity
gfan::ZVector adjustWeightForHomogeneity(gfan::ZVector w) const
Given weight w, returns a strictly positive weight u such that an ideal satisfying the valuation-sepc...
Definition: tropicalStrategy.h:248
ppinitialReduction.h
callgfanlib_conversion.h
tropicalStrategy::restrictToLowerHalfSpace
bool restrictToLowerHalfSpace() const
returns true, if valuation non-trivial, false otherwise
Definition: tropicalStrategy.h:238
tropicalStrategy::getHomogeneitySpace
gfan::ZCone getHomogeneitySpace() const
returns the homogeneity space of the preimage ideal
Definition: tropicalStrategy.h:222
tropicalStrategy::weightAdjustingAlgorithm2
gfan::ZVector(* weightAdjustingAlgorithm2)(const gfan::ZVector &v, const gfan::ZVector &w)
A function such that: Given strictly positive weight w and weight v, returns a strictly positive weig...
Definition: tropicalStrategy.h:93
tropicalStrategy::copyAndChangeOrderingLS
ring copyAndChangeOrderingLS(const ring r, const gfan::ZVector &w, const gfan::ZVector &v) const
Definition: tropicalStrategy.cc:732
tropicalStrategy::computeLift
ideal computeLift(const ideal inJs, const ring s, const ideal inIr, const ideal Ir, const ring r) const
Definition: tropicalStrategy.cc:686
tropicalStrategy::checkForUniformizingParameter
bool checkForUniformizingParameter(const ideal inI, const ring r) const
if valuation non-trivial, checks whether the genearting system contains p otherwise returns true
Definition: tropicalStrategy.cc:865
tropicalStrategy::copyAndChangeOrderingWP
ring copyAndChangeOrderingWP(const ring r, const gfan::ZVector &w, const gfan::ZVector &v) const
Definition: tropicalStrategy.cc:702
tropicalStrategy::checkForUniformizingBinomial
bool checkForUniformizingBinomial(const ideal I, const ring r) const
if valuation non-trivial, checks whether the generating system contains p-t otherwise returns true
Definition: tropicalStrategy.cc:812
tropicalStrategy::negateWeight
gfan::ZVector negateWeight(const gfan::ZVector &w) const
Definition: tropicalStrategy.h:263
tropicalStrategy::reduce
bool reduce(ideal I, const ring r) const
reduces the generators of an ideal I so that the inequalities and equations of the Groebner cone can ...
Definition: tropicalStrategy.cc:416
tropicalStrategy::extraReductionAlgorithm
bool(* extraReductionAlgorithm)(ideal I, ring r, number p)
A function that reduces the generators of an ideal I so that the inequalities and equations of the Gr...
Definition: tropicalStrategy.h:98
simpleideals.h
tropicalStrategy::getExpectedDimension
int getExpectedDimension() const
returns the expected Dimension of the polyhedral output
Definition: tropicalStrategy.h:199
tropicalStrategy::uniformizingParameter
number uniformizingParameter
uniformizing parameter in the valuation ring
Definition: tropicalStrategy.h:69
tropicalStrategy::startingRing
ring startingRing
polynomial ring over the valuation ring extended by one extra variable t
Definition: tropicalStrategy.h:61
rTest
#define rTest(r)
Definition: ring.h:776
tropicalStrategy::isValuationNonTrivial
bool isValuationNonTrivial() const
Definition: tropicalStrategy.h:149
tropicalStrategy::checkInitialIdealForMonomial
std::pair< poly, int > checkInitialIdealForMonomial(const ideal I, const ring r, const gfan::ZVector &w=0) const
If given w, assuming w is in the Groebner cone of the ordering on r and I is a standard basis with re...
Definition: tropicalStrategy.cc:494
tropicalStrategy::getOriginalIdeal
ideal getOriginalIdeal() const
returns the input ideal over the field with valuation
Definition: tropicalStrategy.h:167
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
b
CanonicalForm b
Definition: cfModGcd.cc:4044
tropicalStrategy::originalRing
ring originalRing
polynomial ring over a field with valuation
Definition: tropicalStrategy.h:42
tropicalStrategy::homogeneitySpaceContains
bool homogeneitySpaceContains(const gfan::ZVector &v) const
returns true, if v is contained in the homogeneity space; false otherwise
Definition: tropicalStrategy.h:230
rVar
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:582
tropicalStrategy::adjustWeightUnderHomogeneity
gfan::ZVector adjustWeightUnderHomogeneity(gfan::ZVector v, gfan::ZVector w) const
Given strictly positive weight w and weight v, returns a strictly positive weight u such that on an i...
Definition: tropicalStrategy.h:258
tropicalStrategy::tropicalStrategy
tropicalStrategy(const ideal I, const ring r, const bool completelyHomogeneous=true, const bool completeSpace=true)
Constructor for the trivial valuation case.
Definition: tropicalStrategy.cc:138
i
int i
Definition: cfEzgcd.cc:125
tropicalStrategy::linealitySpace
gfan::ZCone linealitySpace
the homogeneity space of the Grobner fan
Definition: tropicalStrategy.h:57
wAdjAlg1
gfan::ZVector(* wAdjAlg1)(gfan::ZVector)
Definition: tropicalStrategy.h:32
tropicalStrategy::computeStdOfInitialIdeal
ideal computeStdOfInitialIdeal(const ideal inI, const ring r) const
given generators of the initial ideal, computes its standard basis
Definition: tropicalStrategy.cc:654
wAdjAlg2
gfan::ZVector(* wAdjAlg2)(gfan::ZVector, gfan::ZVector)
Definition: tropicalStrategy.h:33
redAlg
bool(* redAlg)(ideal, ring, number)
Definition: tropicalStrategy.h:34
tropicalStrategy::operator=
tropicalStrategy & operator=(const tropicalStrategy &currentStrategy)
assignment operator
Definition: tropicalStrategy.cc:363
tropicalStrategy::getShortcutRingPrependingWeight
ring getShortcutRingPrependingWeight(const ring r, const gfan::ZVector &w) const
If valuation trivial, returns a copy of r with a positive weight prepended, such that any ideal homog...
Definition: tropicalStrategy.cc:446
tropicalStrategy::getShortcutRing
ring getShortcutRing() const
Definition: tropicalStrategy.h:213
flip.h
witness.h
tropicalStrategy::expectedDimension
int expectedDimension
the expected Dimension of the polyhedral output, i.e.
Definition: tropicalStrategy.h:53
tropicalStrategy::weightAdjustingAlgorithm1
gfan::ZVector(* weightAdjustingAlgorithm1)(const gfan::ZVector &w)
A function such that: Given weight w, returns a strictly positive weight u such that an ideal satisfy...
Definition: tropicalStrategy.h:86
tropicalStrategy::findPositionOfUniformizingBinomial
int findPositionOfUniformizingBinomial(const ideal I, const ring r) const
Definition: tropicalStrategy.cc:840
initial.h
tropicalStrategy::putUniformizingBinomialInFront
void putUniformizingBinomialInFront(ideal I, const ring r, const number q) const
Definition: tropicalStrategy.cc:387
tropicalStrategy::getOriginalRing
ring getOriginalRing() const
returns the polynomial ring over the field with valuation
Definition: tropicalStrategy.h:158
tropicalStrategy::computeWitness
ideal computeWitness(const ideal inJ, const ideal inI, const ideal I, const ring r) const
suppose w a weight in maximal groebner cone of > suppose I (initially) reduced standard basis w....
Definition: tropicalStrategy.cc:572
containsMonomial.h
tropicalStrategy::copyAndChangeCoefficientRing
ring copyAndChangeCoefficientRing(const ring r) const
Definition: tropicalStrategy.cc:562
tropicalStrategy::getStartingRing
ring getStartingRing() const
returns the polynomial ring over the valuation ring
Definition: tropicalStrategy.h:176
NULL
#define NULL
Definition: omList.c:10
tropicalStrategy::getExpectedAmbientDimension
int getExpectedAmbientDimension() const
Definition: tropicalStrategy.h:191
ideals.h
tropicalStrategy::onlyLowerHalfSpace
bool onlyLowerHalfSpace
true if valuation non-trivial, false otherwise
Definition: tropicalStrategy.h:78
adjustWeights.h
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
tropicalStrategy::getUniformizingParameter
number getUniformizingParameter() const
returns the uniformizing parameter in the valuation ring
Definition: tropicalStrategy.h:207
p
int p
Definition: cfModGcd.cc:4019
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
ipshell.h
id_Test
#define id_Test(A, lR)
Definition: simpleideals.h:80
n_Test
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:738
tropicalStrategy::startingIdeal
ideal startingIdeal
preimage of the input ideal under the map that sends t to the uniformizing parameter
Definition: tropicalStrategy.h:65
tropicalStrategy::computeFlip
std::pair< ideal, ring > computeFlip(const ideal Ir, const ring r, const gfan::ZVector &interiorPoint, const gfan::ZVector &facetNormal) const
given an interior point of a groebner cone computes the groebner cone adjacent to it
Definition: tropicalStrategy.cc:760
tropicalStrategy::shortcutRing
ring shortcutRing
polynomial ring over the residue field
Definition: tropicalStrategy.h:73
tropicalStrategy::~tropicalStrategy
~tropicalStrategy()
destructor
Definition: tropicalStrategy.cc:346
tropicalStrategy::getStartingIdeal
ideal getStartingIdeal() const
returns the input ideal
Definition: tropicalStrategy.h:185
tropicalStrategy
Definition: tropicalStrategy.h:36