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