Context Navigation

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

spielwiese

Last change on this file since b97cce6 was b97cce6, checked in by Hans Schoenemann <hannes@…>, 19 months ago
fix: redNF and related
Property mode set to `100644`
File size: 131.5 KB

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

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

Download in other formats: