Context Navigation

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

fieker-DuValspielwiese

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

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

Download in other formats: