My Project
Loading...
Searching...
No Matches
containsMonomial.cc
Go to the documentation of this file.
1#include "kernel/polys.h"
3#include "polys/prCopy.h"
4
6#include "bbcone.h"
7#include "std_wrapper.h"
8
9poly checkForMonomialViaSuddenSaturation(const ideal I, const ring r)
10{
11 ring origin = currRing;
12 if (currRing != r)
14
15 ideal M = idInit(1);
16 M->m[0] = p_Init(r);
17 for (int i=1; i<=rVar(r); i++)
18 p_SetExp(M->m[0],i,1,r);
19 p_SetCoeff(M->m[0],n_Init(1,r->cf),r);
20 p_Setm(M->m[0],r); p_Test(M->m[0],r);
21
22 ideal J = id_Copy(I,r); bool b; int k = 0;
23 if (currRing != r) rChangeCurrRing(r);
24 intvec* nullVector = NULL;
25 do
26 {
27 ideal Jstd = kStd(J,currRing->qideal,testHomog,&nullVector);
28 ideal JquotM = idQuot(Jstd,M,true,true);
29 ideal JquotMredJ = kNF(Jstd,currRing->qideal,JquotM);
30 b = idIs0(JquotMredJ);
31 id_Delete(&Jstd,r);
32 id_Delete(&J,r);
33 J = JquotM;
34 id_Delete(&JquotMredJ,r);
35 k++;
36 } while (!b);
37
38 poly monom = NULL;
39 if (id_IsConstant(J,r))
40 {
41 monom = p_Init(r);
42 for (int i=1; i<=rVar(r); i++)
43 p_SetExp(monom,i,k,r);
44 p_SetCoeff(monom,n_Init(1,r->cf),r);
45 p_Setm(monom,r);
46 }
47 id_Delete(&M,r);
48 id_Delete(&J,r);
49
50 if (currRing != origin)
51 rChangeCurrRing(origin);
52 return monom;
53}
54
55poly searchForMonomialViaStepwiseSaturation(const ideal I, const ring r, const gfan::ZVector w0)
56{
57 gfan::ZVector w = w0;
58
59 ring origin = currRing;
60 if (currRing != r)
62
63 // copy ring including qideal but without ordering
64 // set ordering to be wp(w)
65 int n = rVar(r);
66 ring rGraded = rCopy0(r,TRUE,FALSE);
67 rGraded->order = (rRingOrder_t*) omAlloc0(3*sizeof(rRingOrder_t));
68 rGraded->block0 = (int*) omAlloc0(3*sizeof(int));
69 rGraded->block1 = (int*) omAlloc0(3*sizeof(int));
70 rGraded->wvhdl = (int**) omAlloc0(3*sizeof(int**));
71 rGraded->order[0] = ringorder_wp;
72 rGraded->block0[0] = 1;
73 rGraded->block1[0] = n;
74 bool overflow;
75 rGraded->wvhdl[0] = ZVectorToIntStar(w,overflow);
76 rGraded->order[1] = ringorder_C;
77 rComplete(rGraded);
78 rTest(rGraded);
79
80 // map I into the new ring so that it becomes a graded ideal
81 int k = IDELEMS(I);
82 nMapFunc identity = n_SetMap(r->cf,rGraded->cf);
83 ideal Jold = idInit(k);
84 for (int i=0; i<k; i++)
85 Jold->m[i] = p_PermPoly(I->m[i],NULL,r,rGraded,identity,NULL,0);
86
87 // compute std and check whether result contains a monomial,
88 // wrap up computation if it does
89 ideal Jnew = gfanlib_monomialabortStd_wrapper(Jold,rGraded);
90 id_Delete(&Jold,rGraded);
91 k = IDELEMS(Jnew);
92 for (int i=0; i<k; i++)
93 {
94 poly g = Jnew->m[i];
95 if (g!=NULL && pNext(g)==NULL && n_IsUnit(p_GetCoeff(g,r),r->cf))
96 {
97 poly monomial = p_One(r);
98 for (int j=1; j<=rVar(r); j++)
99 p_SetExp(monomial,j,p_GetExp(g,j,rGraded),r);
100 p_Setm(monomial,r);
101
102 id_Delete(&Jnew,rGraded);
103 rDelete(rGraded);
104 if (currRing != origin)
105 rChangeCurrRing(origin);
106 return monomial;
107 }
108 }
109
110 // prepare permutation to cycle all variables
111 int* cycleAllVariables = (int*) omAlloc0((n+1)*sizeof(int));
112 for (int i=1; i<n; i++)
113 cycleAllVariables[i]=i+1;
114 cycleAllVariables[n]=1;
115 // prepare storage of maximal powers that are being divided with
116 int* maxPowers = (int*) omAlloc0((n+1)*sizeof(int));
117
118 for(int currentSaturationVariable=n-1; currentSaturationVariable>0; currentSaturationVariable--)
119 {
120 // divide out the maximal power in the last variable,
121 // storing the maximum of all powers.
122 for (int i=0; i<k; i++)
123 {
124 poly g = Jnew->m[i];
125 int d = p_GetExp(g,n,rGraded);
126 if (d>0)
127 {
128 for (; g!=NULL; pIter(g))
129 {
130 p_SubExp(g,n,d,rGraded);
131 p_Setm(g,rGraded);
132 }
133 if (d>maxPowers[currentSaturationVariable+1])
134 maxPowers[currentSaturationVariable+1]=d;
135 }
136 }
137
138 // cycle all variables, i.e. x_1->x_2, x_2->x_3, ..., x_n->x_1
139 // so that a new variable is at the last position
140 gfan::Integer cache = w[n-1];
141 for (int i=n-1; i>0; i--)
142 w[i] = w[i-1];
143 w[0] = cache;
144
145 ring rGradedNew = rCopy0(r,FALSE,FALSE); // cannot copy q-ideal without ordering
146 rGradedNew->order = (rRingOrder_t*) omAlloc0(3*sizeof(rRingOrder_t));
147 rGradedNew->block0 = (int*) omAlloc0(3*sizeof(int));
148 rGradedNew->block1 = (int*) omAlloc0(3*sizeof(int));
149 rGradedNew->wvhdl = (int**) omAlloc0(3*sizeof(int**));
150 rGradedNew->order[0] = ringorder_wp;
151 rGradedNew->block0[0] = 1;
152 rGradedNew->block1[0] = n;
153 bool overflow;
154 rGradedNew->wvhdl[0] = ZVectorToIntStar(w,overflow);
155 rGradedNew->order[1] = ringorder_C;
156 rComplete(rGradedNew);
157 rTest(rGradedNew);
158
159 identity = n_SetMap(rGraded->cf,rGradedNew->cf);
160 Jold = idInit(k);
161 for (int i=0; i<k; i++)
162 Jold->m[i] = p_PermPoly(Jnew->m[i],cycleAllVariables,rGraded,rGradedNew,identity,NULL,0);
163 id_Delete(&Jnew,rGraded);
164 rDelete(rGraded);
165
166 rGraded = rGradedNew;
167 rGradedNew = NULL;
168
169 // compute std and check whether result contains a monomial,
170 // wrap up computation if it does
171 // adjust for the powers already divided out of the ideal
172 // and the shift of variables!
173 Jnew = gfanlib_monomialabortStd_wrapper(Jold,rGraded);
174 id_Delete(&Jold,rGraded);
175
176 k = IDELEMS(Jnew);
177 for (int i=0; i<k; i++)
178 {
179 poly g = Jnew->m[i];
180 if (g!=NULL && pNext(g)==NULL && n_IsUnit(p_GetCoeff(g,rGraded),rGraded->cf))
181 {
182 poly monomial = p_One(r);
183 for (int j=1; j<=rVar(r); j++)
184 {
185 int jDeshifted = (j-currentSaturationVariable)%n;
186 if (jDeshifted<=0) jDeshifted = jDeshifted+n;
187 p_SetExp(monomial,j,p_GetExp(g,jDeshifted,rGraded)+maxPowers[j],r);
188 }
189 p_Setm(monomial,r);
190
191 id_Delete(&Jnew,rGraded);
192 rDelete(rGraded);
193 omFree(cycleAllVariables);
194 omFree(maxPowers);
195 if (currRing != origin)
196 rChangeCurrRing(origin);
197 return monomial;
198 }
199 }
200 }
201
202 if (currRing != origin)
203 rChangeCurrRing(origin);
204
205 id_Delete(&Jnew,rGraded);
206 rDelete(rGraded);
207 omFree(cycleAllVariables);
208 omFree(maxPowers);
209 return NULL;
210}
211
213{
214 leftv u = args;
215 if ((u != NULL) && (u->Typ() == IDEAL_CMD))
216 {
217 ideal I; poly monom;
218 omUpdateInfo();
219 Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
220 I = (ideal) u->CopyD();
223 p_Delete(&monom,currRing);
224 omUpdateInfo();
225 Print("usedBytesAfter=%ld\n",om_Info.UsedBytes);
226 I = (ideal) u->Data();
227 res->rtyp = POLY_CMD;
229 return FALSE;
230 }
231 return TRUE;
232}
233
235{
236 leftv u = args;
237 if ((u != NULL) && (u->Typ() == IDEAL_CMD))
238 {
239 leftv v = u->next;
240 if ((v != NULL) && ((v->Typ() == BIGINTMAT_CMD) || (v->Typ() == INTVEC_CMD)))
241 {
242 ideal I = (ideal) u->Data();
243 bigintmat* w0=NULL;
244 if (v->Typ() == INTVEC_CMD)
245 {
246 intvec* w00 = (intvec*) v->Data();
247 bigintmat* w0t = iv2bim(w00,coeffs_BIGINT);
248 w0 = w0t->transpose();
249 delete w0t;
250 }
251 else
252 w0 = (bigintmat*) v->Data();
253 gfan::ZVector* w = bigintmatToZVector(w0);
254
255 res->rtyp = POLY_CMD;
257 delete w;
258 if (v->Typ() == INTVEC_CMD)
259 delete w0;
260
261 return FALSE;
262 }
263 }
264 WerrorS("searchForMonomialViaStepwiseSaturation: unexpected parameters");
265 return TRUE;
266}
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
bigintmat * iv2bim(intvec *b, const coeffs C)
Definition: bigintmat.cc:349
int * ZVectorToIntStar(const gfan::ZVector &v, bool &overflow)
gfan::ZVector * bigintmatToZVector(const bigintmat &bim)
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
g
Definition: cfModGcd.cc:4090
CanonicalForm b
Definition: cfModGcd.cc:4103
Matrices of numbers.
Definition: bigintmat.h:51
bigintmat * transpose()
Definition: bigintmat.cc:37
Definition: intvec.h:23
Class used for (list of) interpreter objects.
Definition: subexpr.h:83
void * CopyD(int t)
Definition: subexpr.cc:710
int Typ()
Definition: subexpr.cc:1019
void * Data()
Definition: subexpr.cc:1162
leftv next
Definition: subexpr.h:86
static FORCE_INLINE BOOLEAN n_IsUnit(number n, const coeffs r)
TRUE iff n has a multiplicative inverse in the given coeff field/ring r.
Definition: coeffs.h:512
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition: coeffs.h:697
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:535
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
poly searchForMonomialViaStepwiseSaturation(const ideal I, const ring r, const gfan::ZVector w0)
BOOLEAN checkForMonomial(leftv res, leftv args)
poly checkForMonomialViaSuddenSaturation(const ideal I, const ring r)
#define Print
Definition: emacs.cc:80
CanonicalForm res
Definition: facAbsFact.cc:60
const CanonicalForm & w
Definition: facAbsFact.cc:51
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
int j
Definition: facHensel.cc:110
void WerrorS(const char *s)
Definition: feFopen.cc:24
@ IDEAL_CMD
Definition: grammar.cc:284
@ BIGINTMAT_CMD
Definition: grammar.cc:278
@ POLY_CMD
Definition: grammar.cc:289
ideal idQuot(ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN resultIsIdeal)
Definition: ideals.cc:1494
ideal id_Copy(ideal h1, const ring r)
copy an ideal
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
VAR coeffs coeffs_BIGINT
Definition: ipid.cc:50
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3182
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:2447
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
#define p_GetCoeff(p, r)
Definition: monomials.h:50
#define omFree(addr)
Definition: omAllocDecl.h:261
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define NULL
Definition: omList.c:12
omInfo_t om_Info
Definition: omStats.c:16
poly p_PermPoly(poly p, const int *perm, const ring oldRing, const ring dst, nMapFunc nMap, const int *par_perm, int OldPar, BOOLEAN use_mult)
Definition: p_polys.cc:4130
poly p_One(const ring r)
Definition: p_polys.cc:1313
static long p_SubExp(poly p, int v, long ee, ring r)
Definition: p_polys.h:611
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition: p_polys.h:486
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:231
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:410
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition: p_polys.h:467
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:899
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1318
#define p_Test(p, r)
Definition: p_polys.h:159
void rChangeCurrRing(ring r)
Definition: polys.cc:15
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
Compatibility layer for legacy polynomial operations (over currRing)
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:3450
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
Definition: ring.cc:1421
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:450
rRingOrder_t
order stuff
Definition: ring.h:68
@ ringorder_C
Definition: ring.h:73
@ ringorder_wp
Definition: ring.h:81
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:592
#define rTest(r)
Definition: ring.h:782
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
BOOLEAN id_IsConstant(ideal id, const ring r)
test if the ideal has only constant polynomials NOTE: zero ideal/module is also constant
#define IDELEMS(i)
Definition: simpleideals.h:23
#define M
Definition: sirandom.c:25
ideal gfanlib_monomialabortStd_wrapper(ideal I, ring r, tHomog h=testHomog)
Definition: std_wrapper.cc:172
@ testHomog
Definition: structs.h:38
@ INTVEC_CMD
Definition: tok.h:101
#define omUpdateInfo()
Definition: xalloc.h:230