containsMonomial.cc
Go to the documentation of this file.
1 #include <bbcone.h>
2 #include <kernel/polys.h>
4 #include <polys/prCopy.h>
5 
6 poly checkForMonomialViaSuddenSaturation(const ideal I, const ring r)
7 {
8  ring origin = currRing;
9  if (currRing != r)
10  rChangeCurrRing(r);
11 
12  ideal M = idInit(1);
13  M->m[0] = p_Init(r);
14  for (int i=1; i<=rVar(r); i++)
15  p_SetExp(M->m[0],i,1,r);
16  p_SetCoeff(M->m[0],n_Init(1,r->cf),r);
17  p_Setm(M->m[0],r); p_Test(M->m[0],r);
18 
19  ideal J = id_Copy(I,r); bool b; int k = 0;
20  if (currRing != r) rChangeCurrRing(r);
21  intvec* nullVector = NULL;
22  do
23  {
24  ideal Jstd = kStd(J,currRing->qideal,testHomog,&nullVector);
25  ideal JquotM = idQuot(Jstd,M,true,true);
26  ideal JquotMredJ = kNF(Jstd,currRing->qideal,JquotM);
27  b = idIs0(JquotMredJ);
28  id_Delete(&Jstd,r);
29  id_Delete(&J,r);
30  J = JquotM;
31  id_Delete(&JquotMredJ,r);
32  k++;
33  } while (!b);
34 
35  poly monom = NULL;
36  if (id_IsConstant(J,r))
37  {
38  monom = p_Init(r);
39  for (int i=1; i<=rVar(r); i++)
40  p_SetExp(monom,i,k,r);
41  p_SetCoeff(monom,n_Init(1,r->cf),r);
42  p_Setm(monom,r);
43  }
44  id_Delete(&M,r);
45  id_Delete(&J,r);
46 
47  if (currRing != origin)
48  rChangeCurrRing(origin);
49  return monom;
50 }
51 
52 
54 {
55  leftv u = args;
56  if ((u != NULL) && (u->Typ() == IDEAL_CMD))
57  {
58  ideal I; poly monom;
59  omUpdateInfo();
60  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
61  I = (ideal) u->CopyD();
63  id_Delete(&I,currRing);
64  p_Delete(&monom,currRing);
65  omUpdateInfo();
66  Print("usedBytesAfter=%ld\n",om_Info.UsedBytes);
67  I = (ideal) u->Data();
68  res->rtyp = POLY_CMD;
70  return FALSE;
71  }
72  return TRUE;
73 }
74 
75 #if 0
76 // /***
77 // * Creates an int* representing the transposition of the last two variables
78 // **/
79 // static inline int* createPermutationVectorForSaturation(static const ring &r)
80 // {
81 // int* w = (int*) omAlloc0((rVar(r)+1)*sizeof(int));
82 // for (int i=1; i<=rVar(r)-2; i++)
83 // w[i] = i;
84 // w[rVar(r)-1] = rVar(r);
85 // w[rVar(r)] = rVar(r)-1;
86 // }
87 
88 
89 /***
90  * Creates an int* representing the permutation
91  * 1 -> 1, ..., i-1 -> i-1, i -> n, i+1 -> n-1, ... , n -> i
92  **/
93 static inline int* createPermutationVectorForSaturation(const ring &r, const int i)
94 {
95  int* sigma = (int*) omAlloc0((rVar(r)+1)*sizeof(int));
96  int j;
97  for (j=1; j<i; j++)
98  sigma[j] = j;
99  for (; j<=rVar(r); j++)
100  sigma[j] = rVar(r)-j+i;
101  return(sigma);
102 }
103 
104 
105 /***
106  * Changes the int* representing the permutation
107  * 1 -> 1, ..., i -> i, i+1 -> n, i+2 -> n-1, ... , n -> i+1
108  * to an int* representing the permutation
109  * 1 -> 1, ..., i-1 -> i-1, i -> n, i+1 -> n-1, ... , n -> i
110  **/
111 static void changePermutationVectorForSaturation(int* sigma, const ring &r, const int i)
112 {
113  for (int j=i; j<rVar(r); j++)
114  sigma[j] = rVar(r)-j+i;
115  sigma[rVar(r)] = i;
116 }
117 
118 
119 /***
120  * returns a ring in which the weights of the ring variables are permuted
121  * if handed over a poly in which the variables are permuted, this is basically
122  * as good as permuting the variables of the ring itself.
123  **/
124 static ring permuteWeighstOfRingVariables(const ring &r, const int* const sigma)
125 {
126  ring s = rCopy0(r);
127  for (int j=0; j<rVar(r); j++)
128  {
129  s->wvhdl[0][j] = r->wvhdl[0][sigma[j+1]];
130  s->wvhdl[1][j] = r->wvhdl[1][sigma[j+1]];
131  }
132  rComplete(s,1);
133  rTest(s);
134  return s;
135 }
136 
137 
138 /***
139  * creates a ring s that is a copy of r except with ordering wp(w)
140  **/
141 static inline ring createInitialRingForSaturation(const ring &r, const gfan::ZVector &w, bool &ok)
142 {
143  assume(rVar(r) == (int) w.size());
144 
145  ring s = rCopy0(r); int i;
146  for (i=0; s->order[i]; i++)
147  omFreeSize(s->wvhdl[i],rVar(r)*sizeof(int));
148  i++;
149  omFreeSize(s->order,i*sizeof(int));
150  s->order = (int*) omAlloc0(3*sizeof(int));
151  omFreeSize(s->block0,i*sizeof(int));
152  s->block0 = (int*) omAlloc0(3*sizeof(int));
153  omFreeSize(s->block1,i*sizeof(int));
154  s->block1 = (int*) omAlloc0(3*sizeof(int));
155  omFreeSize(s->wvhdl,i*sizeof(int*));
156  s->wvhdl = (int**) omAlloc0(3*sizeof(int*));
157 
158  s->order[0] = ringorder_wp;
159  s->block0[0] = 1;
160  s->block1[0] = rVar(r);
161  s->wvhdl[0] = ZVectorToIntStar(w,ok);
162  s->order[1]=ringorder_C;
163 
164  rComplete(s,1);
165  rTest(s);
166  return s;
167 }
168 
169 
170 /***
171  * Given an weighted homogeneous ideal I with respect to weight w
172  * that in standard basis form with respect to the ordering ws(-w),
173  * derives the standard basis of I:<x_n>^\infty
174  * and returns a long k such that I:<x_n>^\infty=I:<x_n>^k
175  **/
176 static long deriveStandardBasisOfSaturation(ideal &I, ring &r)
177 {
178  long k=0, l; poly current;
179  for (int i=0; i<IDELEMS(I); i++)
180  {
181  current = I->m[i];
182  l = p_GetExp(current,rVar(r),r);
183  if (k<l) k=l;
184  while (current)
185  {
186  p_SubExp(current,rVar(r),l,r); p_Setm(current,r);
187  pIter(current);
188  }
189  }
190  return k;
191 }
192 
193 
194 /***
195  * Given a weighted homogeneous ideal I with respect to weight w
196  * with constant first element,
197  * returns NULL if I does not contain a monomial
198  * otherwise returns the monomial contained in I
199  **/
200 poly checkForMonomialsViaStepwiseSaturation(const ideal &I, const gfan::ZVector &w)
201 {
202  // assume(rField_is_Ring_Z(currRing));
203 
204  // first we switch to the ground field currRing->cf / I->m[0]
205  ring r = rCopy0(currRing);
206  nKillChar(r->cf);
207  r->cf = nInitChar(n_Zp,(void*)(long)n_Int(p_GetCoeff(I->m[0],currRing),currRing->cf));
208  rComplete(r);
209  rTest(r);
210 
211  ideal J = id_Copy(I, currRing); poly cache; number temp;
212  for (int i=0; i<IDELEMS(I); i++)
213  {
214  cache = J->m[i];
215  while (cache)
216  {
217  // TODO: temp = npMapGMP(p_GetCoeff(cache,currRing),currRing->cf,r->cf);
218  p_SetCoeff(cache,temp,r); pIter(cache);
219  }
220  }
221 
222  J = kStd(J,NULL,isHomog,NULL);
223 
224  bool b = false;
225  ring s = createInitialRingForSaturation(currRing, w, b);
226  if (b)
227  {
228  WerrorS("containsMonomial: overflow in weight vector");
229  return NULL;
230  }
231 
232  return NULL;
233 }
234 #endif //0
const CanonicalForm int s
Definition: facAbsFact.cc:55
BOOLEAN checkForMonomial(leftv res, leftv args)
Class used for (list of) interpreter objects.
Definition: subexpr.h:83
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2815
#define Print
Definition: emacs.cc:83
#define FALSE
Definition: auxiliary.h:140
Compatiblity layer for legacy polynomial operations (over currRing)
ideal id_Copy(ideal h1, const ring r)
copy an ideal
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:539
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
{p < 2^31}
Definition: coeffs.h:30
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:540
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
#define TRUE
Definition: auxiliary.h:144
BOOLEAN id_IsConstant(ideal id, const ring r)
test if the ideal has only constant polynomials NOTE: zero ideal/module is also constant ...
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition: kstd1.cc:2221
int * ZVectorToIntStar(const gfan::ZVector &v, bool &overflow)
void WerrorS(const char *s)
Definition: feFopen.cc:24
int k
Definition: cfEzgcd.cc:93
int Typ()
Definition: subexpr.cc:969
ideal idQuot(ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN resultIsIdeal)
Definition: ideals.cc:1307
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:401
static long p_SubExp(poly p, int v, long ee, ring r)
Definition: p_polys.h:609
void * data
Definition: subexpr.h:89
#define pIter(p)
Definition: monomials.h:44
poly res
Definition: myNF.cc:322
#define M
Definition: sirandom.c:24
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:12
const ring r
Definition: syzextra.cc:208
Definition: intvec.h:16
static FORCE_INLINE long n_Int(number &n, const coeffs r)
conversion of n to an int; 0 if not possible in Z/pZ: the representing int lying in (-p/2 ...
Definition: coeffs.h:548
BOOLEAN rComplete(ring r, int force)
this needs to be called whenever a new ring is created: new fields in ring are created (like VarOffse...
Definition: ring.cc:3436
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:465
int j
Definition: myNF.cc:70
omInfo_t om_Info
Definition: omStats.c:13
#define assume(x)
Definition: mod2.h:405
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
Definition: ring.cc:1318
#define rTest(r)
Definition: ring.h:781
poly checkForMonomialViaSuddenSaturation(const ideal I, const ring r)
int i
Definition: cfEzgcd.cc:123
#define IDELEMS(i)
Definition: simpleideals.h:24
#define p_Test(p, r)
Definition: p_polys.h:160
void rChangeCurrRing(ring r)
Definition: polys.cc:14
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:850
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:484
#define NULL
Definition: omList.c:10
void omUpdateInfo()
Definition: omStats.c:24
const CanonicalForm & w
Definition: facAbsFact.cc:55
int rtyp
Definition: subexpr.h:92
void * Data()
Definition: subexpr.cc:1111
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:436
#define p_GetCoeff(p, r)
Definition: monomials.h:57
polyrec * poly
Definition: hilb.h:10
int BOOLEAN
Definition: auxiliary.h:131
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1248
const poly b
Definition: syzextra.cc:213
void nKillChar(coeffs r)
undo all initialisations
Definition: numbers.cc:488
void * CopyD(int t)
Definition: subexpr.cc:676
#define omAlloc0(size)
Definition: omAllocDecl.h:211
int l
Definition: cfEzgcd.cc:94
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:327