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 idSize
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 #ifndef NDEBUG
138  static tropicalStrategy debugStrategy(const ideal startIdeal, number unifParameter, ring startRing);
139 #endif
140 
141  /**
142  * destructor
143  */
145  /**
146  * assignment operator
147  **/
148  tropicalStrategy& operator=(const tropicalStrategy& currentStrategy);
149 
150  bool isValuationTrivial() const
151  {
152  bool b = (uniformizingParameter==NULL);
153  return b;
154  }
156  {
157  bool b = (uniformizingParameter!=NULL);
158  return b;
159  }
160 
161  /**
162  * returns the polynomial ring over the field with valuation
163  */
164  ring getOriginalRing() const
165  {
166  rTest(originalRing);
167  return originalRing;
168  }
169 
170  /**
171  * returns the input ideal over the field with valuation
172  */
173  ideal getOriginalIdeal() const
174  {
175  if (originalIdeal) id_Test(originalIdeal,originalRing);
176  return originalIdeal;
177  }
178 
179  /**
180  * returns the polynomial ring over the valuation ring
181  */
182  ring getStartingRing() const
183  {
184  if (startingRing) rTest(startingRing);
185  return startingRing;
186  }
187 
188  /**
189  * returns the input ideal
190  */
191  ideal getStartingIdeal() const
192  {
193  if (startingIdeal) id_Test(startingIdeal,startingRing);
194  return startingIdeal;
195  }
196 
198  {
199  return rVar(startingRing);
200  }
201 
202  /**
203  * returns the expected Dimension of the polyhedral output
204  */
206  {
207  return expectedDimension;
208  }
209 
210  /**
211  * returns the uniformizing parameter in the valuation ring
212  */
214  {
215  if (uniformizingParameter) n_Test(uniformizingParameter,startingRing->cf);
216  return uniformizingParameter;
217  }
218 
219  ring getShortcutRing() const
220  {
221  if (shortcutRing) rTest(shortcutRing);
222  return shortcutRing;
223  }
224 
225  /**
226  * returns the homogeneity space of the preimage ideal
227  */
228  gfan::ZCone getHomogeneitySpace() const
229  {
230  return linealitySpace;
231  }
232 
233  /**
234  * returns true, if v is contained in the homogeneity space; false otherwise
235  */
236  bool homogeneitySpaceContains(const gfan::ZVector &v) const
237  {
238  return linealitySpace.contains(v);
239  }
240 
241  /**
242  * returns true, if valuation non-trivial, false otherwise
243  */
245  {
246  return onlyLowerHalfSpace;
247  }
248 
249  /**
250  * Given weight w, returns a strictly positive weight u such that an ideal satisfying
251  * the valuation-sepcific homogeneity conditions is weighted homogeneous with respect to w
252  * if and only if it is homogeneous with respect to u
253  */
254  gfan::ZVector adjustWeightForHomogeneity(gfan::ZVector w) const
255  {
256  return this->weightAdjustingAlgorithm1(w);
257  }
258 
259  /**
260  * Given strictly positive weight w and weight v,
261  * returns a strictly positive weight u such that on an ideal that is weighted homogeneous
262  * with respect to w the weights u and v coincide
263  */
264  gfan::ZVector adjustWeightUnderHomogeneity(gfan::ZVector v, gfan::ZVector w) const
265  {
266  return this->weightAdjustingAlgorithm2(v,w);
267  }
268 
269  gfan::ZVector negateWeight(const gfan::ZVector &w) const
270  {
271  gfan::ZVector wNeg(w.size());
272 
273  if (this->isValuationNonTrivial())
274  {
275  wNeg[0]=w[0];
276  for (unsigned i=1; i<w.size(); i++)
277  wNeg[i]=w[i];
278  }
279  else
280  wNeg = -w;
281 
282  return wNeg;
283  }
284 
285  /**
286  * If valuation trivial, returns a copy of r with a positive weight prepended,
287  * such that any ideal homogeneous with respect to w is homogeneous with respect to that weight.
288  * If valuation non-trivial, changes the coefficient ring to the residue field.
289  */
290  ring getShortcutRingPrependingWeight(const ring r, const gfan::ZVector &w) const;
291 
292  /**
293  * reduces the generators of an ideal I so that
294  * the inequalities and equations of the Groebner cone can be read off.
295  */
296  bool reduce(ideal I, const ring r) const;
297 
298  void pReduce(ideal I, const ring r) const;
299 
300  /**
301  * If given w, assuming w is in the Groebner cone of the ordering on r
302  * and I is a standard basis with respect to that ordering,
303  * checks whether the initial ideal of I with respect to w contains a monomial.
304  * If no w is given, assuming that I is already an initial form of some ideal,
305  * checks whether I contains a monomial.
306  * In both cases returns a monomial, if it contains one, returns NULL otherwise.
307  **/
308  std::pair<poly,int> checkInitialIdealForMonomial(const ideal I, const ring r, const gfan::ZVector &w=0) const;
309 
310  /**
311  * given generators of the initial ideal, computes its standard basis
312  */
313  ideal computeStdOfInitialIdeal(const ideal inI, const ring r) const;
314 
315  /**
316  * suppose w a weight in maximal groebner cone of >
317  * suppose I (initially) reduced standard basis w.r.t. > and inI initial forms of its elements w.r.t. w
318  * suppose inJ elements of initial ideal that are homogeneous w.r.t w
319  * returns J elements of ideal whose initial form w.r.t. w are inI
320  * in particular, if w lies also inthe maximal groebner cone of another ordering >'
321  * and inJ is a standard basis of the initial ideal w.r.t. >'
322  * then the returned J will be a standard baiss of the ideal w.r.t. >'
323  */
324  ideal computeWitness(const ideal inJ, const ideal inI, const ideal I, const ring r) const;
325 
326  ideal computeLift(const ideal inJs, const ring s, const ideal inIr, const ideal Ir, const ring r) const;
327 
328  /**
329  * given an interior point of a groebner cone
330  * computes the groebner cone adjacent to it
331  */
332  std::pair<ideal,ring> computeFlip(const ideal Ir, const ring r, const gfan::ZVector &interiorPoint, const gfan::ZVector &facetNormal) const;
333 };
334 
335 #ifndef NDEBUG
338 #endif
339 
340 #endif
ring getOriginalRing() const
returns the polynomial ring over the field with valuation
const CanonicalForm int s
Definition: facAbsFact.cc:55
int findPositionOfUniformizingBinomial(const ideal I, const ring r) const
ideal getOriginalIdeal() const
returns the input ideal over the field with valuation
Class used for (list of) interpreter objects.
Definition: subexpr.h:83
bool isValuationNonTrivial() const
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...
bool(* redAlg)(ideal, ring, number)
return P p
Definition: myNF.cc:203
#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:537
void pReduce(ideal I, const ring r) 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 ...
bool onlyLowerHalfSpace
true if valuation non-trivial, false otherwise
gfan::ZVector negateWeight(const gfan::ZVector &w) const
static tropicalStrategy debugStrategy(const ideal startIdeal, number unifParameter, ring startRing)
ring getStartingRing() const
returns the polynomial ring over the valuation ring
int getExpectedDimension() const
returns the expected Dimension of the polyhedral output
ideal startingIdeal
preimage of the input ideal under the map that sends t to the uniformizing parameter ...
~tropicalStrategy()
destructor
poly res
Definition: myNF.cc:322
ring copyAndChangeCoefficientRing(const ring r) const
number getUniformizingParameter() const
returns the uniformizing parameter in the valuation ring
const ring r
Definition: syzextra.cc:208
ideal originalIdeal
input ideal, assumed to be a homogeneous prime ideal
ring getShortcutRing() const
ideal computeStdOfInitialIdeal(const ideal inI, const ring r) const
given generators of the initial ideal, computes its standard basis
ring shortcutRing
polynomial ring over the residue field
ideal getStartingIdeal() const
returns the input ideal
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 ...
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...
#define n_Test(a, r)
BOOLEAN n_Test(number a, const coeffs r)
Definition: coeffs.h:739
#define rTest(r)
Definition: ring.h:778
bool homogeneitySpaceContains(const gfan::ZVector &v) const
returns true, if v is contained in the homogeneity space; false otherwise
int getExpectedAmbientDimension() const
void putUniformizingBinomialInFront(ideal I, const ring r, const number q) const
ring copyAndChangeOrderingWP(const ring r, const gfan::ZVector &w, const gfan::ZVector &v) const
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...
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...
gfan::ZCone getHomogeneitySpace() const
returns the homogeneity space of the preimage ideal
bool restrictToLowerHalfSpace() const
returns true, if valuation non-trivial, false otherwise
gfan::ZVector adjustWeightForHomogeneity(gfan::ZVector w) const
Given weight w, returns a strictly positive weight u such that an ideal satisfying the valuation-sepc...
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
#define NULL
Definition: omList.c:10
ring copyAndChangeOrderingLS(const ring r, const gfan::ZVector &w, const gfan::ZVector &v) const
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...
bool checkForUniformizingBinomial(const ideal I, const ring r) const
if valuation non-trivial, checks whether the generating system contains p-t otherwise returns true ...
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...
const CanonicalForm & w
Definition: facAbsFact.cc:55
ideal computeLift(const ideal inJs, const ring s, const ideal inIr, const ideal Ir, const ring r) const
BOOLEAN computeFlipDebug(leftv res, leftv args)
ring originalRing
polynomial ring over a field with valuation
gfan::ZVector(* wAdjAlg2)(gfan::ZVector, gfan::ZVector)
int BOOLEAN
Definition: auxiliary.h:131
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.
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(* weightAdjustingAlgorithm1)(const gfan::ZVector &w)
A function such that: Given weight w, returns a strictly positive weight u such that an ideal satisfy...
BOOLEAN computeWitnessDebug(leftv res, leftv args)
bool isValuationTrivial() const