Context Navigation

source: git/kernel/GBEngine/kstd2.cc @ 4c0fd3

spielwiese

Last change on this file since 4c0fd3 was 4c0fd3, checked in by Hans Schoenemann <hannes@…>, 3 years ago
fix: reduce for ring-cf != Z, Z/n
Property mode set to `100644`
File size: 130.1 KB

Line
1	/****************************************
2	* Computer Algebra System SINGULAR *
3	****************************************/
4	/*
5	* ABSTRACT - Kernel: alg. of Buchberger
6	*/
7
8	// #define PDEBUG 2
9
10	#include "kernel/mod2.h"
11
12	#define GCD_SBA 1
13
14	// define if no buckets should be used
15	// #define NO_BUCKETS
16
17	#ifdef HAVE_PLURAL
18	#define PLURAL_INTERNAL_DECLARATIONS 1
19	#endif
20
21	/***********************************************
22	* SBA stuff -- start
23	***********************************************/
24	#define DEBUGF50 0
25	#define DEBUGF51 0
26
27	#ifdef DEBUGF5
28	#undef DEBUGF5
29	//#define DEBUGF5 1
30	#endif
31
32	#define F5C 1
33	#if F5C
34	#define F5CTAILRED 1
35	#endif
36
37	#define SBA_INTERRED_START 0
38	#define SBA_TAIL_RED 1
39	#define SBA_PRODUCT_CRITERION 0
40	#define SBA_PRINT_ZERO_REDUCTIONS 0
41	#define SBA_PRINT_REDUCTION_STEPS 0
42	#define SBA_PRINT_OPERATIONS 0
43	#define SBA_PRINT_SIZE_G 0
44	#define SBA_PRINT_SIZE_SYZ 0
45	#define SBA_PRINT_PRODUCT_CRITERION 0
46
47	// counts sba's reduction steps
48	#if SBA_PRINT_REDUCTION_STEPS
49	VAR long sba_reduction_steps;
50	VAR long sba_interreduction_steps;
51	#endif
52	#if SBA_PRINT_OPERATIONS
53	VAR long sba_operations;
54	VAR long sba_interreduction_operations;
55	#endif
56
57	/***********************************************
58	* SBA stuff -- done
59	***********************************************/
60
61	#include "kernel/GBEngine/kutil.h"
62	#include "misc/options.h"
63	#include "kernel/polys.h"
64	#include "kernel/ideals.h"
65	#include "kernel/GBEngine/kstd1.h"
66	#include "kernel/GBEngine/khstd.h"
67	#include "polys/kbuckets.h"
68	#include "polys/prCopy.h"
69	#include "polys/weight.h"
70	#include "misc/intvec.h"
71	#ifdef HAVE_PLURAL
72	#include "polys/nc/nc.h"
73	#endif
74	// #include "timer.h"
75
76	#ifdef HAVE_SHIFTBBA
77	#include "polys/shiftop.h"
78	#endif
79
80	VAR int (*test_PosInT)(const TSet T,const int tl,LObject &h);
81	VAR int (*test_PosInL)(const LSet set, const int length,
82	LObject* L,const kStrategy strat);
83
84	int kFindSameLMInT_Z(const kStrategy strat, const LObject* L, const int start)
85	{
86	unsigned long not_sev = ~L->sev;
87	int j = start;
88	int o = -1;
89
90	const TSet T=strat->T;
91	const unsigned long* sevT=strat->sevT;
92	number gcd, ogcd;
93	if (L->p!=NULL)
94	{
95	const ring r=currRing;
96	const poly p=L->p;
97	ogcd = pGetCoeff(p);
98
99	pAssume(~not_sev == p_GetShortExpVector(p, r));
100
101	loop
102	{
103	if (j > strat->tl) return o;
104	if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
105	{
106	gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
107	if (o == -1
108	\|\| n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf))
109	{
110	ogcd = gcd;
111	o = j;
112	}
113	}
114	j++;
115	}
116	}
117	else
118	{
119	const ring r=strat->tailRing;
120	const poly p=L->t_p;
121	ogcd = pGetCoeff(p);
122	loop
123	{
124	if (j > strat->tl) return o;
125	if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
126	{
127	gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
128	if (o == -1
129	\|\| n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf))
130	{
131	ogcd = gcd;
132	o = j;
133	}
134	}
135	j++;
136	}
137	}
138	}
139	// return -1 if T[0] does not divide the leading monomial
140	int kTestDivisibleByT0_Z(const kStrategy strat, const LObject* L)
141	{
142	if (strat->tl < 1)
143	return -1;
144
145	unsigned long not_sev = ~L->sev;
146	const unsigned long sevT0 = strat->sevT[0];
147	number rest, orest, mult;
148	if (L->p!=NULL)
149	{
150	const poly T0p = strat->T[0].p;
151	const ring r = currRing;
152	const poly p = L->p;
153	orest = pGetCoeff(p);
154
155	pAssume(~not_sev == p_GetShortExpVector(p, r));
156
157	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
158	if (p_LmShortDivisibleBy(T0p, sevT0, p, not_sev, r))
159	{
160	mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
161	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
162	{
163	return 0;
164	}
165	}
166	#else
167	if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
168	{
169	mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
170	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
171	{
172	return 0;
173	}
174	}
175	#endif
176	}
177	else
178	{
179	const poly T0p = strat->T[0].t_p;
180	const ring r = strat->tailRing;
181	const poly p = L->t_p;
182	orest = pGetCoeff(p);
183	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
184	if (p_LmShortDivisibleBy(T0p, sevT0,
185	p, not_sev, r))
186	{
187	mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
188	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
189	{
190	return 0;
191	}
192	}
193	#else
194	if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
195	{
196	mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
197	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
198	{
199	return 0;
200	}
201	}
202	#endif
203	}
204	return -1;
205	}
206
207	int kFindDivisibleByInT_Z(const kStrategy strat, const LObject* L, const int start)
208	{
209	unsigned long not_sev = ~L->sev;
210	int j = start;
211	int o = -1;
212
213	const TSet T=strat->T;
214	const unsigned long* sevT=strat->sevT;
215	number rest, orest, mult;
216	if (L->p!=NULL)
217	{
218	const ring r=currRing;
219	const poly p=L->p;
220	orest = pGetCoeff(p);
221
222	pAssume(~not_sev == p_GetShortExpVector(p, r));
223
224	loop
225	{
226	if (j > strat->tl) return o;
227	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
228	if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
229	{
230	mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].p), &rest, r->cf);
231	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
232	{
233	o = j;
234	orest = rest;
235	}
236	}
237	#else
238	if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].p, p, r))
239	{
240	mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].p), &rest, r->cf);
241	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
242	{
243	o = j;
244	orest = rest;
245	}
246	}
247	#endif
248	j++;
249	}
250	}
251	else
252	{
253	const ring r=strat->tailRing;
254	const poly p=L->t_p;
255	orest = pGetCoeff(p);
256	loop
257	{
258	if (j > strat->tl) return o;
259	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
260	if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
261	p, not_sev, r))
262	{
263	mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].t_p), &rest, r->cf);
264	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
265	{
266	o = j;
267	orest = rest;
268	}
269	}
270	#else
271	if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].t_p, p, r))
272	{
273	mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].t_p), &rest, r->cf);
274	if (!n_IsZero(mult, r) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
275	{
276	o = j;
277	orest = rest;
278	}
279	}
280	#endif
281	j++;
282	}
283	}
284	}
285
286	// return -1 if no divisor is found
287	// number of first divisor, otherwise
288	int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start)
289	{
290	unsigned long not_sev = ~L->sev;
291	int j = start;
292
293	const TSet T=strat->T;
294	const unsigned long* sevT=strat->sevT;
295	const ring r=currRing;
296	const BOOLEAN is_Ring=rField_is_Ring(r);
297	if (L->p!=NULL)
298	{
299	const poly p=L->p;
300
301	pAssume(~not_sev == p_GetShortExpVector(p, r));
302
303	if(is_Ring)
304	{
305	loop
306	{
307	if (j > strat->tl) return -1;
308	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
309	if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
310	{
311	if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
312	return j;
313	}
314	#else
315	if (!(sevT[j] & not_sev) &&
316	p_LmDivisibleBy(T[j].p, p, r))
317	{
318	if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
319	return j;
320	}
321	#endif
322	j++;
323	}
324	}
325	else
326	{
327	loop
328	{
329	if (j > strat->tl) return -1;
330	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
331	if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
332	{
333	return j;
334	}
335	#else
336	if (!(sevT[j] & not_sev) &&
337	p_LmDivisibleBy(T[j].p, p, r))
338	{
339	return j;
340	}
341	#endif
342	j++;
343	}
344	}
345	}
346	else
347	{
348	const poly p=L->t_p;
349	const ring r=strat->tailRing;
350	if(is_Ring)
351	{
352	loop
353	{
354	if (j > strat->tl) return -1;
355	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
356	if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
357	p, not_sev, r))
358	{
359	if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
360	return j;
361	}
362	#else
363	if (!(sevT[j] & not_sev) &&
364	p_LmDivisibleBy(T[j].t_p, p, r))
365	{
366	if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
367	return j;
368	}
369	#endif
370	j++;
371	}
372	}
373	else
374	{
375	loop
376	{
377	if (j > strat->tl) return -1;
378	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
379	if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
380	p, not_sev, r))
381	{
382	return j;
383	}
384	#else
385	if (!(sevT[j] & not_sev) &&
386	p_LmDivisibleBy(T[j].t_p, p, r))
387	{
388	return j;
389	}
390	#endif
391	j++;
392	}
393	}
394	}
395	}
396
397	// same as above, only with set S
398	int kFindDivisibleByInS(const kStrategy strat, int* max_ind, LObject* L)
399	{
400	unsigned long not_sev = ~L->sev;
401	poly p = L->GetLmCurrRing();
402	int j = 0;
403
404	pAssume(~not_sev == p_GetShortExpVector(p, currRing));
405
406	BOOLEAN is_Ring=rField_is_Ring(currRing);
407	#if 1
408	int ende;
409	if (is_Ring
410	\|\| (strat->ak>0)
411	\|\| currRing->pLexOrder)
412	ende=strat->sl;
413	else
414	{
415	ende=posInS(strat,*max_ind,p,0)+1;
416	if (ende>(max_ind)) ende=(max_ind);
417	}
418	#else
419	int ende=strat->sl;
420	#endif
421	if(is_Ring)
422	{
423	loop
424	{
425	if (j > ende) return -1;
426	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
427	if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
428	p, not_sev, currRing))
429	{
430	if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
431	return j;
432	}
433	#else
434	if ( !(strat->sevS[j] & not_sev) &&
435	p_LmDivisibleBy(strat->S[j], p, currRing))
436	{
437	if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
438	return j;
439	}
440	#endif
441	j++;
442	}
443	}
444	else
445	{
446	loop
447	{
448	if (j > ende) return -1;
449	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
450	if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
451	p, not_sev, currRing))
452	{
453	return j;
454	}
455	#else
456	if ( !(strat->sevS[j] & not_sev) &&
457	p_LmDivisibleBy(strat->S[j], p, currRing))
458	{
459	return j;
460	}
461	#endif
462	j++;
463	}
464	}
465	}
466
467	int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L)
468	{
469	unsigned long not_sev = ~L->sev;
470	poly p = L->GetLmCurrRing();
471	int j = start;
472
473	pAssume(~not_sev == p_GetShortExpVector(p, currRing));
474	#if 1
475	int ende=max_ind;
476	#else
477	int ende=strat->sl;
478	#endif
479	if(rField_is_Ring(currRing))
480	{
481	loop
482	{
483	if (j > ende) return -1;
484	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
485	if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
486	p, not_sev, currRing))
487	{
488	if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
489	return j;
490	}
491	#else
492	if ( !(strat->sevS[j] & not_sev) &&
493	p_LmDivisibleBy(strat->S[j], p, currRing))
494	{
495	if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
496	return j;
497	}
498	#endif
499	j++;
500	}
501	}
502	else
503	{
504	loop
505	{
506	if (j > ende) return -1;
507	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
508	if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
509	p, not_sev, currRing))
510	{
511	return j;
512	}
513	#else
514	if ( !(strat->sevS[j] & not_sev) &&
515	p_LmDivisibleBy(strat->S[j], p, currRing))
516	{
517	return j;
518	}
519	#endif
520	j++;
521	}
522	}
523	}
524
525	#ifdef HAVE_RINGS
526	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, 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, 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, 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, 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,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	&& ((!TEST_OPT_IDELIM) \|\| (p_Deg(strat->P.p,currRing) > 0)))
2596	{
2597	enterT(strat->P, strat);
2598	if (rField_is_Ring(currRing))
2599	superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2600	else
2601	enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2602	// posInS only depends on the leading term
2603	strat->enterS(strat->P, pos, strat, strat->tl);
2604	#if 0
2605	int pl=pLength(strat->P.p);
2606	if (pl==1)
2607	{
2608	//if (TEST_OPT_PROT)
2609	//PrintS("<1>");
2610	}
2611	else if (pl==2)
2612	{
2613	//if (TEST_OPT_PROT)
2614	//PrintS("<2>");
2615	}
2616	#endif
2617	}
2618	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2619	// Print("[%d]",hilbeledeg);
2620	kDeleteLcm(&strat->P);
2621	if (strat->s_poly!=NULL)
2622	{
2623	// the only valid entries are: strat->P.p,
2624	// strat->tailRing (read-only, keep it)
2625	// (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
2626	if (strat->s_poly(strat))
2627	{
2628	// we are called AFTER enterS, i.e. if we change P
2629	// we have to add it also to S/T
2630	// and add pairs
2631	int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2632	enterT(strat->P, strat);
2633	if (rField_is_Ring(currRing))
2634	superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2635	else
2636	enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2637	strat->enterS(strat->P, pos, strat, strat->tl);
2638	}
2639	}
2640	}
2641	else if (strat->P.p1 == NULL && strat->minim > 0)
2642	{
2643	p_Delete(&strat->P.p2, currRing, strat->tailRing);
2644	}
2645
2646	#ifdef KDEBUG
2647	memset(&(strat->P), 0, sizeof(strat->P));
2648	#endif /* KDEBUG */
2649	kTest_TS(strat);
2650	}
2651	#ifdef KDEBUG
2652	if (TEST_OPT_DEBUG) messageSets(strat);
2653	#endif /* KDEBUG */
2654
2655	if (TEST_OPT_SB_1)
2656	{
2657	if(!rField_is_Ring(currRing))
2658	{
2659	int k=1;
2660	int j;
2661	while(k<=strat->sl)
2662	{
2663	j=0;
2664	loop
2665	{
2666	if (j>=k) break;
2667	clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2668	j++;
2669	}
2670	k++;
2671	}
2672	}
2673	}
2674	/* complete reduction of the standard basis--------- */
2675	if (TEST_OPT_REDSB)
2676	{
2677	completeReduce(strat);
2678	if (strat->completeReduce_retry)
2679	{
2680	// completeReduce needed larger exponents, retry
2681	// to reduce with S (instead of T)
2682	// and in currRing (instead of strat->tailRing)
2683	#ifdef HAVE_TAIL_RING
2684	if(currRing->bitmask>strat->tailRing->bitmask)
2685	{
2686	strat->completeReduce_retry=FALSE;
2687	cleanT(strat);strat->tailRing=currRing;
2688	int i;
2689	for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2690	completeReduce(strat);
2691	}
2692	if (strat->completeReduce_retry)
2693	#endif
2694	Werror("exponent bound is %ld",currRing->bitmask);
2695	}
2696	}
2697	else if (TEST_OPT_PROT) PrintLn();
2698	/* release temp data-------------------------------- */
2699	exitBuchMora(strat);
2700	/* postprocessing for GB over ZZ --------------------*/
2701	if (!errorreported)
2702	{
2703	if(rField_is_Z(currRing))
2704	{
2705	for(int i = 0;i<=strat->sl;i++)
2706	{
2707	if(!nGreaterZero(pGetCoeff(strat->S[i])))
2708	{
2709	strat->S[i] = pNeg(strat->S[i]);
2710	}
2711	}
2712	finalReduceByMon(strat);
2713	for(int i = 0;i<IDELEMS(strat->Shdl);i++)
2714	{
2715	if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
2716	{
2717	strat->S[i] = pNeg(strat->Shdl->m[i]);
2718	}
2719	}
2720	}
2721	//else if (rField_is_Ring(currRing))
2722	// finalReduceByMon(strat);
2723	}
2724	// if (TEST_OPT_WEIGHTM)
2725	// {
2726	// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2727	// if (ecartWeights)
2728	// {
2729	// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2730	// ecartWeights=NULL;
2731	// }
2732	// }
2733	if ((TEST_OPT_PROT) \|\| (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2734	SI_RESTORE_OPT1(save);
2735	/* postprocessing for GB over Q-rings ------------------*/
2736	if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
2737
2738	idTest(strat->Shdl);
2739
2740	return (strat->Shdl);
2741	}
2742
2743	ideal sba (ideal F0, ideal Q,intvec w,intvec hilb,kStrategy strat)
2744	{
2745	// ring order stuff:
2746	// in sba we have (until now) two possibilities:
2747	// 1. an incremental computation w.r.t. (C,monomial order)
2748	// 2. a (possibly non-incremental) computation w.r.t. the
2749	// induced Schreyer order.
2750	// The corresponding orders are computed in sbaRing(), depending
2751	// on the flag strat->sbaOrder
2752	#if SBA_PRINT_ZERO_REDUCTIONS
2753	long zeroreductions = 0;
2754	#endif
2755	#if SBA_PRINT_PRODUCT_CRITERION
2756	long product_criterion = 0;
2757	#endif
2758	#if SBA_PRINT_SIZE_G
2759	int size_g = 0;
2760	int size_g_non_red = 0;
2761	#endif
2762	#if SBA_PRINT_SIZE_SYZ
2763	long size_syz = 0;
2764	#endif
2765	// global variable
2766	#if SBA_PRINT_REDUCTION_STEPS
2767	sba_reduction_steps = 0;
2768	sba_interreduction_steps = 0;
2769	#endif
2770	#if SBA_PRINT_OPERATIONS
2771	sba_operations = 0;
2772	sba_interreduction_operations = 0;
2773	#endif
2774
2775	ideal F1 = F0;
2776	ring sRing, currRingOld;
2777	currRingOld = currRing;
2778	if (strat->sbaOrder == 1 \|\| strat->sbaOrder == 3)
2779	{
2780	sRing = sbaRing(strat);
2781	if (sRing!=currRingOld)
2782	{
2783	rChangeCurrRing (sRing);
2784	F1 = idrMoveR (F0, currRingOld, currRing);
2785	}
2786	}
2787	ideal F;
2788	// sort ideal F
2789	//Put the SigDrop element on the correct position (think of sbaEnterS)
2790	//We also sort them
2791	if(rField_is_Ring(currRing) && strat->sigdrop)
2792	{
2793	#if 1
2794	F = idInit(IDELEMS(F1),F1->rank);
2795	for (int i=0; i<IDELEMS(F1);++i)
2796	F->m[i] = F1->m[i];
2797	if(strat->sbaEnterS >= 0)
2798	{
2799	poly dummy;
2800	dummy = pCopy(F->m[0]); //the sigdrop element
2801	for(int i = 0;i<strat->sbaEnterS;i++)
2802	F->m[i] = F->m[i+1];
2803	F->m[strat->sbaEnterS] = dummy;
2804	}
2805	#else
2806	F = idInit(1,F1->rank);
2807	//printf("\nBefore the initial block sorting:\n");idPrint(F1);
2808	F->m[0] = F1->m[0];
2809	int pos;
2810	if(strat->sbaEnterS >= 0)
2811	{
2812	for(int i=1;i<=strat->sbaEnterS;i++)
2813	{
2814	pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
2815	idInsertPolyOnPos(F,F1->m[i],pos);
2816	}
2817	for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
2818	{
2819	pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
2820	idInsertPolyOnPos(F,F1->m[i],pos);
2821	}
2822	poly dummy;
2823	dummy = pCopy(F->m[0]); //the sigdrop element
2824	for(int i = 0;i<strat->sbaEnterS;i++)
2825	F->m[i] = F->m[i+1];
2826	F->m[strat->sbaEnterS] = dummy;
2827	}
2828	else
2829	{
2830	for(int i=1;i<IDELEMS(F1);i++)
2831	{
2832	pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
2833	idInsertPolyOnPos(F,F1->m[i],pos);
2834	}
2835	}
2836	#endif
2837	//printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
2838	}
2839	else
2840	{
2841	F = idInit(IDELEMS(F1),F1->rank);
2842	intvec *sort = idSort(F1);
2843	for (int i=0; i<sort->length();++i)
2844	F->m[i] = F1->m[(*sort)[i]-1];
2845	if(rField_is_Ring(currRing))
2846	{
2847	// put the monomials after the sbaEnterS polynomials
2848	//printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
2849	int nrmon = 0;
2850	for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
2851	{
2852	//pWrite(F->m[i]);
2853	if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
2854	{
2855	poly mon = F->m[i];
2856	for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
2857	{
2858	F->m[j] = F->m[j-1];
2859	}
2860	F->m[j] = mon;
2861	nrmon++;
2862	}
2863	//idPrint(F);
2864	}
2865	}
2866	}
2867	//printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
2868	if(rField_is_Ring(currRing))
2869	strat->sigdrop = FALSE;
2870	strat->nrsyzcrit = 0;
2871	strat->nrrewcrit = 0;
2872	#if SBA_INTERRED_START
2873	F = kInterRed(F,NULL);
2874	#endif
2875	#if F5DEBUG
2876	printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
2877	rWrite (currRing);
2878	printf("ordSgn = %d\n",currRing->OrdSgn);
2879	printf("\n");
2880	#endif
2881	int srmax,lrmax, red_result = 1;
2882	int olddeg,reduc;
2883	int hilbeledeg=1,hilbcount=0,minimcnt=0;
2884	LObject L;
2885	BOOLEAN withT = TRUE;
2886	strat->max_lower_index = 0;
2887	//initBuchMoraCrit(strat); /set Gebauer, honey, sugarCrit/
2888	initSbaCrit(strat); /set Gebauer, honey, sugarCrit/
2889	initSbaPos(strat);
2890	initHilbCrit(F,Q,&hilb,strat);
2891	initSba(F,strat);
2892	/set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair/
2893	/Shdl=/initSbaBuchMora(F, Q,strat);
2894	idTest(strat->Shdl);
2895	if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2896	srmax = strat->sl;
2897	reduc = olddeg = lrmax = 0;
2898	#ifndef NO_BUCKETS
2899	if (!TEST_OPT_NOT_BUCKETS)
2900	strat->use_buckets = 1;
2901	#endif
2902
2903	// redtailBBa against T for inhomogenous input
2904	// if (!TEST_OPT_OLDSTD)
2905	// withT = ! strat->homog;
2906
2907	// strat->posInT = posInT_pLength;
2908	kTest_TS(strat);
2909
2910	#ifdef HAVE_TAIL_RING
2911	if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2912	kStratInitChangeTailRing(strat);
2913	#endif
2914	if (BVERBOSE(23))
2915	{
2916	if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2917	if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2918	kDebugPrint(strat);
2919	}
2920	// We add the elements directly in S from the previous loop
2921	if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
2922	{
2923	for(int i = 0;i<strat->sbaEnterS;i++)
2924	{
2925	//Update: now the element is at the corect place
2926	//i+1 because on the 0 position is the sigdrop element
2927	enterT(strat->L[strat->Ll-(i)],strat);
2928	strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
2929	}
2930	strat->Ll = strat->Ll - strat->sbaEnterS;
2931	strat->sbaEnterS = -1;
2932	}
2933	kTest_TS(strat);
2934	#ifdef KDEBUG
2935	//kDebugPrint(strat);
2936	#endif
2937	/* compute------------------------------------------------------- */
2938	while (strat->Ll >= 0)
2939	{
2940	if (strat->Ll > lrmax) lrmax =strat->Ll;/stat./
2941	#ifdef KDEBUG
2942	if (TEST_OPT_DEBUG) messageSets(strat);
2943	#endif
2944	if (strat->Ll== 0) strat->interpt=TRUE;
2945	/*
2946	if (TEST_OPT_DEGBOUND
2947	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2948	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2949	{
2950
2951	//stops computation if
2952	// 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2953	//a predefined number Kstd1_deg
2954	while ((strat->Ll >= 0)
2955	&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2956	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2957	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2958	)
2959	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2960	if (strat->Ll<0) break;
2961	else strat->noClearS=TRUE;
2962	}
2963	*/
2964	if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
2965	{
2966	strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
2967	#if F5C
2968	// 1. interreduction of the current standard basis
2969	// 2. generation of new principal syzygy rules for syzCriterion
2970	f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
2971	lrmax, reduc, Q, w, hilb );
2972	#endif
2973	// initialize new syzygy rules for the next iteration step
2974	initSyzRules(strat);
2975	}
2976	/*********************************************************************
2977	* interrreduction step is done, we can go on with the next iteration
2978	* step of the signature-based algorithm
2979	********************************************************************/
2980	/* picks the last element from the lazyset L */
2981	strat->P = strat->L[strat->Ll];
2982	strat->Ll--;
2983
2984	if(rField_is_Ring(currRing))
2985	strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
2986	/* reduction of the element chosen from L */
2987	if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1))
2988	{
2989	//#if 1
2990	#ifdef DEBUGF5
2991	PrintS("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
2992	PrintS("-------------------------------------------------\n");
2993	pWrite(strat->P.sig);
2994	pWrite(pHead(strat->P.p));
2995	pWrite(pHead(strat->P.p1));
2996	pWrite(pHead(strat->P.p2));
2997	PrintS("-------------------------------------------------\n");
2998	#endif
2999	if (pNext(strat->P.p) == strat->tail)
3000	{
3001	// deletes the short spoly
3002	/*
3003	if (rField_is_Ring(currRing))
3004	pLmDelete(strat->P.p);
3005	else
3006	pLmFree(strat->P.p);
3007	*/
3008	// TODO: needs some masking
3009	// TODO: masking needs to vanish once the signature
3010	// sutff is completely implemented
3011	strat->P.p = NULL;
3012	poly m1 = NULL, m2 = NULL;
3013
3014	// check that spoly creation is ok
3015	while (strat->tailRing != currRing &&
3016	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3017	{
3018	assume(m1 == NULL && m2 == NULL);
3019	// if not, change to a ring where exponents are at least
3020	// large enough
3021	if (!kStratChangeTailRing(strat))
3022	{
3023	WerrorS("OVERFLOW...");
3024	break;
3025	}
3026	}
3027	// create the real one
3028	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3029	strat->tailRing, m1, m2, strat->R);
3030
3031	}
3032	else if (strat->P.p1 == NULL)
3033	{
3034	if (strat->minim > 0)
3035	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3036	// for input polys, prepare reduction
3037	if(!rField_is_Ring(currRing))
3038	strat->P.PrepareRed(strat->use_buckets);
3039	}
3040	if (strat->P.p == NULL && strat->P.t_p == NULL)
3041	{
3042	red_result = 0;
3043	}
3044	else
3045	{
3046	//#if 1
3047	#ifdef DEBUGF5
3048	PrintS("Poly before red: ");
3049	pWrite(pHead(strat->P.p));
3050	pWrite(strat->P.sig);
3051	#endif
3052	#if SBA_PRODUCT_CRITERION
3053	if (strat->P.prod_crit)
3054	{
3055	#if SBA_PRINT_PRODUCT_CRITERION
3056	product_criterion++;
3057	#endif
3058	int pos = posInSyz(strat, strat->P.sig);
3059	enterSyz(strat->P, strat, pos);
3060	kDeleteLcm(&strat->P);
3061	red_result = 2;
3062	}
3063	else
3064	{
3065	red_result = strat->red(&strat->P,strat);
3066	}
3067	#else
3068	red_result = strat->red(&strat->P,strat);
3069	#endif
3070	}
3071	}
3072	else
3073	{
3074	/*
3075	if (strat->P.lcm != NULL)
3076	pLmFree(strat->P.lcm);
3077	*/
3078	red_result = 2;
3079	}
3080	if(rField_is_Ring(currRing))
3081	{
3082	if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
3083	{
3084	strat->P.p = pNeg(strat->P.p);
3085	strat->P.sig = pNeg(strat->P.sig);
3086	}
3087	strat->P.pLength = pLength(strat->P.p);
3088	if(strat->P.sig != NULL)
3089	strat->P.sevSig = pGetShortExpVector(strat->P.sig);
3090	if(strat->P.p != NULL)
3091	strat->P.sev = pGetShortExpVector(strat->P.p);
3092	}
3093	//sigdrop case
3094	if(rField_is_Ring(currRing) && strat->sigdrop)
3095	{
3096	//First reduce it as much as one can
3097	red_result = redRing(&strat->P,strat);
3098	if(red_result == 0)
3099	{
3100	strat->sigdrop = FALSE;
3101	pDelete(&strat->P.sig);
3102	strat->P.sig = NULL;
3103	}
3104	else
3105	{
3106	strat->enterS(strat->P, 0, strat, strat->tl);
3107	if (TEST_OPT_PROT)
3108	PrintS("-");
3109	break;
3110	}
3111	}
3112	if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
3113	{
3114	strat->sigdrop = TRUE;
3115	break;
3116	}
3117
3118	if (errorreported) break;
3119
3120	//#if 1
3121	#ifdef DEBUGF5
3122	if (red_result != 0)
3123	{
3124	PrintS("Poly after red: ");
3125	pWrite(pHead(strat->P.p));
3126	pWrite(strat->P.GetLmCurrRing());
3127	pWrite(strat->P.sig);
3128	printf("%d\n",red_result);
3129	}
3130	#endif
3131	if (TEST_OPT_PROT)
3132	{
3133	if(strat->P.p != NULL)
3134	message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3135	&olddeg,&reduc,strat, red_result);
3136	else
3137	message((strat->honey ? strat->P.ecart : 0),
3138	&olddeg,&reduc,strat, red_result);
3139	}
3140
3141	if (strat->overflow)
3142	{
3143	if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
3144	}
3145	// reduction to non-zero new poly
3146	if (red_result == 1)
3147	{
3148	// get the polynomial (canonicalize bucket, make sure P.p is set)
3149	strat->P.GetP(strat->lmBin);
3150
3151	// sig-safe computations may lead to wrong FDeg computation, thus we need
3152	// to recompute it to make sure everything is alright
3153	(strat->P).FDeg = (strat->P).pFDeg();
3154	// in the homogeneous case FDeg >= pFDeg (sugar/honey)
3155	// but now, for entering S, T, we reset it
3156	// in the inhomogeneous case: FDeg == pFDeg
3157	if (strat->homog) strat->initEcart(&(strat->P));
3158
3159	/* statistic */
3160	if (TEST_OPT_PROT) PrintS("s");
3161
3162	//int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3163	// in F5E we know that the last reduced element is already the
3164	// the one with highest signature
3165	int pos = strat->sl+1;
3166
3167	// reduce the tail and normalize poly
3168	// in the ring case we cannot expect LC(f) = 1,
3169	// therefore we call pCleardenom instead of pNorm
3170	#ifdef HAVE_RINGS
3171	poly beforetailred;
3172	if(rField_is_Ring(currRing))
3173	beforetailred = pCopy(strat->P.sig);
3174	#endif
3175	#if SBA_TAIL_RED
3176	if(rField_is_Ring(currRing))
3177	{
3178	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
3179	strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3180	}
3181	else
3182	{
3183	if (strat->sbaOrder != 2)
3184	{
3185	if (TEST_OPT_INTSTRATEGY)
3186	{
3187	strat->P.pCleardenom();
3188	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
3189	{
3190	strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3191	strat->P.pCleardenom();
3192	}
3193	}
3194	else
3195	{
3196	strat->P.pNorm();
3197	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
3198	strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
3199	}
3200	}
3201	}
3202	// It may happen that we have lost the sig in redtailsba
3203	// It cannot reduce to 0 since here we are doing just tail reduction.
3204	// Best case scenerio: remains the leading term
3205	if(rField_is_Ring(currRing) && strat->sigdrop)
3206	{
3207	strat->enterS(strat->P, 0, strat, strat->tl);
3208	break;
3209	}
3210	#endif
3211	if(rField_is_Ring(currRing))
3212	{
3213	if(strat->P.sig == NULL \|\| pLtCmp(beforetailred,strat->P.sig) == 1)
3214	{
3215	strat->sigdrop = TRUE;
3216	//Reduce it as much as you can
3217	red_result = redRing(&strat->P,strat);
3218	if(red_result == 0)
3219	{
3220	//It reduced to 0, cancel the sigdrop
3221	strat->sigdrop = FALSE;
3222	p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
3223	}
3224	else
3225	{
3226	strat->enterS(strat->P, 0, strat, strat->tl);
3227	break;
3228	}
3229	}
3230	p_Delete(&beforetailred,currRing);
3231	// strat->P.p = NULL may appear if we had a sigdrop above and reduced to 0 via redRing
3232	if(strat->P.p == NULL)
3233	goto case_when_red_result_changed;
3234	}
3235	// remove sigsafe label since it is no longer valid for the next element to
3236	// be reduced
3237	if (strat->sbaOrder == 1)
3238	{
3239	for (int jj = 0; jj<strat->tl+1; jj++)
3240	{
3241	if (pGetComp(strat->T[jj].sig) == strat->currIdx)
3242	{
3243	strat->T[jj].is_sigsafe = FALSE;
3244	}
3245	}
3246	}
3247	else
3248	{
3249	for (int jj = 0; jj<strat->tl+1; jj++)
3250	{
3251	strat->T[jj].is_sigsafe = FALSE;
3252	}
3253	}
3254	#ifdef KDEBUG
3255	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3256	#endif /* KDEBUG */
3257
3258	// min_std stuff
3259	if ((strat->P.p1==NULL) && (strat->minim>0))
3260	{
3261	if (strat->minim==1)
3262	{
3263	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3264	p_Delete(&strat->P.p2, currRing, strat->tailRing);
3265	}
3266	else
3267	{
3268	strat->M->m[minimcnt]=strat->P.p2;
3269	strat->P.p2=NULL;
3270	}
3271	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3272	pNext(strat->M->m[minimcnt])
3273	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3274	strat->tailRing, currRing,
3275	currRing->PolyBin);
3276	minimcnt++;
3277	}
3278
3279	// enter into S, L, and T
3280	//if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
3281	enterT(strat->P, strat);
3282	strat->T[strat->tl].is_sigsafe = FALSE;
3283	/*
3284	printf("hier\n");
3285	pWrite(strat->P.GetLmCurrRing());
3286	pWrite(strat->P.sig);
3287	*/
3288	if (rField_is_Ring(currRing))
3289	superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3290	else
3291	enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
3292	if(rField_is_Ring(currRing) && strat->sigdrop)
3293	break;
3294	if(rField_is_Ring(currRing))
3295	strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
3296	strat->enterS(strat->P, pos, strat, strat->tl);
3297	if(strat->sbaOrder != 1)
3298	{
3299	BOOLEAN overwrite = FALSE;
3300	for (int tk=0; tk<strat->sl+1; tk++)
3301	{
3302	if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
3303	{
3304	//printf("TK %d / %d\n",tk,strat->sl);
3305	overwrite = FALSE;
3306	break;
3307	}
3308	}
3309	//printf("OVERWRITE %d\n",overwrite);
3310	if (overwrite)
3311	{
3312	int cmp = pGetComp(strat->P.sig);
3313	int* vv = (int)omAlloc((currRing->N+1)sizeof(int));
3314	p_GetExpV (strat->P.p,vv,currRing);
3315	p_SetExpV (strat->P.sig, vv,currRing);
3316	p_SetComp (strat->P.sig,cmp,currRing);
3317
3318	strat->P.sevSig = pGetShortExpVector (strat->P.sig);
3319	int i;
3320	LObject Q;
3321	for(int ps=0;ps<strat->sl+1;ps++)
3322	{
3323
3324	strat->newt = TRUE;
3325	if (strat->syzl == strat->syzmax)
3326	{
3327	pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
3328	strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
3329	(strat->syzmax)*sizeof(unsigned long),
3330	((strat->syzmax)+setmaxTinc)
3331	*sizeof(unsigned long));
3332	strat->syzmax += setmaxTinc;
3333	}
3334	Q.sig = pCopy(strat->P.sig);
3335	// add LM(F->m[i]) to the signature to get a Schreyer order
3336	// without changing the underlying polynomial ring at all
3337	if (strat->sbaOrder == 0)
3338	p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
3339	// since p_Add_q() destroys all input
3340	// data we need to recreate help
3341	// each time
3342	// ----------------------------------------------------------
3343	// in the Schreyer order we always know that the multiplied
3344	// module monomial strat->P.sig gives the leading monomial of
3345	// the corresponding principal syzygy
3346	// => we do not need to compute the "real" syzygy completely
3347	poly help = p_Copy(strat->sig[ps],currRing);
3348	p_ExpVectorAdd (help,strat->P.p,currRing);
3349	Q.sig = p_Add_q(Q.sig,help,currRing);
3350	//printf("%d. SYZ ",i+1);
3351	//pWrite(strat->syz[i]);
3352	Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
3353	i = posInSyz(strat, Q.sig);
3354	enterSyz(Q, strat, i);
3355	}
3356	}
3357	}
3358	// deg - idx - lp/rp
3359	// => we need to add syzygies with indices > pGetComp(strat->P.sig)
3360	if(strat->sbaOrder == 0 \|\| strat->sbaOrder == 3)
3361	{
3362	int cmp = pGetComp(strat->P.sig);
3363	unsigned max_cmp = IDELEMS(F);
3364	int* vv = (int)omAlloc((currRing->N+1)sizeof(int));
3365	p_GetExpV (strat->P.p,vv,currRing);
3366	LObject Q;
3367	int pos;
3368	int idx = __p_GetComp(strat->P.sig,currRing);
3369	//printf("++ -- adding syzygies -- ++\n");
3370	// if new element is the first one in this index
3371	if (strat->currIdx < idx)
3372	{
3373	for (int i=0; i<strat->sl; ++i)
3374	{
3375	Q.sig = p_Copy(strat->P.sig,currRing);
3376	p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
3377	poly help = p_Copy(strat->sig[i],currRing);
3378	p_ExpVectorAdd(help,strat->P.p,currRing);
3379	Q.sig = p_Add_q(Q.sig,help,currRing);
3380	//pWrite(Q.sig);
3381	pos = posInSyz(strat, Q.sig);
3382	enterSyz(Q, strat, pos);
3383	}
3384	strat->currIdx = idx;
3385	}
3386	else
3387	{
3388	// if the element is not the first one in the given index we build all
3389	// possible syzygies with elements of higher index
3390	for (unsigned i=cmp+1; i<=max_cmp; ++i)
3391	{
3392	pos = -1;
3393	for (int j=0; j<strat->sl; ++j)
3394	{
3395	if (__p_GetComp(strat->sig[j],currRing) == i)
3396	{
3397	pos = j;
3398	break;
3399	}
3400	}
3401	if (pos != -1)
3402	{
3403	Q.sig = p_One(currRing);
3404	p_SetExpV(Q.sig, vv, currRing);
3405	// F->m[i-1] corresponds to index i
3406	p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
3407	p_SetComp(Q.sig, i, currRing);
3408	poly help = p_Copy(strat->P.sig,currRing);
3409	p_ExpVectorAdd(help,strat->S[pos],currRing);
3410	Q.sig = p_Add_q(Q.sig,help,currRing);
3411	if (strat->sbaOrder == 0)
3412	{
3413	if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn)
3414	{
3415	pos = posInSyz(strat, Q.sig);
3416	enterSyz(Q, strat, pos);
3417	}
3418	}
3419	else
3420	{
3421	pos = posInSyz(strat, Q.sig);
3422	enterSyz(Q, strat, pos);
3423	}
3424	}
3425	}
3426	//printf("++ -- done adding syzygies -- ++\n");
3427	}
3428	}
3429	//#if 1
3430	#if DEBUGF50
3431	printf("---------------------------\n");
3432	Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
3433	PrintS("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
3434	PrintS("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
3435	#endif
3436	/*
3437	if (newrules)
3438	{
3439	newrules = FALSE;
3440	}
3441	*/
3442	#if 0
3443	int pl=pLength(strat->P.p);
3444	if (pl==1)
3445	{
3446	//if (TEST_OPT_PROT)
3447	//PrintS("<1>");
3448	}
3449	else if (pl==2)
3450	{
3451	//if (TEST_OPT_PROT)
3452	//PrintS("<2>");
3453	}
3454	#endif
3455	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3456	// Print("[%d]",hilbeledeg);
3457	kDeleteLcm(&strat->P);
3458	if (strat->sl>srmax) srmax = strat->sl;
3459	}
3460	else
3461	{
3462	case_when_red_result_changed:
3463	// adds signature of the zero reduction to
3464	// strat->syz. This is the leading term of
3465	// syzygy and can be used in syzCriterion()
3466	// the signature is added if and only if the
3467	// pair was not detected by the rewritten criterion in strat->red = redSig
3468	if (red_result!=2)
3469	{
3470	#if SBA_PRINT_ZERO_REDUCTIONS
3471	zeroreductions++;
3472	#endif
3473	if(rField_is_Ring(currRing) && strat->P.p == NULL && strat->P.sig == NULL)
3474	{
3475	//Catch the case when p = 0, sig = 0
3476	}
3477	else
3478	{
3479	int pos = posInSyz(strat, strat->P.sig);
3480	enterSyz(strat->P, strat, pos);
3481	//#if 1
3482	#ifdef DEBUGF5
3483	Print("ADDING STUFF TO SYZ : ");
3484	//pWrite(strat->P.p);
3485	pWrite(strat->P.sig);
3486	#endif
3487	}
3488	}
3489	if (strat->P.p1 == NULL && strat->minim > 0)
3490	{
3491	p_Delete(&strat->P.p2, currRing, strat->tailRing);
3492	}
3493	}
3494
3495	#ifdef KDEBUG
3496	memset(&(strat->P), 0, sizeof(strat->P));
3497	#endif /* KDEBUG */
3498	kTest_TS(strat);
3499	}
3500	#if 0
3501	if(strat->sigdrop)
3502	printf("\nSigDrop!\n");
3503	else
3504	printf("\nEnded with no SigDrop\n");
3505	#endif
3506	// Clean strat->P for the next sba call
3507	if(rField_is_Ring(currRing) && strat->sigdrop)
3508	{
3509	//This is used to know how many elements can we directly add to S in the next run
3510	if(strat->P.sig != NULL)
3511	strat->sbaEnterS = pGetComp(strat->P.sig)-1;
3512	//else we already set it at the beggining of the loop
3513	#ifdef KDEBUG
3514	memset(&(strat->P), 0, sizeof(strat->P));
3515	#endif /* KDEBUG */
3516	}
3517	#ifdef KDEBUG
3518	if (TEST_OPT_DEBUG) messageSets(strat);
3519	#endif /* KDEBUG */
3520
3521	if (TEST_OPT_SB_1)
3522	{
3523	if(!rField_is_Ring(currRing))
3524	{
3525	int k=1;
3526	int j;
3527	while(k<=strat->sl)
3528	{
3529	j=0;
3530	loop
3531	{
3532	if (j>=k) break;
3533	clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3534	j++;
3535	}
3536	k++;
3537	}
3538	}
3539	}
3540	/* complete reduction of the standard basis--------- */
3541	if (TEST_OPT_REDSB)
3542	{
3543	completeReduce(strat);
3544	if (strat->completeReduce_retry)
3545	{
3546	// completeReduce needed larger exponents, retry
3547	// to reduce with S (instead of T)
3548	// and in currRing (instead of strat->tailRing)
3549	#ifdef HAVE_TAIL_RING
3550	if(currRing->bitmask>strat->tailRing->bitmask)
3551	{
3552	strat->completeReduce_retry=FALSE;
3553	cleanT(strat);strat->tailRing=currRing;
3554	int i;
3555	for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3556	completeReduce(strat);
3557	}
3558	if (strat->completeReduce_retry)
3559	#endif
3560	Werror("exponent bound is %ld",currRing->bitmask);
3561	}
3562	}
3563	else if (TEST_OPT_PROT) PrintLn();
3564
3565	#if SBA_PRINT_SIZE_SYZ
3566	// that is correct, syzl is counting one too far
3567	size_syz = strat->syzl;
3568	#endif
3569	// if (TEST_OPT_WEIGHTM)
3570	// {
3571	// pRestoreDegProcs(pFDegOld, pLDegOld);
3572	// if (ecartWeights)
3573	// {
3574	// omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
3575	// ecartWeights=NULL;
3576	// }
3577	// }
3578	if (TEST_OPT_PROT) messageStatSBA(hilbcount,strat);
3579	if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3580	#if SBA_PRINT_SIZE_G
3581	size_g_non_red = IDELEMS(strat->Shdl);
3582	#endif
3583	if(!rField_is_Ring(currRing))
3584	exitSba(strat);
3585	// I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
3586	#ifdef HAVE_RINGS
3587	int k;
3588	if(rField_is_Ring(currRing))
3589	{
3590	//for(k = strat->sl;k>=0;k--)
3591	// {printf("\nS[%i] = %p\n",k,strat->Shdl->m[k]);pWrite(strat->Shdl->m[k]);}
3592	k = strat->Ll;
3593	#if 1
3594	// 1 - adds just the unused ones, 0 - adds everthing
3595	for(;k>=0 && (strat->L[k].p1 != NULL \|\| strat->L[k].p2 != NULL);k--)
3596	{
3597	//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);
3598	deleteInL(strat->L,&strat->Ll,k,strat);
3599	}
3600	#endif
3601	//for(int kk = strat->sl;kk>=0;kk--)
3602	// {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
3603	//idPrint(strat->Shdl);
3604	//printf("\nk = %i\n",k);
3605	for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
3606	{
3607	//printf("\nAdded k = %i\n",k);
3608	strat->enterS(strat->L[k], strat->sl+1, strat, strat->tl);
3609	//printf("\nThis elements was added from L on pos %i\n",strat->sl);pWrite(strat->S[strat->sl]);pWrite(strat->sig[strat->sl]);
3610	}
3611	}
3612	// 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
3613	#if 0
3614	if(strat->sigdrop && rField_is_Ring(currRing))
3615	{
3616	for(k=strat->sl;k>=0;k--)
3617	{
3618	printf("\nsig[%i] = ",i);pWrite(strat->sig[k]);
3619	if(strat->sig[k] == NULL)
3620	strat->sig[k] = pCopy(strat->sig[k-1]);
3621	}
3622	}
3623	#endif
3624	#endif
3625	//Never do this - you will damage S
3626	//idSkipZeroes(strat->Shdl);
3627	//idPrint(strat->Shdl);
3628
3629	if ((strat->sbaOrder == 1 \|\| strat->sbaOrder == 3) && sRing!=currRingOld)
3630	{
3631	rChangeCurrRing (currRingOld);
3632	F0 = idrMoveR (F1, sRing, currRing);
3633	strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
3634	rChangeCurrRing (sRing);
3635	if(rField_is_Ring(currRing))
3636	exitSba(strat);
3637	rChangeCurrRing (currRingOld);
3638	if(strat->tailRing == sRing)
3639	strat->tailRing = currRing;
3640	rDelete (sRing);
3641	}
3642	if(rField_is_Ring(currRing) && !strat->sigdrop)
3643	id_DelDiv(strat->Shdl, currRing);
3644	if(!rField_is_Ring(currRing))
3645	id_DelDiv(strat->Shdl, currRing);
3646	idSkipZeroes(strat->Shdl);
3647	idTest(strat->Shdl);
3648
3649	#if SBA_PRINT_SIZE_G
3650	size_g = IDELEMS(strat->Shdl);
3651	#endif
3652	#ifdef DEBUGF5
3653	printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
3654	int oo = 0;
3655	while (oo<IDELEMS(strat->Shdl))
3656	{
3657	printf(" %d. ",oo+1);
3658	pWrite(pHead(strat->Shdl->m[oo]));
3659	oo++;
3660	}
3661	#endif
3662	#if SBA_PRINT_ZERO_REDUCTIONS
3663	printf("----------------------------------------------------------\n");
3664	printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
3665	zeroreductions = 0;
3666	#endif
3667	#if SBA_PRINT_REDUCTION_STEPS
3668	printf("----------------------------------------------------------\n");
3669	printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
3670	#endif
3671	#if SBA_PRINT_OPERATIONS
3672	printf("OPERATIONS: %ld\n",sba_operations);
3673	#endif
3674	#if SBA_PRINT_REDUCTION_STEPS
3675	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3676	printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
3677	#endif
3678	#if SBA_PRINT_OPERATIONS
3679	printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
3680	#endif
3681	#if SBA_PRINT_REDUCTION_STEPS
3682	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3683	printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
3684	sba_interreduction_steps = 0;
3685	sba_reduction_steps = 0;
3686	#endif
3687	#if SBA_PRINT_OPERATIONS
3688	printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
3689	sba_interreduction_operations = 0;
3690	sba_operations = 0;
3691	#endif
3692	#if SBA_PRINT_SIZE_G
3693	printf("----------------------------------------------------------\n");
3694	printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
3695	size_g = 0;
3696	size_g_non_red = 0;
3697	#endif
3698	#if SBA_PRINT_SIZE_SYZ
3699	printf("SIZE OF SYZ: %ld\n",size_syz);
3700	printf("----------------------------------------------------------\n");
3701	size_syz = 0;
3702	#endif
3703	#if SBA_PRINT_PRODUCT_CRITERION
3704	printf("PRODUCT CRITERIA: %ld\n",product_criterion);
3705	product_criterion = 0;
3706	#endif
3707	return (strat->Shdl);
3708	}
3709
3710	poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
3711	{
3712	assume(q!=NULL);
3713	assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3714
3715	// lazy_reduce flags: can be combined by \|
3716	//#define KSTD_NF_LAZY 1
3717	// do only a reduction of the leading term
3718	//#define KSTD_NF_NONORM 4
3719	// only global: avoid normalization, return a multiply of NF
3720	poly p;
3721
3722	//if ((idIs0(F))&&(Q==NULL))
3723	// return pCopy(q); /F=0/
3724	//strat->ak = idRankFreeModule(F);
3725	/- creating temp data structures------------------- -/
3726	BITSET save1;
3727	SI_SAVE_OPT1(save1);
3728	si_opt_1\|=Sy_bit(OPT_REDTAIL);
3729	initBuchMoraCrit(strat);
3730	strat->initEcart = initEcartBBA;
3731	#ifdef HAVE_SHIFTBBA
3732	if (rIsLPRing(currRing))
3733	{
3734	strat->enterS = enterSBbaShift;
3735	}
3736	else
3737	#endif
3738	{
3739	strat->enterS = enterSBba;
3740	}
3741	#ifndef NO_BUCKETS
3742	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3743	#endif
3744	/- set S -/
3745	strat->sl = -1;
3746	/- init local data struct.---------------------------------------- -/
3747	/Shdl=/initS(F,Q,strat);
3748	/- compute------------------------------------------------------- -/
3749	//if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3750	//{
3751	// for (i=strat->sl;i>=0;i--)
3752	// pNorm(strat->S[i]);
3753	//}
3754	kTest(strat);
3755	if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3756	if (BVERBOSE(23)) kDebugPrint(strat);
3757	int max_ind;
3758	p = redNF(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3759	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3760	{
3761	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3762	if (rField_is_Z(currRing)\|\|(rField_is_Zn(currRing)))
3763	{
3764	p = redtailBba_Z(p,max_ind,strat);
3765	}
3766	else if (rField_is_Ring(currRing))
3767	{
3768	p = redtailBba_Ring(p,max_ind,strat);
3769	}
3770	else
3771	{
3772	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3773	p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3774	}
3775	}
3776	/- release temp data------------------------------- -/
3777	assume(strat->L==NULL); /* strat->L unused */
3778	assume(strat->B==NULL); /* strat->B unused */
3779	omFree(strat->sevS);
3780	omFree(strat->ecartS);
3781	assume(strat->T==NULL);//omfree(strat->T);
3782	assume(strat->sevT==NULL);//omfree(strat->sevT);
3783	assume(strat->R==NULL);//omfree(strat->R);
3784	omfree(strat->S_2_R);
3785	omfree(strat->fromQ);
3786	idDelete(&strat->Shdl);
3787	SI_RESTORE_OPT1(save1);
3788	if (TEST_OPT_PROT) PrintLn();
3789	return p;
3790	}
3791
3792	poly kNF2Bound (ideal F,ideal Q,poly q,int bound,kStrategy strat, int lazyReduce)
3793	{
3794	assume(q!=NULL);
3795	assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3796
3797	// lazy_reduce flags: can be combined by \|
3798	//#define KSTD_NF_LAZY 1
3799	// do only a reduction of the leading term
3800	//#define KSTD_NF_NONORM 4
3801	// only global: avoid normalization, return a multiply of NF
3802	poly p;
3803
3804	//if ((idIs0(F))&&(Q==NULL))
3805	// return pCopy(q); /F=0/
3806	//strat->ak = idRankFreeModule(F);
3807	/- creating temp data structures------------------- -/
3808	BITSET save1;
3809	SI_SAVE_OPT1(save1);
3810	si_opt_1\|=Sy_bit(OPT_REDTAIL);
3811	initBuchMoraCrit(strat);
3812	strat->initEcart = initEcartBBA;
3813	strat->enterS = enterSBba;
3814	#ifndef NO_BUCKETS
3815	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3816	#endif
3817	/- set S -/
3818	strat->sl = -1;
3819	/- init local data struct.---------------------------------------- -/
3820	/Shdl=/initS(F,Q,strat);
3821	/- compute------------------------------------------------------- -/
3822	//if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3823	//{
3824	// for (i=strat->sl;i>=0;i--)
3825	// pNorm(strat->S[i]);
3826	//}
3827	kTest(strat);
3828	if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3829	if (BVERBOSE(23)) kDebugPrint(strat);
3830	int max_ind;
3831	p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3832	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3833	{
3834	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3835	if (rField_is_Z(currRing)\|\|(rField_is_Zn(currRing)))
3836	{
3837	p = redtailBba_Z(p,max_ind,strat);
3838	}
3839	else if (rField_is_Ring(currRing))
3840	{
3841	p = redtailBba_Ring(p,max_ind,strat);
3842	}
3843	else
3844	{
3845	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3846	p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
3847	//p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3848	}
3849	}
3850	/- release temp data------------------------------- -/
3851	assume(strat->L==NULL); /* strat->L unused */
3852	assume(strat->B==NULL); /* strat->B unused */
3853	omFree(strat->sevS);
3854	omFree(strat->ecartS);
3855	assume(strat->T==NULL);//omfree(strat->T);
3856	assume(strat->sevT==NULL);//omfree(strat->sevT);
3857	assume(strat->R==NULL);//omfree(strat->R);
3858	omfree(strat->S_2_R);
3859	omfree(strat->fromQ);
3860	idDelete(&strat->Shdl);
3861	SI_RESTORE_OPT1(save1);
3862	if (TEST_OPT_PROT) PrintLn();
3863	return p;
3864	}
3865
3866	ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
3867	{
3868	assume(!idIs0(q));
3869	assume(!(idIs0(F)&&(Q==NULL)));
3870	// lazy_reduce flags: can be combined by \|
3871	//#define KSTD_NF_LAZY 1
3872	// do only a reduction of the leading term
3873	//#define KSTD_NF_NONORM 4
3874	// only global: avoid normalization, return a multiply of NF
3875	poly p;
3876	int i;
3877	ideal res;
3878	int max_ind;
3879
3880	//if (idIs0(q))
3881	// return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3882	//if ((idIs0(F))&&(Q==NULL))
3883	// return idCopy(q); /F=0/
3884	//strat->ak = idRankFreeModule(F);
3885	/- creating temp data structures------------------- -/
3886	BITSET save1;
3887	SI_SAVE_OPT1(save1);
3888	si_opt_1\|=Sy_bit(OPT_REDTAIL);
3889	initBuchMoraCrit(strat);
3890	strat->initEcart = initEcartBBA;
3891	#ifdef HAVE_SHIFTBBA
3892	if (rIsLPRing(currRing))
3893	{
3894	strat->enterS = enterSBbaShift;
3895	}
3896	else
3897	#endif
3898	{
3899	strat->enterS = enterSBba;
3900	}
3901	/- set S -/
3902	strat->sl = -1;
3903	#ifndef NO_BUCKETS
3904	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3905	#endif
3906	/- init local data struct.---------------------------------------- -/
3907	/Shdl=/initS(F,Q,strat);
3908	/- compute------------------------------------------------------- -/
3909	res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3910	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3911	for (i=IDELEMS(q)-1; i>=0; i--)
3912	{
3913	if (q->m[i]!=NULL)
3914	{
3915	if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3916	p = redNF(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3917	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3918	{
3919	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3920	if (rField_is_Z(currRing)\|\|(rField_is_Zn(currRing)))
3921	{
3922	p = redtailBba_Z(p,max_ind,strat);
3923	}
3924	else if (rField_is_Ring(currRing))
3925	{
3926	p = redtailBba_Ring(p,max_ind,strat);
3927	}
3928	else
3929	{
3930	p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3931	}
3932	}
3933	res->m[i]=p;
3934	}
3935	//else
3936	// res->m[i]=NULL;
3937	}
3938	/- release temp data------------------------------- -/
3939	assume(strat->L==NULL); /* strat->L unused */
3940	assume(strat->B==NULL); /* strat->B unused */
3941	omFree(strat->sevS);
3942	omFree(strat->ecartS);
3943	assume(strat->T==NULL);//omfree(strat->T);
3944	assume(strat->sevT==NULL);//omfree(strat->sevT);
3945	assume(strat->R==NULL);//omfree(strat->R);
3946	omfree(strat->S_2_R);
3947	omfree(strat->fromQ);
3948	idDelete(&strat->Shdl);
3949	SI_RESTORE_OPT1(save1);
3950	if (TEST_OPT_PROT) PrintLn();
3951	return res;
3952	}
3953
3954	ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound,kStrategy strat, int lazyReduce)
3955	{
3956	assume(!idIs0(q));
3957	assume(!(idIs0(F)&&(Q==NULL)));
3958	// lazy_reduce flags: can be combined by \|
3959	//#define KSTD_NF_LAZY 1
3960	// do only a reduction of the leading term
3961	//#define KSTD_NF_NONORM 4
3962	// only global: avoid normalization, return a multiply of NF
3963	poly p;
3964	int i;
3965	ideal res;
3966	int max_ind;
3967
3968	//if (idIs0(q))
3969	// return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3970	//if ((idIs0(F))&&(Q==NULL))
3971	// return idCopy(q); /F=0/
3972	//strat->ak = idRankFreeModule(F);
3973	/- creating temp data structures------------------- -/
3974	BITSET save1;
3975	SI_SAVE_OPT1(save1);
3976	si_opt_1\|=Sy_bit(OPT_REDTAIL);
3977	initBuchMoraCrit(strat);
3978	strat->initEcart = initEcartBBA;
3979	strat->enterS = enterSBba;
3980	/- set S -/
3981	strat->sl = -1;
3982	#ifndef NO_BUCKETS
3983	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3984	#endif
3985	/- init local data struct.---------------------------------------- -/
3986	/Shdl=/initS(F,Q,strat);
3987	/- compute------------------------------------------------------- -/
3988	res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3989	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3990	for (i=IDELEMS(q)-1; i>=0; i--)
3991	{
3992	if (q->m[i]!=NULL)
3993	{
3994	if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3995	p = redNFBound(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3996	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3997	{
3998	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3999	if (rField_is_Z(currRing)\|\|(rField_is_Zn(currRing)))
4000	{
4001	p = redtailBba_Z(p,max_ind,strat);
4002	}
4003	else if (rField_is_Ring(currRing))
4004	{
4005	p = redtailBba_Ring(p,max_ind,strat);
4006	}
4007	else
4008	{
4009	p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
4010	}
4011	}
4012	res->m[i]=p;
4013	}
4014	//else
4015	// res->m[i]=NULL;
4016	}
4017	/- release temp data------------------------------- -/
4018	assume(strat->L==NULL); /* strat->L unused */
4019	assume(strat->B==NULL); /* strat->B unused */
4020	omFree(strat->sevS);
4021	omFree(strat->ecartS);
4022	assume(strat->T==NULL);//omfree(strat->T);
4023	assume(strat->sevT==NULL);//omfree(strat->sevT);
4024	assume(strat->R==NULL);//omfree(strat->R);
4025	omfree(strat->S_2_R);
4026	omfree(strat->fromQ);
4027	idDelete(&strat->Shdl);
4028	SI_RESTORE_OPT1(save1);
4029	if (TEST_OPT_PROT) PrintLn();
4030	return res;
4031	}
4032
4033	#if F5C
4034	/*********************************************************************
4035	* interrreduction step of the signature-based algorithm:
4036	* 1. all strat->S are interpreted as new critical pairs
4037	* 2. those pairs need to be completely reduced by the usual (non sig-
4038	* safe) reduction process (including tail reductions)
4039	* 3. strat->S and strat->T are completely new computed in these steps
4040	********************************************************************/
4041	void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
4042	int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
4043	intvec w,intvec hilb )
4044	{
4045	int Ll_old, red_result = 1;
4046	int pos = 0;
4047	hilbeledeg=1;
4048	hilbcount=0;
4049	minimcnt=0;
4050	srmax = 0; // strat->sl is 0 at this point
4051	reduc = olddeg = lrmax = 0;
4052	// we cannot use strat->T anymore
4053	//cleanT(strat);
4054	//strat->tl = -1;
4055	Ll_old = strat->Ll;
4056	while (strat->tl >= 0)
4057	{
4058	if(!strat->T[strat->tl].is_redundant)
4059	{
4060	LObject h;
4061	h.p = strat->T[strat->tl].p;
4062	h.tailRing = strat->T[strat->tl].tailRing;
4063	h.t_p = strat->T[strat->tl].t_p;
4064	if (h.p!=NULL)
4065	{
4066	if (currRing->OrdSgn==-1)
4067	{
4068	cancelunit(&h);
4069	deleteHC(&h, strat);
4070	}
4071	if (h.p!=NULL)
4072	{
4073	if (TEST_OPT_INTSTRATEGY)
4074	{
4075	h.pCleardenom(); // also does remove Content
4076	}
4077	else
4078	{
4079	h.pNorm();
4080	}
4081	strat->initEcart(&h);
4082	if(rField_is_Ring(currRing))
4083	pos = posInLF5CRing(strat->L, Ll_old+1,strat->Ll,&h,strat);
4084	else
4085	pos = strat->Ll+1;
4086	h.sev = pGetShortExpVector(h.p);
4087	enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
4088	}
4089	}
4090	}
4091	strat->tl--;
4092	}
4093	strat->sl = -1;
4094	#if 0
4095	//#ifdef HAVE_TAIL_RING
4096	if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4097	kStratInitChangeTailRing(strat);
4098	#endif
4099	//enterpairs(pOne(),0,0,-1,strat,strat->tl);
4100	//strat->sl = -1;
4101	/* picks the last element from the lazyset L */
4102	while (strat->Ll>Ll_old)
4103	{
4104	strat->P = strat->L[strat->Ll];
4105	strat->Ll--;
4106	//#if 1
4107	#ifdef DEBUGF5
4108	PrintS("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
4109	PrintS("-------------------------------------------------\n");
4110	pWrite(pHead(strat->P.p));
4111	pWrite(pHead(strat->P.p1));
4112	pWrite(pHead(strat->P.p2));
4113	printf("%d\n",strat->tl);
4114	PrintS("-------------------------------------------------\n");
4115	#endif
4116	if (pNext(strat->P.p) == strat->tail)
4117	{
4118	// deletes the short spoly
4119	if (rField_is_Ring(currRing))
4120	pLmDelete(strat->P.p);
4121	else
4122	pLmFree(strat->P.p);
4123
4124	// TODO: needs some masking
4125	// TODO: masking needs to vanish once the signature
4126	// sutff is completely implemented
4127	strat->P.p = NULL;
4128	poly m1 = NULL, m2 = NULL;
4129
4130	// check that spoly creation is ok
4131	while (strat->tailRing != currRing &&
4132	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4133	{
4134	assume(m1 == NULL && m2 == NULL);
4135	// if not, change to a ring where exponents are at least
4136	// large enough
4137	if (!kStratChangeTailRing(strat))
4138	{
4139	WerrorS("OVERFLOW...");
4140	break;
4141	}
4142	}
4143	// create the real one
4144	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4145	strat->tailRing, m1, m2, strat->R);
4146	}
4147	else if (strat->P.p1 == NULL)
4148	{
4149	if (strat->minim > 0)
4150	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4151	// for input polys, prepare reduction
4152	if(!rField_is_Ring(currRing))
4153	strat->P.PrepareRed(strat->use_buckets);
4154	}
4155
4156	if (strat->P.p == NULL && strat->P.t_p == NULL)
4157	{
4158	red_result = 0;
4159	}
4160	else
4161	{
4162	if (TEST_OPT_PROT)
4163	message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4164	&olddeg,&reduc,strat, red_result);
4165
4166	#ifdef DEBUGF5
4167	PrintS("Poly before red: ");
4168	pWrite(strat->P.p);
4169	#endif
4170	/* complete reduction of the element chosen from L */
4171	red_result = strat->red2(&strat->P,strat);
4172	if (errorreported) break;
4173	}
4174
4175	if (strat->overflow)
4176	{
4177	if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4178	}
4179
4180	// reduction to non-zero new poly
4181	if (red_result == 1)
4182	{
4183	// get the polynomial (canonicalize bucket, make sure P.p is set)
4184	strat->P.GetP(strat->lmBin);
4185	// in the homogeneous case FDeg >= pFDeg (sugar/honey)
4186	// but now, for entering S, T, we reset it
4187	// in the inhomogeneous case: FDeg == pFDeg
4188	if (strat->homog) strat->initEcart(&(strat->P));
4189
4190	/* statistic */
4191	if (TEST_OPT_PROT) PrintS("s");
4192	int pos;
4193	#if 1
4194	if(!rField_is_Ring(currRing))
4195	pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4196	else
4197	pos = posInSMonFirst(strat,strat->sl,strat->P.p);
4198	#else
4199	pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4200	#endif
4201	// reduce the tail and normalize poly
4202	// in the ring case we cannot expect LC(f) = 1,
4203	// therefore we call pCleardenom instead of pNorm
4204	#if F5CTAILRED
4205	BOOLEAN withT = TRUE;
4206	if ((TEST_OPT_INTSTRATEGY) \|\| (rField_is_Ring(currRing)))
4207	{
4208	strat->P.pCleardenom();
4209	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
4210	{
4211	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4212	strat->P.pCleardenom();
4213	}
4214	}
4215	else
4216	{
4217	strat->P.pNorm();
4218	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
4219	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
4220	}
4221	#endif
4222	#ifdef KDEBUG
4223	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4224	#endif /* KDEBUG */
4225
4226	// min_std stuff
4227	if ((strat->P.p1==NULL) && (strat->minim>0))
4228	{
4229	if (strat->minim==1)
4230	{
4231	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4232	p_Delete(&strat->P.p2, currRing, strat->tailRing);
4233	}
4234	else
4235	{
4236	strat->M->m[minimcnt]=strat->P.p2;
4237	strat->P.p2=NULL;
4238	}
4239	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4240	pNext(strat->M->m[minimcnt])
4241	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4242	strat->tailRing, currRing,
4243	currRing->PolyBin);
4244	minimcnt++;
4245	}
4246
4247	// enter into S, L, and T
4248	// here we need to recompute new signatures, but those are trivial ones
4249	if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
4250	{
4251	enterT(strat->P, strat);
4252	// posInS only depends on the leading term
4253	strat->enterS(strat->P, pos, strat, strat->tl);
4254	//#if 1
4255	#ifdef DEBUGF5
4256	PrintS("ELEMENT ADDED TO GCURR DURING INTERRED: ");
4257	pWrite(pHead(strat->S[strat->sl]));
4258	pWrite(strat->sig[strat->sl]);
4259	#endif
4260	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4261	}
4262	// Print("[%d]",hilbeledeg);
4263	kDeleteLcm(&strat->P);
4264	if (strat->sl>srmax) srmax = strat->sl;
4265	}
4266	else
4267	{
4268	// adds signature of the zero reduction to
4269	// strat->syz. This is the leading term of
4270	// syzygy and can be used in syzCriterion()
4271	// the signature is added if and only if the
4272	// pair was not detected by the rewritten criterion in strat->red = redSig
4273	if (strat->P.p1 == NULL && strat->minim > 0)
4274	{
4275	p_Delete(&strat->P.p2, currRing, strat->tailRing);
4276	}
4277	}
4278
4279	#ifdef KDEBUG
4280	memset(&(strat->P), 0, sizeof(strat->P));
4281	#endif /* KDEBUG */
4282	}
4283	int cc = 0;
4284	while (cc<strat->tl+1)
4285	{
4286	strat->T[cc].sig = pOne();
4287	p_SetComp(strat->T[cc].sig,cc+1,currRing);
4288	strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
4289	strat->sig[cc] = strat->T[cc].sig;
4290	strat->sevSig[cc] = strat->T[cc].sevSig;
4291	strat->T[cc].is_sigsafe = TRUE;
4292	cc++;
4293	}
4294	strat->max_lower_index = strat->tl;
4295	// set current signature index of upcoming iteration step
4296	// NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
4297	// the corresponding syzygy rules correctly
4298	strat->currIdx = cc+1;
4299	for (int cd=strat->Ll; cd>=0; cd--)
4300	{
4301	p_SetComp(strat->L[cd].sig,cc+1,currRing);
4302	cc++;
4303	}
4304	for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
4305	strat->Shdl->m[cc] = NULL;
4306	#if 0
4307	printf("\nAfter f5c sorting\n");
4308	for(int i=0;i<=strat->sl;i++)
4309	pWrite(pHead(strat->S[i]));
4310	getchar();
4311	#endif
4312	//#if 1
4313	#if DEBUGF5
4314	PrintS("------------------- STRAT S ---------------------\n");
4315	cc = 0;
4316	while (cc<strat->tl+1)
4317	{
4318	pWrite(pHead(strat->S[cc]));
4319	pWrite(strat->sig[cc]);
4320	printf("- - - - - -\n");
4321	cc++;
4322	}
4323	PrintS("-------------------------------------------------\n");
4324	PrintS("------------------- STRAT T ---------------------\n");
4325	cc = 0;
4326	while (cc<strat->tl+1)
4327	{
4328	pWrite(pHead(strat->T[cc].p));
4329	pWrite(strat->T[cc].sig);
4330	printf("- - - - - -\n");
4331	cc++;
4332	}
4333	PrintS("-------------------------------------------------\n");
4334	PrintS("------------------- STRAT L ---------------------\n");
4335	cc = 0;
4336	while (cc<strat->Ll+1)
4337	{
4338	pWrite(pHead(strat->L[cc].p));
4339	pWrite(pHead(strat->L[cc].p1));
4340	pWrite(pHead(strat->L[cc].p2));
4341	pWrite(strat->L[cc].sig);
4342	printf("- - - - - -\n");
4343	cc++;
4344	}
4345	PrintS("-------------------------------------------------\n");
4346	printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
4347	#endif
4348
4349	}
4350	#endif
4351
4352	/* shiftgb stuff */
4353	#ifdef HAVE_SHIFTBBA
4354	ideal bbaShift(ideal F, ideal Q,intvec w,intvec hilb,kStrategy strat)
4355	{
4356	int red_result = 1;
4357	int olddeg,reduc;
4358	int hilbeledeg=1,hilbcount=0,minimcnt=0;
4359	BOOLEAN withT = TRUE; // currently only T contains the shifts
4360	BITSET save;
4361	SI_SAVE_OPT1(save);
4362
4363	initBuchMoraCrit(strat); /set Gebauer, honey, sugarCrit/
4364	if(rField_is_Ring(currRing))
4365	initBuchMoraPosRing(strat);
4366	else
4367	initBuchMoraPos(strat);
4368	initHilbCrit(F,Q,&hilb,strat);
4369	initBba(strat);
4370	/set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair/
4371	/Shdl=/initBuchMora(F, Q,strat);
4372	if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
4373	reduc = olddeg = 0;
4374
4375	#ifndef NO_BUCKETS
4376	if (!TEST_OPT_NOT_BUCKETS)
4377	strat->use_buckets = 1;
4378	#endif
4379	// redtailBBa against T for inhomogenous input
4380	// if (!TEST_OPT_OLDSTD)
4381	// withT = ! strat->homog;
4382
4383	// strat->posInT = posInT_pLength;
4384	kTest_TS(strat);
4385
4386	#ifdef HAVE_TAIL_RING
4387	// if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
4388	// kStratInitChangeTailRing(strat);
4389	strat->tailRing=currRing;
4390	#endif
4391	if (BVERBOSE(23))
4392	{
4393	if (test_PosInT!=NULL) strat->posInT=test_PosInT;
4394	if (test_PosInL!=NULL) strat->posInL=test_PosInL;
4395	kDebugPrint(strat);
4396	}
4397
4398	#ifdef KDEBUG
4399	//kDebugPrint(strat);
4400	#endif
4401	/* compute------------------------------------------------------- */
4402	while (strat->Ll >= 0)
4403	{
4404	#ifdef KDEBUG
4405	if (TEST_OPT_DEBUG) messageSets(strat);
4406	#endif
4407	if (siCntrlc)
4408	{
4409	while (strat->Ll >= 0)
4410	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4411	strat->noClearS=TRUE;
4412	}
4413	if (TEST_OPT_DEGBOUND
4414	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4415	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
4416	{
4417	/*
4418	*stops computation if
4419	* 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
4420	*a predefined number Kstd1_deg
4421	*/
4422	while ((strat->Ll >= 0)
4423	&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
4424	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
4425	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
4426	)
4427	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
4428	if (strat->Ll<0) break;
4429	else strat->noClearS=TRUE;
4430	}
4431	if (strat->Ll== 0) strat->interpt=TRUE;
4432	/* picks the last element from the lazyset L */
4433	strat->P = strat->L[strat->Ll];
4434	strat->Ll--;
4435
4436	if (pNext(strat->P.p) == strat->tail)
4437	{
4438	// deletes the short spoly
4439	if (rField_is_Ring(currRing))
4440	pLmDelete(strat->P.p);
4441	else
4442	pLmFree(strat->P.p);
4443	strat->P.p = NULL;
4444	poly m1 = NULL, m2 = NULL;
4445
4446	// check that spoly creation is ok
4447	while (strat->tailRing != currRing &&
4448	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
4449	{
4450	assume(m1 == NULL && m2 == NULL);
4451	// if not, change to a ring where exponents are at least
4452	// large enough
4453	if (!kStratChangeTailRing(strat))
4454	{
4455	WerrorS("OVERFLOW...");
4456	break;
4457	}
4458	}
4459	// create the real one
4460	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
4461	strat->tailRing, m1, m2, strat->R);
4462	}
4463	else if (strat->P.p1 == NULL)
4464	{
4465	if (strat->minim > 0)
4466	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
4467	// for input polys, prepare reduction
4468	strat->P.PrepareRed(strat->use_buckets);
4469	}
4470
4471	if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
4472	{
4473	red_result = 0;
4474	}
4475	else
4476	{
4477	if (TEST_OPT_PROT)
4478	message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
4479	&olddeg,&reduc,strat, red_result);
4480
4481	/* reduction of the element chosen from L */
4482	red_result = strat->red(&strat->P,strat);
4483	if (errorreported) break;
4484	}
4485
4486	if (strat->overflow)
4487	{
4488	if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
4489	}
4490
4491	// reduction to non-zero new poly
4492	if (red_result == 1)
4493	{
4494	// get the polynomial (canonicalize bucket, make sure P.p is set)
4495	strat->P.GetP(strat->lmBin);
4496	// in the homogeneous case FDeg >= pFDeg (sugar/honey)
4497	// but now, for entering S, T, we reset it
4498	// in the inhomogeneous case: FDeg == pFDeg
4499	if (strat->homog) strat->initEcart(&(strat->P));
4500
4501	/* statistic */
4502	if (TEST_OPT_PROT) PrintS("s");
4503
4504	int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4505
4506	// reduce the tail and normalize poly
4507	// in the ring case we cannot expect LC(f) = 1,
4508	// therefore we call pCleardenom instead of pNorm
4509	strat->redTailChange=FALSE;
4510
4511	/* if we are computing over Z we always want to try and cut down
4512	* the coefficients in the tail terms */
4513	if (rField_is_Z(currRing) && !rHasLocalOrMixedOrdering(currRing))
4514	{
4515	redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
4516	strat->P.pCleardenom();
4517	}
4518
4519	if ((TEST_OPT_INTSTRATEGY) \|\| (rField_is_Ring(currRing)))
4520	{
4521	strat->P.pCleardenom();
4522	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
4523	{
4524	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
4525	strat->P.pCleardenom();
4526	if (strat->redTailChange)
4527	{
4528	strat->P.t_p=NULL;
4529	strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
4530	}
4531	}
4532	}
4533	else
4534	{
4535	strat->P.pNorm();
4536	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
4537	{
4538	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
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
4547	#ifdef KDEBUG
4548	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
4549	#endif /* KDEBUG */
4550
4551	// min_std stuff
4552	if ((strat->P.p1==NULL) && (strat->minim>0))
4553	{
4554	if (strat->minim==1)
4555	{
4556	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
4557	p_Delete(&strat->P.p2, currRing, strat->tailRing);
4558	}
4559	else
4560	{
4561	strat->M->m[minimcnt]=strat->P.p2;
4562	strat->P.p2=NULL;
4563	}
4564	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
4565	pNext(strat->M->m[minimcnt])
4566	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
4567	strat->tailRing, currRing,
4568	currRing->PolyBin);
4569	minimcnt++;
4570	}
4571
4572
4573	// enter into S, L, and T
4574	if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
4575	{
4576	enterT(strat->P, strat);
4577	enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4578	// posInS only depends on the leading term
4579	strat->enterS(strat->P, pos, strat, strat->tl);
4580	if (!strat->rightGB)
4581	enterTShift(strat->P, strat);
4582	}
4583
4584	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
4585	// Print("[%d]",hilbeledeg);
4586	kDeleteLcm(&strat->P);
4587	if (strat->s_poly!=NULL)
4588	{
4589	// the only valid entries are: strat->P.p,
4590	// strat->tailRing (read-only, keep it)
4591	// (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
4592	if (strat->s_poly(strat))
4593	{
4594	// we are called AFTER enterS, i.e. if we change P
4595	// we have to add it also to S/T
4596	// and add pairs
4597	int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
4598	enterT(strat->P, strat);
4599	enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
4600	strat->enterS(strat->P, pos, strat, strat->tl);
4601	if (!strat->rightGB)
4602	enterTShift(strat->P,strat);
4603	}
4604	}
4605	}
4606	else if (strat->P.p1 == NULL && strat->minim > 0)
4607	{
4608	p_Delete(&strat->P.p2, currRing, strat->tailRing);
4609	}
4610	#ifdef KDEBUG
4611	memset(&(strat->P), 0, sizeof(strat->P));
4612	#endif /* KDEBUG */
4613	kTest_TS(strat);
4614	}
4615	#ifdef KDEBUG
4616	if (TEST_OPT_DEBUG) messageSets(strat);
4617	#endif /* KDEBUG */
4618	/* shift case: look for elt's in S such that they are divisible by elt in T */
4619	if ((TEST_OPT_SB_1 \|\| TEST_OPT_REDSB) && !strat->noClearS) // when is OPT_SB_1 set?
4620	{
4621	if(!rField_is_Ring(currRing))
4622	{
4623	for (int k = 0; k <= strat->sl; ++k)
4624	{
4625	if ((strat->fromQ!=NULL) && (strat->fromQ[k])) continue; // do not reduce Q_k
4626	for (int j = 0; j<=strat->tl; ++j)
4627	{
4628	// this is like clearS in bba, but we reduce with elements from T, because it contains the shifts too
4629	assume(strat->sevT[j] == pGetShortExpVector(strat->T[j].p));
4630	assume(strat->sevS[k] == pGetShortExpVector(strat->S[k]));
4631	if (pLmShortDivisibleBy(strat->T[j].p, strat->sevT[j], strat->S[k], ~strat->sevS[k]))
4632	{
4633	if (pLmCmp(strat->T[j].p, strat->S[k]) != 0)
4634	{ // check whether LM is different
4635	deleteInS(k, strat);
4636	--k;
4637	break;
4638	}
4639	}
4640	}
4641	}
4642	}
4643	}
4644	/* complete reduction of the standard basis--------- */
4645	if (TEST_OPT_REDSB)
4646	{
4647	completeReduce(strat, TRUE); //shift: withT = TRUE
4648	if (strat->completeReduce_retry)
4649	{
4650	// completeReduce needed larger exponents, retry
4651	// to reduce with S (instead of T)
4652	// and in currRing (instead of strat->tailRing)
4653	#ifdef HAVE_TAIL_RING
4654	if(currRing->bitmask>strat->tailRing->bitmask)
4655	{
4656	strat->completeReduce_retry=FALSE;
4657	cleanT(strat);strat->tailRing=currRing;
4658	int i;
4659	for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
4660	WarnS("reduction with S is not yet supported by Letterplace"); // if this ever happens, we'll know
4661	completeReduce(strat);
4662	}
4663	if (strat->completeReduce_retry)
4664	#endif
4665	Werror("exponent bound is %ld",currRing->bitmask);
4666	}
4667	}
4668	else if (TEST_OPT_PROT) PrintLn();
4669
4670	/* release temp data-------------------------------- */
4671	exitBuchMora(strat);
4672	/* postprocessing for GB over ZZ --------------------*/
4673	if (!errorreported)
4674	{
4675	if(rField_is_Z(currRing))
4676	{
4677	for(int i = 0;i<=strat->sl;i++)
4678	{
4679	if(!nGreaterZero(pGetCoeff(strat->S[i])))
4680	{
4681	strat->S[i] = pNeg(strat->S[i]);
4682	}
4683	}
4684	finalReduceByMon(strat);
4685	for(int i = 0;i<IDELEMS(strat->Shdl);i++)
4686	{
4687	if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
4688	{
4689	strat->S[i] = pNeg(strat->Shdl->m[i]);
4690	}
4691	}
4692	}
4693	//else if (rField_is_Ring(currRing))
4694	// finalReduceByMon(strat);
4695	}
4696	// if (TEST_OPT_WEIGHTM)
4697	// {
4698	// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
4699	// if (ecartWeights)
4700	// {
4701	// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
4702	// ecartWeights=NULL;
4703	// }
4704	// }
4705	if ((TEST_OPT_PROT) \|\| (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
4706	SI_RESTORE_OPT1(save);
4707	/* postprocessing for GB over Q-rings ------------------*/
4708	if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
4709
4710	idTest(strat->Shdl);
4711
4712	return (strat->Shdl);
4713	}
4714	#endif
4715
4716	#ifdef HAVE_SHIFTBBA
4717	ideal rightgb(ideal F, ideal Q)
4718	{
4719	assume(rIsLPRing(currRing));
4720	assume(idIsInV(F));
4721	ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4722	idSkipZeroes(RS); // is this even necessary?
4723	assume(idIsInV(RS));
4724	return(RS);
4725	}
4726	#endif
4727
4728	/*2
4729	*reduces h with elements from T choosing the first possible
4730	* element in t with respect to the given pDivisibleBy
4731	*/
4732	#ifdef HAVE_SHIFTBBA
4733	int redFirstShift (LObject* h,kStrategy strat)
4734	{
4735	if (h->IsNull()) return 0;
4736
4737	int at, reddeg,d;
4738	int pass = 0;
4739	int j = 0;
4740
4741	if (! strat->homog)
4742	{
4743	d = h->GetpFDeg() + h->ecart;
4744	reddeg = strat->LazyDegree+d;
4745	}
4746	h->SetShortExpVector();
4747	loop
4748	{
4749	j = kFindDivisibleByInT(strat, h);
4750	if (j < 0)
4751	{
4752	h->SetDegStuffReturnLDeg(strat->LDegLast);
4753	return 1;
4754	}
4755
4756	if (!TEST_OPT_INTSTRATEGY)
4757	strat->T[j].pNorm();
4758	#ifdef KDEBUG
4759	if (TEST_OPT_DEBUG)
4760	{
4761	PrintS("reduce ");
4762	h->wrp();
4763	PrintS(" with ");
4764	strat->T[j].wrp();
4765	}
4766	#endif
4767	ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
4768
4769	#ifdef KDEBUG
4770	if (TEST_OPT_DEBUG)
4771	{
4772	PrintS("\nto ");
4773	wrp(h->p);
4774	PrintLn();
4775	}
4776	#endif
4777	if (h->IsNull())
4778	{
4779	kDeleteLcm(h);
4780	h->Clear();
4781	return 0;
4782	}
4783	h->SetShortExpVector();
4784
4785	#if 0
4786	if ((strat->syzComp!=0) && !strat->honey)
4787	{
4788	if ((strat->syzComp>0) &&
4789	(h->Comp() > strat->syzComp))
4790	{
4791	assume(h->MinComp() > strat->syzComp);
4792	#ifdef KDEBUG
4793	if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
4794	#endif
4795	if (strat->homog)
4796	h->SetDegStuffReturnLDeg(strat->LDegLast);
4797	return -2;
4798	}
4799	}
4800	#endif
4801	if (!strat->homog)
4802	{
4803	if (!TEST_OPT_OLDSTD && strat->honey)
4804	{
4805	h->SetpFDeg();
4806	if (strat->T[j].ecart <= h->ecart)
4807	h->ecart = d - h->GetpFDeg();
4808	else
4809	h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
4810
4811	d = h->GetpFDeg() + h->ecart;
4812	}
4813	else
4814	d = h->SetDegStuffReturnLDeg(strat->LDegLast);
4815	/- try to reduce the s-polynomial -/
4816	pass++;
4817	/*
4818	*test whether the polynomial should go to the lazyset L
4819	*-if the degree jumps
4820	*-if the number of pre-defined reductions jumps
4821	*/
4822	if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
4823	&& ((d >= reddeg) \|\| (pass > strat->LazyPass)))
4824	{
4825	h->SetLmCurrRing();
4826	if (strat->posInLDependsOnLength)
4827	h->SetLength(strat->length_pLength);
4828	at = strat->posInL(strat->L,strat->Ll,h,strat);
4829	if (at <= strat->Ll)
4830	{
4831	//int dummy=strat->sl;
4832	/* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
4833	//if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
4834	if (kFindDivisibleByInT(strat, h) < 0)
4835	return 1;
4836	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
4837	#ifdef KDEBUG
4838	if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
4839	#endif
4840	h->Clear();
4841	return -1;
4842	}
4843	}
4844	if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
4845	{
4846	reddeg = d+1;
4847	Print(".%d",d);mflush();
4848	}
4849	}
4850	}
4851	}
4852	#endif

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

Download in other formats: