1 | #ifndef KUTIL_H |
---|
2 | #define KUTIL_H |
---|
3 | /**************************************** |
---|
4 | * Computer Algebra System SINGULAR * |
---|
5 | ****************************************/ |
---|
6 | /* $Id: kutil.h,v 1.37 2000-10-26 06:39:29 obachman Exp $ */ |
---|
7 | /* |
---|
8 | * ABSTRACT: kernel: utils for kStd |
---|
9 | */ |
---|
10 | |
---|
11 | |
---|
12 | #include <string.h> |
---|
13 | #include "mod2.h" |
---|
14 | |
---|
15 | #include "structs.h" |
---|
16 | #include "omalloc.h" |
---|
17 | #include "ring.h" |
---|
18 | #include "pShallowCopyDelete.h" |
---|
19 | |
---|
20 | #define setmax 16 |
---|
21 | |
---|
22 | #undef NO_KINLINE |
---|
23 | #if !defined(KDEBUG) && !defined(NO_INLINE) |
---|
24 | #define KINLINE inline |
---|
25 | #else |
---|
26 | #define KINLINE |
---|
27 | #define NO_KINLINE 1 |
---|
28 | #endif |
---|
29 | |
---|
30 | typedef int* intset; |
---|
31 | |
---|
32 | class sTObject |
---|
33 | { |
---|
34 | public: |
---|
35 | poly p; // Lm(p) \in currRing Tail(p) \in tailRing |
---|
36 | poly t_p; // t_p \in tailRing |
---|
37 | ring tailRing; |
---|
38 | int ecart, length, pLength; |
---|
39 | poly max; // p_MaxExp(pNext(p)) |
---|
40 | unsigned long sev; |
---|
41 | |
---|
42 | |
---|
43 | // initialization |
---|
44 | KINLINE void Init(ring r = currRing); |
---|
45 | KINLINE sTObject(ring tailRing = currRing); |
---|
46 | KINLINE sTObject(poly p, ring tailRing = currRing); |
---|
47 | KINLINE sTObject(poly p, ring c_r, ring tailRing); |
---|
48 | KINLINE sTObject(sTObject* T, int copy); |
---|
49 | |
---|
50 | KINLINE void Set(ring r=currRing); |
---|
51 | KINLINE void Set(poly p_in, ring r=currRing); |
---|
52 | KINLINE void Set(poly p_in, ring c_r, ring t_r); |
---|
53 | |
---|
54 | KINLINE void sTObject::Delete(); |
---|
55 | |
---|
56 | // ring-dependent Lm access |
---|
57 | KINLINE poly GetLm(); // equivalent to GetLmCurrRing |
---|
58 | KINLINE poly GetLmCurrRing(); |
---|
59 | KINLINE poly GetLmTailRing(); |
---|
60 | KINLINE poly GetLm(ring r); |
---|
61 | |
---|
62 | // makes sure that T.p exists |
---|
63 | KINLINE void SetLmCurrRing(); |
---|
64 | |
---|
65 | // Iterations |
---|
66 | KINLINE void LmDeleteAndIter(); |
---|
67 | |
---|
68 | KINLINE int pFDeg(); |
---|
69 | |
---|
70 | // arithmetic |
---|
71 | KINLINE void Mult_nn(number n); |
---|
72 | KINLINE void ShallowCopyDelete(ring new_tailRing, omBin new_tailBin, |
---|
73 | pShallowCopyDeleteProc p_shallow_copy_delete); |
---|
74 | }; |
---|
75 | |
---|
76 | class sLObject : public sTObject |
---|
77 | { |
---|
78 | public: |
---|
79 | poly p1,p2; /*- the pair p comes from -*/ |
---|
80 | |
---|
81 | poly lcm; /*- the lcm of p1,p2 -*/ |
---|
82 | kBucket_pt bucket; |
---|
83 | |
---|
84 | // initialization |
---|
85 | KINLINE void Init(ring tailRing = currRing); |
---|
86 | KINLINE sLObject(ring tailRing = currRing); |
---|
87 | KINLINE sLObject(poly p, ring tailRing = currRing); |
---|
88 | KINLINE sLObject(poly p, ring c_r, ring tailRing); |
---|
89 | |
---|
90 | // Iterations |
---|
91 | KINLINE void LmDeleteAndIter(); |
---|
92 | |
---|
93 | // spoly related things |
---|
94 | KINLINE void SetLmTail(poly lm, poly new_p, int use_bucket, ring r); |
---|
95 | KINLINE void Tail_Minus_mm_Mult_qq(poly m, poly qq, int lq, poly spNoether); |
---|
96 | KINLINE void Tail_Mult_nn(number n); |
---|
97 | KINLINE poly GetP(omBin lmBin = NULL); |
---|
98 | KINLINE void CanonicalizeP(); |
---|
99 | |
---|
100 | KINLINE void ShallowCopyDelete(ring new_tailRing, |
---|
101 | pShallowCopyDeleteProc p_shallow_copy_delete); |
---|
102 | }; |
---|
103 | |
---|
104 | typedef class sTObject TObject; |
---|
105 | typedef class sLObject LObject; |
---|
106 | typedef TObject * TSet; |
---|
107 | typedef LObject * LSet; |
---|
108 | |
---|
109 | extern int HCord; |
---|
110 | |
---|
111 | class skStrategy; |
---|
112 | typedef skStrategy * kStrategy; |
---|
113 | class skStrategy |
---|
114 | { |
---|
115 | public: |
---|
116 | kStrategy next; |
---|
117 | int (*red)(LObject * L,kStrategy strat); |
---|
118 | void (*initEcart)(LObject * L); |
---|
119 | int (*posInT)(const TSet T,const int tl,const LObject &h); |
---|
120 | int (*posInL)(const LSet set, const int length, |
---|
121 | const LObject &L,const kStrategy strat); |
---|
122 | void (*enterS)(LObject h, int pos,kStrategy strat); |
---|
123 | void (*initEcartPair)(LObject * h, poly f, poly g, int ecartF, int ecartG); |
---|
124 | int (*posInLOld)(const LSet Ls,const int Ll, |
---|
125 | const LObject &Lo,const kStrategy strat); |
---|
126 | pFDegProc pOldFDeg; |
---|
127 | ideal Shdl; |
---|
128 | ideal D; /*V(S) is in D(D)*/ |
---|
129 | ideal M; /*set of minimal generators*/ |
---|
130 | polyset S; |
---|
131 | intset ecartS; |
---|
132 | intset fromQ; |
---|
133 | unsigned long* sevS; |
---|
134 | TSet T; |
---|
135 | LSet L; |
---|
136 | LSet B; |
---|
137 | poly kHEdge; |
---|
138 | poly kNoether; |
---|
139 | BOOLEAN * NotUsedAxis; |
---|
140 | LObject P; |
---|
141 | poly tail; |
---|
142 | leftv kIdeal; |
---|
143 | intvec * kModW; |
---|
144 | intvec * kHomW; |
---|
145 | BOOLEAN *pairtest;/*used for enterOnePair*/ |
---|
146 | int cp,c3; |
---|
147 | int sl,mu; |
---|
148 | int tl,tmax; |
---|
149 | int Ll,Lmax; |
---|
150 | int Bl,Bmax; |
---|
151 | int ak,LazyDegree,LazyPass; |
---|
152 | int syzComp; |
---|
153 | int HCord; |
---|
154 | int lastAxis; |
---|
155 | int newIdeal; |
---|
156 | int minim; |
---|
157 | BOOLEAN interpt; |
---|
158 | BOOLEAN homog; |
---|
159 | BOOLEAN kHEdgeFound; |
---|
160 | BOOLEAN honey,sugarCrit; |
---|
161 | BOOLEAN Gebauer,noTailReduction; |
---|
162 | BOOLEAN fromT; |
---|
163 | BOOLEAN noetherSet; |
---|
164 | BOOLEAN update; |
---|
165 | BOOLEAN posInLOldFlag; |
---|
166 | BOOLEAN use_buckets; |
---|
167 | ring tailRing; |
---|
168 | omBin lmBin; |
---|
169 | omBin tailBin; |
---|
170 | /*FALSE, if posInL == posInL10*/ |
---|
171 | char redTailChange; |
---|
172 | char news; |
---|
173 | char newt;/*used for messageSets*/ |
---|
174 | |
---|
175 | KINLINE skStrategy(); |
---|
176 | KINLINE ~skStrategy(); |
---|
177 | }; |
---|
178 | |
---|
179 | void deleteHC(poly *p, int *e, int *l, kStrategy strat); |
---|
180 | void deleteInS (int i,kStrategy strat); |
---|
181 | void cleanT (kStrategy strat); |
---|
182 | LSet initL (); |
---|
183 | void deleteInL(LSet set, int *length, int j,kStrategy strat); |
---|
184 | void enterL (LSet *set,int *length, int *LSetmax, LObject p,int at); |
---|
185 | void initEcartPairBba (LObject* Lp,poly f,poly g,int ecartF,int ecartG); |
---|
186 | void initEcartPairMora (LObject* Lp,poly f,poly g,int ecartF,int ecartG); |
---|
187 | int posInS (polyset set,int length,poly p); |
---|
188 | int posInT0 (const TSet set,const int length,const LObject &p); |
---|
189 | int posInT1 (const TSet set,const int length,const LObject &p); |
---|
190 | int posInT2 (const TSet set,const int length,const LObject &p); |
---|
191 | int posInT11 (const TSet set,const int length,const LObject &p); |
---|
192 | int posInT13 (const TSet set,const int length,const LObject &p); |
---|
193 | int posInT15 (const TSet set,const int length,const LObject &p); |
---|
194 | int posInT17 (const TSet set,const int length,const LObject &p); |
---|
195 | int posInT19 (const TSet set,const int length,const LObject &p); |
---|
196 | void reorderS (int* suc,kStrategy strat); |
---|
197 | int posInL0 (const LSet set, const int length, |
---|
198 | const LObject &L,const kStrategy strat); |
---|
199 | int posInL11 (const LSet set, const int length, |
---|
200 | const LObject &L,const kStrategy strat); |
---|
201 | int posInL13 (const LSet set, const int length, |
---|
202 | const LObject &L,const kStrategy strat); |
---|
203 | int posInL15 (const LSet set, const int length, |
---|
204 | const LObject &L,const kStrategy strat); |
---|
205 | int posInL17 (const LSet set, const int length, |
---|
206 | const LObject &L,const kStrategy strat); |
---|
207 | KINLINE poly redtailBba (poly p,int pos,kStrategy strat); |
---|
208 | poly redtailBba (LObject *L, int pos,kStrategy strat); |
---|
209 | poly redtailSyz (poly p,int pos,kStrategy strat); |
---|
210 | poly redtail (poly p,int pos,kStrategy strat); |
---|
211 | void enterpairs (poly h, int k, int ec, int pos,kStrategy strat); |
---|
212 | void entersets (LObject h); |
---|
213 | void pairs (); |
---|
214 | void message (int i,int* reduc,int* olddeg,kStrategy strat); |
---|
215 | void messageStat (int srmax,int lrmax,int hilbcount,kStrategy strat); |
---|
216 | void messageSets (kStrategy strat); |
---|
217 | void initEcartNormal (LObject* h); |
---|
218 | void initEcartBBA (LObject* h); |
---|
219 | void initS (ideal F, ideal Q,kStrategy strat); |
---|
220 | void initSL (ideal F, ideal Q,kStrategy strat); |
---|
221 | void updateS(BOOLEAN toT,kStrategy strat); |
---|
222 | void enterSBba (LObject p, int pos,kStrategy strat); |
---|
223 | void enterT (LObject p,kStrategy strat); |
---|
224 | void enterTBba (LObject p, int pos,kStrategy strat); |
---|
225 | void cancelunit (LObject* p); |
---|
226 | void HEckeTest (poly pp,kStrategy strat); |
---|
227 | void redtailS (poly* h,int maxIndex); |
---|
228 | void redtailMora (poly* h,int maxIndex); |
---|
229 | void initBuchMoraCrit(kStrategy strat); |
---|
230 | void initHilbCrit(ideal F, ideal Q, intvec **hilb,kStrategy strat); |
---|
231 | void initBuchMoraPos(kStrategy strat); |
---|
232 | void initBuchMora (ideal F, ideal Q,kStrategy strat); |
---|
233 | void exitBuchMora (kStrategy strat); |
---|
234 | void updateResult(ideal r,ideal Q,kStrategy strat); |
---|
235 | void completeReduce (kStrategy strat); |
---|
236 | void kFreeStrat(kStrategy strat); |
---|
237 | BOOLEAN homogTest(polyset F, int Fmax); |
---|
238 | BOOLEAN newHEdge(polyset S, int ak,kStrategy strat); |
---|
239 | |
---|
240 | /*************************************************************** |
---|
241 | * |
---|
242 | * stuff to be inlined |
---|
243 | * |
---|
244 | ***************************************************************/ |
---|
245 | |
---|
246 | KINLINE TSet initT (); |
---|
247 | KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin); |
---|
248 | KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin); |
---|
249 | KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin); |
---|
250 | KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing, omBin bin); |
---|
251 | |
---|
252 | KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing); |
---|
253 | KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing); |
---|
254 | KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing); |
---|
255 | KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing); |
---|
256 | |
---|
257 | // if exp bound is not violated, return TRUE and |
---|
258 | // get m1 = LCM(LM(p1), LM(p2))/LM(p1) |
---|
259 | // m2 = LCM(LM(p1), LM(p2))/LM(p2) |
---|
260 | // return FALSE and m1 == NULL, m2 == NULL , otherwise |
---|
261 | KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r, |
---|
262 | poly &m1, poly &m2, const ring m_r); |
---|
263 | #ifdef KDEBUG |
---|
264 | // test strat |
---|
265 | BOOLEAN kTest(kStrategy strat); |
---|
266 | // test strat, and test that S is contained in T |
---|
267 | BOOLEAN kTest_TS(kStrategy strat); |
---|
268 | // test LObject |
---|
269 | BOOLEAN kTest_L(LObject* L, ring tailRing = NULL, |
---|
270 | BOOLEAN testp = FALSE, int lpos = -1, |
---|
271 | TSet T = NULL, int tlength = -1); |
---|
272 | // test TObject |
---|
273 | BOOLEAN kTest_T(TObject* T, ring tailRing = NULL, int tpos = -1, char T = '?'); |
---|
274 | // test set strat->SevS |
---|
275 | BOOLEAN kTest_S(kStrategy strat); |
---|
276 | #else |
---|
277 | #define kTest(A) ((void)0) |
---|
278 | #define kTest_TS(A) ((void)0) |
---|
279 | #define kTest_T(T) ((void)0) |
---|
280 | #define kTest_S(T) ((void)0) |
---|
281 | #define kTest_L(T) ((void)0) |
---|
282 | #endif |
---|
283 | |
---|
284 | |
---|
285 | /*************************************************************** |
---|
286 | * |
---|
287 | * From kstd2.cc |
---|
288 | * |
---|
289 | ***************************************************************/ |
---|
290 | ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat); |
---|
291 | poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce); |
---|
292 | ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce); |
---|
293 | void initBba(ideal F,kStrategy strat); |
---|
294 | |
---|
295 | /*************************************************************** |
---|
296 | * |
---|
297 | * From kSpolys.cc |
---|
298 | * |
---|
299 | ***************************************************************/ |
---|
300 | // Reduces PR with PW |
---|
301 | // Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR) |
---|
302 | // Changes: PR |
---|
303 | // Const: PW |
---|
304 | // If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW) |
---|
305 | BOOLEAN ksReducePoly(LObject* PR, |
---|
306 | TObject* PW, |
---|
307 | poly spNoether = NULL, |
---|
308 | number *coef = NULL, |
---|
309 | kStrategy strat = NULL); |
---|
310 | |
---|
311 | // Reduces PR at Current->next with PW |
---|
312 | // Assumes PR != NULL, Current contained in PR |
---|
313 | // Current->next != NULL, LM(PW) devides LM(Current->next) |
---|
314 | // Changes: PR |
---|
315 | // Const: PW |
---|
316 | BOOLEAN ksReducePolyTail(LObject* PR, |
---|
317 | TObject* PW, |
---|
318 | poly Current, |
---|
319 | poly spNoether = NULL); |
---|
320 | |
---|
321 | // Creates S-Poly of Pair |
---|
322 | // Const: Pair->p1, Pair->p2 |
---|
323 | // Changes: Pair->p == S-Poly of p1, p2 |
---|
324 | // Assume: Pair->p1 != NULL && Pair->p2 |
---|
325 | void ksCreateSpoly(LObject* Pair, poly spNoether = NULL, |
---|
326 | int use_buckets=0, ring tailRing=currRing, |
---|
327 | poly m1 = NULL, poly m2 = NULL); |
---|
328 | |
---|
329 | |
---|
330 | /*2 |
---|
331 | * creates the leading term of the S-polynomial of p1 and p2 |
---|
332 | * do not destroy p1 and p2 |
---|
333 | * remarks: |
---|
334 | * 1. the coefficient is 0 (nNew) |
---|
335 | * 2. pNext is undefined |
---|
336 | */ |
---|
337 | poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing); |
---|
338 | |
---|
339 | |
---|
340 | /* |
---|
341 | * input - output: a, b |
---|
342 | * returns: |
---|
343 | * a := a/gcd(a,b), b := b/gcd(a,b) |
---|
344 | * and return value |
---|
345 | * 0 -> a != 1, b != 1 |
---|
346 | * 1 -> a == 1, b != 1 |
---|
347 | * 2 -> a != 1, b == 1 |
---|
348 | * 3 -> a == 1, b == 1 |
---|
349 | * this value is used to control the spolys |
---|
350 | */ |
---|
351 | int ksCheckCoeff(number *a, number *b); |
---|
352 | |
---|
353 | // old stuff |
---|
354 | KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether = NULL); |
---|
355 | KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether = NULL); |
---|
356 | KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether = NULL, ring r = currRing); |
---|
357 | KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r = currRing); |
---|
358 | |
---|
359 | /*************************************************************** |
---|
360 | * |
---|
361 | * Routines related for ring changes during std computations |
---|
362 | * |
---|
363 | ***************************************************************/ |
---|
364 | // return TRUE and set m1, m2 to k_GetLcmTerms, |
---|
365 | // if spoly creation of strat->P does not violate |
---|
366 | // exponent bound of strat->tailRing |
---|
367 | // FALSE, otherwise |
---|
368 | BOOLEAN kCheckSpolyCreation(kStrategy strat, poly &m1, poly &m2); |
---|
369 | // change the strat such that strat strat->tailRing == new_tailRing |
---|
370 | void kStratChangeTailRing(kStrategy strat, ring new_tailRing); |
---|
371 | // initiate a change of the tailRing of strat -- should be called |
---|
372 | // right before main loop in bba |
---|
373 | void kStratInitChangeTailRing(kStrategy strat); |
---|
374 | |
---|
375 | #include "kInline.cc" |
---|
376 | |
---|
377 | |
---|
378 | #endif |
---|