Context Navigation

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

fieker-DuValspielwiese

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

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

Download in other formats: