Context Navigation

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

spielwiese

Last change on this file since f6d848 was f6d848, checked in by Hans Schoenemann <hannes@…>, 3 years ago
redHomg/redLazy: buckets
Property mode set to `100644`
File size: 130.4 KB

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

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

Download in other formats: