Context Navigation

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

spielwiese

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

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

Download in other formats: