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