Context Navigation

source: git/kernel/GBEngine/kstd2.cc @ b45eec

spielwiese

Last change on this file since b45eec was b45eec, checked in by Karim Abou Zeid <karim23697@…>, 4 years ago
Merge branch 'stable' into lp_Z
Property mode set to `100644`
File size: 130.2 KB

Line
1	/****************************************
2	* Computer Algebra System SINGULAR *
3	****************************************/
4	/*
5	* ABSTRACT - Kernel: alg. of Buchberger
6	*/
7
8	// #define PDEBUG 2
9
10	#include "kernel/mod2.h"
11
12	#define GCD_SBA 1
13
14	// define if no buckets should be used
15	// #define NO_BUCKETS
16
17	#ifdef HAVE_PLURAL
18	#define PLURAL_INTERNAL_DECLARATIONS 1
19	#endif
20
21	/***********************************************
22	* SBA stuff -- start
23	***********************************************/
24	#define DEBUGF50 0
25	#define DEBUGF51 0
26
27	#ifdef DEBUGF5
28	#undef DEBUGF5
29	//#define DEBUGF5 1
30	#endif
31
32	#define F5C 1
33	#if F5C
34	#define F5CTAILRED 1
35	#endif
36
37	#define SBA_INTERRED_START 0
38	#define SBA_TAIL_RED 1
39	#define SBA_PRODUCT_CRITERION 0
40	#define SBA_PRINT_ZERO_REDUCTIONS 0
41	#define SBA_PRINT_REDUCTION_STEPS 0
42	#define SBA_PRINT_OPERATIONS 0
43	#define SBA_PRINT_SIZE_G 0
44	#define SBA_PRINT_SIZE_SYZ 0
45	#define SBA_PRINT_PRODUCT_CRITERION 0
46
47	// counts sba's reduction steps
48	#if SBA_PRINT_REDUCTION_STEPS
49	VAR long sba_reduction_steps;
50	VAR long sba_interreduction_steps;
51	#endif
52	#if SBA_PRINT_OPERATIONS
53	VAR long sba_operations;
54	VAR long sba_interreduction_operations;
55	#endif
56
57	/***********************************************
58	* SBA stuff -- done
59	***********************************************/
60
61	#include "kernel/GBEngine/kutil.h"
62	#include "misc/options.h"
63	#include "kernel/polys.h"
64	#include "kernel/ideals.h"
65	#include "kernel/GBEngine/kstd1.h"
66	#include "kernel/GBEngine/khstd.h"
67	#include "polys/kbuckets.h"
68	#include "polys/prCopy.h"
69	#include "polys/weight.h"
70	#include "misc/intvec.h"
71	#ifdef HAVE_PLURAL
72	#include "polys/nc/nc.h"
73	#endif
74	// #include "timer.h"
75
76	#ifdef HAVE_SHIFTBBA
77	#include "polys/shiftop.h"
78	#endif
79
80	VAR int (*test_PosInT)(const TSet T,const int tl,LObject &h);
81	VAR int (*test_PosInL)(const LSet set, const int length,
82	LObject* L,const kStrategy strat);
83
84	int kFindSameLMInT_Z(const kStrategy strat, const LObject* L, const int start)
85	{
86	unsigned long not_sev = ~L->sev;
87	int j = start;
88	int o = -1;
89
90	const TSet T=strat->T;
91	const unsigned long* sevT=strat->sevT;
92	number gcd, ogcd;
93	if (L->p!=NULL)
94	{
95	const ring r=currRing;
96	const poly p=L->p;
97	ogcd = pGetCoeff(p);
98
99	pAssume(~not_sev == p_GetShortExpVector(p, r));
100
101	loop
102	{
103	if (j > strat->tl) return o;
104	if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
105	{
106	gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
107	if (o == -1 \|\|
108	n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf) == TRUE) {
109	ogcd = gcd;
110	o = j;
111	}
112	}
113	j++;
114	}
115	}
116	else
117	{
118	const ring r=strat->tailRing;
119	const poly p=L->t_p;
120	ogcd = pGetCoeff(p);
121	loop
122	{
123	if (j > strat->tl) return o;
124	if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
125	{
126	gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
127	if (o == -1 \|\|
128	n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf) == TRUE) {
129	ogcd = gcd;
130	o = j;
131	}
132	}
133	j++;
134	}
135	}
136	}
137	// return -1 if T[0] does not divide the leading monomial
138	int kTestDivisibleByT0_Z(const kStrategy strat, const LObject* L)
139	{
140	if (strat->tl < 1)
141	return -1;
142
143	unsigned long not_sev = ~L->sev;
144	const unsigned long sevT0 = strat->sevT[0];
145	number rest, orest, mult;
146	if (L->p!=NULL)
147	{
148	const poly T0p = strat->T[0].p;
149	const ring r = currRing;
150	const poly p = L->p;
151	orest = pGetCoeff(p);
152
153	pAssume(~not_sev == p_GetShortExpVector(p, r));
154
155	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
156	if (p_LmShortDivisibleBy(T0p, sevT0, p, not_sev, r))
157	{
158	mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
159	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf) == TRUE) {
160	return 0;
161	}
162	}
163	#else
164	if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
165	{
166	mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
167	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf) == TRUE) {
168	return 0;
169	}
170	}
171	#endif
172	}
173	else
174	{
175	const poly T0p = strat->T[0].t_p;
176	const ring r = strat->tailRing;
177	const poly p = L->t_p;
178	orest = pGetCoeff(p);
179	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
180	if (p_LmShortDivisibleBy(T0p, sevT0,
181	p, not_sev, r))
182	{
183	mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
184	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf) == TRUE) {
185	return 0;
186	}
187	}
188	#else
189	if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
190	{
191	mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
192	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf) == TRUE) {
193	return 0;
194	}
195	}
196	#endif
197	}
198	return -1;
199	}
200
201	int kFindDivisibleByInT_Z(const kStrategy strat, const LObject* L, const int start)
202	{
203	unsigned long not_sev = ~L->sev;
204	int j = start;
205	int o = -1;
206
207	const TSet T=strat->T;
208	const unsigned long* sevT=strat->sevT;
209	number rest, orest, mult;
210	if (L->p!=NULL)
211	{
212	const ring r=currRing;
213	const poly p=L->p;
214	orest = pGetCoeff(p);
215
216	pAssume(~not_sev == p_GetShortExpVector(p, r));
217
218	loop
219	{
220	if (j > strat->tl) return o;
221	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
222	if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
223	{
224	mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].p), &rest, r->cf);
225	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf) == TRUE) {
226	o = j;
227	orest = rest;
228	}
229	}
230	#else
231	if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].p, p, r))
232	{
233	mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].p), &rest, r->cf);
234	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf) == TRUE) {
235	o = j;
236	orest = rest;
237	}
238	}
239	#endif
240	j++;
241	}
242	}
243	else
244	{
245	const ring r=strat->tailRing;
246	const poly p=L->t_p;
247	orest = pGetCoeff(p);
248	loop
249	{
250	if (j > strat->tl) return o;
251	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
252	if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
253	p, not_sev, r))
254	{
255	mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].t_p), &rest, r->cf);
256	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf) == TRUE) {
257	o = j;
258	orest = rest;
259	}
260	}
261	#else
262	if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].t_p, p, r))
263	{
264	mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].t_p), &rest, r->cf);
265	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf) == TRUE) {
266	o = j;
267	orest = rest;
268	}
269	}
270	#endif
271	j++;
272	}
273	}
274	}
275
276	// return -1 if no divisor is found
277	// number of first divisor, otherwise
278	int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start)
279	{
280	unsigned long not_sev = ~L->sev;
281	int j = start;
282
283	const TSet T=strat->T;
284	const unsigned long* sevT=strat->sevT;
285	const ring r=currRing;
286	const BOOLEAN is_Ring=rField_is_Ring(r);
287	if (L->p!=NULL)
288	{
289	const poly p=L->p;
290
291	pAssume(~not_sev == p_GetShortExpVector(p, r));
292
293	if(is_Ring)
294	{
295	loop
296	{
297	if (j > strat->tl) return -1;
298	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
299	if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
300	{
301	if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
302	return j;
303	}
304	#else
305	if (!(sevT[j] & not_sev) &&
306	p_LmDivisibleBy(T[j].p, p, r))
307	{
308	if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
309	return j;
310	}
311	#endif
312	j++;
313	}
314	}
315	else
316	{
317	loop
318	{
319	if (j > strat->tl) return -1;
320	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
321	if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
322	{
323	return j;
324	}
325	#else
326	if (!(sevT[j] & not_sev) &&
327	p_LmDivisibleBy(T[j].p, p, r))
328	{
329	return j;
330	}
331	#endif
332	j++;
333	}
334	}
335	}
336	else
337	{
338	const poly p=L->t_p;
339	const ring r=strat->tailRing;
340	if(is_Ring)
341	{
342	loop
343	{
344	if (j > strat->tl) return -1;
345	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
346	if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
347	p, not_sev, r))
348	{
349	if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
350	return j;
351	}
352	#else
353	if (!(sevT[j] & not_sev) &&
354	p_LmDivisibleBy(T[j].t_p, p, r))
355	{
356	if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
357	return j;
358	}
359	#endif
360	j++;
361	}
362	}
363	else
364	{
365	loop
366	{
367	if (j > strat->tl) return -1;
368	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
369	if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
370	p, not_sev, r))
371	{
372	return j;
373	}
374	#else
375	if (!(sevT[j] & not_sev) &&
376	p_LmDivisibleBy(T[j].t_p, p, r))
377	{
378	return j;
379	}
380	#endif
381	j++;
382	}
383	}
384	}
385	}
386
387	// same as above, only with set S
388	int kFindDivisibleByInS(const kStrategy strat, int* max_ind, LObject* L)
389	{
390	unsigned long not_sev = ~L->sev;
391	poly p = L->GetLmCurrRing();
392	int j = 0;
393
394	pAssume(~not_sev == p_GetShortExpVector(p, currRing));
395
396	BOOLEAN is_Ring=rField_is_Ring(currRing);
397	#if 1
398	int ende;
399	if (is_Ring
400	\|\| (strat->ak>0)
401	\|\| currRing->pLexOrder)
402	ende=strat->sl;
403	else
404	{
405	ende=posInS(strat,*max_ind,p,0)+1;
406	if (ende>(max_ind)) ende=(max_ind);
407	}
408	#else
409	int ende=strat->sl;
410	#endif
411	if(is_Ring)
412	{
413	loop
414	{
415	if (j > ende) return -1;
416	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
417	if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
418	p, not_sev, currRing))
419	{
420	if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
421	return j;
422	}
423	#else
424	if ( !(strat->sevS[j] & not_sev) &&
425	p_LmDivisibleBy(strat->S[j], p, currRing))
426	{
427	if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
428	return j;
429	}
430	#endif
431	j++;
432	}
433	}
434	else
435	{
436	loop
437	{
438	if (j > ende) return -1;
439	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
440	if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
441	p, not_sev, currRing))
442	{
443	return j;
444	}
445	#else
446	if ( !(strat->sevS[j] & not_sev) &&
447	p_LmDivisibleBy(strat->S[j], p, currRing))
448	{
449	return j;
450	}
451	#endif
452	j++;
453	}
454	}
455	}
456
457	int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L)
458	{
459	unsigned long not_sev = ~L->sev;
460	poly p = L->GetLmCurrRing();
461	int j = start;
462
463	pAssume(~not_sev == p_GetShortExpVector(p, currRing));
464	#if 1
465	int ende=max_ind;
466	#else
467	int ende=strat->sl;
468	#endif
469	if(rField_is_Ring(currRing))
470	{
471	loop
472	{
473	if (j > ende) return -1;
474	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
475	if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
476	p, not_sev, currRing))
477	{
478	if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
479	return j;
480	}
481	#else
482	if ( !(strat->sevS[j] & not_sev) &&
483	p_LmDivisibleBy(strat->S[j], p, currRing))
484	{
485	if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
486	return j;
487	}
488	#endif
489	j++;
490	}
491	}
492	else
493	{
494	loop
495	{
496	if (j > ende) return -1;
497	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
498	if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
499	p, not_sev, currRing))
500	{
501	return j;
502	}
503	#else
504	if ( !(strat->sevS[j] & not_sev) &&
505	p_LmDivisibleBy(strat->S[j], p, currRing))
506	{
507	return j;
508	}
509	#endif
510	j++;
511	}
512	}
513	}
514
515	#ifdef HAVE_RINGS
516	poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
517	{
518	// m = currRing->ch
519
520	if (input_p == NULL) return NULL;
521
522	poly p = input_p;
523	poly zeroPoly = NULL;
524	unsigned long a = (unsigned long) pGetCoeff(p);
525
526	int k_ind2 = 0;
527	int a_ind2 = ind2(a);
528
529	// unsigned long k = 1;
530	// of interest is only k_ind2, special routine for improvement ... TODO OLIVER
531	for (int i = 1; i <= leadRing->N; i++)
532	{
533	k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing));
534	}
535
536	a = (unsigned long) pGetCoeff(p);
537
538	number tmp1;
539	poly tmp2, tmp3;
540	poly lead_mult = p_ISet(1, tailRing);
541	if (n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
542	{
543	int too_much = k_ind2 + a_ind2 - n_GetChar(leadRing->cf);
544	int s_exp;
545	zeroPoly = p_ISet(a, tailRing);
546	for (int i = 1; i <= leadRing->N; i++)
547	{
548	s_exp = p_GetExp(p, i,leadRing);
549	if (s_exp % 2 != 0)
550	{
551	s_exp = s_exp - 1;
552	}
553	while ( (0 < ind2(s_exp)) && (ind2(s_exp) <= too_much) )
554	{
555	too_much = too_much - ind2(s_exp);
556	s_exp = s_exp - 2;
557	}
558	p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing) - s_exp, tailRing);
559	for (int j = 1; j <= s_exp; j++)
560	{
561	tmp1 = nInit(j);
562	tmp2 = p_ISet(1, tailRing);
563	p_SetExp(tmp2, i, 1, tailRing);
564	p_Setm(tmp2, tailRing);
565	if (nIsZero(tmp1))
566	{ // should nowbe obsolet, test ! TODO OLIVER
567	zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
568	}
569	else
570	{
571	tmp3 = p_NSet(nCopy(tmp1), tailRing);
572	zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing);
573	}
574	}
575	}
576	p_Setm(lead_mult, tailRing);
577	zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing);
578	tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing);
579	for (int i = 1; i <= leadRing->N; i++)
580	{
581	pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
582	}
583	p_Setm(tmp2, leadRing);
584	zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
585	pNext(tmp2) = zeroPoly;
586	return tmp2;
587	}
588	/* unsigned long alpha_k = twoPow(leadRing->ch - k_ind2);
589	if (1 == 0 && alpha_k <= a)
590	{ // Temporarly disabled, reducing coefficients not compatible with std TODO Oliver
591	zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing);
592	for (int i = 1; i <= leadRing->N; i++)
593	{
594	for (unsigned long j = 1; j <= p_GetExp(p, i, leadRing); j++)
595	{
596	tmp1 = nInit(j);
597	tmp2 = p_ISet(1, tailRing);
598	p_SetExp(tmp2, i, 1, tailRing);
599	p_Setm(tmp2, tailRing);
600	if (nIsZero(tmp1))
601	{
602	zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
603	}
604	else
605	{
606	tmp3 = p_ISet((unsigned long) tmp1, tailRing);
607	zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing);
608	}
609	}
610	}
611	tmp2 = p_ISet((unsigned long) pGetCoeff(zeroPoly), leadRing);
612	for (int i = 1; i <= leadRing->N; i++)
613	{
614	pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
615	}
616	p_Setm(tmp2, leadRing);
617	zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
618	pNext(tmp2) = zeroPoly;
619	return tmp2;
620	} */
621	return NULL;
622	}
623	#endif
624
625
626	#ifdef HAVE_RINGS
627	/*2
628	* reduction procedure for the ring Z/2^m
629	*/
630	int redRing_Z (LObject* h,kStrategy strat)
631	{
632	if (h->IsNull()) return 0; // spoly is zero (can only occure with zero divisors)
633	if (strat->tl<0) return 1;
634
635	int at;
636	long d;
637	int j = 0;
638	int pass = 0;
639
640	// TODO warum SetpFDeg notwendig?
641	h->SetpFDeg();
642	assume(h->pFDeg() == h->FDeg);
643	long reddeg = h->GetpFDeg();
644
645	h->SetShortExpVector();
646	loop
647	{
648	/* check if a reducer of the lead term exists */
649	j = kFindDivisibleByInT(strat, h);
650	if (j < 0) {
651	/* check if a reducer with the same lead monomial exists */
652	j = kFindSameLMInT_Z(strat, h);
653	if (j < 0) {
654	/* check if a reducer of the lead monomial exists, by the above
655	* check this is a real divisor of the lead monomial */
656	j = kFindDivisibleByInT_Z(strat, h);
657	if (j < 0)
658	{
659	// over ZZ: cleanup coefficients by complete reduction with monomials
660	if (rHasLocalOrMixedOrdering(currRing))
661	postReduceByMon(h, strat);
662	if(h->p == NULL)
663	{
664	if (h->lcm!=NULL) pLmDelete(h->lcm);
665	h->Clear();
666	return 0;
667	}
668	if(nIsZero(pGetCoeff(h->p))) return 2;
669	j = kFindDivisibleByInT(strat, h);
670	if(j < 0)
671	{
672	if(strat->tl >= 0)
673	h->i_r1 = strat->tl;
674	else
675	h->i_r1 = -1;
676	if (h->GetLmTailRing() == NULL)
677	{
678	if (h->lcm!=NULL) pLmDelete(h->lcm);
679	h->Clear();
680	return 0;
681	}
682	return 1;
683	}
684	}
685	else
686	{
687	/* not(lc(reducer) \| lc(poly)) && not(lc(poly) \| lc(reducer))
688	* => we try to cut down the lead coefficient at least */
689	/* first copy T[j] in order to multiply it with a coefficient later on */
690	number mult, rest;
691	TObject tj = strat->T[j];
692	tj.Copy();
693	/* tj.max_exp = strat->T[j].max_exp; */
694	/* compute division with remainder of lc(h) and lc(T[j]) */
695	mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(strat->T[j].p),
696	&rest, currRing->cf);
697	/* set corresponding new lead coefficient already. we do not
698	* remove the lead term in ksReducePolyLC, but only apply
699	* a lead coefficient reduction */
700	tj.Mult_nn(mult);
701	ksReducePolyLC(h, &tj, NULL, &rest, strat);
702	tj.Delete();
703	tj.Clear();
704	}
705	}
706	else
707	{
708	/* same lead monomial but lead coefficients do not divide each other:
709	* change the polys to h <- spoly(h,tj) and h2 <- gpoly(h,tj). */
710	LObject h2 = *h;
711	h2.Copy();
712
713	ksReducePolyZ(h, &(strat->T[j]), NULL, NULL, strat);
714	ksReducePolyGCD(&h2, &(strat->T[j]), NULL, NULL, strat);
715	if (!rHasLocalOrMixedOrdering(currRing)) {
716	redtailBbaAlsoLC_Z(&h2, j, strat);
717	h2.pCleardenom();
718	}
719	/* replace h2 for tj in L (already generated pairs with tj), S and T */
720	replaceInLAndSAndT(h2, j, strat);
721	}
722	}
723	else
724	{
725	ksReducePoly(h, &(strat->T[j]), NULL, NULL, strat);
726	}
727	/* printf("\nAfter small red: ");pWrite(h->p); */
728	if (h->GetLmTailRing() == NULL)
729	{
730	if (h->lcm!=NULL) pLmDelete(h->lcm);
731	#ifdef KDEBUG
732	h->lcm=NULL;
733	#endif
734	h->Clear();
735	return 0;
736	}
737	h->SetShortExpVector();
738	d = h->SetpFDeg();
739	/- try to reduce the s-polynomial -/
740	pass++;
741	if (!TEST_OPT_REDTHROUGH &&
742	(strat->Ll >= 0) && ((d > reddeg) \|\| (pass > strat->LazyPass)))
743	{
744	h->SetLmCurrRing();
745	if (strat->posInLDependsOnLength)
746	h->SetLength(strat->length_pLength);
747	at = strat->posInL(strat->L,strat->Ll,h,strat);
748	if (at <= strat->Ll)
749	{
750	#ifdef KDEBUG
751	if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
752	#endif
753	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
754	h->Clear();
755	return -1;
756	}
757	}
758	if (d != reddeg)
759	{
760	if (d >= (long)strat->tailRing->bitmask)
761	{
762	if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
763	{
764	strat->overflow=TRUE;
765	//Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
766	h->GetP();
767	at = strat->posInL(strat->L,strat->Ll,h,strat);
768	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
769	h->Clear();
770	return -1;
771	}
772	}
773	else if ((TEST_OPT_PROT) && (strat->Ll < 0))
774	{
775	Print(".%ld",d);mflush();
776	reddeg = d;
777	}
778	}
779	}
780	}
781
782	int redRing (LObject* h,kStrategy strat)
783	{
784	if (h->IsNull()) return 0; // spoly is zero (can only occure with zero divisors)
785	if (strat->tl<0) return 1;
786
787	int at/,i/;
788	long d;
789	int j = 0;
790	int pass = 0;
791	// poly zeroPoly = NULL;
792
793	// TODO warum SetpFDeg notwendig?
794	h->SetpFDeg();
795	assume(h->pFDeg() == h->FDeg);
796	long reddeg = h->GetpFDeg();
797
798	h->SetShortExpVector();
799	loop
800	{
801	j = kFindDivisibleByInT(strat, h);
802	if (j < 0)
803	{
804	// over ZZ: cleanup coefficients by complete reduction with monomials
805	postReduceByMon(h, strat);
806	if(h->p == NULL)
807	{
808	kDeleteLcm(h);
809	h->Clear();
810	return 0;
811	}
812	if(nIsZero(pGetCoeff(h->p))) return 2;
813	j = kFindDivisibleByInT(strat, h);
814	if(j < 0)
815	{
816	if(strat->tl >= 0)
817	h->i_r1 = strat->tl;
818	else
819	h->i_r1 = -1;
820	if (h->GetLmTailRing() == NULL)
821	{
822	kDeleteLcm(h);
823	h->Clear();
824	return 0;
825	}
826	return 1;
827	}
828	}
829	//printf("\nFound one: ");pWrite(strat->T[j].p);
830	//enterT(*h, strat);
831	ksReducePoly(h, &(strat->T[j]), NULL, NULL, strat); // with debug output
832	//printf("\nAfter small red: ");pWrite(h->p);
833	if (h->GetLmTailRing() == NULL)
834	{
835	kDeleteLcm(h);
836	h->Clear();
837	return 0;
838	}
839	h->SetShortExpVector();
840	d = h->SetpFDeg();
841	/- try to reduce the s-polynomial -/
842	pass++;
843	if (!TEST_OPT_REDTHROUGH &&
844	(strat->Ll >= 0) && ((d > reddeg) \|\| (pass > strat->LazyPass)))
845	{
846	h->SetLmCurrRing();
847	if (strat->posInLDependsOnLength)
848	h->SetLength(strat->length_pLength);
849	at = strat->posInL(strat->L,strat->Ll,h,strat);
850	if (at <= strat->Ll)
851	{
852	#ifdef KDEBUG
853	if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
854	#endif
855	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
856	h->Clear();
857	return -1;
858	}
859	}
860	if (d != reddeg)
861	{
862	if (d >= (long)strat->tailRing->bitmask)
863	{
864	if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
865	{
866	strat->overflow=TRUE;
867	//Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
868	h->GetP();
869	at = strat->posInL(strat->L,strat->Ll,h,strat);
870	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
871	h->Clear();
872	return -1;
873	}
874	}
875	else if ((TEST_OPT_PROT) && (strat->Ll < 0))
876	{
877	Print(".%ld",d);mflush();
878	reddeg = d;
879	}
880	}
881	}
882	}
883	#endif
884
885	/*2
886	* reduction procedure for the homogeneous case
887	* and the case of a degree-ordering
888	*/
889	int redHomog (LObject* h,kStrategy strat)
890	{
891	if (strat->tl<0) return 1;
892	//if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
893	assume(h->FDeg == h->pFDeg());
894
895	poly h_p;
896	int i,j,at,pass, ii;
897	unsigned long not_sev;
898	// long reddeg,d;
899
900	pass = j = 0;
901	// d = reddeg = h->GetpFDeg();
902	h->SetShortExpVector();
903	int li;
904	h_p = h->GetLmTailRing();
905	not_sev = ~ h->sev;
906	loop
907	{
908	j = kFindDivisibleByInT(strat, h);
909	if (j < 0) return 1;
910
911	li = strat->T[j].pLength;
912	if (li<=0) li=strat->T[j].GetpLength();
913	ii = j;
914	/*
915	* the polynomial to reduce with (up to the moment) is;
916	* pi with length li
917	*/
918	i = j;
919	#if 1
920	if (TEST_OPT_LENGTH)
921	loop
922	{
923	/- search the shortest possible with respect to length -/
924	i++;
925	if (i > strat->tl)
926	break;
927	if (li==1)
928	break;
929	if ((strat->T[i].pLength < li)
930	&&
931	p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
932	h_p, not_sev, strat->tailRing))
933	{
934	/*
935	* the polynomial to reduce with is now;
936	*/
937	li = strat->T[i].pLength;
938	if (li<=0) li=strat->T[i].GetpLength();
939	ii = i;
940	}
941	}
942	#endif
943
944	/*
945	* end of search: have to reduce with pi
946	*/
947	#ifdef KDEBUG
948	if (TEST_OPT_DEBUG)
949	{
950	PrintS("red:");
951	h->wrp();
952	PrintS(" with ");
953	strat->T[ii].wrp();
954	}
955	#endif
956	assume(strat->fromT == FALSE);
957
958	ksReducePoly(h, &(strat->T[ii]), NULL, NULL, strat);
959	#if SBA_PRINT_REDUCTION_STEPS
960	sba_interreduction_steps++;
961	#endif
962	#if SBA_PRINT_OPERATIONS
963	sba_interreduction_operations += pLength(strat->T[ii].p);
964	#endif
965
966	#ifdef KDEBUG
967	if (TEST_OPT_DEBUG)
968	{
969	PrintS("\nto ");
970	h->wrp();
971	PrintLn();
972	}
973	#endif
974
975	h_p = h->GetLmTailRing();
976	if (h_p == NULL)
977	{
978	kDeleteLcm(h);
979	return 0;
980	}
981	if (TEST_OPT_IDLIFT)
982	{
983	if (h->p!=NULL)
984	{
985	if(p_GetComp(h->p,currRing)>strat->syzComp)
986	{
987	h->Delete();
988	return 0;
989	}
990	}
991	else if (h->t_p!=NULL)
992	{
993	if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
994	{
995	h->Delete();
996	return 0;
997	}
998	}
999	}
1000	#if 0
1001	else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1002	{
1003	if (h->p!=NULL)
1004	{
1005	if(p_GetComp(h->p,currRing)>strat->syzComp)
1006	{
1007	return 1;
1008	}
1009	}
1010	else if (h->t_p!=NULL)
1011	{
1012	if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1013	{
1014	return 1;
1015	}
1016	}
1017	}
1018	#endif
1019	h->SetShortExpVector();
1020	not_sev = ~ h->sev;
1021	/*
1022	* try to reduce the s-polynomial h
1023	*test first whether h should go to the lazyset L
1024	*-if the degree jumps
1025	*-if the number of pre-defined reductions jumps
1026	*/
1027	pass++;
1028	if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1029	{
1030	h->SetLmCurrRing();
1031	at = strat->posInL(strat->L,strat->Ll,h,strat);
1032	if (at <= strat->Ll)
1033	{
1034	#ifdef HAVE_SHIFTBBA
1035	if (rIsLPRing(currRing))
1036	{
1037	if (kFindDivisibleByInT(strat, h) < 0)
1038	return 1;
1039	}
1040	else
1041	#endif
1042	{
1043	int dummy=strat->sl;
1044	if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1045	return 1;
1046	}
1047	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1048	#ifdef KDEBUG
1049	if (TEST_OPT_DEBUG)
1050	Print(" lazy: -> L%d\n",at);
1051	#endif
1052	h->Clear();
1053	return -1;
1054	}
1055	}
1056	}
1057	}
1058
1059	KINLINE int ksReducePolyTailSig(LObject* PR, TObject* PW, LObject* Red, kStrategy strat)
1060	{
1061	BOOLEAN ret;
1062	number coef;
1063	assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
1064	if(!rField_is_Ring(currRing))
1065	Red->HeadNormalize();
1066	/*
1067	printf("------------------------\n");
1068	pWrite(Red->GetLmCurrRing());
1069	*/
1070	if(rField_is_Ring(currRing))
1071	ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
1072	else
1073	ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
1074	if (!ret)
1075	{
1076	if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
1077	{
1078	PR->Mult_nn(coef);
1079	// HANNES: mark for Normalize
1080	}
1081	n_Delete(&coef, currRing->cf);
1082	}
1083	return ret;
1084	}
1085
1086	/*2
1087	* reduction procedure for signature-based standard
1088	* basis algorithms:
1089	* all reductions have to be sig-safe!
1090	*
1091	* 2 is returned if and only if the pair is rejected by the rewritten criterion
1092	* at exactly this point of the computations. This is the last possible point
1093	* such a check can be done => checks with the biggest set of available
1094	* signatures
1095	*/
1096
1097	int redSig (LObject* h,kStrategy strat)
1098	{
1099	if (strat->tl<0) return 1;
1100	//if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1101	//printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1102	assume(h->FDeg == h->pFDeg());
1103	//#if 1
1104	#ifdef DEBUGF5
1105	PrintS("------- IN REDSIG -------\n");
1106	Print("p: ");
1107	pWrite(pHead(h->p));
1108	PrintS("p1: ");
1109	pWrite(pHead(h->p1));
1110	PrintS("p2: ");
1111	pWrite(pHead(h->p2));
1112	PrintS("---------------------------\n");
1113	#endif
1114	poly h_p;
1115	int i,j,at,pass, ii;
1116	int start=0;
1117	int sigSafe;
1118	unsigned long not_sev;
1119	// long reddeg,d;
1120
1121	pass = j = 0;
1122	// d = reddeg = h->GetpFDeg();
1123	h->SetShortExpVector();
1124	int li;
1125	h_p = h->GetLmTailRing();
1126	not_sev = ~ h->sev;
1127	loop
1128	{
1129	j = kFindDivisibleByInT(strat, h, start);
1130	if (j < 0)
1131	{
1132	return 1;
1133	}
1134
1135	li = strat->T[j].pLength;
1136	if (li<=0) li=strat->T[j].GetpLength();
1137	ii = j;
1138	/*
1139	* the polynomial to reduce with (up to the moment) is;
1140	* pi with length li
1141	*/
1142	i = j;
1143	#if 1
1144	if (TEST_OPT_LENGTH)
1145	loop
1146	{
1147	/- search the shortest possible with respect to length -/
1148	i++;
1149	if (i > strat->tl)
1150	break;
1151	if (li==1)
1152	break;
1153	if ((strat->T[i].pLength < li)
1154	&&
1155	p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1156	h_p, not_sev, strat->tailRing))
1157	{
1158	/*
1159	* the polynomial to reduce with is now;
1160	*/
1161	li = strat->T[i].pLength;
1162	if (li<=0) li=strat->T[i].GetpLength();
1163	ii = i;
1164	}
1165	}
1166	start = ii+1;
1167	#endif
1168
1169	/*
1170	* end of search: have to reduce with pi
1171	*/
1172	#ifdef KDEBUG
1173	if (TEST_OPT_DEBUG)
1174	{
1175	PrintS("red:");
1176	h->wrp();
1177	PrintS(" with ");
1178	strat->T[ii].wrp();
1179	}
1180	#endif
1181	assume(strat->fromT == FALSE);
1182	//#if 1
1183	#ifdef DEBUGF5
1184	Print("BEFORE REDUCTION WITH %d:\n",ii);
1185	PrintS("--------------------------------\n");
1186	pWrite(h->sig);
1187	pWrite(strat->T[ii].sig);
1188	pWrite(h->GetLmCurrRing());
1189	pWrite(pHead(h->p1));
1190	pWrite(pHead(h->p2));
1191	pWrite(pHead(strat->T[ii].p));
1192	PrintS("--------------------------------\n");
1193	printf("INDEX OF REDUCER T: %d\n",ii);
1194	#endif
1195	sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1196	#if SBA_PRINT_REDUCTION_STEPS
1197	if (sigSafe != 3)
1198	sba_reduction_steps++;
1199	#endif
1200	#if SBA_PRINT_OPERATIONS
1201	if (sigSafe != 3)
1202	sba_operations += pLength(strat->T[ii].p);
1203	#endif
1204	// if reduction has taken place, i.e. the reduction was sig-safe
1205	// otherwise start is already at the next position and the loop
1206	// searching reducers in T goes on from index start
1207	//#if 1
1208	#ifdef DEBUGF5
1209	Print("SigSAFE: %d\n",sigSafe);
1210	#endif
1211	if (sigSafe != 3)
1212	{
1213	// start the next search for reducers in T from the beginning
1214	start = 0;
1215	#ifdef KDEBUG
1216	if (TEST_OPT_DEBUG)
1217	{
1218	PrintS("\nto ");
1219	h->wrp();
1220	PrintLn();
1221	}
1222	#endif
1223
1224	h_p = h->GetLmTailRing();
1225	if (h_p == NULL)
1226	{
1227	kDeleteLcm(h);
1228	return 0;
1229	}
1230	h->SetShortExpVector();
1231	not_sev = ~ h->sev;
1232	/*
1233	* try to reduce the s-polynomial h
1234	*test first whether h should go to the lazyset L
1235	*-if the degree jumps
1236	*-if the number of pre-defined reductions jumps
1237	*/
1238	pass++;
1239	if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1240	{
1241	h->SetLmCurrRing();
1242	at = strat->posInL(strat->L,strat->Ll,h,strat);
1243	if (at <= strat->Ll)
1244	{
1245	int dummy=strat->sl;
1246	if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1247	{
1248	return 1;
1249	}
1250	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1251	#ifdef KDEBUG
1252	if (TEST_OPT_DEBUG)
1253	Print(" lazy: -> L%d\n",at);
1254	#endif
1255	h->Clear();
1256	return -1;
1257	}
1258	}
1259	}
1260	}
1261	}
1262
1263
1264	int redSigRing (LObject* h,kStrategy strat)
1265	{
1266	//Since reduce is really bad for SBA we use the following idea:
1267	// We first check if we can build a gcd pair between h and S
1268	//where the sig remains the same and replace h by this gcd poly
1269	assume(rField_is_Ring(currRing));
1270	#if GCD_SBA
1271	while(sbaCheckGcdPair(h,strat))
1272	{
1273	h->sev = pGetShortExpVector(h->p);
1274	}
1275	#endif
1276	poly beforeredsig;
1277	beforeredsig = pCopy(h->sig);
1278
1279	if (strat->tl<0) return 1;
1280	//if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1281	//printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
1282	assume(h->FDeg == h->pFDeg());
1283	//#if 1
1284	#ifdef DEBUGF5
1285	Print("------- IN REDSIG -------\n");
1286	Print("p: ");
1287	pWrite(pHead(h->p));
1288	Print("p1: ");
1289	pWrite(pHead(h->p1));
1290	Print("p2: ");
1291	pWrite(pHead(h->p2));
1292	Print("---------------------------\n");
1293	#endif
1294	poly h_p;
1295	int i,j,at,pass, ii;
1296	int start=0;
1297	int sigSafe;
1298	unsigned long not_sev;
1299	// long reddeg,d;
1300
1301	pass = j = 0;
1302	// d = reddeg = h->GetpFDeg();
1303	h->SetShortExpVector();
1304	int li;
1305	h_p = h->GetLmTailRing();
1306	not_sev = ~ h->sev;
1307	loop
1308	{
1309	j = kFindDivisibleByInT(strat, h, start);
1310	if (j < 0)
1311	{
1312	#if GCD_SBA
1313	while(sbaCheckGcdPair(h,strat))
1314	{
1315	h->sev = pGetShortExpVector(h->p);
1316	h->is_redundant = FALSE;
1317	start = 0;
1318	}
1319	#endif
1320	// over ZZ: cleanup coefficients by complete reduction with monomials
1321	postReduceByMonSig(h, strat);
1322	if(h->p == NULL \|\| nIsZero(pGetCoeff(h->p))) return 2;
1323	j = kFindDivisibleByInT(strat, h,start);
1324	if(j < 0)
1325	{
1326	if(strat->tl >= 0)
1327	h->i_r1 = strat->tl;
1328	else
1329	h->i_r1 = -1;
1330	if (h->GetLmTailRing() == NULL)
1331	{
1332	kDeleteLcm(h);
1333	h->Clear();
1334	return 0;
1335	}
1336	//Check for sigdrop after reduction
1337	if(pLtCmp(beforeredsig,h->sig) == 1)
1338	{
1339	strat->sigdrop = TRUE;
1340	//Reduce it as much as you can
1341	int red_result = redRing(h,strat);
1342	if(red_result == 0)
1343	{
1344	//It reduced to 0, cancel the sigdrop
1345	strat->sigdrop = FALSE;
1346	p_Delete(&h->sig,currRing);h->sig = NULL;
1347	return 0;
1348	}
1349	else
1350	{
1351	//strat->enterS(*h, strat->sl+1, strat, strat->tl);
1352	return 0;
1353	}
1354	}
1355	p_Delete(&beforeredsig,currRing);
1356	return 1;
1357	}
1358	}
1359
1360	li = strat->T[j].pLength;
1361	if (li<=0) li=strat->T[j].GetpLength();
1362	ii = j;
1363	/*
1364	* the polynomial to reduce with (up to the moment) is;
1365	* pi with length li
1366	*/
1367	i = j;
1368	if (TEST_OPT_LENGTH)
1369	loop
1370	{
1371	/- search the shortest possible with respect to length -/
1372	i++;
1373	if (i > strat->tl)
1374	break;
1375	if (li==1)
1376	break;
1377	if ((strat->T[i].pLength < li)
1378	&& n_DivBy(pGetCoeff(h_p),pGetCoeff(strat->T[i].p),currRing->cf)
1379	&& p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1380	h_p, not_sev, strat->tailRing))
1381	{
1382	/*
1383	* the polynomial to reduce with is now;
1384	*/
1385	li = strat->T[i].pLength;
1386	if (li<=0) li=strat->T[i].GetpLength();
1387	ii = i;
1388	}
1389	}
1390
1391	start = ii+1;
1392
1393	/*
1394	* end of search: have to reduce with pi
1395	*/
1396	#ifdef KDEBUG
1397	if (TEST_OPT_DEBUG)
1398	{
1399	PrintS("red:");
1400	h->wrp();
1401	PrintS(" with ");
1402	strat->T[ii].wrp();
1403	}
1404	#endif
1405	assume(strat->fromT == FALSE);
1406	//#if 1
1407	#ifdef DEBUGF5
1408	Print("BEFORE REDUCTION WITH %d:\n",ii);
1409	Print("--------------------------------\n");
1410	pWrite(h->sig);
1411	pWrite(strat->T[ii].sig);
1412	pWrite(h->GetLmCurrRing());
1413	pWrite(pHead(h->p1));
1414	pWrite(pHead(h->p2));
1415	pWrite(pHead(strat->T[ii].p));
1416	Print("--------------------------------\n");
1417	printf("INDEX OF REDUCER T: %d\n",ii);
1418	#endif
1419	sigSafe = ksReducePolySigRing(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
1420	if(h->p == NULL && h->sig == NULL)
1421	{
1422	//Trivial case catch
1423	strat->sigdrop = FALSE;
1424	}
1425	#if 0
1426	//If the reducer has the same lt (+ or -) as the other one, reduce it via redRing
1427	//In some cases this proves to be very bad
1428	if(rField_is_Ring(currRing) && h->p != NULL && pLmCmp(h->p,strat->T[ii].p)==0)
1429	{
1430	int red_result = redRing(h,strat);
1431	if(red_result == 0)
1432	{
1433	pDelete(&h->sig);h->sig = NULL;
1434	return 0;
1435	}
1436	else
1437	{
1438	strat->sigdrop = TRUE;
1439	return 1;
1440	}
1441	}
1442	#endif
1443	if(strat->sigdrop)
1444	return 1;
1445	#if SBA_PRINT_REDUCTION_STEPS
1446	if (sigSafe != 3)
1447	sba_reduction_steps++;
1448	#endif
1449	#if SBA_PRINT_OPERATIONS
1450	if (sigSafe != 3)
1451	sba_operations += pLength(strat->T[ii].p);
1452	#endif
1453	// if reduction has taken place, i.e. the reduction was sig-safe
1454	// otherwise start is already at the next position and the loop
1455	// searching reducers in T goes on from index start
1456	//#if 1
1457	#ifdef DEBUGF5
1458	Print("SigSAFE: %d\n",sigSafe);
1459	#endif
1460	if (sigSafe != 3)
1461	{
1462	// start the next search for reducers in T from the beginning
1463	start = 0;
1464	#ifdef KDEBUG
1465	if (TEST_OPT_DEBUG)
1466	{
1467	PrintS("\nto ");
1468	h->wrp();
1469	PrintLn();
1470	}
1471	#endif
1472
1473	h_p = h->GetLmTailRing();
1474	if (h_p == NULL)
1475	{
1476	kDeleteLcm(h);
1477	return 0;
1478	}
1479	h->SetShortExpVector();
1480	not_sev = ~ h->sev;
1481	/*
1482	* try to reduce the s-polynomial h
1483	*test first whether h should go to the lazyset L
1484	*-if the degree jumps
1485	*-if the number of pre-defined reductions jumps
1486	*/
1487	pass++;
1488	if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
1489	{
1490	h->SetLmCurrRing();
1491	at = strat->posInL(strat->L,strat->Ll,h,strat);
1492	if (at <= strat->Ll)
1493	{
1494	int dummy=strat->sl;
1495	if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1496	{
1497	return 1;
1498	}
1499	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1500	#ifdef KDEBUG
1501	if (TEST_OPT_DEBUG)
1502	Print(" lazy: -> L%d\n",at);
1503	#endif
1504	h->Clear();
1505	return -1;
1506	}
1507	}
1508	}
1509	}
1510	}
1511
1512	// tail reduction for SBA
1513	poly redtailSba (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
1514	{
1515	#define REDTAIL_CANONICALIZE 100
1516	strat->redTailChange=FALSE;
1517	if (strat->noTailReduction) return L->GetLmCurrRing();
1518	poly h, p;
1519	p = h = L->GetLmTailRing();
1520	if ((h==NULL) \|\| (pNext(h)==NULL))
1521	return L->GetLmCurrRing();
1522
1523	TObject* With;
1524	// placeholder in case strat->tl < 0
1525	TObject With_s(strat->tailRing);
1526
1527	LObject Ln(pNext(h), strat->tailRing);
1528	Ln.sig = L->sig;
1529	Ln.sevSig = L->sevSig;
1530	Ln.pLength = L->GetpLength() - 1;
1531
1532	pNext(h) = NULL;
1533	if (L->p != NULL) pNext(L->p) = NULL;
1534	L->pLength = 1;
1535
1536	Ln.PrepareRed(strat->use_buckets);
1537
1538	int cnt=REDTAIL_CANONICALIZE;
1539	while(!Ln.IsNull())
1540	{
1541	loop
1542	{
1543	if(rField_is_Ring(currRing) && strat->sigdrop)
1544	break;
1545	Ln.SetShortExpVector();
1546	if (withT)
1547	{
1548	int j;
1549	j = kFindDivisibleByInT(strat, &Ln);
1550	if (j < 0) break;
1551	With = &(strat->T[j]);
1552	}
1553	else
1554	{
1555	With = kFindDivisibleByInS_T(strat, pos, &Ln, &With_s);
1556	if (With == NULL) break;
1557	}
1558	cnt--;
1559	if (cnt==0)
1560	{
1561	cnt=REDTAIL_CANONICALIZE;
1562	/poly tmp=/Ln.CanonicalizeP();
1563	if (normalize && !rField_is_Ring(currRing))
1564	{
1565	Ln.Normalize();
1566	//pNormalize(tmp);
1567	//if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1568	}
1569	}
1570	if (normalize && (!TEST_OPT_INTSTRATEGY) && !rField_is_Ring(currRing) && (!nIsOne(pGetCoeff(With->p))))
1571	{
1572	With->pNorm();
1573	}
1574	strat->redTailChange=TRUE;
1575	int ret = ksReducePolyTailSig(L, With, &Ln, strat);
1576	if(rField_is_Ring(currRing))
1577	L->sig = Ln.sig;
1578	//Because Ln.sig is set to L->sig, but in ksReducePolyTailSig -> ksReducePolySig
1579	// I delete it an then set Ln.sig. Hence L->sig is lost
1580	#if SBA_PRINT_REDUCTION_STEPS
1581	if (ret != 3)
1582	sba_reduction_steps++;
1583	#endif
1584	#if SBA_PRINT_OPERATIONS
1585	if (ret != 3)
1586	sba_operations += pLength(With->p);
1587	#endif
1588	if (ret)
1589	{
1590	// reducing the tail would violate the exp bound
1591	// set a flag and hope for a retry (in bba)
1592	strat->completeReduce_retry=TRUE;
1593	if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
1594	do
1595	{
1596	pNext(h) = Ln.LmExtractAndIter();
1597	pIter(h);
1598	L->pLength++;
1599	} while (!Ln.IsNull());
1600	goto all_done;
1601	}
1602	if (Ln.IsNull()) goto all_done;
1603	if (! withT) With_s.Init(currRing);
1604	if(rField_is_Ring(currRing) && strat->sigdrop)
1605	{
1606	//Cannot break the loop here so easily
1607	break;
1608	}
1609	}
1610	pNext(h) = Ln.LmExtractAndIter();
1611	pIter(h);
1612	if(!rField_is_Ring(currRing))
1613	pNormalize(h);
1614	L->pLength++;
1615	}
1616	all_done:
1617	Ln.Delete();
1618	if (L->p != NULL) pNext(L->p) = pNext(p);
1619
1620	if (strat->redTailChange)
1621	{
1622	L->length = 0;
1623	}
1624	//if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
1625	//L->Normalize(); // HANNES: should have a test
1626	kTest_L(L,strat->tailRing);
1627	return L->GetLmCurrRing();
1628	}
1629
1630	/*2
1631	* reduction procedure for the inhomogeneous case
1632	* and not a degree-ordering
1633	*/
1634	int redLazy (LObject* h,kStrategy strat)
1635	{
1636	if (strat->tl<0) return 1;
1637	int at,i,ii,li;
1638	int j = 0;
1639	int pass = 0;
1640	assume(h->pFDeg() == h->FDeg);
1641	long reddeg = h->GetpFDeg();
1642	long d;
1643	unsigned long not_sev;
1644
1645	h->SetShortExpVector();
1646	poly h_p = h->GetLmTailRing();
1647	not_sev = ~ h->sev;
1648	loop
1649	{
1650	j = kFindDivisibleByInT(strat, h);
1651	if (j < 0) return 1;
1652
1653	li = strat->T[j].pLength;
1654	if (li<=0) li=strat->T[j].GetpLength();
1655	ii = j;
1656	/*
1657	* the polynomial to reduce with (up to the moment) is;
1658	* pi with length li
1659	*/
1660
1661	i = j;
1662	#if 1
1663	if (TEST_OPT_LENGTH)
1664	loop
1665	{
1666	/- search the shortest possible with respect to length -/
1667	i++;
1668	if (i > strat->tl)
1669	break;
1670	if (li==1)
1671	break;
1672	if ((strat->T[i].pLength < li)
1673	&&
1674	p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1675	h_p, not_sev, strat->tailRing))
1676	{
1677	/*
1678	* the polynomial to reduce with is now;
1679	*/
1680	li = strat->T[i].pLength;
1681	if (li<=0) li=strat->T[i].GetpLength();
1682	ii = i;
1683	}
1684	}
1685	#endif
1686
1687	/*
1688	* end of search: have to reduce with pi
1689	*/
1690
1691
1692	#ifdef KDEBUG
1693	if (TEST_OPT_DEBUG)
1694	{
1695	PrintS("red:");
1696	h->wrp();
1697	PrintS(" with ");
1698	strat->T[ii].wrp();
1699	}
1700	#endif
1701
1702	ksReducePoly(h, &(strat->T[ii]), NULL, NULL, strat);
1703	#if SBA_PRINT_REDUCTION_STEPS
1704	sba_interreduction_steps++;
1705	#endif
1706	#if SBA_PRINT_OPERATIONS
1707	sba_interreduction_operations += pLength(strat->T[ii].p);
1708	#endif
1709
1710	#ifdef KDEBUG
1711	if (TEST_OPT_DEBUG)
1712	{
1713	PrintS("\nto ");
1714	h->wrp();
1715	PrintLn();
1716	}
1717	#endif
1718
1719	h_p=h->GetLmTailRing();
1720
1721	if (h_p == NULL)
1722	{
1723	kDeleteLcm(h);
1724	return 0;
1725	}
1726	if (TEST_OPT_IDLIFT)
1727	{
1728	if (h->p!=NULL)
1729	{
1730	if(p_GetComp(h->p,currRing)>strat->syzComp)
1731	{
1732	h->Delete();
1733	return 0;
1734	}
1735	}
1736	else if (h->t_p!=NULL)
1737	{
1738	if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1739	{
1740	h->Delete();
1741	return 0;
1742	}
1743	}
1744	}
1745	#if 0
1746	else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1747	{
1748	if (h->p!=NULL)
1749	{
1750	if(p_GetComp(h->p,currRing)>strat->syzComp)
1751	{
1752	return 1;
1753	}
1754	}
1755	else if (h->t_p!=NULL)
1756	{
1757	if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1758	{
1759	return 1;
1760	}
1761	}
1762	}
1763	#endif
1764	h->SetShortExpVector();
1765	not_sev = ~ h->sev;
1766	d = h->SetpFDeg();
1767	/- try to reduce the s-polynomial -/
1768	pass++;
1769	if (//!TEST_OPT_REDTHROUGH &&
1770	(strat->Ll >= 0) && ((d > reddeg) \|\| (pass > strat->LazyPass)))
1771	{
1772	h->SetLmCurrRing();
1773	at = strat->posInL(strat->L,strat->Ll,h,strat);
1774	if (at <= strat->Ll)
1775	{
1776	#if 1
1777	#ifdef HAVE_SHIFTBBA
1778	if (rIsLPRing(currRing))
1779	{
1780	if (kFindDivisibleByInT(strat, h) < 0)
1781	return 1;
1782	}
1783	else
1784	#endif
1785	{
1786	int dummy=strat->sl;
1787	if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1788	return 1;
1789	}
1790	#endif
1791	#ifdef KDEBUG
1792	if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
1793	#endif
1794	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1795	h->Clear();
1796	return -1;
1797	}
1798	}
1799	else if (d != reddeg)
1800	{
1801	if (d>=(long)strat->tailRing->bitmask)
1802	{
1803	if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
1804	{
1805	strat->overflow=TRUE;
1806	//Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1807	h->GetP();
1808	at = strat->posInL(strat->L,strat->Ll,h,strat);
1809	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1810	h->Clear();
1811	return -1;
1812	}
1813	}
1814	else if ((TEST_OPT_PROT) && (strat->Ll < 0))
1815	{
1816	Print(".%ld",d);mflush();
1817	reddeg = d;
1818	}
1819	}
1820	}
1821	}
1822	/*2
1823	* reduction procedure for the sugar-strategy (honey)
1824	* reduces h with elements from T choosing first possible
1825	* element in T with respect to the given ecart
1826	*/
1827	int redHoney (LObject* h, kStrategy strat)
1828	{
1829	if (strat->tl<0) return 1;
1830	//if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1831	assume(h->FDeg == h->pFDeg());
1832	poly h_p;
1833	int i,j,at,pass,ei, ii, h_d;
1834	unsigned long not_sev;
1835	long reddeg,d;
1836
1837	pass = j = 0;
1838	d = reddeg = h->GetpFDeg() + h->ecart;
1839	h->SetShortExpVector();
1840	int li;
1841	h_p = h->GetLmTailRing();
1842	not_sev = ~ h->sev;
1843
1844	h->PrepareRed(strat->use_buckets);
1845	loop
1846	{
1847	j=kFindDivisibleByInT(strat, h);
1848	if (j < 0) return 1;
1849
1850	ei = strat->T[j].ecart;
1851	li = strat->T[j].pLength;
1852	if (li<=0) li=strat->T[j].GetpLength();
1853	ii = j;
1854	/*
1855	* the polynomial to reduce with (up to the moment) is;
1856	* pi with ecart ei (T[ii])
1857	*/
1858	i = j;
1859	if (TEST_OPT_LENGTH)
1860	loop
1861	{
1862	/- takes the first possible with respect to ecart -/
1863	i++;
1864	if (i > strat->tl)
1865	break;
1866	//if (ei < h->ecart)
1867	// break;
1868	if (li==1)
1869	break;
1870	if ((((strat->T[i].ecart < ei) && (ei> h->ecart))
1871	\|\| ((strat->T[i].ecart <= h->ecart) && (strat->T[i].pLength < li)))
1872	&&
1873	p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1874	h_p, not_sev, strat->tailRing))
1875	{
1876	/*
1877	* the polynomial to reduce with is now;
1878	*/
1879	ei = strat->T[i].ecart;
1880	li = strat->T[i].pLength;
1881	if (li<=0) li=strat->T[i].GetpLength();
1882	ii = i;
1883	}
1884	}
1885
1886	/*
1887	* end of search: have to reduce with pi
1888	*/
1889	if (!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h->ecart))
1890	{
1891	h->GetTP(); // clears bucket
1892	h->SetLmCurrRing();
1893	/*
1894	* It is not possible to reduce h with smaller ecart;
1895	* if possible h goes to the lazy-set L,i.e
1896	* if its position in L would be not the last one
1897	*/
1898	if (strat->Ll >= 0) /* L is not empty */
1899	{
1900	at = strat->posInL(strat->L,strat->Ll,h,strat);
1901	if(at <= strat->Ll)
1902	/- h will not become the next element to reduce -/
1903	{
1904	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1905	#ifdef KDEBUG
1906	if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
1907	#endif
1908	h->Clear();
1909	return -1;
1910	}
1911	}
1912	}
1913	#ifdef KDEBUG
1914	if (TEST_OPT_DEBUG)
1915	{
1916	PrintS("red:");
1917	h->wrp();
1918	Print("\nwith T[%d]:",ii);
1919	strat->T[ii].wrp();
1920	}
1921	#endif
1922	assume(strat->fromT == FALSE);
1923
1924	ksReducePoly(h,&(strat->T[ii]),strat->kNoetherTail(),NULL,strat);
1925	#if SBA_PRINT_REDUCTION_STEPS
1926	sba_interreduction_steps++;
1927	#endif
1928	#if SBA_PRINT_OPERATIONS
1929	sba_interreduction_operations += pLength(strat->T[ii].p);
1930	#endif
1931	#ifdef KDEBUG
1932	if (TEST_OPT_DEBUG)
1933	{
1934	PrintS("\nto:");
1935	h->wrp();
1936	PrintLn();
1937	}
1938	#endif
1939	if(h->IsNull())
1940	{
1941	kDeleteLcm(h);
1942	h->Clear();
1943	return 0;
1944	}
1945	if (TEST_OPT_IDLIFT)
1946	{
1947	if (h->p!=NULL)
1948	{
1949	if(p_GetComp(h->p,currRing)>strat->syzComp)
1950	{
1951	h->Delete();
1952	return 0;
1953	}
1954	}
1955	else if (h->t_p!=NULL)
1956	{
1957	if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1958	{
1959	h->Delete();
1960	return 0;
1961	}
1962	}
1963	}
1964	else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
1965	{
1966	if (h->p!=NULL)
1967	{
1968	if(p_GetComp(h->p,currRing)>strat->syzComp)
1969	{
1970	return 1;
1971	}
1972	}
1973	else if (h->t_p!=NULL)
1974	{
1975	if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1976	{
1977	return 1;
1978	}
1979	}
1980	}
1981	h->SetShortExpVector();
1982	not_sev = ~ h->sev;
1983	h_d = h->SetpFDeg();
1984	/* compute the ecart */
1985	if (ei <= h->ecart)
1986	h->ecart = d-h_d;
1987	else
1988	h->ecart = d-h_d+ei-h->ecart;
1989
1990	/*
1991	* try to reduce the s-polynomial h
1992	*test first whether h should go to the lazyset L
1993	*-if the degree jumps
1994	*-if the number of pre-defined reductions jumps
1995	*/
1996	pass++;
1997	d = h_d + h->ecart;
1998	if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && ((d > reddeg) \|\| (pass > strat->LazyPass)))
1999	{
2000	h->GetTP(); // clear bucket
2001	h->SetLmCurrRing();
2002	at = strat->posInL(strat->L,strat->Ll,h,strat);
2003	if (at <= strat->Ll)
2004	{
2005	#ifdef HAVE_SHIFTBBA
2006	if (rIsLPRing(currRing))
2007	{
2008	if (kFindDivisibleByInT(strat, h) < 0)
2009	return 1;
2010	}
2011	else
2012	#endif
2013	{
2014	int dummy=strat->sl;
2015	if (kFindDivisibleByInS(strat, &dummy, h) < 0)
2016	return 1;
2017	}
2018	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2019	#ifdef KDEBUG
2020	if (TEST_OPT_DEBUG)
2021	Print(" degree jumped: -> L%d\n",at);
2022	#endif
2023	h->Clear();
2024	return -1;
2025	}
2026	}
2027	else if (d > reddeg)
2028	{
2029	if (d>=(long)strat->tailRing->bitmask)
2030	{
2031	if (h->pTotalDeg()+h->ecart >= (long)strat->tailRing->bitmask)
2032	{
2033	strat->overflow=TRUE;
2034	//Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
2035	h->GetP();
2036	at = strat->posInL(strat->L,strat->Ll,h,strat);
2037	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
2038	h->Clear();
2039	return -1;
2040	}
2041	}
2042	else if (TEST_OPT_PROT && (strat->Ll < 0) )
2043	{
2044	//h->wrp(); Print("<%d>\n",h->GetpLength());
2045	reddeg = d;
2046	Print(".%ld",d); mflush();
2047	}
2048	}
2049	}
2050	}
2051
2052	/*2
2053	* reduction procedure for the normal form
2054	*/
2055
2056	poly redNF (poly h,int &max_ind,int nonorm,kStrategy strat)
2057	{
2058	#define REDNF_CANONICALIZE 60
2059	if (h==NULL) return NULL;
2060	int j;
2061	int cnt=REDNF_CANONICALIZE;
2062	max_ind=strat->sl;
2063
2064	if (0 > strat->sl)
2065	{
2066	return h;
2067	}
2068	LObject P(h);
2069	P.SetShortExpVector();
2070	P.bucket = kBucketCreate(currRing);
2071	kBucketInit(P.bucket,P.p,pLength(P.p));
2072	kbTest(P.bucket);
2073	#ifdef HAVE_RINGS
2074	BOOLEAN is_ring = rField_is_Ring(currRing);
2075	#endif
2076	#ifdef KDEBUG
2077	// if (TEST_OPT_DEBUG)
2078	// {
2079	// PrintS("redNF: starting S:\n");
2080	// for( j = 0; j <= max_ind; j++ )
2081	// {
2082	// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2083	// pWrite(strat->S[j]);
2084	// }
2085	// };
2086	#endif
2087
2088	loop
2089	{
2090	j=kFindDivisibleByInS(strat,&max_ind,&P);
2091	if (j>=0)
2092	{
2093	#ifdef HAVE_RINGS
2094	if (!is_ring)
2095	{
2096	#endif
2097	int sl=pSize(strat->S[j]);
2098	int jj=j;
2099	loop
2100	{
2101	int sll;
2102	jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2103	if (jj<0) break;
2104	sll=pSize(strat->S[jj]);
2105	if (sll<sl)
2106	{
2107	#ifdef KDEBUG
2108	if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2109	#endif
2110	//else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2111	j=jj;
2112	sl=sll;
2113	}
2114	}
2115	if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2116	{
2117	pNorm(strat->S[j]);
2118	//if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2119	}
2120	#ifdef HAVE_RINGS
2121	}
2122	#endif
2123	nNormalize(pGetCoeff(P.p));
2124	#ifdef KDEBUG
2125	if (TEST_OPT_DEBUG)
2126	{
2127	PrintS("red:");
2128	wrp(h);
2129	PrintS(" with ");
2130	wrp(strat->S[j]);
2131	}
2132	#endif
2133	#ifdef HAVE_PLURAL
2134	if (rIsPluralRing(currRing))
2135	{
2136	number coef;
2137	nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef);
2138	nDelete(&coef);
2139	}
2140	else
2141	#endif
2142	{
2143	number coef;
2144	coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2145	nDelete(&coef);
2146	}
2147	cnt--;
2148	if (cnt==0)
2149	{
2150	kBucketCanonicalize(P.bucket);
2151	cnt=REDNF_CANONICALIZE;
2152	}
2153	h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2154	if (h==NULL)
2155	{
2156	kBucketDestroy(&P.bucket);
2157
2158	#ifdef KDEBUG
2159	// if (TEST_OPT_DEBUG)
2160	// {
2161	// PrintS("redNF: starting S:\n");
2162	// for( j = 0; j <= max_ind; j++ )
2163	// {
2164	// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2165	// pWrite(strat->S[j]);
2166	// }
2167	// };
2168	#endif
2169
2170	return NULL;
2171	}
2172	kbTest(P.bucket);
2173	P.p=h;
2174	P.t_p=NULL;
2175	P.SetShortExpVector();
2176	#ifdef KDEBUG
2177	if (TEST_OPT_DEBUG)
2178	{
2179	PrintS("\nto:");
2180	wrp(h);
2181	PrintLn();
2182	}
2183	#endif
2184	}
2185	else
2186	{
2187	P.p=kBucketClear(P.bucket);
2188	kBucketDestroy(&P.bucket);
2189	pNormalize(P.p);
2190
2191	#ifdef KDEBUG
2192	// if (TEST_OPT_DEBUG)
2193	// {
2194	// PrintS("redNF: starting S:\n");
2195	// for( j = 0; j <= max_ind; j++ )
2196	// {
2197	// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2198	// pWrite(strat->S[j]);
2199	// }
2200	// };
2201	#endif
2202
2203	return P.p;
2204	}
2205	}
2206	}
2207
2208	/*2
2209	* reduction procedure from global case but with jet bound
2210	*/
2211
2212	poly redNFBound (poly h,int &max_ind,int nonorm,kStrategy strat,int bound)
2213	{
2214	h = pJet(h,bound);
2215	if (h==NULL) return NULL;
2216	int j;
2217	max_ind=strat->sl;
2218
2219	if (0 > strat->sl)
2220	{
2221	return h;
2222	}
2223	LObject P(h);
2224	P.SetShortExpVector();
2225	P.bucket = kBucketCreate(currRing);
2226	kBucketInit(P.bucket,P.p,pLength(P.p));
2227	kbTest(P.bucket);
2228	#ifdef HAVE_RINGS
2229	BOOLEAN is_ring = rField_is_Ring(currRing);
2230	#endif
2231	#ifdef KDEBUG
2232	// if (TEST_OPT_DEBUG)
2233	// {
2234	// PrintS("redNF: starting S:\n");
2235	// for( j = 0; j <= max_ind; j++ )
2236	// {
2237	// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2238	// pWrite(strat->S[j]);
2239	// }
2240	// };
2241	#endif
2242
2243	loop
2244	{
2245	j=kFindDivisibleByInS(strat,&max_ind,&P);
2246	if (j>=0)
2247	{
2248	#ifdef HAVE_RINGS
2249	if (!is_ring)
2250	{
2251	#endif
2252	int sl=pSize(strat->S[j]);
2253	int jj=j;
2254	loop
2255	{
2256	int sll;
2257	jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
2258	if (jj<0) break;
2259	sll=pSize(strat->S[jj]);
2260	if (sll<sl)
2261	{
2262	#ifdef KDEBUG
2263	if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
2264	#endif
2265	//else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
2266	j=jj;
2267	sl=sll;
2268	}
2269	}
2270	if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
2271	{
2272	pNorm(strat->S[j]);
2273	//if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
2274	}
2275	#ifdef HAVE_RINGS
2276	}
2277	#endif
2278	nNormalize(pGetCoeff(P.p));
2279	#ifdef KDEBUG
2280	if (TEST_OPT_DEBUG)
2281	{
2282	PrintS("red:");
2283	wrp(h);
2284	PrintS(" with ");
2285	wrp(strat->S[j]);
2286	}
2287	#endif
2288	#ifdef HAVE_PLURAL
2289	if (rIsPluralRing(currRing))
2290	{
2291	number coef;
2292	nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef);
2293	nDelete(&coef);
2294	}
2295	else
2296	#endif
2297	{
2298	number coef;
2299	coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
2300	P.p = kBucketClear(P.bucket);
2301	P.p = pJet(P.p,bound);
2302	if(!P.IsNull())
2303	{
2304	kBucketDestroy(&P.bucket);
2305	P.SetShortExpVector();
2306	P.bucket = kBucketCreate(currRing);
2307	kBucketInit(P.bucket,P.p,pLength(P.p));
2308	}
2309	nDelete(&coef);
2310	}
2311	h = kBucketGetLm(P.bucket); // FRAGE OLIVER
2312	if (h==NULL)
2313	{
2314	kBucketDestroy(&P.bucket);
2315
2316	#ifdef KDEBUG
2317	// if (TEST_OPT_DEBUG)
2318	// {
2319	// PrintS("redNF: starting S:\n");
2320	// for( j = 0; j <= max_ind; j++ )
2321	// {
2322	// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2323	// pWrite(strat->S[j]);
2324	// }
2325	// };
2326	#endif
2327
2328	return NULL;
2329	}
2330	kbTest(P.bucket);
2331	P.p=h;
2332	P.t_p=NULL;
2333	P.SetShortExpVector();
2334	#ifdef KDEBUG
2335	if (TEST_OPT_DEBUG)
2336	{
2337	PrintS("\nto:");
2338	wrp(h);
2339	PrintLn();
2340	}
2341	#endif
2342	}
2343	else
2344	{
2345	P.p=kBucketClear(P.bucket);
2346	kBucketDestroy(&P.bucket);
2347	pNormalize(P.p);
2348
2349	#ifdef KDEBUG
2350	// if (TEST_OPT_DEBUG)
2351	// {
2352	// PrintS("redNF: starting S:\n");
2353	// for( j = 0; j <= max_ind; j++ )
2354	// {
2355	// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
2356	// pWrite(strat->S[j]);
2357	// }
2358	// };
2359	#endif
2360
2361	return P.p;
2362	}
2363	}
2364	}
2365
2366	void kDebugPrint(kStrategy strat);
2367
2368	ideal bba (ideal F, ideal Q,intvec w,intvec hilb,kStrategy strat)
2369	{
2370	int red_result = 1;
2371	int olddeg,reduc;
2372	int hilbeledeg=1,hilbcount=0,minimcnt=0;
2373	BOOLEAN withT = FALSE;
2374	BITSET save;
2375	SI_SAVE_OPT1(save);
2376
2377	initBuchMoraCrit(strat); /set Gebauer, honey, sugarCrit/
2378	if(rField_is_Ring(currRing))
2379	initBuchMoraPosRing(strat);
2380	else
2381	initBuchMoraPos(strat);
2382	initHilbCrit(F,Q,&hilb,strat);
2383	initBba(strat);
2384	/set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair/
2385	/Shdl=/initBuchMora(F, Q,strat);
2386	if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2387	reduc = olddeg = 0;
2388
2389	#ifndef NO_BUCKETS
2390	if (!TEST_OPT_NOT_BUCKETS)
2391	strat->use_buckets = 1;
2392	#endif
2393	// redtailBBa against T for inhomogenous input
2394	if (!TEST_OPT_OLDSTD)
2395	withT = ! strat->homog;
2396
2397	// strat->posInT = posInT_pLength;
2398	kTest_TS(strat);
2399
2400	#ifdef HAVE_TAIL_RING
2401	if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2402	kStratInitChangeTailRing(strat);
2403	#endif
2404	if (BVERBOSE(23))
2405	{
2406	if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2407	if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2408	kDebugPrint(strat);
2409	}
2410
2411
2412	#ifdef KDEBUG
2413	//kDebugPrint(strat);
2414	#endif
2415	/* compute------------------------------------------------------- */
2416	while (strat->Ll >= 0)
2417	{
2418	#ifdef KDEBUG
2419	if (TEST_OPT_DEBUG) messageSets(strat);
2420	#endif
2421	if (siCntrlc)
2422	{
2423	while (strat->Ll >= 0)
2424	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2425	strat->noClearS=TRUE;
2426	}
2427	if (TEST_OPT_DEGBOUND
2428	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2429	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2430	{
2431	/*
2432	*stops computation if
2433	* 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2434	*a predefined number Kstd1_deg
2435	*/
2436	while ((strat->Ll >= 0)
2437	&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2438	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2439	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2440	)
2441	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2442	if (strat->Ll<0) break;
2443	else strat->noClearS=TRUE;
2444	}
2445	if (strat->Ll== 0) strat->interpt=TRUE;
2446	/* picks the last element from the lazyset L */
2447	strat->P = strat->L[strat->Ll];
2448	strat->Ll--;
2449
2450	if (pNext(strat->P.p) == strat->tail)
2451	{
2452	// deletes the short spoly
2453	if (rField_is_Ring(currRing))
2454	pLmDelete(strat->P.p);
2455	else
2456	pLmFree(strat->P.p);
2457	strat->P.p = NULL;
2458	poly m1 = NULL, m2 = NULL;
2459
2460	// check that spoly creation is ok
2461	while (strat->tailRing != currRing &&
2462	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2463	{
2464	assume(m1 == NULL && m2 == NULL);
2465	// if not, change to a ring where exponents are at least
2466	// large enough
2467	if (!kStratChangeTailRing(strat))
2468	{
2469	WerrorS("OVERFLOW...");
2470	break;
2471	}
2472	}
2473	// create the real one
2474	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2475	strat->tailRing, m1, m2, strat->R);
2476	}
2477	else if (strat->P.p1 == NULL)
2478	{
2479	if (strat->minim > 0)
2480	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2481	// for input polys, prepare reduction
2482	strat->P.PrepareRed(strat->use_buckets);
2483	}
2484
2485	if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
2486	{
2487	red_result = 0;
2488	}
2489	else
2490	{
2491	if (TEST_OPT_PROT)
2492	message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2493	&olddeg,&reduc,strat, red_result);
2494
2495	/* reduction of the element chosen from L */
2496	red_result = strat->red(&strat->P,strat);
2497	if (errorreported) break;
2498	}
2499
2500	if (strat->overflow)
2501	{
2502	if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2503	}
2504
2505	// reduction to non-zero new poly
2506	if (red_result == 1)
2507	{
2508	// get the polynomial (canonicalize bucket, make sure P.p is set)
2509	strat->P.GetP(strat->lmBin);
2510	// in the homogeneous case FDeg >= pFDeg (sugar/honey)
2511	// but now, for entering S, T, we reset it
2512	// in the inhomogeneous case: FDeg == pFDeg
2513	if (strat->homog) strat->initEcart(&(strat->P));
2514
2515	/* statistic */
2516	if (TEST_OPT_PROT) PrintS("s");
2517
2518	int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2519
2520	// reduce the tail and normalize poly
2521	// in the ring case we cannot expect LC(f) = 1,
2522	// therefore we call pCleardenom instead of pNorm
2523	strat->redTailChange=FALSE;
2524
2525	/* if we are computing over Z we always want to try and cut down
2526	* the coefficients in the tail terms */
2527	if (rField_is_Z(currRing) && !rHasLocalOrMixedOrdering(currRing))
2528	{
2529	redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
2530	strat->P.pCleardenom();
2531	}
2532
2533	if ((TEST_OPT_INTSTRATEGY) \|\| (rField_is_Ring(currRing)))
2534	{
2535	strat->P.pCleardenom();
2536	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
2537	{
2538	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
2539	strat->P.pCleardenom();
2540	if (strat->redTailChange) { strat->P.t_p=NULL; }
2541	}
2542	}
2543	else
2544	{
2545	strat->P.pNorm();
2546	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
2547	{
2548	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2549	if (strat->redTailChange) { strat->P.t_p=NULL; }
2550	}
2551	}
2552
2553	#ifdef KDEBUG
2554	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2555	#endif /* KDEBUG */
2556
2557	// min_std stuff
2558	if ((strat->P.p1==NULL) && (strat->minim>0))
2559	{
2560	if (strat->minim==1)
2561	{
2562	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2563	p_Delete(&strat->P.p2, currRing, strat->tailRing);
2564	}
2565	else
2566	{
2567	strat->M->m[minimcnt]=strat->P.p2;
2568	strat->P.p2=NULL;
2569	}
2570	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2571	pNext(strat->M->m[minimcnt])
2572	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2573	strat->tailRing, currRing,
2574	currRing->PolyBin);
2575	minimcnt++;
2576	}
2577
2578	// enter into S, L, and T
2579	if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
2580	{
2581	enterT(strat->P, strat);
2582	if (rField_is_Ring(currRing))
2583	superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2584	else
2585	enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2586	// posInS only depends on the leading term
2587	strat->enterS(strat->P, pos, strat, strat->tl);
2588	#if 0
2589	int pl=pLength(strat->P.p);
2590	if (pl==1)
2591	{
2592	//if (TEST_OPT_PROT)
2593	//PrintS("<1>");
2594	}
2595	else if (pl==2)
2596	{
2597	//if (TEST_OPT_PROT)
2598	//PrintS("<2>");
2599	}
2600	#endif
2601	}
2602	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2603	// Print("[%d]",hilbeledeg);
2604	kDeleteLcm(&strat->P);
2605	if (strat->s_poly!=NULL)
2606	{
2607	// the only valid entries are: strat->P.p,
2608	// strat->tailRing (read-only, keep it)
2609	// (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
2610	if (strat->s_poly(strat))
2611	{
2612	// we are called AFTER enterS, i.e. if we change P
2613	// we have to add it also to S/T
2614	// and add pairs
2615	int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2616	enterT(strat->P, strat);
2617	if (rField_is_Ring(currRing))
2618	superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2619	else
2620	enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2621	strat->enterS(strat->P, pos, strat, strat->tl);
2622	}
2623	}
2624	}
2625	else if (strat->P.p1 == NULL && strat->minim > 0)
2626	{
2627	p_Delete(&strat->P.p2, currRing, strat->tailRing);
2628	}
2629
2630	#ifdef KDEBUG
2631	memset(&(strat->P), 0, sizeof(strat->P));
2632	#endif /* KDEBUG */
2633	kTest_TS(strat);
2634	}
2635	#ifdef KDEBUG
2636	if (TEST_OPT_DEBUG) messageSets(strat);
2637	#endif /* KDEBUG */
2638
2639	if (TEST_OPT_SB_1)
2640	{
2641	if(!rField_is_Ring(currRing))
2642	{
2643	int k=1;
2644	int j;
2645	while(k<=strat->sl)
2646	{
2647	j=0;
2648	loop
2649	{
2650	if (j>=k) break;
2651	clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2652	j++;
2653	}
2654	k++;
2655	}
2656	}
2657	}
2658	/* complete reduction of the standard basis--------- */
2659	if (TEST_OPT_REDSB)
2660	{
2661	completeReduce(strat);
2662	if (strat->completeReduce_retry)
2663	{
2664	// completeReduce needed larger exponents, retry
2665	// to reduce with S (instead of T)
2666	// and in currRing (instead of strat->tailRing)
2667	#ifdef HAVE_TAIL_RING
2668	if(currRing->bitmask>strat->tailRing->bitmask)
2669	{
2670	strat->completeReduce_retry=FALSE;
2671	cleanT(strat);strat->tailRing=currRing;
2672	int i;
2673	for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2674	completeReduce(strat);
2675	}
2676	if (strat->completeReduce_retry)
2677	#endif
2678	Werror("exponent bound is %ld",currRing->bitmask);
2679	}
2680	}
2681	else if (TEST_OPT_PROT) PrintLn();
2682	/* release temp data-------------------------------- */
2683	exitBuchMora(strat);
2684	/* postprocessing for GB over ZZ --------------------*/
2685	if (!errorreported)
2686	{
2687	if(rField_is_Z(currRing))
2688	{
2689	for(int i = 0;i<=strat->sl;i++)
2690	{
2691	if(!nGreaterZero(pGetCoeff(strat->S[i])))
2692	{
2693	strat->S[i] = pNeg(strat->S[i]);
2694	}
2695	}
2696	finalReduceByMon(strat);
2697	for(int i = 0;i<IDELEMS(strat->Shdl);i++)
2698	{
2699	if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
2700	{
2701	strat->S[i] = pNeg(strat->Shdl->m[i]);
2702	}
2703	}
2704	}
2705	//else if (rField_is_Ring(currRing))
2706	// finalReduceByMon(strat);
2707	}
2708	// if (TEST_OPT_WEIGHTM)
2709	// {
2710	// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2711	// if (ecartWeights)
2712	// {
2713	// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2714	// ecartWeights=NULL;
2715	// }
2716	// }
2717	if ((TEST_OPT_PROT) \|\| (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2718	SI_RESTORE_OPT1(save);
2719	/* postprocessing for GB over Q-rings ------------------*/
2720	if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
2721
2722	idTest(strat->Shdl);
2723
2724	return (strat->Shdl);
2725	}
2726
2727	ideal sba (ideal F0, ideal Q,intvec w,intvec hilb,kStrategy strat)
2728	{
2729	// ring order stuff:
2730	// in sba we have (until now) two possibilities:
2731	// 1. an incremental computation w.r.t. (C,monomial order)
2732	// 2. a (possibly non-incremental) computation w.r.t. the
2733	// induced Schreyer order.
2734	// The corresponding orders are computed in sbaRing(), depending
2735	// on the flag strat->sbaOrder
2736	#if SBA_PRINT_ZERO_REDUCTIONS
2737	long zeroreductions = 0;
2738	#endif
2739	#if SBA_PRINT_PRODUCT_CRITERION
2740	long product_criterion = 0;
2741	#endif
2742	#if SBA_PRINT_SIZE_G
2743	int size_g = 0;
2744	int size_g_non_red = 0;
2745	#endif
2746	#if SBA_PRINT_SIZE_SYZ
2747	long size_syz = 0;
2748	#endif
2749	// global variable
2750	#if SBA_PRINT_REDUCTION_STEPS
2751	sba_reduction_steps = 0;
2752	sba_interreduction_steps = 0;
2753	#endif
2754	#if SBA_PRINT_OPERATIONS
2755	sba_operations = 0;
2756	sba_interreduction_operations = 0;
2757	#endif
2758
2759	ideal F1 = F0;
2760	ring sRing, currRingOld;
2761	currRingOld = currRing;
2762	if (strat->sbaOrder == 1 \|\| strat->sbaOrder == 3)
2763	{
2764	sRing = sbaRing(strat);
2765	if (sRing!=currRingOld)
2766	{
2767	rChangeCurrRing (sRing);
2768	F1 = idrMoveR (F0, currRingOld, currRing);
2769	}
2770	}
2771	ideal F;
2772	// sort ideal F
2773	//Put the SigDrop element on the correct position (think of sbaEnterS)
2774	//We also sort them
2775	if(rField_is_Ring(currRing) && strat->sigdrop)
2776	{
2777	#if 1
2778	F = idInit(IDELEMS(F1),F1->rank);
2779	for (int i=0; i<IDELEMS(F1);++i)
2780	F->m[i] = F1->m[i];
2781	if(strat->sbaEnterS >= 0)
2782	{
2783	poly dummy;
2784	dummy = pCopy(F->m[0]); //the sigdrop element
2785	for(int i = 0;i<strat->sbaEnterS;i++)
2786	F->m[i] = F->m[i+1];
2787	F->m[strat->sbaEnterS] = dummy;
2788	}
2789	#else
2790	F = idInit(1,F1->rank);
2791	//printf("\nBefore the initial block sorting:\n");idPrint(F1);
2792	F->m[0] = F1->m[0];
2793	int pos;
2794	if(strat->sbaEnterS >= 0)
2795	{
2796	for(int i=1;i<=strat->sbaEnterS;i++)
2797	{
2798	pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
2799	idInsertPolyOnPos(F,F1->m[i],pos);
2800	}
2801	for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
2802	{
2803	pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
2804	idInsertPolyOnPos(F,F1->m[i],pos);
2805	}
2806	poly dummy;
2807	dummy = pCopy(F->m[0]); //the sigdrop element
2808	for(int i = 0;i<strat->sbaEnterS;i++)
2809	F->m[i] = F->m[i+1];
2810	F->m[strat->sbaEnterS] = dummy;
2811	}
2812	else
2813	{
2814	for(int i=1;i<IDELEMS(F1);i++)
2815	{
2816	pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
2817	idInsertPolyOnPos(F,F1->m[i],pos);
2818	}
2819	}
2820	#endif
2821	//printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
2822	}
2823	else
2824	{
2825	F = idInit(IDELEMS(F1),F1->rank);
2826	intvec *sort = idSort(F1);
2827	for (int i=0; i<sort->length();++i)
2828	F->m[i] = F1->m[(*sort)[i]-1];
2829	if(rField_is_Ring(currRing))
2830	{
2831	// put the monomials after the sbaEnterS polynomials
2832	//printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
2833	int nrmon = 0;
2834	for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
2835	{
2836	//pWrite(F->m[i]);
2837	if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
2838	{
2839	poly mon = F->m[i];
2840	for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
2841	{
2842	F->m[j] = F->m[j-1];
2843	}
2844	F->m[j] = mon;
2845	nrmon++;
2846	}
2847	//idPrint(F);
2848	}
2849	}
2850	}
2851	//printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
2852	if(rField_is_Ring(currRing))
2853	strat->sigdrop = FALSE;
2854	strat->nrsyzcrit = 0;
2855	strat->nrrewcrit = 0;
2856	#if SBA_INTERRED_START
2857	F = kInterRed(F,NULL);
2858	#endif
2859	#if F5DEBUG
2860	printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
2861	rWrite (currRing);
2862	printf("ordSgn = %d\n",currRing->OrdSgn);
2863	printf("\n");
2864	#endif
2865	int srmax,lrmax, red_result = 1;
2866	int olddeg,reduc;
2867	int hilbeledeg=1,hilbcount=0,minimcnt=0;
2868	LObject L;
2869	BOOLEAN withT = TRUE;
2870	strat->max_lower_index = 0;
2871	//initBuchMoraCrit(strat); /set Gebauer, honey, sugarCrit/
2872	initSbaCrit(strat); /set Gebauer, honey, sugarCrit/
2873	initSbaPos(strat);
2874	initHilbCrit(F,Q,&hilb,strat);
2875	initSba(F,strat);
2876	/set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair/
2877	/Shdl=/initSbaBuchMora(F, Q,strat);
2878	idTest(strat->Shdl);
2879	if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2880	srmax = strat->sl;
2881	reduc = olddeg = lrmax = 0;
2882	#ifndef NO_BUCKETS
2883	if (!TEST_OPT_NOT_BUCKETS)
2884	strat->use_buckets = 1;
2885	#endif
2886
2887	// redtailBBa against T for inhomogenous input
2888	// if (!TEST_OPT_OLDSTD)
2889	// withT = ! strat->homog;
2890
2891	// strat->posInT = posInT_pLength;
2892	kTest_TS(strat);
2893
2894	#ifdef HAVE_TAIL_RING
2895	if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2896	kStratInitChangeTailRing(strat);
2897	#endif
2898	if (BVERBOSE(23))
2899	{
2900	if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2901	if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2902	kDebugPrint(strat);
2903	}
2904	// We add the elements directly in S from the previous loop
2905	if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
2906	{
2907	for(int i = 0;i<strat->sbaEnterS;i++)
2908	{
2909	//Update: now the element is at the corect place
2910	//i+1 because on the 0 position is the sigdrop element
2911	enterT(strat->L[strat->Ll-(i)],strat);
2912	strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
2913	}
2914	strat->Ll = strat->Ll - strat->sbaEnterS;
2915	strat->sbaEnterS = -1;
2916	}
2917	kTest_TS(strat);
2918	#ifdef KDEBUG
2919	//kDebugPrint(strat);
2920	#endif
2921	/* compute------------------------------------------------------- */
2922	while (strat->Ll >= 0)
2923	{
2924	if (strat->Ll > lrmax) lrmax =strat->Ll;/stat./
2925	#ifdef KDEBUG
2926	if (TEST_OPT_DEBUG) messageSets(strat);
2927	#endif
2928	if (strat->Ll== 0) strat->interpt=TRUE;
2929	/*
2930	if (TEST_OPT_DEGBOUND
2931	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2932	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2933	{
2934
2935	//stops computation if
2936	// 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2937	//a predefined number Kstd1_deg
2938	while ((strat->Ll >= 0)
2939	&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2940	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2941	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2942	)
2943	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2944	if (strat->Ll<0) break;
2945	else strat->noClearS=TRUE;
2946	}
2947	*/
2948	if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
2949	{
2950	strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
2951	#if F5C
2952	// 1. interreduction of the current standard basis
2953	// 2. generation of new principal syzygy rules for syzCriterion
2954	f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
2955	lrmax, reduc, Q, w, hilb );
2956	#endif
2957	// initialize new syzygy rules for the next iteration step
2958	initSyzRules(strat);
2959	}
2960	/*********************************************************************
2961	* interrreduction step is done, we can go on with the next iteration
2962	* step of the signature-based algorithm
2963	********************************************************************/
2964	/* picks the last element from the lazyset L */
2965	strat->P = strat->L[strat->Ll];
2966	strat->Ll--;
2967
2968	if(rField_is_Ring(currRing))
2969	strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
2970	/* reduction of the element chosen from L */
2971	if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1))
2972	{
2973	//#if 1
2974	#ifdef DEBUGF5
2975	PrintS("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
2976	PrintS("-------------------------------------------------\n");
2977	pWrite(strat->P.sig);
2978	pWrite(pHead(strat->P.p));
2979	pWrite(pHead(strat->P.p1));
2980	pWrite(pHead(strat->P.p2));
2981	PrintS("-------------------------------------------------\n");
2982	#endif
2983	if (pNext(strat->P.p) == strat->tail)
2984	{
2985	// deletes the short spoly
2986	/*
2987	if (rField_is_Ring(currRing))
2988	pLmDelete(strat->P.p);
2989	else
2990	pLmFree(strat->P.p);
2991	*/
2992	// TODO: needs some masking
2993	// TODO: masking needs to vanish once the signature
2994	// sutff is completely implemented
2995	strat->P.p = NULL;
2996	poly m1 = NULL, m2 = NULL;
2997
2998	// check that spoly creation is ok
2999	while (strat->tailRing != currRing &&
3000	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3001	{
3002	assume(m1 == NULL && m2 == NULL);
3003	// if not, change to a ring where exponents are at least
3004	// large enough
3005	if (!kStratChangeTailRing(strat))
3006	{
3007	WerrorS("OVERFLOW...");
3008	break;
3009	}
3010	}
3011	// create the real one
3012	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3013	strat->tailRing, m1, m2, strat->R);
3014
3015	}
3016	else if (strat->P.p1 == NULL)
3017	{
3018	if (strat->minim > 0)
3019	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3020	// for input polys, prepare reduction
3021	if(!rField_is_Ring(currRing))
3022	strat->P.PrepareRed(strat->use_buckets);
3023	}
3024	if (strat->P.p == NULL && strat->P.t_p == NULL)
3025	{
3026	red_result = 0;
3027	}
3028	else
3029	{
3030	//#if 1
3031	#ifdef DEBUGF5
3032	PrintS("Poly before red: ");
3033	pWrite(pHead(strat->P.p));
3034	pWrite(strat->P.sig);
3035	#endif
3036	#if SBA_PRODUCT_CRITERION
3037	if (strat->P.prod_crit)
3038	{
3039	#if SBA_PRINT_PRODUCT_CRITERION
3040	product_criterion++;
3041	#endif
3042	int pos = posInSyz(strat, strat->P.sig);
3043	enterSyz(strat->P, strat, pos);
3044	kDeleteLcm(&strat->P);
3045	red_result = 2;
3046	}
3047	else
3048	{
3049	red_result = strat->red(&strat->P,strat);
3050	}
3051	#else
3052	red_result = strat->red(&strat->P,strat);
3053	#endif
3054	}
3055	}
3056	else
3057	{
3058	/*
3059	if (strat->P.lcm != NULL)
3060	pLmFree(strat->P.lcm);
3061	*/
3062	red_result = 2;
3063	}
3064	if(rField_is_Ring(currRing))
3065	{
3066	if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
3067	{
3068	strat->P.p = pNeg(strat->P.p);
3069	strat->P.sig = pNeg(strat->P.sig);
3070	}
3071	strat->P.pLength = pLength(strat->P.p);
3072	if(strat->P.sig != NULL)
3073	strat->P.sevSig = pGetShortExpVector(strat->P.sig);
3074	if(strat->P.p != NULL)
3075	strat->P.sev = pGetShortExpVector(strat->P.p);
3076	}
3077	//sigdrop case
3078	if(rField_is_Ring(currRing) && strat->sigdrop)
3079	{
3080	//First reduce it as much as one can
3081	red_result = redRing(&strat->P,strat);
3082	if(red_result == 0)
3083	{
3084	strat->sigdrop = FALSE;
3085	pDelete(&strat->P.sig);
3086	strat->P.sig = NULL;
3087	}
3088	else
3089	{
3090	strat->enterS(strat->P, 0, strat, strat->tl);
3091	if (TEST_OPT_PROT)
3092	PrintS("-");
3093	break;
3094	}
3095	}
3096	if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
3097	{
3098	strat->sigdrop = TRUE;
3099	break;
3100	}
3101
3102	if (errorreported) break;
3103
3104	//#if 1
3105	#ifdef DEBUGF5
3106	if (red_result != 0)
3107	{
3108	PrintS("Poly after red: ");
3109	pWrite(pHead(strat->P.p));
3110	pWrite(strat->P.GetLmCurrRing());
3111	pWrite(strat->P.sig);
3112	printf("%d\n",red_result);
3113	}
3114	#endif
3115	if (TEST_OPT_PROT)
3116	{
3117	if(strat->P.p != NULL)
3118	message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3119	&olddeg,&reduc,strat, red_result);
3120	else
3121	message((strat->honey ? strat->P.ecart : 0),
3122	&olddeg,&reduc,strat, red_result);
3123	}
3124
3125	if (strat->overflow)
3126	{
3127	if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
3128	}
3129	// reduction to non-zero new poly
3130	if (red_result == 1)
3131	{
3132	// get the polynomial (canonicalize bucket, make sure P.p is set)
3133	strat->P.GetP(strat->lmBin);
3134
3135	// sig-safe computations may lead to wrong FDeg computation, thus we need
3136	// to recompute it to make sure everything is alright
3137	(strat->P).FDeg = (strat->P).pFDeg();
3138	// in the homogeneous case FDeg >= pFDeg (sugar/honey)
3139	// but now, for entering S, T, we reset it
3140	// in the inhomogeneous case: FDeg == pFDeg
3141	if (strat->homog) strat->initEcart(&(strat->P));
3142
3143	/* statistic */
3144	if (TEST_OPT_PROT) PrintS("s");
3145
3146	//int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3147	// in F5E we know that the last reduced element is already the
3148	// the one with highest signature
3149	int pos = strat->sl+1;
3150
3151	// reduce the tail and normalize poly
3152	// in the ring case we cannot expect LC(f) = 1,
3153	// therefore we call pCleardenom instead of pNorm
3154	#ifdef HAVE_RINGS
3155	poly beforetailred;
3156	if(rField_is_Ring(currRing))
3157	beforetailred = pCopy(strat->P.sig);
3158	#endif
3159	#if SBA_TAIL_RED
3160	if(rField_is_Ring(currRing))
3161	{
3162	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
3163	strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3164	}
3165	else
3166	{
3167	if (strat->sbaOrder != 2)
3168	{
3169	if (TEST_OPT_INTSTRATEGY)
3170	{
3171	strat->P.pCleardenom();
3172	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
3173	{
3174	strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3175	strat->P.pCleardenom();
3176	}
3177	}
3178	else
3179	{
3180	strat->P.pNorm();
3181	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
3182	strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3183	}
3184	}
3185	}
3186	// It may happen that we have lost the sig in redtailsba
3187	// It cannot reduce to 0 since here we are doing just tail reduction.
3188	// Best case scenerio: remains the leading term
3189	if(rField_is_Ring(currRing) && strat->sigdrop)
3190	{
3191	strat->enterS(strat->P, 0, strat, strat->tl);
3192	break;
3193	}
3194	#endif
3195	if(rField_is_Ring(currRing))
3196	{
3197	if(strat->P.sig == NULL \|\| pLtCmp(beforetailred,strat->P.sig) == 1)
3198	{
3199	strat->sigdrop = TRUE;
3200	//Reduce it as much as you can
3201	red_result = redRing(&strat->P,strat);
3202	if(red_result == 0)
3203	{
3204	//It reduced to 0, cancel the sigdrop
3205	strat->sigdrop = FALSE;
3206	p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
3207	}
3208	else
3209	{
3210	strat->enterS(strat->P, 0, strat, strat->tl);
3211	break;
3212	}
3213	}
3214	p_Delete(&beforetailred,currRing);
3215	// strat->P.p = NULL may appear if we had a sigdrop above and reduced to 0 via redRing
3216	if(strat->P.p == NULL)
3217	goto case_when_red_result_changed;
3218	}
3219	// remove sigsafe label since it is no longer valid for the next element to
3220	// be reduced
3221	if (strat->sbaOrder == 1)
3222	{
3223	for (int jj = 0; jj<strat->tl+1; jj++)
3224	{
3225	if (pGetComp(strat->T[jj].sig) == strat->currIdx)
3226	{
3227	strat->T[jj].is_sigsafe = FALSE;
3228	}
3229	}
3230	}
3231	else
3232	{
3233	for (int jj = 0; jj<strat->tl+1; jj++)
3234	{
3235	strat->T[jj].is_sigsafe = FALSE;
3236	}
3237	}
3238	#ifdef KDEBUG
3239	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3240	#endif /* KDEBUG */
3241
3242	// min_std stuff
3243	if ((strat->P.p1==NULL) && (strat->minim>0))
3244	{
3245	if (strat->minim==1)
3246	{
3247	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3248	p_Delete(&strat->P.p2, currRing, strat->tailRing);
3249	}
3250	else
3251	{
3252	strat->M->m[minimcnt]=strat->P.p2;
3253	strat->P.p2=NULL;
3254	}
3255	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3256	pNext(strat->M->m[minimcnt])
3257	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3258	strat->tailRing, currRing,
3259	currRing->PolyBin);
3260	minimcnt++;
3261	}
3262
3263	// enter into S, L, and T
3264	//if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
3265	enterT(strat->P, strat);
3266	strat->T[strat->tl].is_sigsafe = FALSE;
3267	/*
3268	printf("hier\n");
3269	pWrite(strat->P.GetLmCurrRing());
3270	pWrite(strat->P.sig);
3271	*/
3272	if (rField_is_Ring(currRing))
3273	superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3274	else
3275	enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3276	if(rField_is_Ring(currRing) && strat->sigdrop)
3277	break;
3278	if(rField_is_Ring(currRing))
3279	strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
3280	strat->enterS(strat->P, pos, strat, strat->tl);
3281	if(strat->sbaOrder != 1)
3282	{
3283	BOOLEAN overwrite = FALSE;
3284	for (int tk=0; tk<strat->sl+1; tk++)
3285	{
3286	if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
3287	{
3288	//printf("TK %d / %d\n",tk,strat->sl);
3289	overwrite = FALSE;
3290	break;
3291	}
3292	}
3293	//printf("OVERWRITE %d\n",overwrite);
3294	if (overwrite)
3295	{
3296	int cmp = pGetComp(strat->P.sig);
3297	int* vv = (int)omAlloc((currRing->N+1)sizeof(int));
3298	p_GetExpV (strat->P.p,vv,currRing);
3299	p_SetExpV (strat->P.sig, vv,currRing);
3300	p_SetComp (strat->P.sig,cmp,currRing);
3301
3302	strat->P.sevSig = pGetShortExpVector (strat->P.sig);
3303	int i;
3304	LObject Q;
3305	for(int ps=0;ps<strat->sl+1;ps++)
3306	{
3307
3308	strat->newt = TRUE;
3309	if (strat->syzl == strat->syzmax)
3310	{
3311	pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
3312	strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
3313	(strat->syzmax)*sizeof(unsigned long),
3314	((strat->syzmax)+setmaxTinc)
3315	*sizeof(unsigned long));
3316	strat->syzmax += setmaxTinc;
3317	}
3318	Q.sig = pCopy(strat->P.sig);
3319	// add LM(F->m[i]) to the signature to get a Schreyer order
3320	// without changing the underlying polynomial ring at all
3321	if (strat->sbaOrder == 0)
3322	p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
3323	// since p_Add_q() destroys all input
3324	// data we need to recreate help
3325	// each time
3326	// ----------------------------------------------------------
3327	// in the Schreyer order we always know that the multiplied
3328	// module monomial strat->P.sig gives the leading monomial of
3329	// the corresponding principal syzygy
3330	// => we do not need to compute the "real" syzygy completely
3331	poly help = p_Copy(strat->sig[ps],currRing);
3332	p_ExpVectorAdd (help,strat->P.p,currRing);
3333	Q.sig = p_Add_q(Q.sig,help,currRing);
3334	//printf("%d. SYZ ",i+1);
3335	//pWrite(strat->syz[i]);
3336	Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
3337	i = posInSyz(strat, Q.sig);
3338	enterSyz(Q, strat, i);
3339	}
3340	}
3341	}
3342	// deg - idx - lp/rp
3343	// => we need to add syzygies with indices > pGetComp(strat->P.sig)
3344	if(strat->sbaOrder == 0 \|\| strat->sbaOrder == 3)
3345	{
3346	int cmp = pGetComp(strat->P.sig);
3347	unsigned max_cmp = IDELEMS(F);
3348	int* vv = (int)omAlloc((currRing->N+1)sizeof(int));
3349	p_GetExpV (strat->P.p,vv,currRing);
3350	LObject Q;
3351	int pos;
3352	int idx = __p_GetComp(strat->P.sig,currRing);
3353	//printf("++ -- adding syzygies -- ++\n");
3354	// if new element is the first one in this index
3355	if (strat->currIdx < idx)
3356	{
3357	for (int i=0; i<strat->sl; ++i)
3358	{
3359	Q.sig = p_Copy(strat->P.sig,currRing);
3360	p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
3361	poly help = p_Copy(strat->sig[i],currRing);
3362	p_ExpVectorAdd(help,strat->P.p,currRing);
3363	Q.sig = p_Add_q(Q.sig,help,currRing);
3364	//pWrite(Q.sig);
3365	pos = posInSyz(strat, Q.sig);
3366	enterSyz(Q, strat, pos);
3367	}
3368	strat->currIdx = idx;
3369	}
3370	else
3371	{
3372	// if the element is not the first one in the given index we build all
3373	// possible syzygies with elements of higher index
3374	for (unsigned i=cmp+1; i<=max_cmp; ++i)
3375	{
3376	pos = -1;
3377	for (int j=0; j<strat->sl; ++j)
3378	{
3379	if (__p_GetComp(strat->sig[j],currRing) == i)
3380	{
3381	pos = j;
3382	break;
3383	}
3384	}
3385	if (pos != -1)
3386	{
3387	Q.sig = p_One(currRing);
3388	p_SetExpV(Q.sig, vv, currRing);
3389	// F->m[i-1] corresponds to index i
3390	p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
3391	p_SetComp(Q.sig, i, currRing);
3392	poly help = p_Copy(strat->P.sig,currRing);
3393	p_ExpVectorAdd(help,strat->S[pos],currRing);
3394	Q.sig = p_Add_q(Q.sig,help,currRing);
3395	if (strat->sbaOrder == 0)
3396	{
3397	if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn)
3398	{
3399	pos = posInSyz(strat, Q.sig);
3400	enterSyz(Q, strat, pos);
3401	}
3402	}
3403	else
3404	{
3405	pos = posInSyz(strat, Q.sig);
3406	enterSyz(Q, strat, pos);
3407	}
3408	}
3409	}
3410	//printf("++ -- done adding syzygies -- ++\n");
3411	}
3412	}
3413	//#if 1
3414	#if DEBUGF50
3415	printf("---------------------------\n");
3416	Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
3417	PrintS("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
3418	PrintS("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
3419	#endif
3420	/*
3421	if (newrules)
3422	{
3423	newrules = FALSE;
3424	}
3425	*/
3426	#if 0
3427	int pl=pLength(strat->P.p);
3428	if (pl==1)
3429	{
3430	//if (TEST_OPT_PROT)
3431	//PrintS("<1>");
3432	}
3433	else if (pl==2)
3434	{
3435	//if (TEST_OPT_PROT)
3436	//PrintS("<2>");
3437	}
3438	#endif
3439	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3440	// Print("[%d]",hilbeledeg);
3441	kDeleteLcm(&strat->P);
3442	if (strat->sl>srmax) srmax = strat->sl;
3443	}
3444	else
3445	{
3446	case_when_red_result_changed:
3447	// adds signature of the zero reduction to
3448	// strat->syz. This is the leading term of
3449	// syzygy and can be used in syzCriterion()
3450	// the signature is added if and only if the
3451	// pair was not detected by the rewritten criterion in strat->red = redSig
3452	if (red_result!=2)
3453	{
3454	#if SBA_PRINT_ZERO_REDUCTIONS
3455	zeroreductions++;
3456	#endif
3457	if(rField_is_Ring(currRing) && strat->P.p == NULL && strat->P.sig == NULL)
3458	{
3459	//Catch the case when p = 0, sig = 0
3460	}
3461	else
3462	{
3463	int pos = posInSyz(strat, strat->P.sig);
3464	enterSyz(strat->P, strat, pos);
3465	//#if 1
3466	#ifdef DEBUGF5
3467	Print("ADDING STUFF TO SYZ : ");
3468	//pWrite(strat->P.p);
3469	pWrite(strat->P.sig);
3470	#endif
3471	}
3472	}
3473	if (strat->P.p1 == NULL && strat->minim > 0)
3474	{
3475	p_Delete(&strat->P.p2, currRing, strat->tailRing);
3476	}
3477	}
3478
3479	#ifdef KDEBUG
3480	memset(&(strat->P), 0, sizeof(strat->P));
3481	#endif /* KDEBUG */
3482	kTest_TS(strat);
3483	}
3484	#if 0
3485	if(strat->sigdrop)
3486	printf("\nSigDrop!\n");
3487	else
3488	printf("\nEnded with no SigDrop\n");
3489	#endif
3490	// Clean strat->P for the next sba call
3491	if(rField_is_Ring(currRing) && strat->sigdrop)
3492	{
3493	//This is used to know how many elements can we directly add to S in the next run
3494	if(strat->P.sig != NULL)
3495	strat->sbaEnterS = pGetComp(strat->P.sig)-1;
3496	//else we already set it at the beggining of the loop
3497	#ifdef KDEBUG
3498	memset(&(strat->P), 0, sizeof(strat->P));
3499	#endif /* KDEBUG */
3500	}
3501	#ifdef KDEBUG
3502	if (TEST_OPT_DEBUG) messageSets(strat);
3503	#endif /* KDEBUG */
3504
3505	if (TEST_OPT_SB_1)
3506	{
3507	if(!rField_is_Ring(currRing))
3508	{
3509	int k=1;
3510	int j;
3511	while(k<=strat->sl)
3512	{
3513	j=0;
3514	loop
3515	{
3516	if (j>=k) break;
3517	clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3518	j++;
3519	}
3520	k++;
3521	}
3522	}
3523	}
3524	/* complete reduction of the standard basis--------- */
3525	if (TEST_OPT_REDSB)
3526	{
3527	completeReduce(strat);
3528	if (strat->completeReduce_retry)
3529	{
3530	// completeReduce needed larger exponents, retry
3531	// to reduce with S (instead of T)
3532	// and in currRing (instead of strat->tailRing)
3533	#ifdef HAVE_TAIL_RING
3534	if(currRing->bitmask>strat->tailRing->bitmask)
3535	{
3536	strat->completeReduce_retry=FALSE;
3537	cleanT(strat);strat->tailRing=currRing;
3538	int i;
3539	for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3540	completeReduce(strat);
3541	}
3542	if (strat->completeReduce_retry)
3543	#endif
3544	Werror("exponent bound is %ld",currRing->bitmask);
3545	}
3546	}
3547	else if (TEST_OPT_PROT) PrintLn();
3548
3549	#if SBA_PRINT_SIZE_SYZ
3550	// that is correct, syzl is counting one too far
3551	size_syz = strat->syzl;
3552	#endif
3553	// if (TEST_OPT_WEIGHTM)
3554	// {
3555	// pRestoreDegProcs(pFDegOld, pLDegOld);
3556	// if (ecartWeights)
3557	// {
3558	// omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
3559	// ecartWeights=NULL;
3560	// }
3561	// }
3562	if (TEST_OPT_PROT) messageStatSBA(hilbcount,strat);
3563	if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3564	#if SBA_PRINT_SIZE_G
3565	size_g_non_red = IDELEMS(strat->Shdl);
3566	#endif
3567	if(!rField_is_Ring(currRing))
3568	exitSba(strat);
3569	// I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
3570	#ifdef HAVE_RINGS
3571	int k;
3572	if(rField_is_Ring(currRing))
3573	{
3574	//for(k = strat->sl;k>=0;k--)
3575	// {printf("\nS[%i] = %p\n",k,strat->Shdl->m[k]);pWrite(strat->Shdl->m[k]);}
3576	k = strat->Ll;
3577	#if 1
3578	// 1 - adds just the unused ones, 0 - adds everthing
3579	for(;k>=0 && (strat->L[k].p1 != NULL \|\| strat->L[k].p2 != NULL);k--)
3580	{
3581	//printf("\nDeleted k = %i, %p\n",k,strat->L[k].p);pWrite(strat->L[k].p);pWrite(strat->L[k].p1);pWrite(strat->L[k].p2);
3582	deleteInL(strat->L,&strat->Ll,k,strat);
3583	}
3584	#endif
3585	//for(int kk = strat->sl;kk>=0;kk--)
3586	// {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
3587	//idPrint(strat->Shdl);
3588	//printf("\nk = %i\n",k);
3589	for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
3590	{
3591	//printf("\nAdded k = %i\n",k);
3592	strat->enterS(strat->L[k], strat->sl+1, strat, strat->tl);
3593	//printf("\nThis elements was added from L on pos %i\n",strat->sl);pWrite(strat->S[strat->sl]);pWrite(strat->sig[strat->sl]);
3594	}
3595	}
3596	// Find the "sigdrop element" and put the same signature as the previous one - do we really need this?? - now i put it on the 0 position - no more comparing needed
3597	#if 0
3598	if(strat->sigdrop && rField_is_Ring(currRing))
3599	{
3600	for(k=strat->sl;k>=0;k--)
3601	{
3602	printf("\nsig[%i] = ",i);pWrite(strat->sig[k]);
3603	if(strat->sig[k] == NULL)
3604	strat->sig[k] = pCopy(strat->sig[k-1]);
3605	}
3606	}
3607	#endif
3608	#endif
3609	//Never do this - you will damage S
3610	//idSkipZeroes(strat->Shdl);
3611	//idPrint(strat->Shdl);
3612
3613	if ((strat->sbaOrder == 1 \|\| strat->sbaOrder == 3) && sRing!=currRingOld)
3614	{
3615	rChangeCurrRing (currRingOld);
3616	F0 = idrMoveR (F1, sRing, currRing);
3617	strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
3618	rChangeCurrRing (sRing);
3619	if(rField_is_Ring(currRing))
3620	exitSba(strat);
3621	rChangeCurrRing (currRingOld);
3622	if(strat->tailRing == sRing)
3623	strat->tailRing = currRing;
3624	rDelete (sRing);
3625	}
3626	if(rField_is_Ring(currRing) && !strat->sigdrop)
3627	id_DelDiv(strat->Shdl, currRing);
3628	if(!rField_is_Ring(currRing))
3629	id_DelDiv(strat->Shdl, currRing);
3630	idSkipZeroes(strat->Shdl);
3631	idTest(strat->Shdl);
3632
3633	#if SBA_PRINT_SIZE_G
3634	size_g = IDELEMS(strat->Shdl);
3635	#endif
3636	#ifdef DEBUGF5
3637	printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
3638	int oo = 0;
3639	while (oo<IDELEMS(strat->Shdl))
3640	{
3641	printf(" %d. ",oo+1);
3642	pWrite(pHead(strat->Shdl->m[oo]));
3643	oo++;
3644	}
3645	#endif
3646	#if SBA_PRINT_ZERO_REDUCTIONS
3647	printf("----------------------------------------------------------\n");
3648	printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
3649	zeroreductions = 0;
3650	#endif
3651	#if SBA_PRINT_REDUCTION_STEPS
3652	printf("----------------------------------------------------------\n");
3653	printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
3654	#endif
3655	#if SBA_PRINT_OPERATIONS
3656	printf("OPERATIONS: %ld\n",sba_operations);
3657	#endif
3658	#if SBA_PRINT_REDUCTION_STEPS
3659	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3660	printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
3661	#endif
3662	#if SBA_PRINT_OPERATIONS
3663	printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
3664	#endif
3665	#if SBA_PRINT_REDUCTION_STEPS
3666	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3667	printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
3668	sba_interreduction_steps = 0;
3669	sba_reduction_steps = 0;
3670	#endif
3671	#if SBA_PRINT_OPERATIONS
3672	printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
3673	sba_interreduction_operations = 0;
3674	sba_operations = 0;
3675	#endif
3676	#if SBA_PRINT_SIZE_G
3677	printf("----------------------------------------------------------\n");
3678	printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
3679	size_g = 0;
3680	size_g_non_red = 0;
3681	#endif
3682	#if SBA_PRINT_SIZE_SYZ
3683	printf("SIZE OF SYZ: %ld\n",size_syz);
3684	printf("----------------------------------------------------------\n");
3685	size_syz = 0;
3686	#endif
3687	#if SBA_PRINT_PRODUCT_CRITERION
3688	printf("PRODUCT CRITERIA: %ld\n",product_criterion);
3689	product_criterion = 0;
3690	#endif
3691	return (strat->Shdl);
3692	}
3693
3694	poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
3695	{
3696	assume(q!=NULL);
3697	assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3698
3699	// lazy_reduce flags: can be combined by \|
3700	//#define KSTD_NF_LAZY 1
3701	// do only a reduction of the leading term
3702	//#define KSTD_NF_NONORM 4
3703	// only global: avoid normalization, return a multiply of NF
3704	poly p;
3705
3706	//if ((idIs0(F))&&(Q==NULL))
3707	// return pCopy(q); /F=0/
3708	//strat->ak = idRankFreeModule(F);
3709	/- creating temp data structures------------------- -/
3710	BITSET save1;
3711	SI_SAVE_OPT1(save1);
3712	si_opt_1\|=Sy_bit(OPT_REDTAIL);
3713	initBuchMoraCrit(strat);
3714	strat->initEcart = initEcartBBA;
3715	#ifdef HAVE_SHIFTBBA
3716	if (rIsLPRing(currRing))
3717	{
3718	strat->enterS = enterSBbaShift;
3719	}
3720	else
3721	#endif
3722	{
3723	strat->enterS = enterSBba;
3724	}
3725	#ifndef NO_BUCKETS
3726	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3727	#endif
3728	/- set S -/
3729	strat->sl = -1;
3730	/- init local data struct.---------------------------------------- -/
3731	/Shdl=/initS(F,Q,strat);
3732	/- compute------------------------------------------------------- -/
3733	//if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3734	//{
3735	// for (i=strat->sl;i>=0;i--)
3736	// pNorm(strat->S[i]);
3737	//}
3738	kTest(strat);
3739	if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3740	if (BVERBOSE(23)) kDebugPrint(strat);
3741	int max_ind;
3742	p = redNF(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3743	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3744	{
3745	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3746	if (rField_is_Ring(currRing))
3747	{
3748	p = redtailBba_Z(p,max_ind,strat);
3749	}
3750	else
3751	{
3752	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3753	p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3754	}
3755	}
3756	/- release temp data------------------------------- -/
3757	assume(strat->L==NULL); /* strat->L unused */
3758	assume(strat->B==NULL); /* strat->B unused */
3759	omFree(strat->sevS);
3760	omFree(strat->ecartS);
3761	assume(strat->T==NULL);//omfree(strat->T);
3762	assume(strat->sevT==NULL);//omfree(strat->sevT);
3763	assume(strat->R==NULL);//omfree(strat->R);
3764	omfree(strat->S_2_R);
3765	omfree(strat->fromQ);
3766	#ifdef HAVE_SHIFTBBA
3767	// only LM of elements in S is shifted
3768	// necessary to prevent deleting the tail multiple times
3769	if (rIsLPRing(currRing))
3770	{
3771	for (int j = 0; j < IDELEMS(strat->Shdl); j++)
3772	{
3773	if (strat->Shdl->m[j]!=NULL && pmFirstVblock(strat->Shdl->m[j]) > 1)
3774	{
3775	// otherwise the tail would be freed multiple times
3776	pNext(strat->Shdl->m[j]) = NULL;
3777	}
3778	}
3779	}
3780	#endif
3781	idDelete(&strat->Shdl);
3782	SI_RESTORE_OPT1(save1);
3783	if (TEST_OPT_PROT) PrintLn();
3784	return p;
3785	}
3786
3787	poly kNF2Bound (ideal F,ideal Q,poly q,int bound,kStrategy strat, int lazyReduce)
3788	{
3789	assume(q!=NULL);
3790	assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3791
3792	// lazy_reduce flags: can be combined by \|
3793	//#define KSTD_NF_LAZY 1
3794	// do only a reduction of the leading term
3795	//#define KSTD_NF_NONORM 4
3796	// only global: avoid normalization, return a multiply of NF
3797	poly p;
3798
3799	//if ((idIs0(F))&&(Q==NULL))
3800	// return pCopy(q); /F=0/
3801	//strat->ak = idRankFreeModule(F);
3802	/- creating temp data structures------------------- -/
3803	BITSET save1;
3804	SI_SAVE_OPT1(save1);
3805	si_opt_1\|=Sy_bit(OPT_REDTAIL);
3806	initBuchMoraCrit(strat);
3807	strat->initEcart = initEcartBBA;
3808	strat->enterS = enterSBba;
3809	#ifndef NO_BUCKETS
3810	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3811	#endif
3812	/- set S -/
3813	strat->sl = -1;
3814	/- init local data struct.---------------------------------------- -/
3815	/Shdl=/initS(F,Q,strat);
3816	/- compute------------------------------------------------------- -/
3817	//if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3818	//{
3819	// for (i=strat->sl;i>=0;i--)
3820	// pNorm(strat->S[i]);
3821	//}
3822	kTest(strat);
3823	if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3824	if (BVERBOSE(23)) kDebugPrint(strat);
3825	int max_ind;
3826	p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3827	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3828	{
3829	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3830	if (rField_is_Ring(currRing))
3831	{
3832	p = redtailBba_Z(p,max_ind,strat);
3833	}
3834	else
3835	{
3836	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3837	p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
3838	//p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3839	}
3840	}
3841	/- release temp data------------------------------- -/
3842	assume(strat->L==NULL); /* strat->L unused */
3843	assume(strat->B==NULL); /* strat->B unused */
3844	omFree(strat->sevS);
3845	omFree(strat->ecartS);
3846	assume(strat->T==NULL);//omfree(strat->T);
3847	assume(strat->sevT==NULL);//omfree(strat->sevT);
3848	assume(strat->R==NULL);//omfree(strat->R);
3849	omfree(strat->S_2_R);
3850	omfree(strat->fromQ);
3851	idDelete(&strat->Shdl);
3852	SI_RESTORE_OPT1(save1);
3853	if (TEST_OPT_PROT) PrintLn();
3854	return p;
3855	}
3856
3857	ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
3858	{
3859	assume(!idIs0(q));
3860	assume(!(idIs0(F)&&(Q==NULL)));
3861	// lazy_reduce flags: can be combined by \|
3862	//#define KSTD_NF_LAZY 1
3863	// do only a reduction of the leading term
3864	//#define KSTD_NF_NONORM 4
3865	// only global: avoid normalization, return a multiply of NF
3866	poly p;
3867	int i;
3868	ideal res;
3869	int max_ind;
3870
3871	//if (idIs0(q))
3872	// return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3873	//if ((idIs0(F))&&(Q==NULL))
3874	// return idCopy(q); /F=0/
3875	//strat->ak = idRankFreeModule(F);
3876	/- creating temp data structures------------------- -/
3877	BITSET save1;
3878	SI_SAVE_OPT1(save1);
3879	si_opt_1\|=Sy_bit(OPT_REDTAIL);
3880	initBuchMoraCrit(strat);
3881	strat->initEcart = initEcartBBA;
3882	#ifdef HAVE_SHIFTBBA
3883	if (rIsLPRing(currRing))
3884	{
3885	strat->enterS = enterSBbaShift;
3886	}
3887	else
3888	#endif
3889	{
3890	strat->enterS = enterSBba;
3891	}
3892	/- set S -/
3893	strat->sl = -1;
3894	#ifndef NO_BUCKETS
3895	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3896	#endif
3897	/- init local data struct.---------------------------------------- -/
3898	/Shdl=/initS(F,Q,strat);
3899	/- compute------------------------------------------------------- -/
3900	res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3901	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3902	for (i=IDELEMS(q)-1; i>=0; i--)
3903	{
3904	if (q->m[i]!=NULL)
3905	{
3906	if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3907	p = redNF(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3908	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3909	{
3910	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3911	if (rField_is_Ring(currRing))
3912	{
3913	p = redtailBba_Z(p,max_ind,strat);
3914	}
3915	else
3916	{
3917	p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3918	}
3919	}
3920	res->m[i]=p;
3921	}
3922	//else
3923	// res->m[i]=NULL;
3924	}
3925	/- release temp data------------------------------- -/
3926	assume(strat->L==NULL); /* strat->L unused */
3927	assume(strat->B==NULL); /* strat->B unused */
3928	omFree(strat->sevS);
3929	omFree(strat->ecartS);
3930	assume(strat->T==NULL);//omfree(strat->T);
3931	assume(strat->sevT==NULL);//omfree(strat->sevT);
3932	assume(strat->R==NULL);//omfree(strat->R);
3933	omfree(strat->S_2_R);
3934	omfree(strat->fromQ);
3935	#ifdef HAVE_SHIFTBBA
3936	// only LM of elements in S is shifted
3937	// necessary to prevent deleting the tail multiple times
3938	if (rIsLPRing(currRing))
3939	{
3940	for (int j = 0; j < IDELEMS(strat->Shdl); j++)
3941	{
3942	if (strat->Shdl->m[j]!=NULL && pmFirstVblock(strat->Shdl->m[j]) > 1)
3943	{
3944	// otherwise the tail would be freed multiple times
3945	pNext(strat->Shdl->m[j]) = NULL;
3946	}
3947	}
3948	}
3949	#endif
3950	idDelete(&strat->Shdl);
3951	SI_RESTORE_OPT1(save1);
3952	if (TEST_OPT_PROT) PrintLn();
3953	return res;
3954	}
3955
3956	ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound,kStrategy strat, int lazyReduce)
3957	{
3958	assume(!idIs0(q));
3959	assume(!(idIs0(F)&&(Q==NULL)));
3960	// lazy_reduce flags: can be combined by \|
3961	//#define KSTD_NF_LAZY 1
3962	// do only a reduction of the leading term
3963	//#define KSTD_NF_NONORM 4
3964	// only global: avoid normalization, return a multiply of NF
3965	poly p;
3966	int i;
3967	ideal res;
3968	int max_ind;
3969
3970	//if (idIs0(q))
3971	// return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3972	//if ((idIs0(F))&&(Q==NULL))
3973	// return idCopy(q); /F=0/
3974	//strat->ak = idRankFreeModule(F);
3975	/- creating temp data structures------------------- -/
3976	BITSET save1;
3977	SI_SAVE_OPT1(save1);
3978	si_opt_1\|=Sy_bit(OPT_REDTAIL);
3979	initBuchMoraCrit(strat);
3980	strat->initEcart = initEcartBBA;
3981	strat->enterS = enterSBba;
3982	/- set S -/
3983	strat->sl = -1;
3984	#ifndef NO_BUCKETS
3985	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3986	#endif
3987	/- init local data struct.---------------------------------------- -/
3988	/Shdl=/initS(F,Q,strat);
3989	/- compute------------------------------------------------------- -/
3990	res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3991	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3992	for (i=IDELEMS(q)-1; i>=0; i--)
3993	{
3994	if (q->m[i]!=NULL)
3995	{
3996	if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3997	p = redNFBound(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3998	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3999	{
4000	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
4001	if (rField_is_Ring(currRing))
4002	{
4003	p = redtailBba_Z(p,max_ind,strat);
4004	}
4005	else
4006	{
4007	p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
4008	}
4009	}
4010	res->m[i]=p;
4011	}
4012	//else
4013	// res->m[i]=NULL;
4014	}
4015	/- release temp data------------------------------- -/
4016	assume(strat->L==NULL); /* strat->L unused */
4017	assume(strat->B==NULL); /* strat->B unused */
4018	omFree(strat->sevS);
4019	omFree(strat->ecartS);
4020	assume(strat->T==NULL);//omfree(strat->T);
4021	assume(strat->sevT==NULL);//omfree(strat->sevT);
4022	assume(strat->R==NULL);//omfree(strat->R);
4023	omfree(strat->S_2_R);
4024	omfree(strat->fromQ);
4025	idDelete(&strat->Shdl);
4026	SI_RESTORE_OPT1(save1);
4027	if (TEST_OPT_PROT) PrintLn();
4028	return res;
4029	}
4030
4031	#if F5C
4032	/*********************************************************************
4033	* interrreduction step of the signature-based algorithm:
4034	* 1. all strat->S are interpreted as new critical pairs
4035	* 2. those pairs need to be completely reduced by the usual (non sig-
4036	* safe) reduction process (including tail reductions)
4037	* 3. strat->S and strat->T are completely new computed in these steps
4038	********************************************************************/
4039	void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
4040	int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
4041	intvec w,intvec hilb )
4042	{
4043	int Ll_old, red_result = 1;
4044	int pos = 0;
4045	hilbeledeg=1;
4046	hilbcount=0;
4047	minimcnt=0;
4048	srmax = 0; // strat->sl is 0 at this point
4049	reduc = olddeg = lrmax = 0;
4050	// we cannot use strat->T anymore
4051	//cleanT(strat);
4052	//strat->tl = -1;
4053	Ll_old = strat->Ll;
4054	while (strat->tl >= 0)
4055	{
4056	if(!strat->T[strat->tl].is_redundant)
4057	{
4058	LObject h;
4059	h.p = strat->T[strat->tl].p;
4060	h.tailRing = strat->T[strat->tl].tailRing;
4061	h.t_p = strat->T[strat->tl].t_p;
4062	if (h.p!=NULL)
4063	{
4064	if (currRing->OrdSgn==-1)
4065	{
4066	cancelunit(&h);
4067	deleteHC(&h, strat);
4068	}
4069	if (h.p!=NULL)
4070	{
4071	if (TEST_OPT_INTSTRATEGY)
4072	{
4073	h.pCleardenom(); // also does remove Content
4074	}
4075	else
4076	{
4077	h.pNorm();
4078	}
4079	strat->initEcart(&h);
4080	if(rField_is_Ring(currRing))
4081	pos = posInLF5CRing(strat->L, Ll_old+1,strat->Ll,&h,strat);
4082	else
4083	pos = strat->Ll+1;
4084	h.sev = pGetShortExpVector(h.p);
4085	enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
4086	}
4087	}
4088	}
4089	strat->tl--;
4090	}
4091	strat->sl = -1;
4092	#if 0
4093	//#ifdef HAVE_TAIL_RING
4094	if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4095	kStratInitChangeTailRing(strat);
4096	#endif
4097	//enterpairs(pOne(),0,0,-1,strat,strat->tl);
4098	//strat->sl = -1;
4099	/* picks the last element from the lazyset L */
4100	while (strat->Ll>Ll_old)
4101	{
4102	strat->P = strat->L[strat->Ll];
4103	strat->Ll--;
4104	//#if 1
4105	#ifdef DEBUGF5
4106	PrintS("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
4107	PrintS("-------------------------------------------------\n");
4108	pWrite(pHead(strat->P.p));
4109	pWrite(pHead(strat->P.p1));
4110	pWrite(pHead(strat->P.p2));
4111	printf("%d\n",strat->tl);
4112	PrintS("-------------------------------------------------\n");
4113	#endif
4114	if (pNext(strat->P.p) == strat->tail)
4115	{
4116	// deletes the short spoly
4117	if (rField_is_Ring(currRing))
4118	pLmDelete(strat->P.p);
4119	else
4120	pLmFree(strat->P.p);
4121
4122	// TODO: needs some masking
4123	// TODO: masking needs to vanish once the signature
4124	// sutff is completely implemented
4125	strat->P.p = NULL;
4126	poly m1 = NULL, m2 = NULL;
4127
4128	// check that spoly creation is ok
4129	while (strat->tailRing != currRing &&
4130	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4131	{
4132	assume(m1 == NULL && m2 == NULL);
4133	// if not, change to a ring where exponents are at least
4134	// large enough
4135	if (!kStratChangeTailRing(strat))
4136	{
4137	WerrorS("OVERFLOW...");
4138	break;
4139	}
4140	}
4141	// create the real one
4142	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4143	strat->tailRing, m1, m2, strat->R);
4144	}
4145	else if (strat->P.p1 == NULL)
4146	{
4147	if (strat->minim > 0)
4148	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4149	// for input polys, prepare reduction
4150	if(!rField_is_Ring(currRing))
4151	strat->P.PrepareRed(strat->use_buckets);
4152	}
4153
4154	if (strat->P.p == NULL && strat->P.t_p == NULL)
4155	{
4156	red_result = 0;
4157	}
4158	else
4159	{
4160	if (TEST_OPT_PROT)
4161	message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4162	&olddeg,&reduc,strat, red_result);
4163
4164	#ifdef DEBUGF5
4165	PrintS("Poly before red: ");
4166	pWrite(strat->P.p);
4167	#endif
4168	/* complete reduction of the element chosen from L */
4169	red_result = strat->red2(&strat->P,strat);
4170	if (errorreported) break;
4171	}
4172
4173	if (strat->overflow)
4174	{
4175	if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4176	}
4177
4178	// reduction to non-zero new poly
4179	if (red_result == 1)
4180	{
4181	// get the polynomial (canonicalize bucket, make sure P.p is set)
4182	strat->P.GetP(strat->lmBin);
4183	// in the homogeneous case FDeg >= pFDeg (sugar/honey)
4184	// but now, for entering S, T, we reset it
4185	// in the inhomogeneous case: FDeg == pFDeg
4186	if (strat->homog) strat->initEcart(&(strat->P));
4187
4188	/* statistic */
4189	if (TEST_OPT_PROT) PrintS("s");
4190	int pos;
4191	#if 1
4192	if(!rField_is_Ring(currRing))
4193	pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4194	else
4195	pos = posInSMonFirst(strat,strat->sl,strat->P.p);
4196	#else
4197	pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4198	#endif
4199	// reduce the tail and normalize poly
4200	// in the ring case we cannot expect LC(f) = 1,
4201	// therefore we call pCleardenom instead of pNorm
4202	#if F5CTAILRED
4203	BOOLEAN withT = TRUE;
4204	if ((TEST_OPT_INTSTRATEGY) \|\| (rField_is_Ring(currRing)))
4205	{
4206	strat->P.pCleardenom();
4207	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
4208	{
4209	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4210	strat->P.pCleardenom();
4211	}
4212	}
4213	else
4214	{
4215	strat->P.pNorm();
4216	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
4217	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4218	}
4219	#endif
4220	#ifdef KDEBUG
4221	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4222	#endif /* KDEBUG */
4223
4224	// min_std stuff
4225	if ((strat->P.p1==NULL) && (strat->minim>0))
4226	{
4227	if (strat->minim==1)
4228	{
4229	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4230	p_Delete(&strat->P.p2, currRing, strat->tailRing);
4231	}
4232	else
4233	{
4234	strat->M->m[minimcnt]=strat->P.p2;
4235	strat->P.p2=NULL;
4236	}
4237	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4238	pNext(strat->M->m[minimcnt])
4239	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4240	strat->tailRing, currRing,
4241	currRing->PolyBin);
4242	minimcnt++;
4243	}
4244
4245	// enter into S, L, and T
4246	// here we need to recompute new signatures, but those are trivial ones
4247	if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
4248	{
4249	enterT(strat->P, strat);
4250	// posInS only depends on the leading term
4251	strat->enterS(strat->P, pos, strat, strat->tl);
4252	//#if 1
4253	#ifdef DEBUGF5
4254	PrintS("ELEMENT ADDED TO GCURR DURING INTERRED: ");
4255	pWrite(pHead(strat->S[strat->sl]));
4256	pWrite(strat->sig[strat->sl]);
4257	#endif
4258	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4259	}
4260	// Print("[%d]",hilbeledeg);
4261	kDeleteLcm(&strat->P);
4262	if (strat->sl>srmax) srmax = strat->sl;
4263	}
4264	else
4265	{
4266	// adds signature of the zero reduction to
4267	// strat->syz. This is the leading term of
4268	// syzygy and can be used in syzCriterion()
4269	// the signature is added if and only if the
4270	// pair was not detected by the rewritten criterion in strat->red = redSig
4271	if (strat->P.p1 == NULL && strat->minim > 0)
4272	{
4273	p_Delete(&strat->P.p2, currRing, strat->tailRing);
4274	}
4275	}
4276
4277	#ifdef KDEBUG
4278	memset(&(strat->P), 0, sizeof(strat->P));
4279	#endif /* KDEBUG */
4280	}
4281	int cc = 0;
4282	while (cc<strat->tl+1)
4283	{
4284	strat->T[cc].sig = pOne();
4285	p_SetComp(strat->T[cc].sig,cc+1,currRing);
4286	strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
4287	strat->sig[cc] = strat->T[cc].sig;
4288	strat->sevSig[cc] = strat->T[cc].sevSig;
4289	strat->T[cc].is_sigsafe = TRUE;
4290	cc++;
4291	}
4292	strat->max_lower_index = strat->tl;
4293	// set current signature index of upcoming iteration step
4294	// NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
4295	// the corresponding syzygy rules correctly
4296	strat->currIdx = cc+1;
4297	for (int cd=strat->Ll; cd>=0; cd--)
4298	{
4299	p_SetComp(strat->L[cd].sig,cc+1,currRing);
4300	cc++;
4301	}
4302	for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
4303	strat->Shdl->m[cc] = NULL;
4304	#if 0
4305	printf("\nAfter f5c sorting\n");
4306	for(int i=0;i<=strat->sl;i++)
4307	pWrite(pHead(strat->S[i]));
4308	getchar();
4309	#endif
4310	//#if 1
4311	#if DEBUGF5
4312	PrintS("------------------- STRAT S ---------------------\n");
4313	cc = 0;
4314	while (cc<strat->tl+1)
4315	{
4316	pWrite(pHead(strat->S[cc]));
4317	pWrite(strat->sig[cc]);
4318	printf("- - - - - -\n");
4319	cc++;
4320	}
4321	PrintS("-------------------------------------------------\n");
4322	PrintS("------------------- STRAT T ---------------------\n");
4323	cc = 0;
4324	while (cc<strat->tl+1)
4325	{
4326	pWrite(pHead(strat->T[cc].p));
4327	pWrite(strat->T[cc].sig);
4328	printf("- - - - - -\n");
4329	cc++;
4330	}
4331	PrintS("-------------------------------------------------\n");
4332	PrintS("------------------- STRAT L ---------------------\n");
4333	cc = 0;
4334	while (cc<strat->Ll+1)
4335	{
4336	pWrite(pHead(strat->L[cc].p));
4337	pWrite(pHead(strat->L[cc].p1));
4338	pWrite(pHead(strat->L[cc].p2));
4339	pWrite(strat->L[cc].sig);
4340	printf("- - - - - -\n");
4341	cc++;
4342	}
4343	PrintS("-------------------------------------------------\n");
4344	printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
4345	#endif
4346
4347	}
4348	#endif
4349
4350	/* shiftgb stuff */
4351	#ifdef HAVE_SHIFTBBA
4352
4353
4354	ideal bbaShift(ideal F, ideal Q,intvec w,intvec hilb,kStrategy strat)
4355	{
4356	int red_result = 1;
4357	int olddeg,reduc;
4358	int hilbeledeg=1,hilbcount=0,minimcnt=0;
4359	BOOLEAN withT = TRUE; // currently only T contains the shifts
4360	BITSET save;
4361	SI_SAVE_OPT1(save);
4362
4363	initBuchMoraCrit(strat); /set Gebauer, honey, sugarCrit/
4364	if(rField_is_Ring(currRing))
4365	initBuchMoraPosRing(strat);
4366	else
4367	initBuchMoraPos(strat);
4368	initHilbCrit(F,Q,&hilb,strat);
4369	initBba(strat);
4370	/set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair/
4371	/Shdl=/initBuchMora(F, Q,strat);
4372	if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
4373	reduc = olddeg = 0;
4374
4375	#ifndef NO_BUCKETS
4376	if (!TEST_OPT_NOT_BUCKETS)
4377	strat->use_buckets = 1;
4378	#endif
4379	// redtailBBa against T for inhomogenous input
4380	// if (!TEST_OPT_OLDSTD)
4381	// withT = ! strat->homog;
4382
4383	// strat->posInT = posInT_pLength;
4384	kTest_TS(strat);
4385
4386	#ifdef HAVE_TAIL_RING
4387	// if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4388	// kStratInitChangeTailRing(strat);
4389	strat->tailRing=currRing;
4390	#endif
4391	if (BVERBOSE(23))
4392	{
4393	if (test_PosInT!=NULL) strat->posInT=test_PosInT;
4394	if (test_PosInL!=NULL) strat->posInL=test_PosInL;
4395	kDebugPrint(strat);
4396	}
4397
4398	#ifdef KDEBUG
4399	//kDebugPrint(strat);
4400	#endif
4401	/* compute------------------------------------------------------- */
4402	while (strat->Ll >= 0)
4403	{
4404	#ifdef KDEBUG
4405	if (TEST_OPT_DEBUG) messageSets(strat);
4406	#endif
4407	if (siCntrlc)
4408	{
4409	while (strat->Ll >= 0)
4410	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4411	strat->noClearS=TRUE;
4412	}
4413	if (TEST_OPT_DEGBOUND
4414	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4415	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
4416	{
4417	/*
4418	*stops computation if
4419	* 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
4420	*a predefined number Kstd1_deg
4421	*/
4422	while ((strat->Ll >= 0)
4423	&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
4424	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4425	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
4426	)
4427	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4428	if (strat->Ll<0) break;
4429	else strat->noClearS=TRUE;
4430	}
4431	if (strat->Ll== 0) strat->interpt=TRUE;
4432	/* picks the last element from the lazyset L */
4433	strat->P = strat->L[strat->Ll];
4434	strat->Ll--;
4435
4436	if (pNext(strat->P.p) == strat->tail)
4437	{
4438	// deletes the short spoly
4439	if (rField_is_Ring(currRing))
4440	pLmDelete(strat->P.p);
4441	else
4442	pLmFree(strat->P.p);
4443	strat->P.p = NULL;
4444	poly m1 = NULL, m2 = NULL;
4445
4446	// check that spoly creation is ok
4447	while (strat->tailRing != currRing &&
4448	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4449	{
4450	assume(m1 == NULL && m2 == NULL);
4451	// if not, change to a ring where exponents are at least
4452	// large enough
4453	if (!kStratChangeTailRing(strat))
4454	{
4455	WerrorS("OVERFLOW...");
4456	break;
4457	}
4458	}
4459	// create the real one
4460	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4461	strat->tailRing, m1, m2, strat->R);
4462	}
4463	else if (strat->P.p1 == NULL)
4464	{
4465	if (strat->minim > 0)
4466	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4467	// for input polys, prepare reduction
4468	strat->P.PrepareRed(strat->use_buckets);
4469	}
4470
4471	if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
4472	{
4473	red_result = 0;
4474	}
4475	else
4476	{
4477	if (TEST_OPT_PROT)
4478	message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4479	&olddeg,&reduc,strat, red_result);
4480
4481	/* reduction of the element chosen from L */
4482	red_result = strat->red(&strat->P,strat);
4483	if (errorreported) break;
4484	}
4485
4486	if (strat->overflow)
4487	{
4488	if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4489	}
4490
4491	// reduction to non-zero new poly
4492	if (red_result == 1)
4493	{
4494	// get the polynomial (canonicalize bucket, make sure P.p is set)
4495	strat->P.GetP(strat->lmBin);
4496	// in the homogeneous case FDeg >= pFDeg (sugar/honey)
4497	// but now, for entering S, T, we reset it
4498	// in the inhomogeneous case: FDeg == pFDeg
4499	if (strat->homog) strat->initEcart(&(strat->P));
4500
4501	/* statistic */
4502	if (TEST_OPT_PROT) PrintS("s");
4503
4504	int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4505
4506	// reduce the tail and normalize poly
4507	// in the ring case we cannot expect LC(f) = 1,
4508	// therefore we call pCleardenom instead of pNorm
4509	strat->redTailChange=FALSE;
4510
4511	/* if we are computing over Z we always want to try and cut down
4512	* the coefficients in the tail terms */
4513	if (rField_is_Z(currRing) && !rHasLocalOrMixedOrdering(currRing)) {
4514	redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
4515	strat->P.pCleardenom();
4516	}
4517
4518	if ((TEST_OPT_INTSTRATEGY) \|\| (rField_is_Ring(currRing)))
4519	{
4520	strat->P.pCleardenom();
4521	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
4522	{
4523	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
4524	strat->P.pCleardenom();
4525	if (strat->redTailChange)
4526	{
4527	strat->P.t_p=NULL;
4528	strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4529	}
4530	}
4531	}
4532	else
4533	{
4534	strat->P.pNorm();
4535	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
4536	{
4537	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4538	if (strat->redTailChange)
4539	{
4540	strat->P.t_p=NULL;
4541	strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4542	}
4543	}
4544	}
4545
4546	#ifdef KDEBUG
4547	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4548	#endif /* KDEBUG */
4549
4550	// min_std stuff
4551	if ((strat->P.p1==NULL) && (strat->minim>0))
4552	{
4553	if (strat->minim==1)
4554	{
4555	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4556	p_Delete(&strat->P.p2, currRing, strat->tailRing);
4557	}
4558	else
4559	{
4560	strat->M->m[minimcnt]=strat->P.p2;
4561	strat->P.p2=NULL;
4562	}
4563	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4564	pNext(strat->M->m[minimcnt])
4565	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4566	strat->tailRing, currRing,
4567	currRing->PolyBin);
4568	minimcnt++;
4569	}
4570
4571
4572	// enter into S, L, and T
4573	if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
4574	{
4575	enterT(strat->P, strat);
4576	enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4577	// posInS only depends on the leading term
4578	strat->enterS(strat->P, pos, strat, strat->tl);
4579	if (!strat->rightGB)
4580	enterTShift(strat->P, strat);
4581	}
4582
4583	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4584	// Print("[%d]",hilbeledeg);
4585	kDeleteLcm(&strat->P);
4586	if (strat->s_poly!=NULL)
4587	{
4588	// the only valid entries are: strat->P.p,
4589	// strat->tailRing (read-only, keep it)
4590	// (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
4591	if (strat->s_poly(strat))
4592	{
4593	// we are called AFTER enterS, i.e. if we change P
4594	// we have to add it also to S/T
4595	// and add pairs
4596	int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4597	enterT(strat->P, strat);
4598	enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4599	strat->enterS(strat->P, pos, strat, strat->tl);
4600	if (!strat->rightGB)
4601	enterTShift(strat->P,strat);
4602	}
4603	}
4604	}
4605	else if (strat->P.p1 == NULL && strat->minim > 0)
4606	{
4607	p_Delete(&strat->P.p2, currRing, strat->tailRing);
4608	}
4609	#ifdef KDEBUG
4610	memset(&(strat->P), 0, sizeof(strat->P));
4611	#endif /* KDEBUG */
4612	kTest_TS(strat);
4613	}
4614	#ifdef KDEBUG
4615	if (TEST_OPT_DEBUG) messageSets(strat);
4616	#endif /* KDEBUG */
4617	/* shift case: look for elt's in S such that they are divisible by elt in T */
4618	if ((TEST_OPT_SB_1 \|\| TEST_OPT_REDSB) && !strat->noClearS) // when is OPT_SB_1 set?
4619	{
4620	if(!rField_is_Ring(currRing))
4621	{
4622	for (int k = 0; k <= strat->sl; ++k)
4623	{
4624	if ((strat->fromQ!=NULL) && (strat->fromQ[k])) continue; // do not reduce Q_k
4625	for (int j = 0; j<=strat->tl; ++j)
4626	{
4627	// this is like clearS in bba, but we reduce with elements from T, because it contains the shifts too
4628	assume(strat->sevT[j] == pGetShortExpVector(strat->T[j].p));
4629	assume(strat->sevS[k] == pGetShortExpVector(strat->S[k]));
4630	if (pLmShortDivisibleBy(strat->T[j].p, strat->sevT[j], strat->S[k], ~strat->sevS[k]))
4631	{
4632	if (pLmCmp(strat->T[j].p, strat->S[k]) != 0) { // check whether LM is different
4633	deleteInS(k, strat);
4634	--k;
4635	break;
4636	}
4637	}
4638	}
4639	}
4640	}
4641	}
4642	/* complete reduction of the standard basis--------- */
4643	if (TEST_OPT_REDSB)
4644	{
4645	completeReduce(strat, TRUE); //shift: withT = TRUE
4646	if (strat->completeReduce_retry)
4647	{
4648	// completeReduce needed larger exponents, retry
4649	// to reduce with S (instead of T)
4650	// and in currRing (instead of strat->tailRing)
4651	#ifdef HAVE_TAIL_RING
4652	if(currRing->bitmask>strat->tailRing->bitmask)
4653	{
4654	strat->completeReduce_retry=FALSE;
4655	cleanT(strat);strat->tailRing=currRing;
4656	int i;
4657	for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
4658	WarnS("reduction with S is not yet supported by Letterplace"); // if this ever happens, we'll know
4659	completeReduce(strat);
4660	}
4661	if (strat->completeReduce_retry)
4662	#endif
4663	Werror("exponent bound is %ld",currRing->bitmask);
4664	}
4665	}
4666	else if (TEST_OPT_PROT) PrintLn();
4667
4668	/* release temp data-------------------------------- */
4669	exitBuchMora(strat);
4670	/* postprocessing for GB over ZZ --------------------*/
4671	if (!errorreported)
4672	{
4673	if(rField_is_Z(currRing))
4674	{
4675	for(int i = 0;i<=strat->sl;i++)
4676	{
4677	if(!nGreaterZero(pGetCoeff(strat->S[i])))
4678	{
4679	strat->S[i] = pNeg(strat->S[i]);
4680	}
4681	}
4682	finalReduceByMon(strat);
4683	for(int i = 0;i<IDELEMS(strat->Shdl);i++)
4684	{
4685	if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
4686	{
4687	strat->S[i] = pNeg(strat->Shdl->m[i]);
4688	}
4689	}
4690	}
4691	//else if (rField_is_Ring(currRing))
4692	// finalReduceByMon(strat);
4693	}
4694	// if (TEST_OPT_WEIGHTM)
4695	// {
4696	// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
4697	// if (ecartWeights)
4698	// {
4699	// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
4700	// ecartWeights=NULL;
4701	// }
4702	// }
4703	if ((TEST_OPT_PROT) \|\| (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
4704	SI_RESTORE_OPT1(save);
4705	/* postprocessing for GB over Q-rings ------------------*/
4706	if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
4707
4708	idTest(strat->Shdl);
4709
4710	return (strat->Shdl);
4711	}
4712
4713	#ifdef HAVE_SHIFTBBA
4714	ideal rightgb(ideal F, ideal Q)
4715	{
4716	assume(rIsLPRing(currRing));
4717	assume(idIsInV(F));
4718	ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4719	idSkipZeroes(RS); // is this even necessary?
4720	assume(idIsInV(RS));
4721	return(RS);
4722	}
4723	#endif
4724
4725	/*2
4726	*reduces h with elements from T choosing the first possible
4727	* element in t with respect to the given pDivisibleBy
4728	*/
4729	int redFirstShift (LObject* h,kStrategy strat)
4730	{
4731	if (h->IsNull()) return 0;
4732
4733	int at, reddeg,d;
4734	int pass = 0;
4735	int j = 0;
4736
4737	if (! strat->homog)
4738	{
4739	d = h->GetpFDeg() + h->ecart;
4740	reddeg = strat->LazyDegree+d;
4741	}
4742	h->SetShortExpVector();
4743	loop
4744	{
4745	j = kFindDivisibleByInT(strat, h);
4746	if (j < 0)
4747	{
4748	h->SetDegStuffReturnLDeg(strat->LDegLast);
4749	return 1;
4750	}
4751
4752	if (!TEST_OPT_INTSTRATEGY)
4753	strat->T[j].pNorm();
4754	#ifdef KDEBUG
4755	if (TEST_OPT_DEBUG)
4756	{
4757	PrintS("reduce ");
4758	h->wrp();
4759	PrintS(" with ");
4760	strat->T[j].wrp();
4761	}
4762	#endif
4763	ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, strat);
4764
4765	#ifdef KDEBUG
4766	if (TEST_OPT_DEBUG)
4767	{
4768	PrintS("\nto ");
4769	wrp(h->p);
4770	PrintLn();
4771	}
4772	#endif
4773	if (h->IsNull())
4774	{
4775	kDeleteLcm(h);
4776	h->Clear();
4777	return 0;
4778	}
4779	h->SetShortExpVector();
4780
4781	#if 0
4782	if ((strat->syzComp!=0) && !strat->honey)
4783	{
4784	if ((strat->syzComp>0) &&
4785	(h->Comp() > strat->syzComp))
4786	{
4787	assume(h->MinComp() > strat->syzComp);
4788	#ifdef KDEBUG
4789	if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
4790	#endif
4791	if (strat->homog)
4792	h->SetDegStuffReturnLDeg(strat->LDegLast);
4793	return -2;
4794	}
4795	}
4796	#endif
4797	if (!strat->homog)
4798	{
4799	if (!TEST_OPT_OLDSTD && strat->honey)
4800	{
4801	h->SetpFDeg();
4802	if (strat->T[j].ecart <= h->ecart)
4803	h->ecart = d - h->GetpFDeg();
4804	else
4805	h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
4806
4807	d = h->GetpFDeg() + h->ecart;
4808	}
4809	else
4810	d = h->SetDegStuffReturnLDeg(strat->LDegLast);
4811	/- try to reduce the s-polynomial -/
4812	pass++;
4813	/*
4814	*test whether the polynomial should go to the lazyset L
4815	*-if the degree jumps
4816	*-if the number of pre-defined reductions jumps
4817	*/
4818	if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
4819	&& ((d >= reddeg) \|\| (pass > strat->LazyPass)))
4820	{
4821	h->SetLmCurrRing();
4822	if (strat->posInLDependsOnLength)
4823	h->SetLength(strat->length_pLength);
4824	at = strat->posInL(strat->L,strat->Ll,h,strat);
4825	if (at <= strat->Ll)
4826	{
4827	//int dummy=strat->sl;
4828	/* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
4829	//if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
4830	if (kFindDivisibleByInT(strat, h) < 0)
4831	return 1;
4832	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
4833	#ifdef KDEBUG
4834	if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
4835	#endif
4836	h->Clear();
4837	return -1;
4838	}
4839	}
4840	if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
4841	{
4842	reddeg = d+1;
4843	Print(".%d",d);mflush();
4844	}
4845	}
4846	}
4847	}
4848	#endif

Note: See TracBrowser for help on using the repository browser.

Download in other formats: