My Project
kstd1.cc
Go to the documentation of this file.
1/****************************************
2* Computer Algebra System SINGULAR *
3****************************************/
4/*
5* ABSTRACT:
6*/
7
8// TODO: why the following is here instead of mod2.h???
9
10
11// define if buckets should be used
12#define MORA_USE_BUCKETS
13
14#define PRE_INTEGER_CHECK 0
15
16#include "kernel/mod2.h"
17
18#include "misc/options.h"
19#include "misc/intvec.h"
20
21#include "polys/weight.h"
22#include "kernel/polys.h"
23
28#include "kernel/ideals.h"
29
30//#include "ipprint.h"
31
32#ifdef HAVE_PLURAL
33#include "polys/nc/nc.h"
34#include "polys/nc/sca.h"
35#include "kernel/GBEngine/nc.h"
36#endif
37
39
40#ifdef HAVE_SHIFTBBA
41#include "polys/shiftop.h"
42#endif
43
44/* the list of all options which give a warning by test */
46 |Sy_bit(OPT_REDSB) /* 1 */
47 |Sy_bit(OPT_NOT_SUGAR) /* 3 */
48 |Sy_bit(OPT_INTERRUPT) /* 4 */
49 |Sy_bit(OPT_SUGARCRIT) /* 5 */
52 |Sy_bit(OPT_FASTHC) /* 10 */
53 |Sy_bit(OPT_INTSTRATEGY) /* 26 */
54 |Sy_bit(OPT_INFREDTAIL) /* 28 */
55 |Sy_bit(OPT_NOTREGULARITY) /* 30 */
56 |Sy_bit(OPT_WEIGHTM); /* 31 */
57
58/* the list of all options which may be used by option and test */
59/* definition of ALL options: libpolys/misc/options.h */
61 |Sy_bit(1)
62 |Sy_bit(2) // obachman 10/00: replaced by notBucket
63 |Sy_bit(3)
64 |Sy_bit(4)
65 |Sy_bit(5)
66 |Sy_bit(6)
67// |Sy_bit(7) obachman 11/00 tossed: 12/00 used for redThrough
68 |Sy_bit(7) // OPT_REDTHROUGH
69 |Sy_bit(8) // obachman 11/00 tossed -> motsak 2011 experimental: OPT_NO_SYZ_MINIM
70 |Sy_bit(9)
71 |Sy_bit(10)
72 |Sy_bit(11)
73 |Sy_bit(12)
74 |Sy_bit(13)
75 |Sy_bit(14)
76 |Sy_bit(15)
77 |Sy_bit(16)
78 |Sy_bit(17)
79 |Sy_bit(18)
80 |Sy_bit(19)
81// |Sy_bit(20) obachman 11/00 tossed: 12/00 used for redOldStd
83 |Sy_bit(21)
84 |Sy_bit(22)
85 /*|Sy_bit(23)*/
86 /*|Sy_bit(24)*/
89 |Sy_bit(27)
90 |Sy_bit(28)
91 |Sy_bit(29)
92 |Sy_bit(30)
93 |Sy_bit(31);
94
95//static BOOLEAN posInLOldFlag;
96 /*FALSE, if posInL == posInL10*/
97// returns TRUE if mora should use buckets, false otherwise
98static BOOLEAN kMoraUseBucket(kStrategy strat);
99
100static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
101{
102// if (strat->ak == 0 && !rIsSyzIndexRing(currRing))
103 strat->length_pLength = TRUE;
104// else
105// strat->length_pLength = FALSE;
106
107 if ((ldeg == pLDeg0c /*&& !rIsSyzIndexRing(currRing)*/) ||
108 (ldeg == pLDeg0 && strat->ak == 0))
109 {
110 strat->LDegLast = TRUE;
111 }
112 else
113 {
114 strat->LDegLast = FALSE;
115 }
116}
117
118
119static int doRed (LObject* h, TObject* with,BOOLEAN intoT,kStrategy strat, bool redMoraNF)
120{
121 int ret;
122#if KDEBUG > 0
123 kTest_L(h);
124 kTest_T(with);
125#endif
126 // Hmmm ... why do we do this -- polys from T should already be normalized
128 with->pNorm();
129#ifdef KDEBUG
130 if (TEST_OPT_DEBUG)
131 {
132 PrintS("reduce ");h->wrp();PrintS(" with ");with->wrp();PrintLn();
133 }
134#endif
135 if (intoT)
136 {
137 // need to do it exactly like this: otherwise
138 // we might get errors
139 LObject L= *h;
140 L.Copy();
141 h->GetP();
142 h->length=h->pLength=pLength(h->p);
143 ret = ksReducePoly(&L, with, strat->kNoetherTail(), NULL, NULL, strat);
144 if (ret)
145 {
146 if (ret < 0) return ret;
147 if (h->tailRing != strat->tailRing)
148 h->ShallowCopyDelete(strat->tailRing,
150 strat->tailRing));
151 }
153 enterT_strong(*h,strat);
154 else
155 enterT(*h,strat);
156 *h = L;
157 }
158 else
159 ret = ksReducePoly(h, with, strat->kNoetherTail(), NULL, NULL, strat);
160#ifdef KDEBUG
161 if (TEST_OPT_DEBUG)
162 {
163 PrintS("to ");h->wrp();PrintLn();
164 }
165#endif
166 return ret;
167}
168
170{
171 int i,at,ei,li,ii;
172 int j = 0;
173 int pass = 0;
174 long d,reddeg;
175
176 d = h->GetpFDeg()+ h->ecart;
177 reddeg = strat->LazyDegree+d;
178 h->SetShortExpVector();
179 loop
180 {
181 j = kFindDivisibleByInT(strat, h);
182 if (j < 0)
183 {
184 if (strat->honey) h->SetLength(strat->length_pLength);
185 return 1;
186 }
187
188 ei = strat->T[j].ecart;
189 ii = j;
190
191 if (ei > h->ecart && ii < strat->tl)
192 {
193 unsigned long not_sev=~h->sev;
194 poly h_t= h->GetLmTailRing();
195 li = strat->T[j].length;
196 if (li<=0) li=strat->T[j].GetpLength();
197 // the polynomial to reduce with (up to the moment) is;
198 // pi with ecart ei and length li
199 // look for one with smaller ecart
200 i = j;
201 loop
202 {
203 /*- takes the first possible with respect to ecart -*/
204 i++;
205#if 1
206 if (i > strat->tl) break;
207 if (strat->T[i].length<=0) strat->T[i].GetpLength();
208 if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
209 strat->T[i].length < li))
210 &&
211 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h_t, not_sev, strat->tailRing))
212#else
213 j = kFindDivisibleByInT(strat, h, i);
214 if (j < 0) break;
215 i = j;
216 if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
217 strat->T[i].length < li))
218#endif
219 {
220 // the polynomial to reduce with is now
221 ii = i;
222 ei = strat->T[i].ecart;
223 if (ei <= h->ecart) break;
224 li = strat->T[i].length;
225 }
226 }
227 }
228
229 // end of search: have to reduce with pi
230 if (ei > h->ecart)
231 {
232 // It is not possible to reduce h with smaller ecart;
233 // if possible h goes to the lazy-set L,i.e
234 // if its position in L would be not the last one
235 strat->fromT = TRUE;
236 if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
237 {
238 h->SetLmCurrRing();
239 if (strat->honey && strat->posInLDependsOnLength)
240 h->SetLength(strat->length_pLength);
241 assume(h->FDeg == h->pFDeg());
242 at = strat->posInL(strat->L,strat->Ll,h,strat);
243 if (at <= strat->Ll)
244 {
245 /*- h will not become the next element to reduce -*/
246 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
247#ifdef KDEBUG
248 if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
249#endif
250 h->Clear();
251 strat->fromT = FALSE;
252 return -1;
253 }
254 }
255 }
256
257 // now we finally can reduce
258 doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
259 strat->fromT=FALSE;
260
261 // are we done ???
262 if (h->IsNull())
263 {
265 kDeleteLcm(h);
266 h->Clear();
267 return 0;
268 }
269 if (TEST_OPT_IDLIFT)
270 {
271 if (h->p!=NULL)
272 {
273 if(p_GetComp(h->p,currRing)>strat->syzComp)
274 {
275 h->Delete();
276 return 0;
277 }
278 }
279 else if (h->t_p!=NULL)
280 {
281 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
282 {
283 h->Delete();
284 return 0;
285 }
286 }
287 }
288 #if 0
289 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
290 {
291 if (h->p!=NULL)
292 {
293 if(p_GetComp(h->p,currRing)>strat->syzComp)
294 {
295 return 1;
296 }
297 }
298 else if (h->t_p!=NULL)
299 {
300 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
301 {
302 return 1;
303 }
304 }
305 }
306 #endif
307
308 // done ? NO!
309 h->SetShortExpVector();
310 h->SetpFDeg();
311 if (strat->honey)
312 {
313 if (ei <= h->ecart)
314 h->ecart = d-h->GetpFDeg();
315 else
316 h->ecart = d-h->GetpFDeg()+ei-h->ecart;
317 }
318 else
319 // this has the side effect of setting h->length
320 h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
321#if 0
322 if (strat->syzComp!=0)
323 {
324 if ((strat->syzComp>0) && (h->Comp() > strat->syzComp))
325 {
326 assume(h->MinComp() > strat->syzComp);
327 if (strat->honey) h->SetLength();
328#ifdef KDEBUG
329 if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
330#endif
331 return -2;
332 }
333 }
334#endif
335 /*- try to reduce the s-polynomial -*/
336 pass++;
337 d = h->GetpFDeg()+h->ecart;
338 /*
339 *test whether the polynomial should go to the lazyset L
340 *-if the degree jumps
341 *-if the number of pre-defined reductions jumps
342 */
343 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
344 && ((d >= reddeg) || (pass > strat->LazyPass)))
345 {
346 h->SetLmCurrRing();
347 if (strat->honey && strat->posInLDependsOnLength)
348 h->SetLength(strat->length_pLength);
349 assume(h->FDeg == h->pFDeg());
350 at = strat->posInL(strat->L,strat->Ll,h,strat);
351 if (at <= strat->Ll)
352 {
353 int dummy=strat->sl;
354 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
355 {
356 if (strat->honey && !strat->posInLDependsOnLength)
357 h->SetLength(strat->length_pLength);
358 return 1;
359 }
360 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
361#ifdef KDEBUG
362 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
363#endif
364 h->Clear();
365 return -1;
366 }
367 }
368 else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
369 {
370 Print(".%ld",d);mflush();
371 reddeg = d+1;
372 if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
373 {
374 strat->overflow=TRUE;
375 //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
376 h->GetP();
377 at = strat->posInL(strat->L,strat->Ll,h,strat);
378 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
379 h->Clear();
380 return -1;
381 }
382 }
383 }
384}
385
386#ifdef HAVE_RINGS
388{
389 int i,at,ei,li,ii;
390 int j = 0;
391 int pass = 0;
392 long d,reddeg;
393
394 d = h->GetpFDeg()+ h->ecart;
395 reddeg = strat->LazyDegree+d;
396 h->SetShortExpVector();
397 loop
398 {
399 j = kFindDivisibleByInT(strat, h);
400 if (j < 0)
401 {
402 // over ZZ: cleanup coefficients by complete reduction with monomials
403 postReduceByMon(h, strat);
404 if(h->p == NULL)
405 {
406 kDeleteLcm(h);
407 h->Clear();
408 return 0;
409 }
410 if (strat->honey) h->SetLength(strat->length_pLength);
411 if(strat->tl >= 0)
412 h->i_r1 = strat->tl;
413 else
414 h->i_r1 = -1;
415 if (h->GetLmTailRing() == NULL)
416 {
417 kDeleteLcm(h);
418 h->Clear();
419 return 0;
420 }
421 return 1;
422 }
423
424 ei = strat->T[j].ecart;
425 ii = j;
426 if (ei > h->ecart && ii < strat->tl)
427 {
428 li = strat->T[j].length;
429 // the polynomial to reduce with (up to the moment) is;
430 // pi with ecart ei and length li
431 // look for one with smaller ecart
432 i = j;
433 loop
434 {
435 /*- takes the first possible with respect to ecart -*/
436 i++;
437#if 1
438 if (i > strat->tl) break;
439 if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
440 strat->T[i].length < li))
441 &&
442 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing)
443 &&
444 n_DivBy(h->p->coef,strat->T[i].p->coef,strat->tailRing->cf))
445#else
446 j = kFindDivisibleByInT(strat, h, i);
447 if (j < 0) break;
448 i = j;
449 if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
450 strat->T[i].length < li))
451#endif
452 {
453 // the polynomial to reduce with is now
454 ii = i;
455 ei = strat->T[i].ecart;
456 if (ei <= h->ecart) break;
457 li = strat->T[i].length;
458 }
459 }
460 }
461
462 // end of search: have to reduce with pi
463 if (ei > h->ecart)
464 {
465 // It is not possible to reduce h with smaller ecart;
466 // if possible h goes to the lazy-set L,i.e
467 // if its position in L would be not the last one
468 strat->fromT = TRUE;
469 if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
470 {
471 h->SetLmCurrRing();
472 if (strat->honey && strat->posInLDependsOnLength)
473 h->SetLength(strat->length_pLength);
474 assume(h->FDeg == h->pFDeg());
475 at = strat->posInL(strat->L,strat->Ll,h,strat);
476 if (at <= strat->Ll && pLmCmp(h->p, strat->L[strat->Ll].p) != 0 && !nEqual(h->p->coef, strat->L[strat->Ll].p->coef))
477 {
478 /*- h will not become the next element to reduce -*/
479 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
480 #ifdef KDEBUG
481 if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
482 #endif
483 h->Clear();
484 strat->fromT = FALSE;
485 return -1;
486 }
487 }
488 doRed(h,&(strat->T[ii]),strat->fromT,strat,TRUE);
489 }
490 else
491 {
492 // now we finally can reduce
493 doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
494 }
495 strat->fromT=FALSE;
496 // are we done ???
497 if (h->IsNull())
498 {
499 kDeleteLcm(h);
500 h->Clear();
501 return 0;
502 }
503
504 // NO!
505 h->SetShortExpVector();
506 h->SetpFDeg();
507 if (strat->honey)
508 {
509 if (ei <= h->ecart)
510 h->ecart = d-h->GetpFDeg();
511 else
512 h->ecart = d-h->GetpFDeg()+ei-h->ecart;
513 }
514 else
515 // this has the side effect of setting h->length
516 h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
517 /*- try to reduce the s-polynomial -*/
518 pass++;
519 d = h->GetpFDeg()+h->ecart;
520 /*
521 *test whether the polynomial should go to the lazyset L
522 *-if the degree jumps
523 *-if the number of pre-defined reductions jumps
524 */
525 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
526 && ((d >= reddeg) || (pass > strat->LazyPass)))
527 {
528 h->SetLmCurrRing();
529 if (strat->honey && strat->posInLDependsOnLength)
530 h->SetLength(strat->length_pLength);
531 assume(h->FDeg == h->pFDeg());
532 at = strat->posInL(strat->L,strat->Ll,h,strat);
533 if (at <= strat->Ll)
534 {
535 int dummy=strat->sl;
536 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
537 {
538 if (strat->honey && !strat->posInLDependsOnLength)
539 h->SetLength(strat->length_pLength);
540 return 1;
541 }
542 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
543#ifdef KDEBUG
544 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
545#endif
546 h->Clear();
547 return -1;
548 }
549 }
550 else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
551 {
552 Print(".%ld",d);mflush();
553 reddeg = d+1;
554 if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
555 {
556 strat->overflow=TRUE;
557 //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
558 h->GetP();
559 at = strat->posInL(strat->L,strat->Ll,h,strat);
560 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
561 h->Clear();
562 return -1;
563 }
564 }
565 }
566}
567
569{
570 int i,at,ei,li,ii;
571 int j = 0;
572 int pass = 0;
573 long d,reddeg;
574 int docoeffred = 0;
575 poly T0p = strat->T[0].p;
576 int T0ecart = strat->T[0].ecart;
577
578
579 d = h->GetpFDeg()+ h->ecart;
580 reddeg = strat->LazyDegree+d;
581 h->SetShortExpVector();
582 if ((strat->tl>=0)
583 &&strat->T[0].GetpFDeg() == 0
584 && strat->T[0].length <= 2)
585 {
586 docoeffred = 1;
587 }
588 loop
589 {
590 /* cut down the lead coefficients, only possible if the degree of
591 * T[0] is 0 (constant). This is only efficient if T[0] is short, thus
592 * we ask for the length of T[0] to be <= 2 */
593 if (docoeffred)
594 {
595 j = kTestDivisibleByT0_Z(strat, h);
596 if (j == 0 && n_DivBy(pGetCoeff(h->p), pGetCoeff(T0p), currRing->cf) == FALSE
597 && T0ecart <= h->ecart)
598 {
599 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
600 * => we try to cut down the lead coefficient at least */
601 /* first copy T[j] in order to multiply it with a coefficient later on */
602 number mult, rest;
603 TObject tj = strat->T[0];
604 tj.Copy();
605 /* compute division with remainder of lc(h) and lc(T[j]) */
606 mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(T0p),
607 &rest, currRing->cf);
608 /* set corresponding new lead coefficient already. we do not
609 * remove the lead term in ksReducePolyLC, but only apply
610 * a lead coefficient reduction */
611 tj.Mult_nn(mult);
612 ksReducePolyLC(h, &tj, NULL, &rest, strat);
613 tj.Delete();
614 tj.Clear();
615 if (n_IsZero(pGetCoeff(h->GetP()),currRing->cf))
616 {
617 h->LmDeleteAndIter();
618 }
619 }
620 }
621 j = kFindDivisibleByInT(strat, h);
622 if (j < 0)
623 {
624 // over ZZ: cleanup coefficients by complete reduction with monomials
625 postReduceByMon(h, strat);
626 if(h->p == NULL)
627 {
628 kDeleteLcm(h);
629 h->Clear();
630 return 0;
631 }
632 if (strat->honey) h->SetLength(strat->length_pLength);
633 if(strat->tl >= 0)
634 h->i_r1 = strat->tl;
635 else
636 h->i_r1 = -1;
637 if (h->GetLmTailRing() == NULL)
638 {
639 kDeleteLcm(h);
640 h->Clear();
641 return 0;
642 }
643 return 1;
644 }
645
646 ei = strat->T[j].ecart;
647 ii = j;
648#if 1
649 if (ei > h->ecart && ii < strat->tl)
650 {
651 li = strat->T[j].length;
652 // the polynomial to reduce with (up to the moment) is;
653 // pi with ecart ei and length li
654 // look for one with smaller ecart
655 i = j;
656 loop
657 {
658 /*- takes the first possible with respect to ecart -*/
659 i++;
660#if 1
661 if (i > strat->tl) break;
662 if ((strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
663 strat->T[i].length < li))
664 &&
665 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i], h->GetLmTailRing(), ~h->sev, strat->tailRing)
666 &&
667 n_DivBy(h->p->coef,strat->T[i].p->coef,strat->tailRing->cf))
668#else
669 j = kFindDivisibleByInT(strat, h, i);
670 if (j < 0) break;
671 i = j;
672 if (strat->T[i].ecart < ei || (strat->T[i].ecart == ei &&
673 strat->T[i].length < li))
674#endif
675 {
676 // the polynomial to reduce with is now
677 ii = i;
678 ei = strat->T[i].ecart;
679 if (ei <= h->ecart) break;
680 li = strat->T[i].length;
681 }
682 }
683 }
684#endif
685
686 // end of search: have to reduce with pi
687 if (ei > h->ecart)
688 {
689 // It is not possible to reduce h with smaller ecart;
690 // if possible h goes to the lazy-set L,i.e
691 // if its position in L would be not the last one
692 strat->fromT = TRUE;
693 if (!TEST_OPT_REDTHROUGH && strat->Ll >= 0) /*- L is not empty -*/
694 {
695 h->SetLmCurrRing();
696 if (strat->honey && strat->posInLDependsOnLength)
697 h->SetLength(strat->length_pLength);
698 assume(h->FDeg == h->pFDeg());
699 at = strat->posInL(strat->L,strat->Ll,h,strat);
700 if (at <= strat->Ll && pLmCmp(h->p, strat->L[strat->Ll].p) != 0 && !nEqual(h->p->coef, strat->L[strat->Ll].p->coef))
701 {
702 /*- h will not become the next element to reduce -*/
703 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
704#ifdef KDEBUG
705 if (TEST_OPT_DEBUG) Print(" ecart too big; -> L%d\n",at);
706#endif
707 h->Clear();
708 strat->fromT = FALSE;
709 return -1;
710 }
711 }
712 doRed(h,&(strat->T[ii]),strat->fromT,strat,TRUE);
713 }
714 else
715 {
716 // now we finally can reduce
717 doRed(h,&(strat->T[ii]),strat->fromT,strat,FALSE);
718 }
719 strat->fromT=FALSE;
720 // are we done ???
721 if (h->IsNull())
722 {
723 kDeleteLcm(h);
724 h->Clear();
725 return 0;
726 }
727
728 // NO!
729 h->SetShortExpVector();
730 h->SetpFDeg();
731 if (strat->honey)
732 {
733 if (ei <= h->ecart)
734 h->ecart = d-h->GetpFDeg();
735 else
736 h->ecart = d-h->GetpFDeg()+ei-h->ecart;
737 }
738 else
739 // this has the side effect of setting h->length
740 h->ecart = h->pLDeg(strat->LDegLast) - h->GetpFDeg();
741 /*- try to reduce the s-polynomial -*/
742 pass++;
743 d = h->GetpFDeg()+h->ecart;
744 /*
745 *test whether the polynomial should go to the lazyset L
746 *-if the degree jumps
747 *-if the number of pre-defined reductions jumps
748 */
749 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
750 && ((d >= reddeg) || (pass > strat->LazyPass)))
751 {
752 h->SetLmCurrRing();
753 if (strat->honey && strat->posInLDependsOnLength)
754 h->SetLength(strat->length_pLength);
755 assume(h->FDeg == h->pFDeg());
756 at = strat->posInL(strat->L,strat->Ll,h,strat);
757 if (at <= strat->Ll)
758 {
759 int dummy=strat->sl;
760 if (kFindDivisibleByInS(strat, &dummy, h) < 0)
761 {
762 if (strat->honey && !strat->posInLDependsOnLength)
763 h->SetLength(strat->length_pLength);
764 return 1;
765 }
766 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
767#ifdef KDEBUG
768 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
769#endif
770 h->Clear();
771 return -1;
772 }
773 }
774 else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
775 {
776 Print(".%ld",d);mflush();
777 reddeg = d+1;
778 if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
779 {
780 strat->overflow=TRUE;
781 //Print("OVERFLOW in redEcart d=%ld, max=%ld",d,strat->tailRing->bitmask);
782 h->GetP();
783 at = strat->posInL(strat->L,strat->Ll,h,strat);
784 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
785 h->Clear();
786 return -1;
787 }
788 }
789 }
790}
791#endif
792
793/*2
794*reduces h with elements from T choosing the first possible
795* element in t with respect to the given pDivisibleBy
796*/
798{
799 if (strat->tl<0) return 1;
800 if (h->IsNull()) return 0;
801
802 int at;
803 long reddeg,d;
804 int pass = 0;
805 int cnt = RED_CANONICALIZE;
806 int j = 0;
807
808 if (! strat->homog)
809 {
810 d = h->GetpFDeg() + h->ecart;
811 reddeg = strat->LazyDegree+d;
812 }
813 h->SetShortExpVector();
814 loop
815 {
816 j = kFindDivisibleByInT(strat, h);
817 if (j < 0)
818 {
819 h->SetDegStuffReturnLDeg(strat->LDegLast);
820 return 1;
821 }
822
824 strat->T[j].pNorm();
825#ifdef KDEBUG
826 if (TEST_OPT_DEBUG)
827 {
828 PrintS("reduce ");
829 h->wrp();
830 PrintS(" with ");
831 strat->T[j].wrp();
832 }
833#endif
834 ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
835#ifdef KDEBUG
836 if (TEST_OPT_DEBUG)
837 {
838 PrintS(" to ");
839 wrp(h->p);
840 PrintLn();
841 }
842#endif
843 if (h->IsNull())
844 {
846 kDeleteLcm(h);
847 h->Clear();
848 return 0;
849 }
850 if (TEST_OPT_IDLIFT)
851 {
852 if (h->p!=NULL)
853 {
854 if(p_GetComp(h->p,currRing)>strat->syzComp)
855 {
856 h->Delete();
857 return 0;
858 }
859 }
860 else if (h->t_p!=NULL)
861 {
862 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
863 {
864 h->Delete();
865 return 0;
866 }
867 }
868 }
869 #if 0
870 else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
871 {
872 if (h->p!=NULL)
873 {
874 if(p_GetComp(h->p,currRing)>strat->syzComp)
875 {
876 return 1;
877 }
878 }
879 else if (h->t_p!=NULL)
880 {
881 if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
882 {
883 return 1;
884 }
885 }
886 }
887 #endif
888 h->SetShortExpVector();
889
890#if 0
891 if ((strat->syzComp!=0) && !strat->honey)
892 {
893 if ((strat->syzComp>0) &&
894 (h->Comp() > strat->syzComp))
895 {
896 assume(h->MinComp() > strat->syzComp);
897#ifdef KDEBUG
898 if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
899#endif
900 if (strat->homog)
901 h->SetDegStuffReturnLDeg(strat->LDegLast);
902 return -2;
903 }
904 }
905#endif
906 if (!strat->homog)
907 {
908 if (!TEST_OPT_OLDSTD && strat->honey)
909 {
910 h->SetpFDeg();
911 if (strat->T[j].ecart <= h->ecart)
912 h->ecart = d - h->GetpFDeg();
913 else
914 h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
915
916 d = h->GetpFDeg() + h->ecart;
917 }
918 else
919 d = h->SetDegStuffReturnLDeg(strat->LDegLast);
920 /*- try to reduce the s-polynomial -*/
921 cnt--;
922 pass++;
923 /*
924 *test whether the polynomial should go to the lazyset L
925 *-if the degree jumps
926 *-if the number of pre-defined reductions jumps
927 */
928 if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
929 && ((d >= reddeg) || (pass > strat->LazyPass)))
930 {
931 h->SetLmCurrRing();
932 if (strat->posInLDependsOnLength)
933 h->SetLength(strat->length_pLength);
934 at = strat->posInL(strat->L,strat->Ll,h,strat);
935 if (at <= strat->Ll)
936 {
937 int dummy=strat->sl;
938 if (kFindDivisibleByInS(strat,&dummy, h) < 0)
939 return 1;
940 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
941#ifdef KDEBUG
942 if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
943#endif
944 h->Clear();
945 return -1;
946 }
947 }
948 if (UNLIKELY(cnt==0))
949 {
950 h->CanonicalizeP();
952 //if (TEST_OPT_PROT) { PrintS("!");mflush(); }
953 }
954 if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
955 {
956 reddeg = d+1;
957 Print(".%ld",d);mflush();
958 if (h->pTotalDeg()+h->ecart >= (int)strat->tailRing->bitmask)
959 {
960 strat->overflow=TRUE;
961 //Print("OVERFLOW in redFirst d=%ld, max=%ld",d,strat->tailRing->bitmask);
962 h->GetP();
963 at = strat->posInL(strat->L,strat->Ll,h,strat);
964 enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
965 h->Clear();
966 return -1;
967 }
968 }
969 }
970 }
971}
972
973/*2
974* reduces h with elements from T choosing first possible
975* element in T with respect to the given ecart
976* used for computing normal forms outside kStd
977*/
978static poly redMoraNF (poly h,kStrategy strat, int flag)
979{
980 LObject H;
981 H.p = h;
982 int j = 0;
983 int z = 10;
984 int o = H.SetpFDeg();
985 H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
986 if ((flag & 2) == 0) cancelunit(&H,TRUE);
987 H.sev = pGetShortExpVector(H.p);
988 loop
989 {
990 if (j > strat->tl)
991 {
992 return H.p;
993 }
994 if (TEST_V_DEG_STOP)
995 {
996 if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
997 if (H.p==NULL) return NULL;
998 }
999 unsigned long not_sev = ~ H.sev;
1000 if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
1001 )
1002 {
1003 /*- remember the found T-poly -*/
1004 // poly pi = strat->T[j].p;
1005 int ei = strat->T[j].ecart;
1006 int li = strat->T[j].length;
1007 int ii = j;
1008 /*
1009 * the polynomial to reduce with (up to the moment) is;
1010 * pi with ecart ei and length li
1011 */
1012 loop
1013 {
1014 /*- look for a better one with respect to ecart -*/
1015 /*- stop, if the ecart is small enough (<=ecart(H)) -*/
1016 j++;
1017 if (j > strat->tl) break;
1018 if (ei <= H.ecart) break;
1019 if (((strat->T[j].ecart < ei)
1020 || ((strat->T[j].ecart == ei)
1021 && (strat->T[j].length < li)))
1022 && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
1023 )
1024 {
1025 /*
1026 * the polynomial to reduce with is now;
1027 */
1028 // pi = strat->T[j].p;
1029 ei = strat->T[j].ecart;
1030 li = strat->T[j].length;
1031 ii = j;
1032 }
1033 }
1034 /*
1035 * end of search: have to reduce with pi
1036 */
1037 z++;
1038 if (z>10)
1039 {
1040 pNormalize(H.p);
1041 z=0;
1042 }
1043 if ((ei > H.ecart) && (strat->kNoether==NULL))
1044 {
1045 /*
1046 * It is not possible to reduce h with smaller ecart;
1047 * we have to reduce with bad ecart: H has to enter in T
1048 */
1049 LObject L= H;
1050 L.Copy();
1051 H.GetP();
1052 H.length=H.pLength=pLength(H.p);
1053 ksReducePoly(&L, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
1054 (flag & KSTD_NF_NONORM)==0);
1055 enterT(H,strat);
1056 H = L;
1057 }
1058 else
1059 {
1060 /*
1061 * we reduce with good ecart, h need not to be put to T
1062 */
1063 ksReducePoly(&H, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
1064 (flag & KSTD_NF_NONORM)==0);
1065 }
1066 if (H.p == NULL)
1067 return NULL;
1068 /*- try to reduce the s-polynomial -*/
1069 o = H.SetpFDeg();
1070 if ((flag & KSTD_NF_ECART) == 0) cancelunit(&H,TRUE);
1071 H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
1072 j = 0;
1073 H.sev = pGetShortExpVector(H.p);
1074 }
1075 else
1076 {
1077 j++;
1078 }
1079 }
1080}
1081
1082#ifdef HAVE_RINGS
1083static poly redMoraNFRing (poly h,kStrategy strat, int flag)
1084{
1085 LObject H;
1086 H.p = h;
1087 int j0, j = 0;
1088 int docoeffred = 0;
1089 poly T0p = strat->T[0].p;
1090 int T0ecart = strat->T[0].ecart;
1091 int o = H.SetpFDeg();
1092 H.ecart = currRing->pLDeg(H.p,&H.length,currRing)-o;
1093 if ((flag & KSTD_NF_ECART) == 0) cancelunit(&H,TRUE);
1094 H.sev = pGetShortExpVector(H.p);
1095 unsigned long not_sev = ~ H.sev;
1096 if (strat->T[0].GetpFDeg() == 0 && strat->T[0].length <= 2)
1097 {
1098 docoeffred = 1; // euclidean ring required: n_QuotRem
1099 if (currRing->cf->cfQuotRem==ndQuotRem)
1100 {
1101 docoeffred = 0;
1102 }
1103 }
1104 loop
1105 {
1106 /* cut down the lead coefficients, only possible if the degree of
1107 * T[0] is 0 (constant). This is only efficient if T[0] is short, thus
1108 * we ask for the length of T[0] to be <= 2 */
1109 if (docoeffred)
1110 {
1111 j0 = kTestDivisibleByT0_Z(strat, &H);
1112 if ((j0 == 0)
1113 && (n_DivBy(pGetCoeff(H.p), pGetCoeff(T0p), currRing->cf) == FALSE)
1114 && (T0ecart <= H.ecart))
1115 {
1116 /* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
1117 * => we try to cut down the lead coefficient at least */
1118 /* first copy T[j0] in order to multiply it with a coefficient later on */
1119 number mult, rest;
1120 TObject tj = strat->T[0];
1121 tj.Copy();
1122 /* compute division with remainder of lc(h) and lc(T[j]) */
1123 mult = n_QuotRem(pGetCoeff(H.p), pGetCoeff(T0p),
1124 &rest, currRing->cf);
1125 /* set corresponding new lead coefficient already. we do not
1126 * remove the lead term in ksReducePolyLC, but only apply
1127 * a lead coefficient reduction */
1128 tj.Mult_nn(mult);
1129 ksReducePolyLC(&H, &tj, NULL, &rest, strat);
1130 tj.Delete();
1131 tj.Clear();
1132 }
1133 }
1134 if (j > strat->tl)
1135 {
1136 return H.p;
1137 }
1138 if (TEST_V_DEG_STOP)
1139 {
1140 if (kModDeg(H.p)>Kstd1_deg) pLmDelete(&H.p);
1141 if (H.p==NULL) return NULL;
1142 }
1143 if (p_LmShortDivisibleBy(strat->T[j].GetLmTailRing(), strat->sevT[j], H.GetLmTailRing(), not_sev, strat->tailRing)
1144 && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
1145 )
1146 {
1147 /*- remember the found T-poly -*/
1148 // poly pi = strat->T[j].p;
1149 int ei = strat->T[j].ecart;
1150 int li = strat->T[j].length;
1151 int ii = j;
1152 /*
1153 * the polynomial to reduce with (up to the moment) is;
1154 * pi with ecart ei and length li
1155 */
1156 loop
1157 {
1158 /*- look for a better one with respect to ecart -*/
1159 /*- stop, if the ecart is small enough (<=ecart(H)) -*/
1160 j++;
1161 if (j > strat->tl) break;
1162 if (ei <= H.ecart) break;
1163 if (((strat->T[j].ecart < ei)
1164 || ((strat->T[j].ecart == ei)
1165 && (strat->T[j].length < li)))
1166 && pLmShortDivisibleBy(strat->T[j].p,strat->sevT[j], H.p, not_sev)
1167 && (n_DivBy(H.p->coef, strat->T[j].p->coef,strat->tailRing->cf))
1168 )
1169 {
1170 /*
1171 * the polynomial to reduce with is now;
1172 */
1173 // pi = strat->T[j].p;
1174 ei = strat->T[j].ecart;
1175 li = strat->T[j].length;
1176 ii = j;
1177 }
1178 }
1179 /*
1180 * end of search: have to reduce with pi
1181 */
1182 if ((ei > H.ecart) && (strat->kNoether==NULL))
1183 {
1184 /*
1185 * It is not possible to reduce h with smaller ecart;
1186 * we have to reduce with bad ecart: H has to enter in T
1187 */
1188 LObject L= H;
1189 L.Copy();
1190 H.GetP();
1191 H.length=H.pLength=pLength(H.p);
1192 ksReducePoly(&L, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
1193 (flag & KSTD_NF_NONORM)==0);
1194 enterT_strong(H,strat);
1195 H = L;
1196 }
1197 else
1198 {
1199 /*
1200 * we reduce with good ecart, h need not to be put to T
1201 */
1202 ksReducePoly(&H, &(strat->T[ii]), strat->kNoetherTail(), NULL, NULL, strat,
1203 (flag & KSTD_NF_NONORM)==0);
1204 }
1205 if (H.p == NULL)
1206 return NULL;
1207 /*- try to reduce the s-polynomial -*/
1208 o = H.SetpFDeg();
1209 if ((flag &2 ) == 0) cancelunit(&H,TRUE);
1210 H.ecart = currRing->pLDeg(H.p,&(H.length),currRing)-o;
1211 j = 0;
1212 H.sev = pGetShortExpVector(H.p);
1213 not_sev = ~ H.sev;
1214 }
1215 else
1216 {
1217 j++;
1218 }
1219 }
1220}
1221#endif
1222
1223/*2
1224*reorders L with respect to posInL
1225*/
1227{
1228 int i,j,at;
1229 LObject p;
1230
1231 for (i=1; i<=strat->Ll; i++)
1232 {
1233 at = strat->posInL(strat->L,i-1,&(strat->L[i]),strat);
1234 if (at != i)
1235 {
1236 p = strat->L[i];
1237 for (j=i-1; j>=at; j--) strat->L[j+1] = strat->L[j];
1238 strat->L[at] = p;
1239 }
1240 }
1241}
1242
1243/*2
1244*reorders T with respect to length
1245*/
1247{
1248 int i,j,at;
1249 TObject p;
1250 unsigned long sev;
1251
1252
1253 for (i=1; i<=strat->tl; i++)
1254 {
1255 if (strat->T[i-1].length > strat->T[i].length)
1256 {
1257 p = strat->T[i];
1258 sev = strat->sevT[i];
1259 at = i-1;
1260 loop
1261 {
1262 at--;
1263 if (at < 0) break;
1264 if (strat->T[i].length > strat->T[at].length) break;
1265 }
1266 for (j = i-1; j>at; j--)
1267 {
1268 strat->T[j+1]=strat->T[j];
1269 strat->sevT[j+1]=strat->sevT[j];
1270 strat->R[strat->T[j+1].i_r] = &(strat->T[j+1]);
1271 }
1272 strat->T[at+1]=p;
1273 strat->sevT[at+1] = sev;
1274 strat->R[p.i_r] = &(strat->T[at+1]);
1275 }
1276 }
1277}
1278
1279/*2
1280*looks whether exactly (currRing->N)-1 axis are used
1281*returns last != 0 in this case
1282*last is the (first) unused axis
1283*/
1284void missingAxis (int* last,kStrategy strat)
1285{
1286 int i = 0;
1287 int k = 0;
1288
1289 *last = 0;
1291 {
1292 loop
1293 {
1294 i++;
1295 if (i > (currRing->N)) break;
1296 if (strat->NotUsedAxis[i])
1297 {
1298 *last = i;
1299 k++;
1300 }
1301 if (k>1)
1302 {
1303 *last = 0;
1304 break;
1305 }
1306 }
1307 }
1308}
1309
1310/*2
1311*last is the only non used axis, it looks
1312*for a monomial in p being a pure power of this
1313*variable and returns TRUE in this case
1314*(*length) gives the length between the pure power and the leading term
1315*(should be minimal)
1316*/
1317BOOLEAN hasPurePower (const poly p,int last, int *length,kStrategy strat)
1318{
1319 poly h;
1320 int i;
1321
1322 if (pNext(p) == strat->tail)
1323 return FALSE;
1324 pp_Test(p, currRing, strat->tailRing);
1325 if (strat->ak <= 0 || p_MinComp(p, currRing, strat->tailRing) == strat->ak)
1326 {
1328 if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(p), currRing->cf))) i=0;
1329 if (i == last)
1330 {
1331 *length = 0;
1332 return TRUE;
1333 }
1334 *length = 1;
1335 h = pNext(p);
1336 while (h != NULL)
1337 {
1338 i = p_IsPurePower(h, strat->tailRing);
1339 if (rField_is_Ring(currRing) && (!n_IsUnit(pGetCoeff(h), currRing->cf))) i=0;
1340 if (i==last) return TRUE;
1341 (*length)++;
1342 pIter(h);
1343 }
1344 }
1345 return FALSE;
1346}
1347
1349{
1350 if (L->bucket != NULL)
1351 {
1352 poly p = L->GetP();
1353 return hasPurePower(p, last, length, strat);
1354 }
1355 else
1356 {
1357 return hasPurePower(L->p, last, length, strat);
1358 }
1359}
1360
1361/*2
1362* looks up the position of polynomial p in L
1363* in the case of looking for the pure powers
1364*/
1365int posInL10 (const LSet set,const int length, LObject* p,const kStrategy strat)
1366{
1367 int j,dp,dL;
1368
1369 if (length<0) return 0;
1370 if (hasPurePower(p,strat->lastAxis,&dp,strat))
1371 {
1372 int op= p->GetpFDeg() +p->ecart;
1373 for (j=length; j>=0; j--)
1374 {
1375 if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat))
1376 return j+1;
1377 if (dp < dL)
1378 return j+1;
1379 if ((dp == dL)
1380 && (set[j].GetpFDeg()+set[j].ecart >= op))
1381 return j+1;
1382 }
1383 }
1384 j=length;
1385 loop
1386 {
1387 if (j<0) break;
1388 if (!hasPurePower(&(set[j]),strat->lastAxis,&dL,strat)) break;
1389 j--;
1390 }
1391 return strat->posInLOld(set,j,p,strat);
1392}
1393
1394
1395/*2
1396* computes the s-polynomials L[ ].p in L
1397*/
1399{
1400 LObject p;
1401 int dL;
1402 int j=strat->Ll;
1403 loop
1404 {
1405 if (j<0) break;
1406 if (hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat))
1407 {
1408 p=strat->L[strat->Ll];
1409 strat->L[strat->Ll]=strat->L[j];
1410 strat->L[j]=p;
1411 break;
1412 }
1413 j--;
1414 }
1415 if (j<0)
1416 {
1417 j=strat->Ll;
1418 loop
1419 {
1420 if (j<0) break;
1421 if (pNext(strat->L[j].p) == strat->tail)
1422 {
1424 pLmDelete(strat->L[j].p); /*deletes the short spoly and computes*/
1425 else
1426 pLmFree(strat->L[j].p); /*deletes the short spoly and computes*/
1427 strat->L[j].p = NULL;
1428 poly m1 = NULL, m2 = NULL;
1429 // check that spoly creation is ok
1430 while (strat->tailRing != currRing &&
1431 !kCheckSpolyCreation(&(strat->L[j]), strat, m1, m2))
1432 {
1433 assume(m1 == NULL && m2 == NULL);
1434 // if not, change to a ring where exponents are at least
1435 // large enough
1436 kStratChangeTailRing(strat);
1437 }
1438 /* create the real one */
1439 ksCreateSpoly(&(strat->L[j]), strat->kNoetherTail(), FALSE,
1440 strat->tailRing, m1, m2, strat->R);
1441
1442 strat->L[j].SetLmCurrRing();
1443 if (!strat->honey)
1444 strat->initEcart(&strat->L[j]);
1445 else
1446 strat->L[j].SetLength(strat->length_pLength);
1447
1448 BOOLEAN pp = hasPurePower(&(strat->L[j]),strat->lastAxis,&dL,strat);
1449
1450 if (strat->use_buckets) strat->L[j].PrepareRed(TRUE);
1451
1452 if (pp)
1453 {
1454 p=strat->L[strat->Ll];
1455 strat->L[strat->Ll]=strat->L[j];
1456 strat->L[j]=p;
1457 break;
1458 }
1459 }
1460 j--;
1461 }
1462 }
1463}
1464
1465/*2
1466* computes the s-polynomials L[ ].p in L and
1467* cuts elements in L above noether
1468*/
1470{
1471
1472 int i = 0;
1473 kTest_TS(strat);
1474 while (i <= strat->Ll)
1475 {
1476 if (pNext(strat->L[i].p) == strat->tail)
1477 {
1478 /*- deletes the int spoly and computes -*/
1479 if (pLmCmp(strat->L[i].p,strat->kNoether) == -1)
1480 {
1482 pLmDelete(strat->L[i].p);
1483 else
1484 pLmFree(strat->L[i].p);
1485 strat->L[i].p = NULL;
1486 }
1487 else
1488 {
1490 pLmDelete(strat->L[i].p);
1491 else
1492 pLmFree(strat->L[i].p);
1493 strat->L[i].p = NULL;
1494 poly m1 = NULL, m2 = NULL;
1495 // check that spoly creation is ok
1496 while (strat->tailRing != currRing &&
1497 !kCheckSpolyCreation(&(strat->L[i]), strat, m1, m2))
1498 {
1499 assume(m1 == NULL && m2 == NULL);
1500 // if not, change to a ring where exponents are at least
1501 // large enough
1502 kStratChangeTailRing(strat);
1503 }
1504 /* create the real one */
1505 ksCreateSpoly(&(strat->L[i]), strat->kNoetherTail(), FALSE,
1506 strat->tailRing, m1, m2, strat->R);
1507 if (! strat->L[i].IsNull())
1508 {
1509 strat->L[i].SetLmCurrRing();
1510 strat->L[i].SetpFDeg();
1511 strat->L[i].ecart
1512 = strat->L[i].pLDeg(strat->LDegLast) - strat->L[i].GetpFDeg();
1513 if (strat->use_buckets) strat->L[i].PrepareRed(TRUE);
1514 }
1515 }
1516 }
1517 deleteHC(&(strat->L[i]), strat);
1518 if (strat->L[i].IsNull())
1519 deleteInL(strat->L,&strat->Ll,i,strat);
1520 else
1521 {
1522#ifdef KDEBUG
1523 kTest_L(&(strat->L[i]), strat, TRUE, i, strat->T, strat->tl);
1524#endif
1525 i++;
1526 }
1527 }
1528 kTest_TS(strat);
1529}
1530
1531/*2
1532* cuts in T above strat->kNoether and tries to cancel a unit
1533* changes also S as S is a subset of T
1534*/
1536{
1537 int i = 0;
1538 LObject p;
1539
1540 while (i <= strat->tl)
1541 {
1542 p = strat->T[i];
1543 deleteHC(&p,strat, TRUE);
1544 /*- tries to cancel a unit: -*/
1545 cancelunit(&p);
1546 if (TEST_OPT_INTSTRATEGY) /* deleteHC and/or cancelunit may have changed p*/
1547 p.pCleardenom();
1548 if (p.p != strat->T[i].p)
1549 {
1550 strat->sevT[i] = pGetShortExpVector(p.p);
1551 p.SetpFDeg();
1552 }
1553 strat->T[i] = p;
1554 i++;
1555 }
1556}
1557
1558/*2
1559* arranges red, pos and T if strat->kAllAxis (first time)
1560*/
1562{
1563 if (strat->update)
1564 {
1565 kTest_TS(strat);
1566 strat->update = (strat->tl == -1);
1567 if (TEST_OPT_WEIGHTM)
1568 {
1570 if (strat->tailRing != currRing)
1571 {
1572 strat->tailRing->pFDeg = strat->pOrigFDeg_TailRing;
1573 strat->tailRing->pLDeg = strat->pOrigLDeg_TailRing;
1574 }
1575 int i;
1576 for (i=strat->Ll; i>=0; i--)
1577 {
1578 strat->L[i].SetpFDeg();
1579 }
1580 for (i=strat->tl; i>=0; i--)
1581 {
1582 strat->T[i].SetpFDeg();
1583 }
1584 if (ecartWeights)
1585 {
1586 omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(short));
1588 }
1589 }
1590 if (TEST_OPT_FASTHC)
1591 {
1592 strat->posInL = strat->posInLOld;
1593 strat->lastAxis = 0;
1594 }
1595 if (TEST_OPT_FINDET)
1596 return;
1597
1599 {
1600 strat->red = redFirst;
1601 strat->use_buckets = kMoraUseBucket(strat);
1602 }
1603 updateT(strat);
1604
1606 {
1607 strat->posInT = posInT2;
1608 reorderT(strat);
1609 }
1610 }
1611 kTest_TS(strat);
1612}
1613
1614/*2
1615*-puts p to the standardbasis s at position at
1616*-reduces the tail of p if TEST_OPT_REDTAIL
1617*-tries to cancel a unit
1618*-HEckeTest
1619* if TRUE
1620* - decides about reduction-strategies
1621* - computes noether
1622* - stops computation if TEST_OPT_FINDET
1623* - cuts the tails of the polynomials
1624* in s,t and the elements in L above noether
1625* and cancels units if possible
1626* - reorders s,L
1627*/
1628void enterSMora (LObject &p,int atS,kStrategy strat, int atR = -1)
1629{
1630 enterSBba(p, atS, strat, atR);
1631 #ifdef KDEBUG
1632 if (TEST_OPT_DEBUG)
1633 {
1634 Print("new s%d:",atS);
1635 p_wrp(p.p,currRing,strat->tailRing);
1636 PrintLn();
1637 }
1638 #endif
1639 HEckeTest(p.p,strat);
1640 if (strat->kAllAxis)
1641 {
1642 if (newHEdge(strat))
1643 {
1644 firstUpdate(strat);
1645 if (TEST_OPT_FINDET)
1646 return;
1647
1648 /*- cuts elements in L above noether and reorders L -*/
1649 updateLHC(strat);
1650 /*- reorders L with respect to posInL -*/
1651 reorderL(strat);
1652 }
1653 }
1654 else if ((strat->kNoether==NULL)
1655 && (TEST_OPT_FASTHC))
1656 {
1657 if (strat->posInLOldFlag)
1658 {
1659 missingAxis(&strat->lastAxis,strat);
1660 if (strat->lastAxis)
1661 {
1662 strat->posInLOld = strat->posInL;
1663 strat->posInLOldFlag = FALSE;
1664 strat->posInL = posInL10;
1665 strat->posInLDependsOnLength = TRUE;
1666 updateL(strat);
1667 reorderL(strat);
1668 }
1669 }
1670 else if (strat->lastAxis)
1671 updateL(strat);
1672 }
1673}
1674
1675/*2
1676*-puts p to the standardbasis s at position at
1677*-HEckeTest
1678* if TRUE
1679* - computes noether
1680*/
1681void enterSMoraNF (LObject &p, int atS,kStrategy strat, int atR = -1)
1682{
1683 enterSBba(p, atS, strat, atR);
1684 if ((!strat->kAllAxis) || (strat->kNoether!=NULL)) HEckeTest(p.p,strat);
1685 if (strat->kAllAxis)
1686 newHEdge(strat);
1687}
1688
1690{
1691 /* setting global variables ------------------- */
1692 strat->enterS = enterSBba;
1693 strat->red = redHoney;
1694 if (strat->honey)
1695 strat->red = redHoney;
1696 else if (currRing->pLexOrder && !strat->homog)
1697 strat->red = redLazy;
1698 else
1699 {
1700 strat->LazyPass *=4;
1701 strat->red = redHomog;
1702 }
1704 {
1705 if (rField_is_Z(currRing))
1706 strat->red = redRing_Z;
1707 else
1708 strat->red = redRing;
1709 }
1710 if (TEST_OPT_IDLIFT
1711 && (!rIsNCRing(currRing))
1712 && (!rField_is_Ring(currRing)))
1713 strat->red=redLiftstd;
1714 if (currRing->pLexOrder && strat->honey)
1715 strat->initEcart = initEcartNormal;
1716 else
1717 strat->initEcart = initEcartBBA;
1718 if (strat->honey)
1720 else
1722// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1723// {
1724// //interred machen Aenderung
1725// strat->pOrigFDeg=pFDeg;
1726// strat->pOrigLDeg=pLDeg;
1727// //h=ggetid("ecart");
1728// //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1729// //{
1730// // ecartWeights=iv2array(IDINTVEC(h));
1731// //}
1732// //else
1733// {
1734// ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1735// /*uses automatic computation of the ecartWeights to set them*/
1736// kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights);
1737// }
1738// pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
1739// if (TEST_OPT_PROT)
1740// {
1741// for(i=1; i<=(currRing->N); i++)
1742// Print(" %d",ecartWeights[i]);
1743// PrintLn();
1744// mflush();
1745// }
1746// }
1747}
1748
1749void initSba(ideal F,kStrategy strat)
1750{
1751 int i;
1752 //idhdl h;
1753 /* setting global variables ------------------- */
1754 strat->enterS = enterSSba;
1755 strat->red2 = redHoney;
1756 if (strat->honey)
1757 strat->red2 = redHoney;
1758 else if (currRing->pLexOrder && !strat->homog)
1759 strat->red2 = redLazy;
1760 else
1761 {
1762 strat->LazyPass *=4;
1763 strat->red2 = redHomog;
1764 }
1766 {
1768 {strat->red2 = redRiloc;}
1769 else
1770 {strat->red2 = redRing;}
1771 }
1772 if (currRing->pLexOrder && strat->honey)
1773 strat->initEcart = initEcartNormal;
1774 else
1775 strat->initEcart = initEcartBBA;
1776 if (strat->honey)
1778 else
1780 //strat->kIdeal = NULL;
1781 //if (strat->ak==0) strat->kIdeal->rtyp=IDEAL_CMD;
1782 //else strat->kIdeal->rtyp=MODUL_CMD;
1783 //strat->kIdeal->data=(void *)strat->Shdl;
1784 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1785 {
1786 //interred machen Aenderung
1787 strat->pOrigFDeg = currRing->pFDeg;
1788 strat->pOrigLDeg = currRing->pLDeg;
1789 //h=ggetid("ecart");
1790 //if ((h!=NULL) /*&& (IDTYP(h)==INTVEC_CMD)*/)
1791 //{
1792 // ecartWeights=iv2array(IDINTVEC(h));
1793 //}
1794 //else
1795 {
1796 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1797 /*uses automatic computation of the ecartWeights to set them*/
1799 }
1801 if (TEST_OPT_PROT)
1802 {
1803 for(i=1; i<=(currRing->N); i++)
1804 Print(" %d",ecartWeights[i]);
1805 PrintLn();
1806 mflush();
1807 }
1808 }
1809 // for sig-safe reductions in signature-based
1810 // standard basis computations
1812 strat->red = redSigRing;
1813 else
1814 strat->red = redSig;
1815 //strat->sbaOrder = 1;
1816 strat->currIdx = 1;
1817}
1818
1819void initMora(ideal F,kStrategy strat)
1820{
1821 int i,j;
1822
1823 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1824 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1825 strat->enterS = enterSMora;
1826 strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1827 strat->posInLOld = strat->posInL;
1828 strat->posInLOldFlag = TRUE;
1829 strat->initEcart = initEcartNormal;
1830 strat->kAllAxis = (currRing->ppNoether) != NULL; //!!
1831 if ( currRing->ppNoether != NULL )
1832 {
1833 strat->kNoether = pCopy((currRing->ppNoether));
1834 strat->red = redFirst; /*take the first possible in T*/
1835 if (TEST_OPT_PROT)
1836 {
1837 Print("H(%ld)",p_FDeg(currRing->ppNoether,currRing)+1);
1838 mflush();
1839 }
1840 }
1841 else if (strat->homog)
1842 strat->red = redFirst; /*take the first possible in T*/
1843 else
1844 strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1845 if (currRing->ppNoether != NULL)
1846 {
1847 HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1848 }
1849 else
1850 {
1851 HCord = 32000;/*- very large -*/
1852 }
1853
1855 {
1856 if (rField_is_Z(currRing))
1857 strat->red = redRiloc_Z;
1858 else
1859 strat->red = redRiloc;
1860 }
1861
1862 /*reads the ecartWeights used for Graebes method from the
1863 *intvec ecart and set ecartWeights
1864 */
1865 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1866 {
1867 //interred machen Aenderung
1868 strat->pOrigFDeg=currRing->pFDeg;
1869 strat->pOrigLDeg=currRing->pLDeg;
1870 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1871 /*uses automatic computation of the ecartWeights to set them*/
1873
1875 if (TEST_OPT_PROT)
1876 {
1877 for(i=1; i<=(currRing->N); i++)
1878 Print(" %d",ecartWeights[i]);
1879 PrintLn();
1880 mflush();
1881 }
1882 }
1883 kOptimizeLDeg(currRing->pLDeg, strat);
1884}
1885
1886void kDebugPrint(kStrategy strat);
1887
1888ideal mora (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat)
1889{
1890 int olddeg = 0;
1891 int reduc = 0;
1892 int red_result = 1;
1893 int hilbeledeg=1,hilbcount=0;
1894 BITSET save1;
1895 SI_SAVE_OPT1(save1);
1897 {
1898 si_opt_1 &= ~Sy_bit(OPT_REDSB);
1899 si_opt_1 &= ~Sy_bit(OPT_REDTAIL);
1900 }
1901
1902 strat->update = TRUE;
1903 /*- setting global variables ------------------- -*/
1904 initBuchMoraCrit(strat);
1905 initHilbCrit(F,Q,&hilb,strat);
1906 initMora(F,strat);
1908 initBuchMoraPosRing(strat);
1909 else
1910 initBuchMoraPos(strat);
1911 /*Shdl=*/initBuchMora(F,Q,strat);
1912 if (TEST_OPT_FASTHC) missingAxis(&strat->lastAxis,strat);
1913 /*updateS in initBuchMora has Hecketest
1914 * and could have put strat->kHEdgdeFound FALSE*/
1915 if (TEST_OPT_FASTHC && (strat->lastAxis) && strat->posInLOldFlag)
1916 {
1917 strat->posInLOld = strat->posInL;
1918 strat->posInLOldFlag = FALSE;
1919 strat->posInL = posInL10;
1920 updateL(strat);
1921 reorderL(strat);
1922 }
1923 kTest_TS(strat);
1924 strat->use_buckets = kMoraUseBucket(strat);
1925
1926#ifdef HAVE_TAIL_RING
1927 if (strat->homog && strat->red == redFirst)
1928 if(!idIs0(F) &&(!rField_is_Ring(currRing)))
1930#endif
1931
1932 if (BVERBOSE(23))
1933 {
1934 kDebugPrint(strat);
1935 }
1936//deleteInL(strat->L,&strat->Ll,1,strat);
1937//deleteInL(strat->L,&strat->Ll,0,strat);
1938
1939 /*- compute-------------------------------------------*/
1940 while (strat->Ll >= 0)
1941 {
1942 #ifdef KDEBUG
1943 if (TEST_OPT_DEBUG) messageSets(strat);
1944 #endif
1945 if (siCntrlc)
1946 {
1947 while (strat->Ll >= 0)
1948 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1949 strat->noClearS=TRUE;
1950 }
1952 && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
1953 {
1954 /*
1955 * stops computation if
1956 * - 24 (degBound)
1957 * && upper degree is bigger than Kstd1_deg
1958 */
1959 while ((strat->Ll >= 0)
1960 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1961 && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
1962 )
1963 {
1964 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1965 //if (TEST_OPT_PROT)
1966 //{
1967 // PrintS("D"); mflush();
1968 //}
1969 }
1970 if (strat->Ll<0) break;
1971 else strat->noClearS=TRUE;
1972 }
1973 strat->P = strat->L[strat->Ll];/*- picks the last element from the lazyset L -*/
1974 if (strat->Ll==0) strat->interpt=TRUE;
1975 strat->Ll--;
1976 // create the real Spoly
1977 if (pNext(strat->P.p) == strat->tail)
1978 {
1979 /*- deletes the short spoly and computes -*/
1981 pLmDelete(strat->P.p);
1982 else
1983 pLmFree(strat->P.p);
1984 strat->P.p = NULL;
1985 poly m1 = NULL, m2 = NULL;
1986 // check that spoly creation is ok
1987 while (strat->tailRing != currRing &&
1988 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1989 {
1990 assume(m1 == NULL && m2 == NULL);
1991 // if not, change to a ring where exponents are large enough
1992 kStratChangeTailRing(strat);
1993 }
1994 /* create the real one */
1995 ksCreateSpoly(&(strat->P), strat->kNoetherTail(), strat->use_buckets,
1996 strat->tailRing, m1, m2, strat->R);
1997 if (!strat->use_buckets)
1998 strat->P.SetLength(strat->length_pLength);
1999 }
2000 else if (strat->P.p1 == NULL)
2001 {
2002 // for input polys, prepare reduction (buckets !)
2003 strat->P.SetLength(strat->length_pLength);
2004 strat->P.PrepareRed(strat->use_buckets);
2005 }
2006
2007 // the s-poly
2008 if (!strat->P.IsNull())
2009 {
2010 // might be NULL from noether !!!
2011 if (TEST_OPT_PROT)
2012 message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
2013 // reduce
2014 red_result = strat->red(&strat->P,strat);
2015 }
2016
2017 // the reduced s-poly
2018 if (! strat->P.IsNull())
2019 {
2020 strat->P.GetP();
2021 // statistics
2022 if (TEST_OPT_PROT) PrintS("s");
2023 // normalization
2025 strat->P.pCleardenom();
2026 else
2027 strat->P.pNorm();
2028 // tailreduction
2029 strat->P.p = redtail(&(strat->P),strat->sl,strat);
2030 if (strat->P.p==NULL)
2031 {
2032 WerrorS("exponent overflow - wrong ordering");
2033 return(idInit(1,1));
2034 }
2035 // set ecart -- might have changed because of tail reductions
2036 if ((!strat->noTailReduction) && (!strat->honey))
2037 strat->initEcart(&strat->P);
2038 // cancel unit
2039 cancelunit(&strat->P);
2040 // for char 0, clear denominators
2041 if ((strat->P.p->next==NULL) /* i.e. cancelunit did something*/
2043 strat->P.pCleardenom();
2044
2045 strat->P.SetShortExpVector();
2046 enterT(strat->P,strat);
2047 // build new pairs
2049 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2050 else
2051 enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2052 // put in S
2053 strat->enterS(strat->P,
2054 posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
2055 strat, strat->tl);
2056 // apply hilbert criterion
2057 if (hilb!=NULL)
2058 {
2059 if (strat->homog==isHomog)
2060 khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2061 else
2062 khCheckLocInhom(Q,w,hilb,hilbcount,strat);
2063 }
2064
2065 // clear strat->P
2066 kDeleteLcm(&strat->P);
2067
2068#ifdef KDEBUG
2069 // make sure kTest_TS does not complain about strat->P
2070 strat->P.Clear();
2071#endif
2072 }
2073 if (strat->kAllAxis)
2074 {
2075 if ((TEST_OPT_FINDET)
2076 || ((TEST_OPT_MULTBOUND) && (scMult0Int(strat->Shdl,NULL) < Kstd1_mu)))
2077 {
2078 // obachman: is this still used ???
2079 /*
2080 * stops computation if strat->kAllAxis and
2081 * - 27 (finiteDeterminacyTest)
2082 * or
2083 * - 23
2084 * (multBound)
2085 * && multiplicity of the ideal is smaller then a predefined number mu
2086 */
2087 while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2088 }
2089 }
2090 kTest_TS(strat);
2091 }
2092 /*- complete reduction of the standard basis------------------------ -*/
2093 if (TEST_OPT_REDSB) completeReduce(strat);
2094 else if (TEST_OPT_PROT) PrintLn();
2095 /*- release temp data------------------------------- -*/
2096 exitBuchMora(strat);
2097 /*- polynomials used for HECKE: HC, noether -*/
2098 if (TEST_OPT_FINDET)
2099 {
2100 if (strat->kNoether!=NULL)
2101 Kstd1_mu=currRing->pFDeg(strat->kNoether,currRing);
2102 else
2103 Kstd1_mu=-1;
2104 }
2105 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2106 if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2107 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2108 if ((TEST_OPT_PROT)||(TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2109// if (TEST_OPT_WEIGHTM)
2110// {
2111// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2112// if (ecartWeights)
2113// {
2114// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2115// ecartWeights=NULL;
2116// }
2117// }
2118 if(nCoeff_is_Z(currRing->cf))
2119 finalReduceByMon(strat);
2120 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2121 SI_RESTORE_OPT1(save1);
2122 idTest(strat->Shdl);
2123 return (strat->Shdl);
2124}
2125
2126poly kNF1 (ideal F,ideal Q,poly q, kStrategy strat, int lazyReduce)
2127{
2128 assume(q!=NULL);
2129 assume(!(idIs0(F)&&(Q==NULL)));
2130
2131// lazy_reduce flags: can be combined by |
2132//#define KSTD_NF_LAZY 1
2133 // do only a reduction of the leading term
2134//#define KSTD_NF_ECART 2
2135 // only local: reduce even with bad ecart
2136 poly p;
2137 int i;
2138 int j;
2139 int o;
2140 LObject h;
2141 BITSET save1;
2142 SI_SAVE_OPT1(save1);
2143
2144 //if ((idIs0(F))&&(Q==NULL))
2145 // return pCopy(q); /*F=0*/
2146 //strat->ak = si_max(idRankFreeModule(F),pMaxComp(q));
2147 /*- creating temp data structures------------------- -*/
2148 //strat->kAllAxis = (currRing->ppNoether) != NULL;
2149 strat->kNoether = pCopy((currRing->ppNoether));
2152 si_opt_1&=~Sy_bit(OPT_INTSTRATEGY);
2154 && (! TEST_V_DEG_STOP)
2155 && (0<Kstd1_deg)
2156 && ((strat->kNoether==NULL)
2158 {
2159 pLmDelete(&strat->kNoether);
2160 strat->kNoether=pOne();
2161 pSetExp(strat->kNoether,1, Kstd1_deg+1);
2162 pSetm(strat->kNoether);
2163 // strat->kAllAxis=TRUE;
2164 }
2165 initBuchMoraCrit(strat);
2167 initBuchMoraPosRing(strat);
2168 else
2169 initBuchMoraPos(strat);
2170 initMora(F,strat);
2171 strat->enterS = enterSMoraNF;
2172 /*- set T -*/
2173 strat->tl = -1;
2174 strat->tmax = setmaxT;
2175 strat->T = initT();
2176 strat->R = initR();
2177 strat->sevT = initsevT();
2178 /*- set S -*/
2179 strat->sl = -1;
2180 /*- init local data struct.-------------------------- -*/
2181 /*Shdl=*/initS(F,Q,strat);
2182 if ((strat->ak!=0)
2183 && (strat->kAllAxis)) /*never true for ring-cf*/
2184 {
2185 if (strat->ak!=1)
2186 {
2187 pSetComp(strat->kNoether,1);
2188 pSetmComp(strat->kNoether);
2189 poly p=pHead(strat->kNoether);
2190 pSetComp(p,strat->ak);
2191 pSetmComp(p);
2192 p=pAdd(strat->kNoether,p);
2193 strat->kNoether=pNext(p);
2195 }
2196 }
2197 if (((lazyReduce & KSTD_NF_LAZY)==0)
2198 && (!rField_is_Ring(currRing)))
2199 {
2200 for (i=strat->sl; i>=0; i--)
2201 pNorm(strat->S[i]);
2202 }
2203 /*- puts the elements of S also to T -*/
2204 for (i=0; i<=strat->sl; i++)
2205 {
2206 h.p = strat->S[i];
2207 h.ecart = strat->ecartS[i];
2208 if (strat->sevS[i] == 0) strat->sevS[i] = pGetShortExpVector(h.p);
2209 else assume(strat->sevS[i] == pGetShortExpVector(h.p));
2210 h.length = pLength(h.p);
2211 h.sev = strat->sevS[i];
2212 h.SetpFDeg();
2213 enterT(h,strat);
2214 }
2215#ifdef KDEBUG
2216// kDebugPrint(strat);
2217#endif
2218 /*- compute------------------------------------------- -*/
2219 p = pCopy(q);
2220 deleteHC(&p,&o,&j,strat);
2221 kTest(strat);
2222 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2223 if (BVERBOSE(23)) kDebugPrint(strat);
2225 {
2226 if (p!=NULL) p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
2227 }
2228 else
2229 {
2230 if (p!=NULL) p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2231 }
2232 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2233 {
2234 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2235 p = redtail(p,strat->sl,strat);
2236 }
2237 /*- release temp data------------------------------- -*/
2238 cleanT(strat);
2239 assume(strat->L==NULL); /*strat->L unused */
2240 assume(strat->B==NULL); /*strat->B unused */
2241 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2242 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2243 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2244 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2245 omFree(strat->sevT);
2246 omFree(strat->S_2_R);
2247 omFree(strat->R);
2248
2249 if ((Q!=NULL)&&(strat->fromQ!=NULL))
2250 {
2251 i=((IDELEMS(Q)+IDELEMS(F)+15)/16)*16;
2252 omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2253 strat->fromQ=NULL;
2254 }
2255 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2256// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2257// {
2258// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2259// if (ecartWeights)
2260// {
2261// omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2262// ecartWeights=NULL;
2263// }
2264// }
2265 idDelete(&strat->Shdl);
2266 SI_RESTORE_OPT1(save1);
2267 if (TEST_OPT_PROT) PrintLn();
2268 return p;
2269}
2270
2271ideal kNF1 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce)
2272{
2273 assume(!idIs0(q));
2274 assume(!(idIs0(F)&&(Q==NULL)));
2275
2276// lazy_reduce flags: can be combined by |
2277//#define KSTD_NF_LAZY 1
2278 // do only a reduction of the leading term
2279//#define KSTD_NF_ECART 2
2280 // only local: reduce even with bad ecart
2281 poly p;
2282 int i;
2283 int j;
2284 int o;
2285 LObject h;
2286 ideal res;
2287 BITSET save1;
2288 SI_SAVE_OPT1(save1);
2289
2290 //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2291 //if ((idIs0(F))&&(Q==NULL))
2292 // return idCopy(q); /*F=0*/
2293 //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2294 /*- creating temp data structures------------------- -*/
2295 //strat->kAllAxis = (currRing->ppNoether) != NULL;
2296 strat->kNoether=pCopy((currRing->ppNoether));
2299 && (0<Kstd1_deg)
2300 && ((strat->kNoether==NULL)
2302 {
2303 pLmDelete(&strat->kNoether);
2304 strat->kNoether=pOne();
2305 pSetExp(strat->kNoether,1, Kstd1_deg+1);
2306 pSetm(strat->kNoether);
2307 //strat->kAllAxis=TRUE;
2308 }
2309 initBuchMoraCrit(strat);
2311 initBuchMoraPosRing(strat);
2312 else
2313 initBuchMoraPos(strat);
2314 initMora(F,strat);
2315 strat->enterS = enterSMoraNF;
2316 /*- set T -*/
2317 strat->tl = -1;
2318 strat->tmax = setmaxT;
2319 strat->T = initT();
2320 strat->R = initR();
2321 strat->sevT = initsevT();
2322 /*- set S -*/
2323 strat->sl = -1;
2324 /*- init local data struct.-------------------------- -*/
2325 /*Shdl=*/initS(F,Q,strat);
2326 if ((strat->ak!=0)
2327 && (strat->kNoether!=NULL))
2328 {
2329 if (strat->ak!=1)
2330 {
2331 pSetComp(strat->kNoether,1);
2332 pSetmComp(strat->kNoether);
2333 poly p=pHead(strat->kNoether);
2334 pSetComp(p,strat->ak);
2335 pSetmComp(p);
2336 p=pAdd(strat->kNoether,p);
2337 strat->kNoether=pNext(p);
2339 }
2340 }
2341 if (((lazyReduce & KSTD_NF_LAZY)==0)
2342 && (!rField_is_Ring(currRing)))
2343 {
2344 for (i=strat->sl; i>=0; i--)
2345 pNorm(strat->S[i]);
2346 }
2347 /*- compute------------------------------------------- -*/
2348 res=idInit(IDELEMS(q),strat->ak);
2349 for (i=0; i<IDELEMS(q); i++)
2350 {
2351 if (q->m[i]!=NULL)
2352 {
2353 p = pCopy(q->m[i]);
2354 deleteHC(&p,&o,&j,strat);
2355 if (p!=NULL)
2356 {
2357 /*- puts the elements of S also to T -*/
2358 for (j=0; j<=strat->sl; j++)
2359 {
2360 h.p = strat->S[j];
2361 h.ecart = strat->ecartS[j];
2362 h.pLength = h.length = pLength(h.p);
2363 if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2364 else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2365 h.sev = strat->sevS[j];
2366 h.SetpFDeg();
2368 enterT_strong(h,strat);
2369 else
2370 enterT(h,strat);
2371 }
2372 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2374 {
2375 p = redMoraNFRing(p,strat, lazyReduce);
2376 }
2377 else
2378 p = redMoraNF(p,strat, lazyReduce);
2379 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2380 {
2381 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2382 p = redtail(p,strat->sl,strat);
2383 }
2384 cleanT(strat);
2385 }
2386 res->m[i]=p;
2387 }
2388 //else
2389 // res->m[i]=NULL;
2390 }
2391 /*- release temp data------------------------------- -*/
2392 assume(strat->L==NULL); /*strat->L unused */
2393 assume(strat->B==NULL); /*strat->B unused */
2394 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2395 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2396 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2397 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2398 omFree(strat->sevT);
2399 omFree(strat->S_2_R);
2400 omFree(strat->R);
2401 if ((Q!=NULL)&&(strat->fromQ!=NULL))
2402 {
2404 omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2405 strat->fromQ=NULL;
2406 }
2407 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2408// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2409// {
2410// pFDeg=strat->pOrigFDeg;
2411// pLDeg=strat->pOrigLDeg;
2412// if (ecartWeights)
2413// {
2414// omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2415// ecartWeights=NULL;
2416// }
2417// }
2418 idDelete(&strat->Shdl);
2419 SI_RESTORE_OPT1(save1);
2420 if (TEST_OPT_PROT) PrintLn();
2421 return res;
2422}
2423
2425
2426long kModDeg(poly p,const ring r)
2427{
2428 long o=p_WDegree(p, r);
2429 long i=__p_GetComp(p, r);
2430 if (i==0) return o;
2431 //assume((i>0) && (i<=kModW->length()));
2432 if (i<=kModW->length())
2433 return o+(*kModW)[i-1];
2434 return o;
2435}
2436long kHomModDeg(poly p,const ring r)
2437{
2438 int i;
2439 long j=0;
2440
2441 for (i=r->N;i>0;i--)
2442 j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2443 if (kModW == NULL) return j;
2444 i = __p_GetComp(p,r);
2445 if (i==0) return j;
2446 return j+(*kModW)[i-1];
2447}
2448
2449ideal kStd(ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
2450 int newIdeal, intvec *vw, s_poly_proc_t sp)
2451{
2452 if(idIs0(F))
2453 return idInit(1,F->rank);
2454
2455 if((Q!=NULL)&&(idIs0(Q))) Q=NULL;
2456#ifdef HAVE_SHIFTBBA
2457 if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
2458#endif
2459
2460 ideal r;
2461 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2462 BOOLEAN delete_w=(w==NULL);
2463 kStrategy strat=new skStrategy;
2464
2465 strat->s_poly=sp;
2467 strat->syzComp = syzComp;
2468 if (TEST_OPT_SB_1
2470 )
2471 strat->newIdeal = newIdeal;
2473 strat->LazyPass=20;
2474 else
2475 strat->LazyPass=2;
2476 strat->LazyDegree = 1;
2477 strat->ak = id_RankFreeModule(F,currRing);
2478 strat->kModW=kModW=NULL;
2479 strat->kHomW=kHomW=NULL;
2480 if (vw != NULL)
2481 {
2482 currRing->pLexOrder=FALSE;
2483 strat->kHomW=kHomW=vw;
2484 strat->pOrigFDeg = currRing->pFDeg;
2485 strat->pOrigLDeg = currRing->pLDeg;
2487 toReset = TRUE;
2488 }
2489 if (h==testHomog)
2490 {
2491 if (strat->ak == 0)
2492 {
2493 h = (tHomog)idHomIdeal(F,Q);
2494 w=NULL;
2495 }
2496 else if (!TEST_OPT_DEGBOUND)
2497 {
2498 if (w!=NULL)
2499 h = (tHomog)idHomModule(F,Q,w);
2500 else
2501 h = (tHomog)idHomIdeal(F,Q);
2502 }
2503 }
2504 currRing->pLexOrder=b;
2505 if (h==isHomog)
2506 {
2507 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2508 {
2509 strat->kModW = kModW = *w;
2510 if (vw == NULL)
2511 {
2512 strat->pOrigFDeg = currRing->pFDeg;
2513 strat->pOrigLDeg = currRing->pLDeg;
2515 toReset = TRUE;
2516 }
2517 }
2518 currRing->pLexOrder = TRUE;
2519 if (hilb==NULL) strat->LazyPass*=2;
2520 }
2521 strat->homog=h;
2522#ifdef KDEBUG
2523 idTest(F);
2524 if (Q!=NULL) idTest(Q);
2525#endif
2526#ifdef HAVE_PLURAL
2528 {
2529 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2530 strat->no_prod_crit = ! bIsSCA;
2531 if (w!=NULL)
2532 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2533 else
2534 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2535 }
2536 else
2537#endif
2538 {
2539 #if PRE_INTEGER_CHECK
2540 //the preinteger check strategy is not for modules
2541 if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2542 {
2543 ideal FCopy = idCopy(F);
2544 poly pFmon = preIntegerCheck(FCopy, Q);
2545 if(pFmon != NULL)
2546 {
2547 idInsertPoly(FCopy, pFmon);
2548 strat->kModW=kModW=NULL;
2549 if (h==testHomog)
2550 {
2551 if (strat->ak == 0)
2552 {
2553 h = (tHomog)idHomIdeal(FCopy,Q);
2554 w=NULL;
2555 }
2556 else if (!TEST_OPT_DEGBOUND)
2557 {
2558 if (w!=NULL)
2559 h = (tHomog)idHomModule(FCopy,Q,w);
2560 else
2561 h = (tHomog)idHomIdeal(FCopy,Q);
2562 }
2563 }
2564 currRing->pLexOrder=b;
2565 if (h==isHomog)
2566 {
2567 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2568 {
2569 strat->kModW = kModW = *w;
2570 if (vw == NULL)
2571 {
2572 strat->pOrigFDeg = currRing->pFDeg;
2573 strat->pOrigLDeg = currRing->pLDeg;
2575 toReset = TRUE;
2576 }
2577 }
2578 currRing->pLexOrder = TRUE;
2579 if (hilb==NULL) strat->LazyPass*=2;
2580 }
2581 strat->homog=h;
2582 }
2583 omTestMemory(1);
2584 if(w == NULL)
2585 {
2587 r=mora(FCopy,Q,NULL,hilb,strat);
2588 else
2589 r=bba(FCopy,Q,NULL,hilb,strat);
2590 }
2591 else
2592 {
2594 r=mora(FCopy,Q,*w,hilb,strat);
2595 else
2596 r=bba(FCopy,Q,*w,hilb,strat);
2597 }
2598 idDelete(&FCopy);
2599 }
2600 else
2601 #endif
2602 {
2603 if(w==NULL)
2604 {
2606 r=mora(F,Q,NULL,hilb,strat);
2607 else
2608 r=bba(F,Q,NULL,hilb,strat);
2609 }
2610 else
2611 {
2613 r=mora(F,Q,*w,hilb,strat);
2614 else
2615 r=bba(F,Q,*w,hilb,strat);
2616 }
2617 }
2618 }
2619#ifdef KDEBUG
2620 idTest(r);
2621#endif
2622 if (toReset)
2623 {
2624 kModW = NULL;
2626 }
2627 currRing->pLexOrder = b;
2628//Print("%d reductions canceled \n",strat->cel);
2629 delete(strat);
2630 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2631 return r;
2632}
2633
2634ideal kSba(ideal F, ideal Q, tHomog h,intvec ** w, int sbaOrder, int arri, intvec *hilb,int syzComp,
2635 int newIdeal, intvec *vw)
2636{
2637 if(idIs0(F))
2638 return idInit(1,F->rank);
2640 {
2641 ideal r;
2642 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2643 BOOLEAN delete_w=(w==NULL);
2644 kStrategy strat=new skStrategy;
2645 strat->sbaOrder = sbaOrder;
2646 if (arri!=0)
2647 {
2648 strat->rewCrit1 = arriRewDummy;
2649 strat->rewCrit2 = arriRewCriterion;
2651 }
2652 else
2653 {
2657 }
2658
2660 strat->syzComp = syzComp;
2661 if (TEST_OPT_SB_1)
2662 //if(!rField_is_Ring(currRing)) // always true here
2663 strat->newIdeal = newIdeal;
2665 strat->LazyPass=20;
2666 else
2667 strat->LazyPass=2;
2668 strat->LazyDegree = 1;
2672 strat->ak = id_RankFreeModule(F,currRing);
2673 strat->kModW=kModW=NULL;
2674 strat->kHomW=kHomW=NULL;
2675 if (vw != NULL)
2676 {
2677 currRing->pLexOrder=FALSE;
2678 strat->kHomW=kHomW=vw;
2679 strat->pOrigFDeg = currRing->pFDeg;
2680 strat->pOrigLDeg = currRing->pLDeg;
2682 toReset = TRUE;
2683 }
2684 if (h==testHomog)
2685 {
2686 if (strat->ak == 0)
2687 {
2688 h = (tHomog)idHomIdeal(F,Q);
2689 w=NULL;
2690 }
2691 else if (!TEST_OPT_DEGBOUND)
2692 {
2693 if (w!=NULL)
2694 h = (tHomog)idHomModule(F,Q,w);
2695 else
2696 h = (tHomog)idHomIdeal(F,Q);
2697 }
2698 }
2699 currRing->pLexOrder=b;
2700 if (h==isHomog)
2701 {
2702 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2703 {
2704 strat->kModW = kModW = *w;
2705 if (vw == NULL)
2706 {
2707 strat->pOrigFDeg = currRing->pFDeg;
2708 strat->pOrigLDeg = currRing->pLDeg;
2710 toReset = TRUE;
2711 }
2712 }
2713 currRing->pLexOrder = TRUE;
2714 if (hilb==NULL) strat->LazyPass*=2;
2715 }
2716 strat->homog=h;
2717 #ifdef KDEBUG
2718 idTest(F);
2719 if(Q != NULL)
2720 idTest(Q);
2721 #endif
2722 #ifdef HAVE_PLURAL
2724 {
2725 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2726 strat->no_prod_crit = ! bIsSCA;
2727 if (w!=NULL)
2728 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2729 else
2730 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2731 }
2732 else
2733 #endif
2734 {
2736 {
2737 if (w!=NULL)
2738 r=mora(F,Q,*w,hilb,strat);
2739 else
2740 r=mora(F,Q,NULL,hilb,strat);
2741 }
2742 else
2743 {
2744 strat->sigdrop = FALSE;
2745 if (w!=NULL)
2746 r=sba(F,Q,*w,hilb,strat);
2747 else
2748 r=sba(F,Q,NULL,hilb,strat);
2749 }
2750 }
2751 #ifdef KDEBUG
2752 idTest(r);
2753 #endif
2754 if (toReset)
2755 {
2756 kModW = NULL;
2758 }
2759 currRing->pLexOrder = b;
2760 //Print("%d reductions canceled \n",strat->cel);
2761 //delete(strat);
2762 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2763 return r;
2764 }
2765 else
2766 {
2767 //--------------------------RING CASE-------------------------
2768 assume(sbaOrder == 1);
2769 assume(arri == 0);
2770 ideal r;
2771 r = idCopy(F);
2772 int sbaEnterS = -1;
2773 bool sigdrop = TRUE;
2774 //This is how we set the SBA algorithm;
2775 int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2776 while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2777 && (blockred <= blockedreductions))
2778 {
2779 loops++;
2780 if(loops == 1)
2781 sigdrop = FALSE;
2782 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2783 BOOLEAN delete_w=(w==NULL);
2784 kStrategy strat=new skStrategy;
2785 strat->sbaEnterS = sbaEnterS;
2786 strat->sigdrop = sigdrop;
2787 #if 0
2788 strat->blockred = blockred;
2789 #else
2790 strat->blockred = 0;
2791 #endif
2792 strat->blockredmax = blockedreductions;
2793 //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2794 //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2795 strat->sbaOrder = sbaOrder;
2796 if (arri!=0)
2797 {
2798 strat->rewCrit1 = arriRewDummy;
2799 strat->rewCrit2 = arriRewCriterion;
2801 }
2802 else
2803 {
2807 }
2808
2810 strat->syzComp = syzComp;
2811 if (TEST_OPT_SB_1)
2813 strat->newIdeal = newIdeal;
2815 strat->LazyPass=20;
2816 else
2817 strat->LazyPass=2;
2818 strat->LazyDegree = 1;
2822 strat->ak = id_RankFreeModule(F,currRing);
2823 strat->kModW=kModW=NULL;
2824 strat->kHomW=kHomW=NULL;
2825 if (vw != NULL)
2826 {
2827 currRing->pLexOrder=FALSE;
2828 strat->kHomW=kHomW=vw;
2829 strat->pOrigFDeg = currRing->pFDeg;
2830 strat->pOrigLDeg = currRing->pLDeg;
2832 toReset = TRUE;
2833 }
2834 if (h==testHomog)
2835 {
2836 if (strat->ak == 0)
2837 {
2838 h = (tHomog)idHomIdeal(F,Q);
2839 w=NULL;
2840 }
2841 else if (!TEST_OPT_DEGBOUND)
2842 {
2843 if (w!=NULL)
2844 h = (tHomog)idHomModule(F,Q,w);
2845 else
2846 h = (tHomog)idHomIdeal(F,Q);
2847 }
2848 }
2849 currRing->pLexOrder=b;
2850 if (h==isHomog)
2851 {
2852 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2853 {
2854 strat->kModW = kModW = *w;
2855 if (vw == NULL)
2856 {
2857 strat->pOrigFDeg = currRing->pFDeg;
2858 strat->pOrigLDeg = currRing->pLDeg;
2860 toReset = TRUE;
2861 }
2862 }
2863 currRing->pLexOrder = TRUE;
2864 if (hilb==NULL) strat->LazyPass*=2;
2865 }
2866 strat->homog=h;
2867 #ifdef KDEBUG
2868 idTest(F);
2869 if(Q != NULL)
2870 idTest(Q);
2871 #endif
2872 #ifdef HAVE_PLURAL
2874 {
2875 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2876 strat->no_prod_crit = ! bIsSCA;
2877 if (w!=NULL)
2878 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2879 else
2880 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2881 }
2882 else
2883 #endif
2884 {
2886 {
2887 if (w!=NULL)
2888 r=mora(F,Q,*w,hilb,strat);
2889 else
2890 r=mora(F,Q,NULL,hilb,strat);
2891 }
2892 else
2893 {
2894 if (w!=NULL)
2895 r=sba(r,Q,*w,hilb,strat);
2896 else
2897 {
2898 r=sba(r,Q,NULL,hilb,strat);
2899 }
2900 }
2901 }
2902 #ifdef KDEBUG
2903 idTest(r);
2904 #endif
2905 if (toReset)
2906 {
2907 kModW = NULL;
2909 }
2910 currRing->pLexOrder = b;
2911 //Print("%d reductions canceled \n",strat->cel);
2912 sigdrop = strat->sigdrop;
2913 sbaEnterS = strat->sbaEnterS;
2914 blockred = strat->blockred;
2915 delete(strat);
2916 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2917 }
2918 // Go to std
2919 if(sigdrop || blockred > blockedreductions)
2920 {
2921 r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2922 }
2923 return r;
2924 }
2925}
2926
2927#ifdef HAVE_SHIFTBBA
2928ideal kStdShift(ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
2929 int newIdeal, intvec *vw, BOOLEAN rightGB)
2930{
2932 assume(idIsInV(F));
2933 ideal r;
2934 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2935 BOOLEAN delete_w=(w==NULL);
2936 kStrategy strat=new skStrategy;
2937 intvec* temp_w=NULL;
2938
2939 strat->rightGB = rightGB;
2940
2942 strat->syzComp = syzComp;
2943 if (TEST_OPT_SB_1)
2945 strat->newIdeal = newIdeal;
2947 strat->LazyPass=20;
2948 else
2949 strat->LazyPass=2;
2950 strat->LazyDegree = 1;
2951 strat->ak = id_RankFreeModule(F,currRing);
2952 strat->kModW=kModW=NULL;
2953 strat->kHomW=kHomW=NULL;
2954 if (vw != NULL)
2955 {
2956 currRing->pLexOrder=FALSE;
2957 strat->kHomW=kHomW=vw;
2958 strat->pOrigFDeg = currRing->pFDeg;
2959 strat->pOrigLDeg = currRing->pLDeg;
2961 toReset = TRUE;
2962 }
2963 if (h==testHomog)
2964 {
2965 if (strat->ak == 0)
2966 {
2967 h = (tHomog)idHomIdeal(F,Q);
2968 w=NULL;
2969 }
2970 else if (!TEST_OPT_DEGBOUND)
2971 {
2972 if (w!=NULL)
2973 h = (tHomog)idHomModule(F,Q,w);
2974 else
2975 h = (tHomog)idHomIdeal(F,Q);
2976 }
2977 }
2978 currRing->pLexOrder=b;
2979 if (h==isHomog)
2980 {
2981 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2982 {
2983 strat->kModW = kModW = *w;
2984 if (vw == NULL)
2985 {
2986 strat->pOrigFDeg = currRing->pFDeg;
2987 strat->pOrigLDeg = currRing->pLDeg;
2989 toReset = TRUE;
2990 }
2991 }
2992 currRing->pLexOrder = TRUE;
2993 if (hilb==NULL) strat->LazyPass*=2;
2994 }
2995 strat->homog=h;
2996#ifdef KDEBUG
2997 idTest(F);
2998#endif
3000 {
3001 /* error: no local ord yet with shifts */
3002 WerrorS("No local ordering possible for shift algebra");
3003 return(NULL);
3004 }
3005 else
3006 {
3007 /* global ordering */
3008 if (w!=NULL)
3009 r=bbaShift(F,Q,*w,hilb,strat);
3010 else
3011 r=bbaShift(F,Q,NULL,hilb,strat);
3012 }
3013#ifdef KDEBUG
3014 idTest(r);
3015#endif
3016 if (toReset)
3017 {
3018 kModW = NULL;
3020 }
3021 currRing->pLexOrder = b;
3022//Print("%d reductions canceled \n",strat->cel);
3023 delete(strat);
3024 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
3025 assume(idIsInV(r));
3026 return r;
3027}
3028#endif
3029
3030//##############################################################
3031//##############################################################
3032//##############################################################
3033//##############################################################
3034//##############################################################
3035
3036ideal kMin_std(ideal F, ideal Q, tHomog h,intvec ** w, ideal &M, intvec *hilb,
3037 int syzComp, int reduced)
3038{
3039 if(idIs0(F))
3040 {
3041 M=idInit(1,F->rank);
3042 return idInit(1,F->rank);
3043 }
3045 {
3046 ideal sb;
3047 sb = kStd(F, Q, h, w, hilb);
3048 idSkipZeroes(sb);
3049 if(IDELEMS(sb) <= IDELEMS(F))
3050 {
3051 M = idCopy(sb);
3052 idSkipZeroes(M);
3053 return(sb);
3054 }
3055 else
3056 {
3057 M = idCopy(F);
3058 idSkipZeroes(M);
3059 return(sb);
3060 }
3061 }
3062 ideal r=NULL;
3063 int Kstd1_OldDeg = Kstd1_deg,i;
3064 intvec* temp_w=NULL;
3065 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3066 BOOLEAN delete_w=(w==NULL);
3067 BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
3068 kStrategy strat=new skStrategy;
3069
3071 strat->syzComp = syzComp;
3073 strat->LazyPass=20;
3074 else
3075 strat->LazyPass=2;
3076 strat->LazyDegree = 1;
3077 strat->minim=(reduced % 2)+1;
3078 strat->ak = id_RankFreeModule(F,currRing);
3079 if (delete_w)
3080 {
3081 temp_w=new intvec((strat->ak)+1);
3082 w = &temp_w;
3083 }
3084 if (h==testHomog)
3085 {
3086 if (strat->ak == 0)
3087 {
3088 h = (tHomog)idHomIdeal(F,Q);
3089 w=NULL;
3090 }
3091 else
3092 {
3093 h = (tHomog)idHomModule(F,Q,w);
3094 }
3095 }
3096 if (h==isHomog)
3097 {
3098 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3099 {
3100 kModW = *w;
3101 strat->kModW = *w;
3102 assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3103 strat->pOrigFDeg = currRing->pFDeg;
3104 strat->pOrigLDeg = currRing->pLDeg;
3106
3107 toReset = TRUE;
3108 if (reduced>1)
3109 {
3110 Kstd1_OldDeg=Kstd1_deg;
3111 Kstd1_deg = -1;
3112 for (i=IDELEMS(F)-1;i>=0;i--)
3113 {
3114 if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3115 Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3116 }
3117 }
3118 }
3119 currRing->pLexOrder = TRUE;
3120 strat->LazyPass*=2;
3121 }
3122 strat->homog=h;
3123 ideal SB=NULL;
3125 {
3126 r=idMinBase(F,&SB); // SB and M via minbase
3127 strat->M=r;
3128 r=SB;
3129 }
3130 else
3131 {
3132 if (w!=NULL)
3133 r=bba(F,Q,*w,hilb,strat);
3134 else
3135 r=bba(F,Q,NULL,hilb,strat);
3136 }
3137#ifdef KDEBUG
3138 {
3139 int i;
3140 for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3141 }
3142#endif
3143 idSkipZeroes(r);
3144 if (toReset)
3145 {
3147 kModW = NULL;
3148 }
3149 currRing->pLexOrder = b;
3150 if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3151 if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3152 {
3153 M=idInit(1,F->rank);
3154 M->m[0]=pOne();
3155 //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3156 if (strat->M!=NULL) idDelete(&strat->M);
3157 }
3158 else if (strat->M==NULL)
3159 {
3160 M=idInit(1,F->rank);
3161 WarnS("no minimal generating set computed");
3162 }
3163 else
3164 {
3165 idSkipZeroes(strat->M);
3166 M=strat->M;
3167 }
3168 delete(strat);
3169 if (reduced>2)
3170 {
3171 Kstd1_deg=Kstd1_OldDeg;
3172 if (!oldDegBound)
3173 si_opt_1 &= ~Sy_bit(OPT_DEGBOUND);
3174 }
3175 else
3176 {
3177 if (IDELEMS(M)>IDELEMS(r))
3178 {
3179 idDelete(&M);
3180 M=idCopy(r);
3181 }
3182 }
3183 return r;
3184}
3185
3186poly kNF(ideal F, ideal Q, poly p,int syzComp, int lazyReduce)
3187{
3188 if (p==NULL)
3189 return NULL;
3190
3191 poly pp = p;
3192
3193#ifdef HAVE_PLURAL
3194 if(rIsSCA(currRing))
3195 {
3196 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3197 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3198 pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3199
3200 if(Q == currRing->qideal)
3202 }
3203#endif
3204 if((Q!=NULL) &&(idIs0(Q))) Q=NULL;
3205
3206 if ((idIs0(F))&&(Q==NULL))
3207 {
3208#ifdef HAVE_PLURAL
3209 if(p != pp)
3210 return pp;
3211#endif
3212 return pCopy(p); /*F+Q=0*/
3213 }
3214
3215 kStrategy strat=new skStrategy;
3216 strat->syzComp = syzComp;
3218 poly res;
3219
3221 {
3222#ifdef HAVE_SHIFTBBA
3223 if (currRing->isLPring)
3224 {
3225 WerrorS("No local ordering possible for shift algebra");
3226 return(NULL);
3227 }
3228#endif
3229 res=kNF1(F,Q,pp,strat,lazyReduce);
3230 }
3231 else
3232 res=kNF2(F,Q,pp,strat,lazyReduce);
3233 delete(strat);
3234
3235#ifdef HAVE_PLURAL
3236 if(pp != p)
3237 p_Delete(&pp, currRing);
3238#endif
3239 return res;
3240}
3241
3242poly kNFBound(ideal F, ideal Q, poly p,int bound,int syzComp, int lazyReduce)
3243{
3244 if (p==NULL)
3245 return NULL;
3246
3247 poly pp = p;
3248
3249#ifdef HAVE_PLURAL
3250 if(rIsSCA(currRing))
3251 {
3252 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3253 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3254 pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3255
3256 if(Q == currRing->qideal)
3258 }
3259#endif
3260
3261 if ((idIs0(F))&&(Q==NULL))
3262 {
3263#ifdef HAVE_PLURAL
3264 if(p != pp)
3265 return pp;
3266#endif
3267 return pCopy(p); /*F+Q=0*/
3268 }
3269
3270 kStrategy strat=new skStrategy;
3271 strat->syzComp = syzComp;
3273 poly res;
3274 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3275 delete(strat);
3276
3277#ifdef HAVE_PLURAL
3278 if(pp != p)
3279 p_Delete(&pp, currRing);
3280#endif
3281 return res;
3282}
3283
3284ideal kNF(ideal F, ideal Q, ideal p,int syzComp,int lazyReduce)
3285{
3286 ideal res;
3287 if (TEST_OPT_PROT)
3288 {
3289 Print("(S:%d)",IDELEMS(p));mflush();
3290 }
3291 if (idIs0(p))
3292 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3293
3294 ideal pp = p;
3295#ifdef HAVE_PLURAL
3296 if(rIsSCA(currRing))
3297 {
3298 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3299 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3300 pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3301
3302 if(Q == currRing->qideal)
3304 }
3305#endif
3306
3307 if ((Q!=NULL)&&(idIs0(Q))) Q=NULL;
3308
3309 if ((idIs0(F))&&(Q==NULL))
3310 {
3311#ifdef HAVE_PLURAL
3312 if(p != pp)
3313 return pp;
3314#endif
3315 return idCopy(p); /*F+Q=0*/
3316 }
3317
3318 kStrategy strat=new skStrategy;
3319 strat->syzComp = syzComp;
3321 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3322 {
3323 strat->ak = si_max(strat->ak,(int)F->rank);
3324 }
3325
3327 {
3328#ifdef HAVE_SHIFTBBA
3329 if (currRing->isLPring)
3330 {
3331 WerrorS("No local ordering possible for shift algebra");
3332 return(NULL);
3333 }
3334#endif
3335 res=kNF1(F,Q,pp,strat,lazyReduce);
3336 }
3337 else
3338 res=kNF2(F,Q,pp,strat,lazyReduce);
3339 delete(strat);
3340
3341#ifdef HAVE_PLURAL
3342 if(pp != p)
3344#endif
3345
3346 return res;
3347}
3348
3349ideal kNFBound(ideal F, ideal Q, ideal p,int bound,int syzComp,int lazyReduce)
3350{
3351 ideal res;
3352 if (TEST_OPT_PROT)
3353 {
3354 Print("(S:%d)",IDELEMS(p));mflush();
3355 }
3356 if (idIs0(p))
3357 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3358
3359 ideal pp = p;
3360#ifdef HAVE_PLURAL
3361 if(rIsSCA(currRing))
3362 {
3363 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3364 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3365 pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3366
3367 if(Q == currRing->qideal)
3369 }
3370#endif
3371
3372 if ((idIs0(F))&&(Q==NULL))
3373 {
3374#ifdef HAVE_PLURAL
3375 if(p != pp)
3376 return pp;
3377#endif
3378 return idCopy(p); /*F+Q=0*/
3379 }
3380
3381 kStrategy strat=new skStrategy;
3382 strat->syzComp = syzComp;
3384 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3385 {
3386 strat->ak = si_max(strat->ak,(int)F->rank);
3387 }
3388
3389 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3390 delete(strat);
3391
3392#ifdef HAVE_PLURAL
3393 if(pp != p)
3395#endif
3396
3397 return res;
3398}
3399
3400poly k_NF (ideal F, ideal Q, poly p,int syzComp, int lazyReduce, const ring _currRing)
3401{
3402 const ring save = currRing;
3403 if( currRing != _currRing ) rChangeCurrRing(_currRing);
3404 poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3405 if( currRing != save ) rChangeCurrRing(save);
3406 return ret;
3407}
3408
3409/*2
3410*interreduces F
3411*/
3412// old version
3413ideal kInterRedOld (ideal F,const ideal Q)
3414{
3415 int j;
3416 kStrategy strat = new skStrategy;
3417
3418 ideal tempF = F;
3419 ideal tempQ = Q;
3420
3421#ifdef HAVE_PLURAL
3422 if(rIsSCA(currRing))
3423 {
3424 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3425 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3426 tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3427
3428 // this should be done on the upper level!!! :
3429 // tempQ = SCAQuotient(currRing);
3430
3431 if(Q == currRing->qideal)
3432 tempQ = SCAQuotient(currRing);
3433 }
3434#endif
3435
3436// if (TEST_OPT_PROT)
3437// {
3438// writeTime("start InterRed:");
3439// mflush();
3440// }
3441 //strat->syzComp = 0;
3442 strat->kAllAxis = (currRing->ppNoether) != NULL;
3443 strat->kNoether=pCopy((currRing->ppNoether));
3444 strat->ak = id_RankFreeModule(tempF,currRing);
3445 initBuchMoraCrit(strat);
3446 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3447 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3448 strat->enterS = enterSBba;
3449 strat->posInT = posInT17;
3450 strat->initEcart = initEcartNormal;
3451 strat->sl = -1;
3452 strat->tl = -1;
3453 strat->tmax = setmaxT;
3454 strat->T = initT();
3455 strat->R = initR();
3456 strat->sevT = initsevT();
3458 initS(tempF, tempQ, strat);
3459 if (TEST_OPT_REDSB)
3460 strat->noTailReduction=FALSE;
3461 updateS(TRUE,strat);
3463 completeReduce(strat);
3464 //else if (TEST_OPT_PROT) PrintLn();
3465 cleanT(strat);
3466 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
3467 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3468 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3469 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3470 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3471 omfree(strat->sevT);
3472 omfree(strat->S_2_R);
3473 omfree(strat->R);
3474
3475 if (strat->fromQ)
3476 {
3477 for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3478 {
3479 if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3480 }
3481 omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
3482 }
3483// if (TEST_OPT_PROT)
3484// {
3485// writeTime("end Interred:");
3486// mflush();
3487// }
3488 ideal shdl=strat->Shdl;
3489 idSkipZeroes(shdl);
3490 if (strat->fromQ)
3491 {
3492 strat->fromQ=NULL;
3493 ideal res=kInterRed(shdl,NULL);
3494 idDelete(&shdl);
3495 shdl=res;
3496 }
3497 delete(strat);
3498#ifdef HAVE_PLURAL
3499 if( tempF != F )
3500 id_Delete( &tempF, currRing);
3501#endif
3502 return shdl;
3503}
3504// new version
3505ideal kInterRedBba (ideal F, ideal Q, int &need_retry)
3506{
3507 need_retry=0;
3508 int red_result = 1;
3509 int olddeg,reduc;
3510 BOOLEAN withT = FALSE;
3511 // BOOLEAN toReset=FALSE;
3512 kStrategy strat=new skStrategy;
3513 tHomog h;
3514
3516 strat->LazyPass=20;
3517 else
3518 strat->LazyPass=2;
3519 strat->LazyDegree = 1;
3520 strat->ak = id_RankFreeModule(F,currRing);
3521 strat->syzComp = strat->ak;
3522 strat->kModW=kModW=NULL;
3523 strat->kHomW=kHomW=NULL;
3524 if (strat->ak == 0)
3525 {
3526 h = (tHomog)idHomIdeal(F,Q);
3527 }
3528 else if (!TEST_OPT_DEGBOUND)
3529 {
3530 h = (tHomog)idHomIdeal(F,Q);
3531 }
3532 else
3533 h = isNotHomog;
3534 if (h==isHomog)
3535 {
3536 strat->LazyPass*=2;
3537 }
3538 strat->homog=h;
3539#ifdef KDEBUG
3540 idTest(F);
3541#endif
3542
3543 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
3545 initBuchMoraPosRing(strat);
3546 else
3547 initBuchMoraPos(strat);
3548 initBba(strat);
3549 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
3550 strat->posInL=posInL0; /* ord according pComp */
3551
3552 /*Shdl=*/initBuchMora(F, Q, strat);
3553 reduc = olddeg = 0;
3554
3555#ifndef NO_BUCKETS
3557 strat->use_buckets = 1;
3558#endif
3559
3560 // redtailBBa against T for inhomogeneous input
3561 if (!TEST_OPT_OLDSTD)
3562 withT = ! strat->homog;
3563
3564 // strat->posInT = posInT_pLength;
3565 kTest_TS(strat);
3566
3567#ifdef HAVE_TAIL_RING
3569#endif
3570
3571 /* compute------------------------------------------------------- */
3572 while (strat->Ll >= 0)
3573 {
3574 #ifdef KDEBUG
3575 if (TEST_OPT_DEBUG) messageSets(strat);
3576 #endif
3577 if (strat->Ll== 0) strat->interpt=TRUE;
3578 /* picks the last element from the lazyset L */
3579 strat->P = strat->L[strat->Ll];
3580 strat->Ll--;
3581
3582 if (strat->P.p1 == NULL)
3583 {
3584 // for input polys, prepare reduction
3585 strat->P.PrepareRed(strat->use_buckets);
3586 }
3587
3588 if (strat->P.p == NULL && strat->P.t_p == NULL)
3589 {
3590 red_result = 0;
3591 }
3592 else
3593 {
3594 if (TEST_OPT_PROT)
3595 message(strat->P.pFDeg(),
3596 &olddeg,&reduc,strat, red_result);
3597
3598 /* reduction of the element chosen from L */
3599 red_result = strat->red(&strat->P,strat);
3600 }
3601
3602 // reduction to non-zero new poly
3603 if (red_result == 1)
3604 {
3605 /* statistic */
3606 if (TEST_OPT_PROT) PrintS("s");
3607
3608 // get the polynomial (canonicalize bucket, make sure P.p is set)
3609 strat->P.GetP(strat->lmBin);
3610
3611 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3612
3613 // reduce the tail and normalize poly
3614 // in the ring case we cannot expect LC(f) = 1,
3615 // therefore we call pCleardenom instead of pNorm
3617 {
3618 strat->P.pCleardenom();
3619 if (0)
3620 //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3621 {
3622 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3623 strat->P.pCleardenom();
3624 }
3625 }
3626 else
3627 {
3628 strat->P.pNorm();
3629 if (0)
3630 //if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
3631 strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3632 }
3633
3634#ifdef KDEBUG
3635 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3636#endif
3637
3638 // enter into S, L, and T
3639 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3640 {
3641 enterT(strat->P, strat);
3642 // posInS only depends on the leading term
3643 strat->enterS(strat->P, pos, strat, strat->tl);
3644
3645 if (pos<strat->sl)
3646 {
3647 need_retry++;
3648 // move all "larger" elements fromS to L
3649 // remove them from T
3650 int ii=pos+1;
3651 for(;ii<=strat->sl;ii++)
3652 {
3653 LObject h;
3654 h.Clear();
3655 h.tailRing=strat->tailRing;
3656 h.p=strat->S[ii]; strat->S[ii]=NULL;
3657 strat->initEcart(&h);
3658 h.sev=strat->sevS[ii];
3659 int jj=strat->tl;
3660 while (jj>=0)
3661 {
3662 if (strat->T[jj].p==h.p)
3663 {
3664 strat->T[jj].p=NULL;
3665 if (jj<strat->tl)
3666 {
3667 memmove(&(strat->T[jj]),&(strat->T[jj+1]),
3668 (strat->tl-jj)*sizeof(strat->T[jj]));
3669 memmove(&(strat->sevT[jj]),&(strat->sevT[jj+1]),
3670 (strat->tl-jj)*sizeof(strat->sevT[jj]));
3671 }
3672 strat->tl--;
3673 break;
3674 }
3675 jj--;
3676 }
3677 int lpos=strat->posInL(strat->L,strat->Ll,&h,strat);
3678 enterL(&strat->L,&strat->Ll,&strat->Lmax,h,lpos);
3679 #ifdef KDEBUG
3680 if (TEST_OPT_DEBUG)
3681 {
3682 Print("move S[%d] -> L[%d]: ",ii,pos);
3683 p_wrp(h.p,currRing, strat->tailRing);
3684 PrintLn();
3685 }
3686 #endif
3687 }
3688 if (strat->fromQ!=NULL)
3689 {
3690 for(ii=pos+1;ii<=strat->sl;ii++) strat->fromQ[ii]=0;
3691 }
3692 strat->sl=pos;
3693 }
3694 }
3695 else
3696 {
3697 // clean P
3698 }
3699 kDeleteLcm(&strat->P);
3700 }
3701
3702#ifdef KDEBUG
3703 if (TEST_OPT_DEBUG)
3704 {
3705 messageSets(strat);
3706 }
3707 strat->P.Clear();
3708#endif
3709 //kTest_TS(strat);: i_r out of sync in kInterRedBba, but not used!
3710 }
3711#ifdef KDEBUG
3712 //if (TEST_OPT_DEBUG) messageSets(strat);
3713#endif
3714 /* complete reduction of the standard basis--------- */
3715
3716 if((need_retry<=0) && (TEST_OPT_REDSB))
3717 {
3718 completeReduce(strat);
3719 if (strat->completeReduce_retry)
3720 {
3721 // completeReduce needed larger exponents, retry
3722 // hopefully: kStratChangeTailRing already provided a larger tailRing
3723 // (otherwise: it will fail again)
3725 completeReduce(strat);
3726 if (strat->completeReduce_retry)
3727 {
3728#ifdef HAVE_TAIL_RING
3729 if(currRing->bitmask>strat->tailRing->bitmask)
3730 {
3731 // retry without T
3733 cleanT(strat);strat->tailRing=currRing;
3734 int i;
3735 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3736 completeReduce(strat);
3737 }
3738 if (strat->completeReduce_retry)
3739#endif
3740 Werror("exponent bound is %ld",currRing->bitmask);
3741 }
3742 }
3743 }
3744 else if (TEST_OPT_PROT) PrintLn();
3745
3746
3747 /* release temp data-------------------------------- */
3748 exitBuchMora(strat);
3749// if (TEST_OPT_WEIGHTM)
3750// {
3751// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3752// if (ecartWeights)
3753// {
3754// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
3755// ecartWeights=NULL;
3756// }
3757// }
3758 //if (TEST_OPT_PROT) messageStat(0/*hilbcount*/,strat);
3759 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3760 ideal res=strat->Shdl;
3761 strat->Shdl=NULL;
3762 delete strat;
3763 return res;
3764}
3765ideal kInterRed (ideal F,const ideal Q)
3766{
3767#ifdef HAVE_PLURAL
3768 if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3769#endif
3772 )
3773 return kInterRedOld(F,Q);
3774
3775 //return kInterRedOld(F,Q);
3776
3777 BITSET save1;
3778 SI_SAVE_OPT1(save1);
3779 //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3781 //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3782 //si_opt_1&= ~Sy_bit(OPT_REDSB);
3783 //extern char * showOption() ;
3784 //Print("%s\n",showOption());
3785
3786 int need_retry;
3787 int counter=3;
3788 ideal res, res1;
3789 int elems;
3790 ideal null=NULL;
3791 if ((Q==NULL) || (!TEST_OPT_REDSB))
3792 {
3793 elems=idElem(F);
3794 res=kInterRedBba(F,Q,need_retry);
3795 }
3796 else
3797 {
3798 ideal FF=idSimpleAdd(F,Q);
3799 res=kInterRedBba(FF,NULL,need_retry);
3800 idDelete(&FF);
3801 null=idInit(1,1);
3802 if (need_retry)
3803 res1=kNF(null,Q,res,0,KSTD_NF_LAZY);
3804 else
3805 res1=kNF(null,Q,res);
3806 idDelete(&res);
3807 res=res1;
3808 need_retry=1;
3809 }
3810 if (idElem(res)<=1) need_retry=0;
3811 while (need_retry && (counter>0))
3812 {
3813 #ifdef KDEBUG
3814 if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3815 #endif
3816 res1=kInterRedBba(res,Q,need_retry);
3817 int new_elems=idElem(res1);
3818 counter -= (new_elems >= elems);
3819 elems = new_elems;
3820 idDelete(&res);
3821 if (idElem(res1)<=1) need_retry=0;
3822 if ((Q!=NULL) && (TEST_OPT_REDSB))
3823 {
3824 if (need_retry)
3825 res=kNF(null,Q,res1,0,KSTD_NF_LAZY);
3826 else
3827 res=kNF(null,Q,res1);
3828 idDelete(&res1);
3829 }
3830 else
3831 res = res1;
3832 if (idElem(res)<=1) need_retry=0;
3833 }
3834 if (null!=NULL) idDelete(&null);
3835 SI_RESTORE_OPT1(save1);
3837 return res;
3838}
3839
3840// returns TRUE if mora should use buckets, false otherwise
3842{
3843#ifdef MORA_USE_BUCKETS
3845 return FALSE;
3846 if (strat->red == redFirst)
3847 {
3848#ifdef NO_LDEG
3849 if (strat->syzComp==0)
3850 return TRUE;
3851#else
3852 if ((strat->homog || strat->honey) && (strat->syzComp==0))
3853 return TRUE;
3854#endif
3855 }
3856 else
3857 {
3858 #ifdef HAVE_RINGS
3859 assume(strat->red == redEcart || strat->red == redRiloc || strat->red == redRiloc_Z);
3860 #else
3861 assume(strat->red == redEcart);
3862 #endif
3863 if (strat->honey && (strat->syzComp==0))
3864 return TRUE;
3865 }
3866#endif
3867 return FALSE;
3868}
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
#define UNLIKELY(X)
Definition: auxiliary.h:404
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
void * ADDRESS
Definition: auxiliary.h:119
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4078
CanonicalForm b
Definition: cfModGcd.cc:4103
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
Definition: intvec.h:23
KINLINE poly kNoetherTail()
Definition: kInline.h:66
intvec * kModW
Definition: kutil.h:335
bool sigdrop
Definition: kutil.h:359
int * S_2_R
Definition: kutil.h:342
ring tailRing
Definition: kutil.h:343
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:291
char noTailReduction
Definition: kutil.h:378
int currIdx
Definition: kutil.h:317
char posInLOldFlag
Definition: kutil.h:382
pFDegProc pOrigFDeg_TailRing
Definition: kutil.h:298
int Ll
Definition: kutil.h:351
TSet T
Definition: kutil.h:326
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:293
omBin lmBin
Definition: kutil.h:344
intset ecartS
Definition: kutil.h:309
char honey
Definition: kutil.h:377
unsigned syzComp
Definition: kutil.h:354
char rightGB
Definition: kutil.h:369
polyset S
Definition: kutil.h:306
int minim
Definition: kutil.h:357
poly kNoether
Definition: kutil.h:329
BOOLEAN * NotUsedAxis
Definition: kutil.h:332
LSet B
Definition: kutil.h:328
int ak
Definition: kutil.h:353
TObject ** R
Definition: kutil.h:340
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:295
int lastAxis
Definition: kutil.h:355
ideal M
Definition: kutil.h:305
int tl
Definition: kutil.h:350
int(* red2)(LObject *L, kStrategy strat)
Definition: kutil.h:279
unsigned long * sevT
Definition: kutil.h:325
intvec * kHomW
Definition: kutil.h:336
poly tail
Definition: kutil.h:334
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:284
int blockred
Definition: kutil.h:364
ideal Shdl
Definition: kutil.h:303
unsigned sbaOrder
Definition: kutil.h:316
pFDegProc pOrigFDeg
Definition: kutil.h:296
int blockredmax
Definition: kutil.h:365
int tmax
Definition: kutil.h:350
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:288
char LDegLast
Definition: kutil.h:385
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:287
char kAllAxis
Definition: kutil.h:376
intset fromQ
Definition: kutil.h:321
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:286
char use_buckets
Definition: kutil.h:383
char interpt
Definition: kutil.h:371
int newIdeal
Definition: kutil.h:356
char fromT
Definition: kutil.h:379
char completeReduce_retry
Definition: kutil.h:403
void(* initEcart)(TObject *L)
Definition: kutil.h:280
LObject P
Definition: kutil.h:302
char noClearS
Definition: kutil.h:402
int Lmax
Definition: kutil.h:351
char z2homog
Definition: kutil.h:374
int LazyPass
Definition: kutil.h:353
char no_prod_crit
Definition: kutil.h:394
char overflow
Definition: kutil.h:404
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.h:290
LSet L
Definition: kutil.h:327
char length_pLength
Definition: kutil.h:387
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:281
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:278
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:294
int sl
Definition: kutil.h:348
int sbaEnterS
Definition: kutil.h:362
int LazyDegree
Definition: kutil.h:353
char posInLDependsOnLength
Definition: kutil.h:389
unsigned long * sevS
Definition: kutil.h:322
char homog
Definition: kutil.h:372
pLDegProc pOrigLDeg
Definition: kutil.h:297
char update
Definition: kutil.h:381
s_poly_proc_t s_poly
Definition: kutil.h:300
pLDegProc pOrigLDeg_TailRing
Definition: kutil.h:299
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition: coeffs.h:813
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 number n_QuotRem(number a, number b, number *q, const coeffs r)
Definition: coeffs.h:678
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:461
static FORCE_INLINE BOOLEAN n_DivBy(number a, number b, const coeffs r)
test whether 'a' is divisible 'b'; for r encoding a field: TRUE iff 'b' does not represent zero in Z:...
Definition: coeffs.h:750
#define Print
Definition: emacs.cc:80
#define WarnS
Definition: emacs.cc:78
CanonicalForm res
Definition: facAbsFact.cc:60
const CanonicalForm & w
Definition: facAbsFact.cc:51
CanonicalForm H
Definition: facAbsFact.cc:60
int j
Definition: facHensel.cc:110
void WerrorS(const char *s)
Definition: feFopen.cc:24
if(!FE_OPT_NO_SHELL_FLAG)(void) system(sys)
#define VAR
Definition: globaldefs.h:5
long scMult0Int(ideal S, ideal Q)
Definition: hdegree.cc:950
STATIC_VAR poly last
Definition: hdegree.cc:1172
ideal idMinBase(ideal h1, ideal *SB)
Definition: ideals.cc:51
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
#define idSimpleAdd(A, B)
Definition: ideals.h:42
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
static BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition: ideals.h:96
#define idTest(id)
Definition: ideals.h:47
static BOOLEAN idHomIdeal(ideal id, ideal Q=NULL)
Definition: ideals.h:91
ideal idCopy(ideal A)
Definition: ideals.h:60
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
STATIC_VAR Poly * h
Definition: janet.cc:971
STATIC_VAR jList * Q
Definition: janet.cc:30
KINLINE TSet initT()
Definition: kInline.h:84
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition: kInline.h:1214
KINLINE TObject ** initR()
Definition: kInline.h:95
KINLINE BOOLEAN arriRewDummy(poly, unsigned long, poly, kStrategy, int)
Definition: kInline.h:1264
KINLINE unsigned long * initsevT()
Definition: kInline.h:100
int redLiftstd(LObject *h, kStrategy strat)
Definition: kLiftstd.cc:167
static ideal nc_GB(const ideal F, const ideal Q, const intvec *w, const intvec *hilb, kStrategy strat, const ring r)
Definition: nc.h:27
void khCheckLocInhom(ideal Q, intvec *w, intvec *hilb, int &count, kStrategy strat)
Definition: khstd.cc:133
void khCheck(ideal Q, intvec *w, intvec *hilb, int &eledeg, int &count, kStrategy strat)
Definition: khstd.cc:28
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition: kspoly.cc:481
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition: kspoly.cc:1208
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat, BOOLEAN reduce)
Definition: kspoly.cc:189
long kHomModDeg(poly p, const ring r)
Definition: kstd1.cc:2436
void reorderT(kStrategy strat)
Definition: kstd1.cc:1246
poly kNFBound(ideal F, ideal Q, poly p, int bound, int syzComp, int lazyReduce)
Definition: kstd1.cc:3242
ideal mora(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd1.cc:1888
void initMora(ideal F, kStrategy strat)
Definition: kstd1.cc:1819
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:797
void firstUpdate(kStrategy strat)
Definition: kstd1.cc:1561
long kModDeg(poly p, const ring r)
Definition: kstd1.cc:2426
poly k_NF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce, const ring _currRing)
NOTE: this is just a wrapper which sets currRing for the actual kNF call.
Definition: kstd1.cc:3400
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:169
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1681
static int doRed(LObject *h, TObject *with, BOOLEAN intoT, kStrategy strat, bool redMoraNF)
Definition: kstd1.cc:119
ideal kMin_std(ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb, int syzComp, int reduced)
Definition: kstd1.cc:3036
void updateLHC(kStrategy strat)
Definition: kstd1.cc:1469
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition: kstd1.cc:2928
void missingAxis(int *last, kStrategy strat)
Definition: kstd1.cc:1284
void reorderL(kStrategy strat)
Definition: kstd1.cc:1226
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition: kstd1.cc:1365
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition: kstd1.cc:3505
static BOOLEAN kMoraUseBucket(kStrategy strat)
Definition: kstd1.cc:3841
poly kNF1(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd1.cc:2126
ideal kInterRed(ideal F, const ideal Q)
Definition: kstd1.cc:3765
static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
Definition: kstd1.cc:100
void initBba(kStrategy strat)
Definition: kstd1.cc:1689
int redRiloc(LObject *h, kStrategy strat)
Definition: kstd1.cc:387
void initSba(ideal F, kStrategy strat)
Definition: kstd1.cc:1749
static poly redMoraNFRing(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:1083
void kDebugPrint(kStrategy strat)
Definition: kutil.cc:11560
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1628
VAR intvec * kHomW
Definition: kstd1.cc:2424
VAR intvec * kModW
Definition: kstd1.cc:2424
ideal kInterRedOld(ideal F, const ideal Q)
Definition: kstd1.cc:3413
void updateL(kStrategy strat)
Definition: kstd1.cc:1398
VAR BITSET validOpts
Definition: kstd1.cc:60
void updateT(kStrategy strat)
Definition: kstd1.cc:1535
BOOLEAN hasPurePower(const poly p, int last, int *length, kStrategy strat)
Definition: kstd1.cc:1317
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3186
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:978
VAR BITSET kOptions
Definition: kstd1.cc:45
int redRiloc_Z(LObject *h, kStrategy strat)
Definition: kstd1.cc:568
ideal kSba(ideal F, ideal Q, tHomog h, intvec **w, int sbaOrder, int arri, intvec *hilb, int syzComp, int newIdeal, intvec *vw)
Definition: kstd1.cc:2634
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:2449
#define KSTD_NF_LAZY
Definition: kstd1.h:17
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:50
#define KSTD_NF_NONORM
Definition: kstd1.h:21
BOOLEAN(* s_poly_proc_t)(kStrategy strat)
Definition: kstd1.h:14
#define KSTD_NF_ECART
Definition: kstd1.h:19
EXTERN_VAR int Kstd1_mu
Definition: kstd1.h:50
int redRing_Z(LObject *h, kStrategy strat)
Definition: kstd2.cc:683
int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject *L)
return -1 if no divisor is found number of first divisor in S, otherwise
Definition: kstd2.cc:421
int kTestDivisibleByT0_Z(const kStrategy strat, const LObject *L)
tests if T[0] divides the leading monomial of L, returns -1 if not
Definition: kstd2.cc:146
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3960
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:2084
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:1121
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2994
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2636
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1879
int redSigRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:1509
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:1341
poly kNF2Bound(ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:4042
int redRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:954
int kFindDivisibleByInT(const kStrategy strat, const LObject *L, const int start)
return -1 if no divisor is found number of first divisor in T, otherwise
Definition: kstd2.cc:321
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:4601
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:7512
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:6883
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5306
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:9800
VAR int HCord
Definition: kutil.cc:246
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition: kutil.cc:6689
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9178
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition: kutil.cc:6664
void enterSSba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:8952
BOOLEAN kTest(kStrategy strat)
Definition: kutil.cc:1012
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:1073
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition: kutil.cc:1952
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition: kutil.cc:1280
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition: kutil.cc:6605
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4947
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4509
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9458
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1326
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9627
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7635
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition: kutil.cc:11021
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition: kutil.cc:5643
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3458
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9278
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition: kutil.cc:10763
void HEckeTest(poly pp, kStrategy strat)
Definition: kutil.cc:501
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition: kutil.cc:926
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:9885
void initEcartNormal(TObject *h)
Definition: kutil.cc:1304
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:4685
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:8594
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10534
void cleanT(kStrategy strat)
Definition: kutil.cc:565
BOOLEAN kTest_T(TObject *T, kStrategy strat, int i, char TN)
Definition: kutil.cc:801
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition: kutil.cc:294
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10128
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4478
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1215
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11114
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9476
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10340
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9713
void messageSets(kStrategy strat)
Definition: kutil.cc:7585
poly preIntegerCheck(const ideal Forig, const ideal Q)
used for GB over ZZ: look for constant and monomial elements in the ideal background: any known const...
Definition: kutil.cc:10596
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3217
void initEcartBBA(TObject *h)
Definition: kutil.cc:1312
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition: kutil.cc:1319
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7553
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition: kutil.cc:10928
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:8829
BOOLEAN newHEdge(kStrategy strat)
Definition: kutil.cc:10462
void cancelunit(LObject *L, BOOLEAN inNF)
Definition: kutil.cc:373
#define setmaxTinc
Definition: kutil.h:34
LObject * LSet
Definition: kutil.h:60
static void kDeleteLcm(LObject *P)
Definition: kutil.h:880
#define setmaxT
Definition: kutil.h:33
#define RED_CANONICALIZE
Definition: kutil.h:36
class sTObject TObject
Definition: kutil.h:57
class sLObject LObject
Definition: kutil.h:58
static bool rIsSCA(const ring r)
Definition: nc.h:190
ideal id_KillSquares(const ideal id, const short iFirstAltVar, const short iLastAltVar, const ring r, const bool bSkipZeroes)
Definition: sca.cc:1518
poly p_KillSquares(const poly p, const short iFirstAltVar, const short iLastAltVar, const ring r)
Definition: sca.cc:1463
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:647
#define assume(x)
Definition: mod2.h:389
#define p_GetComp(p, r)
Definition: monomials.h:64
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:44
#define __p_GetComp(p, r)
Definition: monomials.h:63
number ndQuotRem(number a, number b, number *r, const coeffs R)
Definition: numbers.cc:358
#define nEqual(n1, n2)
Definition: numbers.h:20
#define omfree(addr)
Definition: omAllocDecl.h:237
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
omError_t omTestMemory(int check_level)
Definition: omDebug.c:94
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
#define NULL
Definition: omList.c:12
VAR BOOLEAN siCntrlc
Definition: options.c:14
VAR unsigned si_opt_1
Definition: options.c:5
#define TEST_OPT_WEIGHTM
Definition: options.h:121
#define OPT_SUGARCRIT
Definition: options.h:80
#define OPT_PROT
Definition: options.h:75
#define OPT_INFREDTAIL
Definition: options.h:94
#define OPT_INTSTRATEGY
Definition: options.h:92
#define TEST_OPT_IDLIFT
Definition: options.h:129
#define TEST_OPT_INTSTRATEGY
Definition: options.h:110
#define BVERBOSE(a)
Definition: options.h:35
#define OPT_WEIGHTM
Definition: options.h:97
#define TEST_OPT_FINDET
Definition: options.h:111
#define OPT_REDTAIL
Definition: options.h:91
#define SI_SAVE_OPT1(A)
Definition: options.h:21
#define SI_RESTORE_OPT1(A)
Definition: options.h:24
#define OPT_NOT_SUGAR
Definition: options.h:78
#define TEST_OPT_OLDSTD
Definition: options.h:123
#define OPT_REDTHROUGH
Definition: options.h:82
#define OPT_REDSB
Definition: options.h:76
#define Sy_bit(x)
Definition: options.h:31
#define TEST_OPT_REDSB
Definition: options.h:104
#define OPT_NOTREGULARITY
Definition: options.h:96
#define TEST_OPT_DEGBOUND
Definition: options.h:113
#define TEST_OPT_SB_1
Definition: options.h:119
#define TEST_OPT_RETURN_SB
Definition: options.h:112
#define TEST_OPT_MULTBOUND
Definition: options.h:114
#define TEST_OPT_PROT
Definition: options.h:103
#define TEST_OPT_REDTHROUGH
Definition: options.h:122
#define OPT_INTERRUPT
Definition: options.h:79
#define OPT_DEGBOUND
Definition: options.h:90
#define TEST_V_DEG_STOP
Definition: options.h:137
#define TEST_OPT_FASTHC
Definition: options.h:109
#define TEST_OPT_DEBUG
Definition: options.h:108
#define OPT_FASTHC
Definition: options.h:85
#define TEST_OPT_REDTAIL_SYZ
Definition: options.h:117
#define OPT_OLDSTD
Definition: options.h:86
#define TEST_OPT_STAIRCASEBOUND
Definition: options.h:115
#define TEST_OPT_NOT_BUCKETS
Definition: options.h:105
pShallowCopyDeleteProc pGetShallowCopyDeleteProc(ring, ring)
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition: p_polys.cc:1226
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition: p_polys.cc:3649
long pLDeg0c(poly p, int *l, const ring r)
Definition: p_polys.cc:770
long pLDeg0(poly p, int *l, const ring r)
Definition: p_polys.cc:739
void pSetDegProcs(ring r, pFDegProc new_FDeg, pLDegProc new_lDeg)
Definition: p_polys.cc:3637
long p_WDegree(poly p, const ring r)
Definition: p_polys.cc:714
static int pLength(poly a)
Definition: p_polys.h:190
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:723
static long p_FDeg(const poly p, const ring r)
Definition: p_polys.h:380
static long p_MinComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:313
#define pp_Test(p, lmRing, tailRing)
Definition: p_polys.h:163
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1910
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:469
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:901
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:373
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)
#define pAdd(p, q)
Definition: polys.h:203
#define pTest(p)
Definition: polys.h:414
#define pDelete(p_ptr)
Definition: polys.h:186
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition: polys.h:67
#define pSetm(p)
Definition: polys.h:271
#define pIsConstant(p)
like above, except that Comp must be 0
Definition: polys.h:238
#define pGetComp(p)
Component.
Definition: polys.h:37
void pNorm(poly p)
Definition: polys.h:362
#define pLmShortDivisibleBy(a, sev_a, b, not_sev_b)
Divisibility tests based on Short Exponent vectors sev_a == pGetShortExpVector(a) not_sev_b == ~ pGet...
Definition: polys.h:146
#define pMaxComp(p)
Definition: polys.h:299
#define pSetComp(p, v)
Definition: polys.h:38
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
Definition: polys.h:152
void wrp(poly p)
Definition: polys.h:310
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
Definition: polys.h:70
#define pSetmComp(p)
TODO:
Definition: polys.h:273
#define pNormalize(p)
Definition: polys.h:317
#define pSetExp(p, i, v)
Definition: polys.h:42
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105
#define pCopy(p)
return a copy of the poly
Definition: polys.h:185
#define pOne()
Definition: polys.h:315
#define pWTotaldegree(p)
Definition: polys.h:283
void PrintS(const char *s)
Definition: reporter.cc:284
void PrintLn()
Definition: reporter.cc:310
void Werror(const char *fmt,...)
Definition: reporter.cc:189
#define mflush()
Definition: reporter.h:58
static BOOLEAN rField_is_Z(const ring r)
Definition: ring.h:509
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:400
long(* pLDegProc)(poly p, int *length, ring r)
Definition: ring.h:37
static BOOLEAN rIsLPRing(const ring r)
Definition: ring.h:411
static BOOLEAN rIsNCRing(const ring r)
Definition: ring.h:421
static BOOLEAN rField_is_numeric(const ring r)
Definition: ring.h:515
BOOLEAN rHasMixedOrdering(const ring r)
Definition: ring.h:763
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:592
BOOLEAN rHasGlobalOrdering(const ring r)
Definition: ring.h:761
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:762
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:548
#define rField_is_Ring(R)
Definition: ring.h:485
ideal SCAQuotient(const ring r)
Definition: sca.h:10
static short scaLastAltVar(ring r)
Definition: sca.h:25
static short scaFirstAltVar(ring r)
Definition: sca.h:18
#define idIsInV(I)
Definition: shiftop.h:49
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
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define IDELEMS(i)
Definition: simpleideals.h:23
static int idElem(const ideal F)
number of non-zero polys in F
Definition: simpleideals.h:69
#define M
Definition: sirandom.c:25
tHomog
Definition: structs.h:35
@ isHomog
Definition: structs.h:37
@ testHomog
Definition: structs.h:38
@ isNotHomog
Definition: structs.h:36
#define BITSET
Definition: structs.h:16
#define loop
Definition: structs.h:75
long totaldegreeWecart(poly p, ring r)
Definition: weight.cc:217
long maxdegreeWecart(poly p, int *l, ring r)
Definition: weight.cc:247
void kEcartWeights(poly *s, int sl, short *eweight, const ring R)
Definition: weight.cc:182
EXTERN_VAR short * ecartWeights
Definition: weight.h:12