Context Navigation

source: git/kernel/GBEngine/kstd2.cc @ 036a5e

spielwiese

Last change on this file since 036a5e was 036a5e, checked in by Hans Schoenemann <hannes@…>, 3 years ago
new ksReducePoly
Property mode set to `100644`
File size: 130.5 KB

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

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

Download in other formats: