Context Navigation

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

spielwiese

Last change on this file since bf6051e was 164e05, checked in by Hans Schoenemann <hannes@…>, 18 months ago
simplify kFind*
Property mode set to `100644`
File size: 129.5 KB

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

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

Download in other formats: