Context Navigation

source: git/kernel/GBEngine/kstd2.cc @ 6f203b

spielwiese

Last change on this file since 6f203b was 6f203b, checked in by Hans Schoenemann <hannes@…>, 8 years ago
chg: clean strat-P before calling strat->s_poly (in bba)
Property mode set to `100644`
File size: 92.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
11
12
13
14	#include <kernel/mod2.h>
15
16	#define ADIDEBUG 0
17	#define ADIDEBUG_COUNT 0
18
19	// define if no buckets should be used
20	// #define NO_BUCKETS
21
22	#ifdef HAVE_PLURAL
23	#define PLURAL_INTERNAL_DECLARATIONS 1
24	#endif
25
26	/***********************************************
27	* SBA stuff -- start
28	***********************************************/
29	#define DEBUGF50 0
30	#define DEBUGF51 0
31
32	#ifdef DEBUGF5
33	#undef DEBUGF5
34	//#define DEBUGF5 1
35	#endif
36
37	#define F5C 1
38	#if F5C
39	#define F5CTAILRED 1
40	#endif
41
42	#define SBA_INTERRED_START 0
43	#define SBA_TAIL_RED 1
44	#define SBA_PRODUCT_CRITERION 0
45	#define SBA_PRINT_ZERO_REDUCTIONS 0
46	#define SBA_PRINT_REDUCTION_STEPS 0
47	#define SBA_PRINT_OPERATIONS 0
48	#define SBA_PRINT_SIZE_G 0
49	#define SBA_PRINT_SIZE_SYZ 0
50	#define SBA_PRINT_PRODUCT_CRITERION 0
51
52	// counts sba's reduction steps
53	#if SBA_PRINT_REDUCTION_STEPS
54	long sba_reduction_steps;
55	long sba_interreduction_steps;
56	#endif
57	#if SBA_PRINT_OPERATIONS
58	long sba_operations;
59	long sba_interreduction_operations;
60	#endif
61
62	/***********************************************
63	* SBA stuff -- done
64	***********************************************/
65
66	#include <kernel/GBEngine/kutil.h>
67	#include <misc/options.h>
68	#include <omalloc/omalloc.h>
69	#include <kernel/polys.h>
70	#include <kernel/ideals.h>
71	#include <kernel/GBEngine/kstd1.h>
72	#include <kernel/GBEngine/khstd.h>
73	#include <polys/kbuckets.h>
74	#include <polys/prCopy.h>
75	//#include "cntrlc.h"
76	#include <polys/weight.h>
77	#include <misc/intvec.h>
78	#ifdef HAVE_PLURAL
79	#include <polys/nc/nc.h>
80	#endif
81	// #include "timer.h"
82
83	/* shiftgb stuff */
84	#include <kernel/GBEngine/shiftgb.h>
85
86	int (*test_PosInT)(const TSet T,const int tl,LObject &h);
87	int (*test_PosInL)(const LSet set, const int length,
88	LObject* L,const kStrategy strat);
89
90	// return -1 if no divisor is found
91	// number of first divisor, otherwise
92	int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start)
93	{
94	unsigned long not_sev = ~L->sev;
95	int j = start;
96
97	const TSet T=strat->T;
98	const unsigned long* sevT=strat->sevT;
99	if (L->p!=NULL)
100	{
101	const ring r=currRing;
102	const poly p=L->p;
103
104	pAssume(~not_sev == p_GetShortExpVector(p, r));
105
106	loop
107	{
108	if (j > strat->tl) return -1;
109	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
110	if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
111	{
112	if(rField_is_Ring(r))
113	{
114	if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r))
115	return j;}
116	else
117	{
118	return j;
119	}
120	}
121	#else
122	if (!(sevT[j] & not_sev) &&
123	p_LmDivisibleBy(T[j].p, p, r))
124	{
125	if(rField_is_Ring(r))
126	{
127	if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r))
128	return j;
129	}
130	else
131	{
132	return j;
133	}
134	}
135	#endif
136	j++;
137	}
138	}
139	else
140	{
141	const poly p=L->t_p;
142	const ring r=strat->tailRing;
143	loop
144	{
145	if (j > strat->tl) return -1;
146	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
147	if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
148	p, not_sev, r))
149	{
150	if(rField_is_Ring(r))
151	{
152	if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r))
153	return j;
154	}
155	else
156	{
157	return j;
158	}
159	}
160	#else
161	if (!(sevT[j] & not_sev) &&
162	p_LmDivisibleBy(T[j].t_p, p, r))
163	{
164	if(rField_is_Ring(r))
165	{
166	if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r))
167	return j;
168	}
169	else
170	{
171	return j;
172	}
173	}
174	#endif
175	j++;
176	}
177	}
178	}
179
180	// same as above, only with set S
181	int kFindDivisibleByInS(const kStrategy strat, int* max_ind, LObject* L)
182	{
183	unsigned long not_sev = ~L->sev;
184	poly p = L->GetLmCurrRing();
185	int j = 0;
186
187	pAssume(~not_sev == p_GetShortExpVector(p, currRing));
188	#if 1
189	int ende;
190	if ((strat->ak>0) \|\| currRing->pLexOrder) ende=strat->sl;
191	else ende=posInS(strat,*max_ind,p,0)+1;
192	if (ende>(max_ind)) ende=(max_ind);
193	#else
194	int ende=strat->sl;
195	#endif
196	(*max_ind)=ende;
197	loop
198	{
199	if (j > ende) return -1;
200	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
201	if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
202	p, not_sev, currRing))
203	{
204	if(rField_is_Ring(currRing))
205	{if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing))
206	return j;}
207	else
208	return j;
209	}
210	#else
211	if ( !(strat->sevS[j] & not_sev) &&
212	p_LmDivisibleBy(strat->S[j], p, currRing))
213	{
214	if(rField_is_Ring(currRing))
215	{if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing))
216	return j;}
217	else
218	return j;
219	}
220	#endif
221	j++;
222	}
223	}
224
225	int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L)
226	{
227	unsigned long not_sev = ~L->sev;
228	poly p = L->GetLmCurrRing();
229	int j = start;
230
231	pAssume(~not_sev == p_GetShortExpVector(p, currRing));
232	#if 1
233	int ende=max_ind;
234	#else
235	int ende=strat->sl;
236	#endif
237	loop
238	{
239	if (j > ende) return -1;
240	#if defined(PDEBUG) \|\| defined(PDIV_DEBUG)
241	if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
242	p, not_sev, currRing))
243	{
244	if(rField_is_Ring(currRing))
245	{if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing))
246	return j;}
247	else
248	return j;
249	}
250	#else
251	if ( !(strat->sevS[j] & not_sev) &&
252	p_LmDivisibleBy(strat->S[j], p, currRing))
253	{
254	if(rField_is_Ring(currRing))
255	{if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing))
256	return j;}
257	else
258	return j;
259	}
260	#endif
261	j++;
262	}
263	}
264
265	#ifdef HAVE_RINGS
266	poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
267	{
268	// m = currRing->ch
269
270	if (input_p == NULL) return NULL;
271
272	poly p = input_p;
273	poly zeroPoly = NULL;
274	unsigned long a = (unsigned long) pGetCoeff(p);
275
276	int k_ind2 = 0;
277	int a_ind2 = ind2(a);
278
279	// unsigned long k = 1;
280	// of interest is only k_ind2, special routine for improvement ... TODO OLIVER
281	for (int i = 1; i <= leadRing->N; i++)
282	{
283	k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing));
284	}
285
286	a = (unsigned long) pGetCoeff(p);
287
288	number tmp1;
289	poly tmp2, tmp3;
290	poly lead_mult = p_ISet(1, tailRing);
291	if (n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
292	{
293	int too_much = k_ind2 + a_ind2 - n_GetChar(leadRing->cf);
294	int s_exp;
295	zeroPoly = p_ISet(a, tailRing);
296	for (int i = 1; i <= leadRing->N; i++)
297	{
298	s_exp = p_GetExp(p, i,leadRing);
299	if (s_exp % 2 != 0)
300	{
301	s_exp = s_exp - 1;
302	}
303	while ( (0 < ind2(s_exp)) && (ind2(s_exp) <= too_much) )
304	{
305	too_much = too_much - ind2(s_exp);
306	s_exp = s_exp - 2;
307	}
308	p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing) - s_exp, tailRing);
309	for (int j = 1; j <= s_exp; j++)
310	{
311	tmp1 = nInit(j);
312	tmp2 = p_ISet(1, tailRing);
313	p_SetExp(tmp2, i, 1, tailRing);
314	p_Setm(tmp2, tailRing);
315	if (nIsZero(tmp1))
316	{ // should nowbe obsolet, test ! TODO OLIVER
317	zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
318	}
319	else
320	{
321	tmp3 = p_NSet(nCopy(tmp1), tailRing);
322	zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing);
323	}
324	}
325	}
326	p_Setm(lead_mult, tailRing);
327	zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing);
328	tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing);
329	for (int i = 1; i <= leadRing->N; i++)
330	{
331	pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
332	}
333	p_Setm(tmp2, leadRing);
334	zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
335	pNext(tmp2) = zeroPoly;
336	return tmp2;
337	}
338	/* unsigned long alpha_k = twoPow(leadRing->ch - k_ind2);
339	if (1 == 0 && alpha_k <= a)
340	{ // Temporarly disabled, reducing coefficients not compatible with std TODO Oliver
341	zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing);
342	for (int i = 1; i <= leadRing->N; i++)
343	{
344	for (unsigned long j = 1; j <= p_GetExp(p, i, leadRing); j++)
345	{
346	tmp1 = nInit(j);
347	tmp2 = p_ISet(1, tailRing);
348	p_SetExp(tmp2, i, 1, tailRing);
349	p_Setm(tmp2, tailRing);
350	if (nIsZero(tmp1))
351	{
352	zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
353	}
354	else
355	{
356	tmp3 = p_ISet((unsigned long) tmp1, tailRing);
357	zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing);
358	}
359	}
360	}
361	tmp2 = p_ISet((unsigned long) pGetCoeff(zeroPoly), leadRing);
362	for (int i = 1; i <= leadRing->N; i++)
363	{
364	pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
365	}
366	p_Setm(tmp2, leadRing);
367	zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
368	pNext(tmp2) = zeroPoly;
369	return tmp2;
370	} */
371	return NULL;
372	}
373	#endif
374
375
376	#ifdef HAVE_RINGS
377	/*2
378	* reduction procedure for the ring Z/2^m
379	*/
380	int redRing (LObject* h,kStrategy strat)
381	{
382	if (h->IsNull()) return 0; // spoly is zero (can only occure with zero divisors)
383	if (strat->tl<0) return 1;
384
385	int at/,i/;
386	long d;
387	int j = 0;
388	int pass = 0;
389	// poly zeroPoly = NULL;
390
391	// TODO warum SetpFDeg notwendig?
392	h->SetpFDeg();
393	assume(h->pFDeg() == h->FDeg);
394	long reddeg = h->GetpFDeg();
395
396	h->SetShortExpVector();
397	loop
398	{
399	j = kFindDivisibleByInT(strat, h);
400	if (j < 0)
401	{
402	// over ZZ: cleanup coefficients by complete reduction with monomials
403	postReduceByMon(h, strat);
404	if(nIsZero(pGetCoeff(h->p))) return 2;
405	j = kFindDivisibleByInT(strat, h);
406	if(j < 0)
407	{
408	if(strat->tl >= 0)
409	h->i_r1 = strat->tl;
410	else
411	h->i_r1 = -1;
412	if (h->GetLmTailRing() == NULL)
413	{
414	if (h->lcm!=NULL) pLmDelete(h->lcm);
415	h->Clear();
416	return 0;
417	}
418	return 1;
419	}
420	}
421	//enterT(*h, strat);
422	ksReducePoly(h, &(strat->T[j]), NULL, NULL, strat); // with debug output
423
424	if (h->GetLmTailRing() == NULL)
425	{
426	if (h->lcm!=NULL) pLmDelete(h->lcm);
427	#ifdef KDEBUG
428	h->lcm=NULL;
429	#endif
430	h->Clear();
431	return 0;
432	}
433	h->SetShortExpVector();
434	d = h->SetpFDeg();
435	/- try to reduce the s-polynomial -/
436	pass++;
437	if (!TEST_OPT_REDTHROUGH &&
438	(strat->Ll >= 0) && ((d > reddeg) \|\| (pass > strat->LazyPass)))
439	{
440	h->SetLmCurrRing();
441	if (strat->posInLDependsOnLength)
442	h->SetLength(strat->length_pLength);
443	at = strat->posInL(strat->L,strat->Ll,h,strat);
444	if (at <= strat->Ll)
445	{
446	#ifdef KDEBUG
447	if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
448	#endif
449	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
450	h->Clear();
451	return -1;
452	}
453	}
454	if (d != reddeg)
455	{
456	if (d >= (long)strat->tailRing->bitmask)
457	{
458	if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
459	{
460	strat->overflow=TRUE;
461	//Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
462	h->GetP();
463	at = strat->posInL(strat->L,strat->Ll,h,strat);
464	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
465	h->Clear();
466	return -1;
467	}
468	}
469	else if ((TEST_OPT_PROT) && (strat->Ll < 0))
470	{
471	Print(".%ld",d);mflush();
472	reddeg = d;
473	}
474	}
475	}
476	}
477	#endif
478
479	/*2
480	* reduction procedure for the homogeneous case
481	* and the case of a degree-ordering
482	*/
483	int redHomog (LObject* h,kStrategy strat)
484	{
485	if (strat->tl<0) return 1;
486	//if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
487	assume(h->FDeg == h->pFDeg());
488
489	poly h_p;
490	int i,j,at,pass, ii;
491	unsigned long not_sev;
492	// long reddeg,d;
493
494	pass = j = 0;
495	// d = reddeg = h->GetpFDeg();
496	h->SetShortExpVector();
497	int li;
498	h_p = h->GetLmTailRing();
499	not_sev = ~ h->sev;
500	loop
501	{
502	j = kFindDivisibleByInT(strat, h);
503	if (j < 0) return 1;
504
505	li = strat->T[j].pLength;
506	ii = j;
507	/*
508	* the polynomial to reduce with (up to the moment) is;
509	* pi with length li
510	*/
511	i = j;
512	#if 1
513	if (TEST_OPT_LENGTH)
514	loop
515	{
516	/- search the shortest possible with respect to length -/
517	i++;
518	if (i > strat->tl)
519	break;
520	if (li<=1)
521	break;
522	if ((strat->T[i].pLength < li)
523	&&
524	p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
525	h_p, not_sev, strat->tailRing))
526	{
527	/*
528	* the polynomial to reduce with is now;
529	*/
530	li = strat->T[i].pLength;
531	ii = i;
532	}
533	}
534	#endif
535
536	/*
537	* end of search: have to reduce with pi
538	*/
539	#ifdef KDEBUG
540	if (TEST_OPT_DEBUG)
541	{
542	PrintS("red:");
543	h->wrp();
544	PrintS(" with ");
545	strat->T[ii].wrp();
546	}
547	#endif
548	assume(strat->fromT == FALSE);
549
550	ksReducePoly(h, &(strat->T[ii]), NULL, NULL, strat);
551	#if SBA_PRINT_REDUCTION_STEPS
552	sba_interreduction_steps++;
553	#endif
554	#if SBA_PRINT_OPERATIONS
555	sba_interreduction_operations += pLength(strat->T[ii].p);
556	#endif
557
558	#ifdef KDEBUG
559	if (TEST_OPT_DEBUG)
560	{
561	PrintS("\nto ");
562	h->wrp();
563	PrintLn();
564	}
565	#endif
566
567	h_p = h->GetLmTailRing();
568	if (h_p == NULL)
569	{
570	if (h->lcm!=NULL) pLmFree(h->lcm);
571	#ifdef KDEBUG
572	h->lcm=NULL;
573	#endif
574	return 0;
575	}
576	h->SetShortExpVector();
577	not_sev = ~ h->sev;
578	/*
579	* try to reduce the s-polynomial h
580	*test first whether h should go to the lazyset L
581	*-if the degree jumps
582	*-if the number of pre-defined reductions jumps
583	*/
584	pass++;
585	if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
586	{
587	h->SetLmCurrRing();
588	at = strat->posInL(strat->L,strat->Ll,h,strat);
589	if (at <= strat->Ll)
590	{
591	int dummy=strat->sl;
592	if (kFindDivisibleByInS(strat, &dummy, h) < 0)
593	return 1;
594	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
595	#ifdef KDEBUG
596	if (TEST_OPT_DEBUG)
597	Print(" lazy: -> L%d\n",at);
598	#endif
599	h->Clear();
600	return -1;
601	}
602	}
603	}
604	}
605
606	KINLINE int ksReducePolyTailSig(LObject* PR, TObject* PW, LObject* Red)
607	{
608	BOOLEAN ret;
609	number coef;
610
611	assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
612	Red->HeadNormalize();
613	/*
614	printf("------------------------\n");
615	pWrite(Red->GetLmCurrRing());
616	*/
617	ret = ksReducePolySig(Red, PW, 1, NULL, &coef);
618
619
620	if (!ret)
621	{
622	if (! n_IsOne(coef, currRing->cf))
623	{
624	PR->Mult_nn(coef);
625	// HANNES: mark for Normalize
626	}
627	n_Delete(&coef, currRing->cf);
628	}
629	return ret;
630	}
631
632	/*2
633	* reduction procedure for signature-based standard
634	* basis algorithms:
635	* all reductions have to be sig-safe!
636	*
637	* 2 is returned if and only if the pair is rejected by the rewritten criterion
638	* at exactly this point of the computations. This is the last possible point
639	* such a check can be done => checks with the biggest set of available
640	* signatures
641	*/
642	int redSig (LObject* h,kStrategy strat)
643	{
644	if (strat->tl<0) return 1;
645	//if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
646	//printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
647	assume(h->FDeg == h->pFDeg());
648	//#if 1
649	#ifdef DEBUGF5
650	Print("------- IN REDSIG -------\n");
651	Print("p: ");
652	pWrite(pHead(h->p));
653	Print("p1: ");
654	pWrite(pHead(h->p1));
655	Print("p2: ");
656	pWrite(pHead(h->p2));
657	Print("---------------------------\n");
658	#endif
659	poly h_p;
660	int i,j,at,pass, ii;
661	int start=0;
662	int sigSafe;
663	unsigned long not_sev;
664	// long reddeg,d;
665
666	pass = j = 0;
667	// d = reddeg = h->GetpFDeg();
668	h->SetShortExpVector();
669	int li;
670	h_p = h->GetLmTailRing();
671	not_sev = ~ h->sev;
672	loop
673	{
674	j = kFindDivisibleByInT(strat, h, start);
675	if (j < 0)
676	{
677	return 1;
678	}
679
680	li = strat->T[j].pLength;
681	ii = j;
682	/*
683	* the polynomial to reduce with (up to the moment) is;
684	* pi with length li
685	*/
686	i = j;
687	#if 1
688	if (TEST_OPT_LENGTH)
689	loop
690	{
691	/- search the shortest possible with respect to length -/
692	i++;
693	if (i > strat->tl)
694	break;
695	if (li<=1)
696	break;
697	if ((strat->T[i].pLength < li)
698	&&
699	p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
700	h_p, not_sev, strat->tailRing))
701	{
702	/*
703	* the polynomial to reduce with is now;
704	*/
705	li = strat->T[i].pLength;
706	ii = i;
707	}
708	}
709	start = ii+1;
710	#endif
711
712	/*
713	* end of search: have to reduce with pi
714	*/
715	#ifdef KDEBUG
716	if (TEST_OPT_DEBUG)
717	{
718	PrintS("red:");
719	h->wrp();
720	PrintS(" with ");
721	strat->T[ii].wrp();
722	}
723	#endif
724	assume(strat->fromT == FALSE);
725	//#if 1
726	#ifdef DEBUGF5
727	Print("BEFORE REDUCTION WITH %d:\n",ii);
728	Print("--------------------------------\n");
729	pWrite(h->sig);
730	pWrite(strat->T[ii].sig);
731	pWrite(h->GetLmCurrRing());
732	pWrite(pHead(h->p1));
733	pWrite(pHead(h->p2));
734	pWrite(pHead(strat->T[ii].p));
735	Print("--------------------------------\n");
736	printf("INDEX OF REDUCER T: %d\n",ii);
737	#endif
738	sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
739	#if SBA_PRINT_REDUCTION_STEPS
740	if (sigSafe != 3)
741	sba_reduction_steps++;
742	#endif
743	#if SBA_PRINT_OPERATIONS
744	if (sigSafe != 3)
745	sba_operations += pLength(strat->T[ii].p);
746	#endif
747	// if reduction has taken place, i.e. the reduction was sig-safe
748	// otherwise start is already at the next position and the loop
749	// searching reducers in T goes on from index start
750	//#if 1
751	#ifdef DEBUGF5
752	Print("SigSAFE: %d\n",sigSafe);
753	#endif
754	if (sigSafe != 3)
755	{
756	// start the next search for reducers in T from the beginning
757	start = 0;
758	#ifdef KDEBUG
759	if (TEST_OPT_DEBUG)
760	{
761	PrintS("\nto ");
762	h->wrp();
763	PrintLn();
764	}
765	#endif
766
767	h_p = h->GetLmTailRing();
768	if (h_p == NULL)
769	{
770	if (h->lcm!=NULL) pLmFree(h->lcm);
771	#ifdef KDEBUG
772	h->lcm=NULL;
773	#endif
774	return 0;
775	}
776	h->SetShortExpVector();
777	not_sev = ~ h->sev;
778	/*
779	* try to reduce the s-polynomial h
780	*test first whether h should go to the lazyset L
781	*-if the degree jumps
782	*-if the number of pre-defined reductions jumps
783	*/
784	pass++;
785	if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
786	{
787	h->SetLmCurrRing();
788	at = strat->posInL(strat->L,strat->Ll,h,strat);
789	if (at <= strat->Ll)
790	{
791	int dummy=strat->sl;
792	if (kFindDivisibleByInS(strat, &dummy, h) < 0)
793	{
794	return 1;
795	}
796	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
797	#ifdef KDEBUG
798	if (TEST_OPT_DEBUG)
799	Print(" lazy: -> L%d\n",at);
800	#endif
801	h->Clear();
802	return -1;
803	}
804	}
805	}
806	}
807	}
808
809	// tail reduction for SBA
810	poly redtailSba (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
811	{
812	#define REDTAIL_CANONICALIZE 100
813	strat->redTailChange=FALSE;
814	if (strat->noTailReduction) return L->GetLmCurrRing();
815	poly h, p;
816	p = h = L->GetLmTailRing();
817	if ((h==NULL) \|\| (pNext(h)==NULL))
818	return L->GetLmCurrRing();
819
820	TObject* With;
821	// placeholder in case strat->tl < 0
822	TObject With_s(strat->tailRing);
823
824	LObject Ln(pNext(h), strat->tailRing);
825	Ln.sig = L->sig;
826	Ln.sevSig = L->sevSig;
827	Ln.pLength = L->GetpLength() - 1;
828
829	pNext(h) = NULL;
830	if (L->p != NULL) pNext(L->p) = NULL;
831	L->pLength = 1;
832
833	Ln.PrepareRed(strat->use_buckets);
834
835	int cnt=REDTAIL_CANONICALIZE;
836	while(!Ln.IsNull())
837	{
838	loop
839	{
840	Ln.SetShortExpVector();
841	if (withT)
842	{
843	int j;
844	j = kFindDivisibleByInT(strat, &Ln);
845	if (j < 0) break;
846	With = &(strat->T[j]);
847	}
848	else
849	{
850	With = kFindDivisibleByInS(strat, pos, &Ln, &With_s);
851	if (With == NULL) break;
852	}
853	cnt--;
854	if (cnt==0)
855	{
856	cnt=REDTAIL_CANONICALIZE;
857	/poly tmp=/Ln.CanonicalizeP();
858	if (normalize)
859	{
860	Ln.Normalize();
861	//pNormalize(tmp);
862	//if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
863	}
864	}
865	if (normalize && (!TEST_OPT_INTSTRATEGY) && (!nIsOne(pGetCoeff(With->p))))
866	{
867	With->pNorm();
868	}
869	strat->redTailChange=TRUE;
870	int ret = ksReducePolyTailSig(L, With, &Ln);
871	#if SBA_PRINT_REDUCTION_STEPS
872	if (ret != 3)
873	sba_reduction_steps++;
874	#endif
875	#if SBA_PRINT_OPERATIONS
876	if (ret != 3)
877	sba_operations += pLength(With->p);
878	#endif
879	if (ret)
880	{
881	// reducing the tail would violate the exp bound
882	// set a flag and hope for a retry (in bba)
883	strat->completeReduce_retry=TRUE;
884	if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
885	do
886	{
887	pNext(h) = Ln.LmExtractAndIter();
888	pIter(h);
889	L->pLength++;
890	} while (!Ln.IsNull());
891	goto all_done;
892	}
893	if (Ln.IsNull()) goto all_done;
894	if (! withT) With_s.Init(currRing);
895	}
896	pNext(h) = Ln.LmExtractAndIter();
897	pIter(h);
898	pNormalize(h);
899	L->pLength++;
900	}
901
902	all_done:
903	Ln.Delete();
904	if (L->p != NULL) pNext(L->p) = pNext(p);
905
906	if (strat->redTailChange)
907	{
908	L->length = 0;
909	}
910
911	//if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
912	//L->Normalize(); // HANNES: should have a test
913	kTest_L(L);
914	return L->GetLmCurrRing();
915	}
916
917	/*2
918	* reduction procedure for the inhomogeneous case
919	* and not a degree-ordering
920	*/
921	int redLazy (LObject* h,kStrategy strat)
922	{
923	if (strat->tl<0) return 1;
924	int at,i,ii,li;
925	int j = 0;
926	int pass = 0;
927	assume(h->pFDeg() == h->FDeg);
928	long reddeg = h->GetpFDeg();
929	long d;
930	unsigned long not_sev;
931
932	h->SetShortExpVector();
933	poly h_p = h->GetLmTailRing();
934	not_sev = ~ h->sev;
935	loop
936	{
937	j = kFindDivisibleByInT(strat, h);
938	if (j < 0) return 1;
939
940	li = strat->T[j].pLength;
941	#if 0
942	if (li==0)
943	{
944	li=strat->T[j].pLength=pLength(strat->T[j].p);
945	}
946	#endif
947	ii = j;
948	/*
949	* the polynomial to reduce with (up to the moment) is;
950	* pi with length li
951	*/
952
953	i = j;
954	#if 1
955	if (TEST_OPT_LENGTH)
956	loop
957	{
958	/- search the shortest possible with respect to length -/
959	i++;
960	if (i > strat->tl)
961	break;
962	if (li<=1)
963	break;
964	#if 0
965	if (strat->T[i].pLength==0)
966	{
967	PrintS("!");
968	strat->T[i].pLength=pLength(strat->T[i].p);
969	}
970	#endif
971	if ((strat->T[i].pLength < li)
972	&&
973	p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
974	h_p, not_sev, strat->tailRing))
975	{
976	/*
977	* the polynomial to reduce with is now;
978	*/
979	PrintS("+");
980	li = strat->T[i].pLength;
981	ii = i;
982	}
983	}
984	#endif
985
986	/*
987	* end of search: have to reduce with pi
988	*/
989
990
991	#ifdef KDEBUG
992	if (TEST_OPT_DEBUG)
993	{
994	PrintS("red:");
995	h->wrp();
996	PrintS(" with ");
997	strat->T[ii].wrp();
998	}
999	#endif
1000
1001	ksReducePoly(h, &(strat->T[ii]), NULL, NULL, strat);
1002	#if SBA_PRINT_REDUCTION_STEPS
1003	sba_interreduction_steps++;
1004	#endif
1005	#if SBA_PRINT_OPERATIONS
1006	sba_interreduction_operations += pLength(strat->T[ii].p);
1007	#endif
1008
1009	#ifdef KDEBUG
1010	if (TEST_OPT_DEBUG)
1011	{
1012	PrintS("\nto ");
1013	h->wrp();
1014	PrintLn();
1015	}
1016	#endif
1017
1018	h_p=h->GetLmTailRing();
1019
1020	if (h_p == NULL)
1021	{
1022	if (h->lcm!=NULL) pLmFree(h->lcm);
1023	#ifdef KDEBUG
1024	h->lcm=NULL;
1025	#endif
1026	return 0;
1027	}
1028	h->SetShortExpVector();
1029	not_sev = ~ h->sev;
1030	d = h->SetpFDeg();
1031	/- try to reduce the s-polynomial -/
1032	pass++;
1033	if (//!TEST_OPT_REDTHROUGH &&
1034	(strat->Ll >= 0) && ((d > reddeg) \|\| (pass > strat->LazyPass)))
1035	{
1036	h->SetLmCurrRing();
1037	at = strat->posInL(strat->L,strat->Ll,h,strat);
1038	if (at <= strat->Ll)
1039	{
1040	#if 1
1041	int dummy=strat->sl;
1042	if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1043	return 1;
1044	#endif
1045	#ifdef KDEBUG
1046	if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
1047	#endif
1048	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1049	h->Clear();
1050	return -1;
1051	}
1052	}
1053	else if (d != reddeg)
1054	{
1055	if (d>=(long)strat->tailRing->bitmask)
1056	{
1057	if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
1058	{
1059	strat->overflow=TRUE;
1060	//Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1061	h->GetP();
1062	at = strat->posInL(strat->L,strat->Ll,h,strat);
1063	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1064	h->Clear();
1065	return -1;
1066	}
1067	}
1068	else if ((TEST_OPT_PROT) && (strat->Ll < 0))
1069	{
1070	Print(".%ld",d);mflush();
1071	reddeg = d;
1072	}
1073	}
1074	}
1075	}
1076	/*2
1077	* reduction procedure for the sugar-strategy (honey)
1078	* reduces h with elements from T choosing first possible
1079	* element in T with respect to the given ecart
1080	*/
1081	int redHoney (LObject* h, kStrategy strat)
1082	{
1083	if (strat->tl<0) return 1;
1084	//if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
1085	assume(h->FDeg == h->pFDeg());
1086	poly h_p;
1087	int i,j,at,pass,ei, ii, h_d;
1088	unsigned long not_sev;
1089	long reddeg,d;
1090
1091	pass = j = 0;
1092	d = reddeg = h->GetpFDeg() + h->ecart;
1093	h->SetShortExpVector();
1094	int li;
1095	h_p = h->GetLmTailRing();
1096	not_sev = ~ h->sev;
1097
1098	h->PrepareRed(strat->use_buckets);
1099	loop
1100	{
1101	j=kFindDivisibleByInT(strat, h);
1102	if (j < 0) return 1;
1103
1104	ei = strat->T[j].ecart;
1105	li = strat->T[j].pLength;
1106	ii = j;
1107	/*
1108	* the polynomial to reduce with (up to the moment) is;
1109	* pi with ecart ei
1110	*/
1111	i = j;
1112	if (TEST_OPT_LENGTH)
1113	loop
1114	{
1115	/- takes the first possible with respect to ecart -/
1116	i++;
1117	if (i > strat->tl)
1118	break;
1119	//if (ei < h->ecart)
1120	// break;
1121	if (li<=1)
1122	break;
1123	if ((((strat->T[i].ecart < ei) && (ei> h->ecart))
1124	\|\| ((strat->T[i].ecart <= h->ecart) && (strat->T[i].pLength < li)))
1125	&&
1126	p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
1127	h_p, not_sev, strat->tailRing))
1128	{
1129	/*
1130	* the polynomial to reduce with is now;
1131	*/
1132	ei = strat->T[i].ecart;
1133	li = strat->T[i].pLength;
1134	ii = i;
1135	}
1136	}
1137
1138	/*
1139	* end of search: have to reduce with pi
1140	*/
1141	if (!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h->ecart))
1142	{
1143	h->GetTP(); // clears bucket
1144	h->SetLmCurrRing();
1145	/*
1146	* It is not possible to reduce h with smaller ecart;
1147	* if possible h goes to the lazy-set L,i.e
1148	* if its position in L would be not the last one
1149	*/
1150	if (strat->Ll >= 0) /* L is not empty */
1151	{
1152	at = strat->posInL(strat->L,strat->Ll,h,strat);
1153	if(at <= strat->Ll)
1154	/- h will not become the next element to reduce -/
1155	{
1156	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1157	#ifdef KDEBUG
1158	if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
1159	#endif
1160	h->Clear();
1161	return -1;
1162	}
1163	}
1164	}
1165	#ifdef KDEBUG
1166	if (TEST_OPT_DEBUG)
1167	{
1168	PrintS("red:");
1169	h->wrp();
1170	PrintS(" with ");
1171	strat->T[ii].wrp();
1172	}
1173	#endif
1174	assume(strat->fromT == FALSE);
1175
1176	number coef;
1177	ksReducePoly(h,&(strat->T[ii]),strat->kNoetherTail(),&coef,strat);
1178	#if SBA_PRINT_REDUCTION_STEPS
1179	sba_interreduction_steps++;
1180	#endif
1181	#if SBA_PRINT_OPERATIONS
1182	sba_interreduction_operations += pLength(strat->T[ii].p);
1183	#endif
1184	#ifdef KDEBUG
1185	if (TEST_OPT_DEBUG)
1186	{
1187	PrintS("\nto:");
1188	h->wrp();
1189	PrintLn();
1190	}
1191	#endif
1192	if(h->IsNull())
1193	{
1194	h->Clear();
1195	if (h->lcm!=NULL) pLmFree(h->lcm);
1196	#ifdef KDEBUG
1197	h->lcm=NULL;
1198	#endif
1199	return 0;
1200	}
1201	if (TEST_OPT_IDLIFT)
1202	{
1203	if (h->p!=NULL)
1204	{
1205	if(p_GetComp(h->p,currRing)>strat->syzComp)
1206	{
1207	h->Delete();
1208	return 0;
1209	}
1210	}
1211	else if (h->t_p!=NULL)
1212	{
1213	if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
1214	{
1215	h->Delete();
1216	return 0;
1217	}
1218	}
1219	}
1220	h->SetShortExpVector();
1221	not_sev = ~ h->sev;
1222	h_d = h->SetpFDeg();
1223	/* compute the ecart */
1224	if (ei <= h->ecart)
1225	h->ecart = d-h_d;
1226	else
1227	h->ecart = d-h_d+ei-h->ecart;
1228
1229	/*
1230	* try to reduce the s-polynomial h
1231	*test first whether h should go to the lazyset L
1232	*-if the degree jumps
1233	*-if the number of pre-defined reductions jumps
1234	*/
1235	pass++;
1236	d = h_d + h->ecart;
1237	if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && ((d > reddeg) \|\| (pass > strat->LazyPass)))
1238	{
1239	h->GetTP(); // clear bucket
1240	h->SetLmCurrRing();
1241	at = strat->posInL(strat->L,strat->Ll,h,strat);
1242	if (at <= strat->Ll)
1243	{
1244	int dummy=strat->sl;
1245	if (kFindDivisibleByInS(strat, &dummy, h) < 0)
1246	return 1;
1247	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1248	#ifdef KDEBUG
1249	if (TEST_OPT_DEBUG)
1250	Print(" degree jumped: -> L%d\n",at);
1251	#endif
1252	h->Clear();
1253	return -1;
1254	}
1255	}
1256	else if (d > reddeg)
1257	{
1258	if (d>=(long)strat->tailRing->bitmask)
1259	{
1260	if (h->pTotalDeg()+h->ecart >= (long)strat->tailRing->bitmask)
1261	{
1262	strat->overflow=TRUE;
1263	//Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
1264	h->GetP();
1265	at = strat->posInL(strat->L,strat->Ll,h,strat);
1266	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
1267	h->Clear();
1268	return -1;
1269	}
1270	}
1271	else if (TEST_OPT_PROT && (strat->Ll < 0) )
1272	{
1273	//h->wrp(); Print("<%d>\n",h->GetpLength());
1274	reddeg = d;
1275	Print(".%ld",d); mflush();
1276	}
1277	}
1278	}
1279	}
1280
1281	/*2
1282	* reduction procedure for the normal form
1283	*/
1284
1285	poly redNF (poly h,int &max_ind,int nonorm,kStrategy strat)
1286	{
1287	if (h==NULL) return NULL;
1288	int j;
1289	max_ind=strat->sl;
1290
1291	if (0 > strat->sl)
1292	{
1293	return h;
1294	}
1295	LObject P(h);
1296	P.SetShortExpVector();
1297	P.bucket = kBucketCreate(currRing);
1298	kBucketInit(P.bucket,P.p,pLength(P.p));
1299	kbTest(P.bucket);
1300	#ifdef HAVE_RINGS
1301	BOOLEAN is_ring = rField_is_Ring(currRing);
1302	#endif
1303	#ifdef KDEBUG
1304	// if (TEST_OPT_DEBUG)
1305	// {
1306	// PrintS("redNF: starting S:\n");
1307	// for( j = 0; j <= max_ind; j++ )
1308	// {
1309	// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1310	// pWrite(strat->S[j]);
1311	// }
1312	// };
1313	#endif
1314
1315	loop
1316	{
1317	j=kFindDivisibleByInS(strat,&max_ind,&P);
1318	if (j>=0)
1319	{
1320	#ifdef HAVE_RINGS
1321	if (!is_ring)
1322	{
1323	#endif
1324	int sl=pSize(strat->S[j]);
1325	int jj=j;
1326	loop
1327	{
1328	int sll;
1329	jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
1330	if (jj<0) break;
1331	sll=pSize(strat->S[jj]);
1332	if (sll<sl)
1333	{
1334	#ifdef KDEBUG
1335	if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
1336	#endif
1337	//else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
1338	j=jj;
1339	sl=sll;
1340	}
1341	}
1342	if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
1343	{
1344	pNorm(strat->S[j]);
1345	//if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
1346	}
1347	#ifdef HAVE_RINGS
1348	}
1349	#endif
1350	nNormalize(pGetCoeff(P.p));
1351	#ifdef KDEBUG
1352	if (TEST_OPT_DEBUG)
1353	{
1354	PrintS("red:");
1355	wrp(h);
1356	PrintS(" with ");
1357	wrp(strat->S[j]);
1358	}
1359	#endif
1360	#ifdef HAVE_PLURAL
1361	if (rIsPluralRing(currRing))
1362	{
1363	number coef;
1364	nc_kBucketPolyRed(P.bucket,strat->S[j],&coef);
1365	nDelete(&coef);
1366	}
1367	else
1368	#endif
1369	{
1370	number coef;
1371	coef=kBucketPolyRed(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
1372	nDelete(&coef);
1373	}
1374	h = kBucketGetLm(P.bucket); // FRAGE OLIVER
1375	if (h==NULL)
1376	{
1377	kBucketDestroy(&P.bucket);
1378
1379	#ifdef KDEBUG
1380	// if (TEST_OPT_DEBUG)
1381	// {
1382	// PrintS("redNF: starting S:\n");
1383	// for( j = 0; j <= max_ind; j++ )
1384	// {
1385	// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1386	// pWrite(strat->S[j]);
1387	// }
1388	// };
1389	#endif
1390
1391	return NULL;
1392	}
1393	kbTest(P.bucket);
1394	P.p=h;
1395	P.t_p=NULL;
1396	P.SetShortExpVector();
1397	#ifdef KDEBUG
1398	if (TEST_OPT_DEBUG)
1399	{
1400	PrintS("\nto:");
1401	wrp(h);
1402	PrintLn();
1403	}
1404	#endif
1405	}
1406	else
1407	{
1408	P.p=kBucketClear(P.bucket);
1409	kBucketDestroy(&P.bucket);
1410	pNormalize(P.p);
1411
1412	#ifdef KDEBUG
1413	// if (TEST_OPT_DEBUG)
1414	// {
1415	// PrintS("redNF: starting S:\n");
1416	// for( j = 0; j <= max_ind; j++ )
1417	// {
1418	// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
1419	// pWrite(strat->S[j]);
1420	// }
1421	// };
1422	#endif
1423
1424	return P.p;
1425	}
1426	}
1427	}
1428
1429	void kDebugPrint(kStrategy strat);
1430
1431	ideal bba (ideal F, ideal Q,intvec w,intvec hilb,kStrategy strat)
1432	{
1433	int red_result = 1;
1434	int olddeg,reduc;
1435	int hilbeledeg=1,hilbcount=0,minimcnt=0;
1436	BOOLEAN withT = FALSE;
1437	BITSET save;
1438	SI_SAVE_OPT1(save);
1439
1440	initBuchMoraCrit(strat); /set Gebauer, honey, sugarCrit/
1441	initBuchMoraPos(strat);
1442	initHilbCrit(F,Q,&hilb,strat);
1443	initBba(strat);
1444	/set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair/
1445	/Shdl=/initBuchMora(F, Q,strat);
1446	if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
1447	reduc = olddeg = 0;
1448
1449	#ifndef NO_BUCKETS
1450	if (!TEST_OPT_NOT_BUCKETS)
1451	strat->use_buckets = 1;
1452	#endif
1453	// redtailBBa against T for inhomogenous input
1454	if (!TEST_OPT_OLDSTD)
1455	withT = ! strat->homog;
1456
1457	// strat->posInT = posInT_pLength;
1458	kTest_TS(strat);
1459
1460	#ifdef HAVE_TAIL_RING
1461	if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
1462	kStratInitChangeTailRing(strat);
1463	#endif
1464	if (BVERBOSE(23))
1465	{
1466	if (test_PosInT!=NULL) strat->posInT=test_PosInT;
1467	if (test_PosInL!=NULL) strat->posInL=test_PosInL;
1468	kDebugPrint(strat);
1469	}
1470
1471
1472	#ifdef KDEBUG
1473	//kDebugPrint(strat);
1474	#endif
1475	/* compute------------------------------------------------------- */
1476	while (strat->Ll >= 0)
1477	{
1478	#ifdef KDEBUG
1479	if (TEST_OPT_DEBUG) messageSets(strat);
1480	#endif
1481	if (strat->Ll== 0) strat->interpt=TRUE;
1482	if (TEST_OPT_DEGBOUND
1483	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1484	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
1485	{
1486	/*
1487	*stops computation if
1488	* 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
1489	*a predefined number Kstd1_deg
1490	*/
1491	while ((strat->Ll >= 0)
1492	&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1493	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1494	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
1495	)
1496	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1497	if (strat->Ll<0) break;
1498	else strat->noClearS=TRUE;
1499	}
1500	/* picks the last element from the lazyset L */
1501	strat->P = strat->L[strat->Ll];
1502	strat->Ll--;
1503
1504	if (pNext(strat->P.p) == strat->tail)
1505	{
1506	// deletes the short spoly
1507	if (rField_is_Ring(currRing))
1508	pLmDelete(strat->P.p);
1509	else
1510	pLmFree(strat->P.p);
1511	strat->P.p = NULL;
1512	poly m1 = NULL, m2 = NULL;
1513
1514	// check that spoly creation is ok
1515	while (strat->tailRing != currRing &&
1516	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1517	{
1518	assume(m1 == NULL && m2 == NULL);
1519	// if not, change to a ring where exponents are at least
1520	// large enough
1521	if (!kStratChangeTailRing(strat))
1522	{
1523	WerrorS("OVERFLOW...");
1524	break;
1525	}
1526	}
1527	// create the real one
1528	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
1529	strat->tailRing, m1, m2, strat->R);
1530	}
1531	else if (strat->P.p1 == NULL)
1532	{
1533	if (strat->minim > 0)
1534	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
1535	// for input polys, prepare reduction
1536	strat->P.PrepareRed(strat->use_buckets);
1537	}
1538
1539	if (strat->P.p == NULL && strat->P.t_p == NULL)
1540	{
1541	red_result = 0;
1542	}
1543	else
1544	{
1545	if (TEST_OPT_PROT)
1546	message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
1547	&olddeg,&reduc,strat, red_result);
1548
1549	/* reduction of the element chosen from L */
1550	red_result = strat->red(&strat->P,strat);
1551	if (errorreported) break;
1552	}
1553
1554	if (strat->overflow)
1555	{
1556	if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
1557	}
1558
1559	// reduction to non-zero new poly
1560	if (red_result == 1)
1561	{
1562	// get the polynomial (canonicalize bucket, make sure P.p is set)
1563	strat->P.GetP(strat->lmBin);
1564	// in the homogeneous case FDeg >= pFDeg (sugar/honey)
1565	// but now, for entering S, T, we reset it
1566	// in the inhomogeneous case: FDeg == pFDeg
1567	if (strat->homog) strat->initEcart(&(strat->P));
1568
1569	/* statistic */
1570	if (TEST_OPT_PROT) PrintS("s");
1571
1572	int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
1573
1574	// reduce the tail and normalize poly
1575	// in the ring case we cannot expect LC(f) = 1,
1576	// therefore we call pContent instead of pNorm
1577	if ((TEST_OPT_INTSTRATEGY) \|\| (rField_is_Ring(currRing)))
1578	{
1579	strat->P.pCleardenom();
1580	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
1581	{
1582	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
1583	strat->P.pCleardenom();
1584	}
1585	}
1586	else
1587	{
1588	strat->P.pNorm();
1589	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
1590	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
1591	}
1592
1593	#ifdef KDEBUG
1594	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
1595	#endif /* KDEBUG */
1596
1597	// min_std stuff
1598	if ((strat->P.p1==NULL) && (strat->minim>0))
1599	{
1600	if (strat->minim==1)
1601	{
1602	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
1603	p_Delete(&strat->P.p2, currRing, strat->tailRing);
1604	}
1605	else
1606	{
1607	strat->M->m[minimcnt]=strat->P.p2;
1608	strat->P.p2=NULL;
1609	}
1610	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
1611	pNext(strat->M->m[minimcnt])
1612	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
1613	strat->tailRing, currRing,
1614	currRing->PolyBin);
1615	minimcnt++;
1616	}
1617
1618	// enter into S, L, and T
1619	if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
1620	{
1621	enterT(strat->P, strat);
1622	if (rField_is_Ring(currRing))
1623	superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
1624	else
1625	enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
1626	// posInS only depends on the leading term
1627	strat->enterS(strat->P, pos, strat, strat->tl);
1628	#if 0
1629	int pl=pLength(strat->P.p);
1630	if (pl==1)
1631	{
1632	//if (TEST_OPT_PROT)
1633	//PrintS("<1>");
1634	}
1635	else if (pl==2)
1636	{
1637	//if (TEST_OPT_PROT)
1638	//PrintS("<2>");
1639	}
1640	#endif
1641	}
1642	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
1643	// Print("[%d]",hilbeledeg);
1644	if (strat->P.lcm!=NULL)
1645	{
1646	if (rField_is_Ring(currRing)) pLmDelete(strat->P.lcm);
1647	else pLmFree(strat->P.lcm);
1648	strat->P.lcm=NULL;
1649	}
1650	if (strat->s_poly!=NULL)
1651	{
1652	// the only valid entries are: strat->P.p,
1653	// strat->tailRing (read-only, keep it)
1654	// (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
1655	if (strat->s_poly(strat))
1656	{
1657	// we are called AFTER enterS, i.e. if we change P
1658	// we have to add it also to S/T
1659	// and add pairs
1660	int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
1661	enterT(strat->P, strat);
1662	if (rField_is_Ring(currRing))
1663	superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
1664	else
1665	enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
1666	strat->enterS(strat->P, pos, strat, strat->tl);
1667	}
1668	}
1669	}
1670	else if (strat->P.p1 == NULL && strat->minim > 0)
1671	{
1672	p_Delete(&strat->P.p2, currRing, strat->tailRing);
1673	}
1674
1675	#ifdef KDEBUG
1676	memset(&(strat->P), 0, sizeof(strat->P));
1677	#endif /* KDEBUG */
1678	kTest_TS(strat);
1679	}
1680	#ifdef KDEBUG
1681	if (TEST_OPT_DEBUG) messageSets(strat);
1682	#endif /* KDEBUG */
1683
1684	if (TEST_OPT_SB_1)
1685	{
1686	if(!rField_is_Ring(currRing))
1687	{
1688	int k=1;
1689	int j;
1690	while(k<=strat->sl)
1691	{
1692	j=0;
1693	loop
1694	{
1695	if (j>=k) break;
1696	clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
1697	j++;
1698	}
1699	k++;
1700	}
1701	}
1702	}
1703	/* complete reduction of the standard basis--------- */
1704	if (TEST_OPT_REDSB)
1705	{
1706	completeReduce(strat);
1707	#ifdef HAVE_TAIL_RING
1708	if (strat->completeReduce_retry)
1709	{
1710	// completeReduce needed larger exponents, retry
1711	// to reduce with S (instead of T)
1712	// and in currRing (instead of strat->tailRing)
1713	cleanT(strat);strat->tailRing=currRing;
1714	int i;
1715	for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
1716	completeReduce(strat);
1717	}
1718	#endif
1719	}
1720	else if (TEST_OPT_PROT) PrintLn();
1721	if(nCoeff_is_Ring_Z(currRing->cf))
1722	finalReduceByMon(strat);
1723	if(rField_is_Ring(currRing))
1724	{
1725	for(int i = 0;i<=strat->sl;i++)
1726	{
1727	if(!nGreaterZero(pGetCoeff(strat->S[i])))
1728	{
1729	strat->S[i] = pNeg(strat->S[i]);
1730	}
1731	}
1732	}
1733	/* release temp data-------------------------------- */
1734	exitBuchMora(strat);
1735	// if (TEST_OPT_WEIGHTM)
1736	// {
1737	// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
1738	// if (ecartWeights)
1739	// {
1740	// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
1741	// ecartWeights=NULL;
1742	// }
1743	// }
1744	if ((TEST_OPT_PROT) \|\| (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
1745	SI_RESTORE_OPT1(save);
1746	if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
1747
1748	idTest(strat->Shdl);
1749
1750	return (strat->Shdl);
1751	}
1752	ideal sba (ideal F0, ideal Q,intvec w,intvec hilb,kStrategy strat)
1753	{
1754	// ring order stuff:
1755	// in sba we have (until now) two possibilities:
1756	// 1. an incremental computation w.r.t. (C,monomial order)
1757	// 2. a (possibly non-incremental) computation w.r.t. the
1758	// induced Schreyer order.
1759	// The corresponding orders are computed in sbaRing(), depending
1760	// on the flag strat->sbaOrder
1761	#if SBA_PRINT_ZERO_REDUCTIONS
1762	long zeroreductions = 0;
1763	#endif
1764	#if SBA_PRINT_PRODUCT_CRITERION
1765	long product_criterion = 0;
1766	#endif
1767	#if SBA_PRINT_SIZE_G
1768	int size_g = 0;
1769	int size_g_non_red = 0;
1770	#endif
1771	#if SBA_PRINT_SIZE_SYZ
1772	long size_syz = 0;
1773	#endif
1774	// global variable
1775	#if SBA_PRINT_REDUCTION_STEPS
1776	sba_reduction_steps = 0;
1777	sba_interreduction_steps = 0;
1778	#endif
1779	#if SBA_PRINT_OPERATIONS
1780	sba_operations = 0;
1781	sba_interreduction_operations = 0;
1782	#endif
1783
1784	ideal F1 = F0;
1785	ring sRing, currRingOld;
1786	currRingOld = currRing;
1787	if (strat->sbaOrder == 1 \|\| strat->sbaOrder == 3)
1788	{
1789	sRing = sbaRing(strat);
1790	if (sRing!=currRingOld)
1791	{
1792	rChangeCurrRing (sRing);
1793	F1 = idrMoveR (F0, currRingOld, currRing);
1794	}
1795	}
1796	// sort ideal F
1797	ideal F = idInit(IDELEMS(F1),F1->rank);
1798	intvec *sort = idSort(F1);
1799	for (int i=0; i<sort->length();++i)
1800	F->m[i] = F1->m[(*sort)[i]-1];
1801	#if SBA_INTERRED_START
1802	F = kInterRed(F,NULL);
1803	#endif
1804	#if F5DEBUG
1805	printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
1806	rWrite (currRing);
1807	printf("ordSgn = %d\n",currRing->OrdSgn);
1808	printf("\n");
1809	#endif
1810	int srmax,lrmax, red_result = 1;
1811	int olddeg,reduc;
1812	int hilbeledeg=1,hilbcount=0,minimcnt=0;
1813	LObject L;
1814	BOOLEAN withT = TRUE;
1815	strat->max_lower_index = 0;
1816
1817	//initBuchMoraCrit(strat); /set Gebauer, honey, sugarCrit/
1818	initSbaCrit(strat); /set Gebauer, honey, sugarCrit/
1819	initSbaPos(strat);
1820	//initBuchMoraPos(strat);
1821	initHilbCrit(F,Q,&hilb,strat);
1822	initSba(F,strat);
1823	/set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair/
1824	/Shdl=/initSbaBuchMora(F, Q,strat);
1825	if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
1826	srmax = strat->sl;
1827	reduc = olddeg = lrmax = 0;
1828
1829	#ifndef NO_BUCKETS
1830	if (!TEST_OPT_NOT_BUCKETS)
1831	strat->use_buckets = 1;
1832	#endif
1833
1834	// redtailBBa against T for inhomogenous input
1835	// if (!TEST_OPT_OLDSTD)
1836	// withT = ! strat->homog;
1837
1838	// strat->posInT = posInT_pLength;
1839	kTest_TS(strat);
1840
1841	#ifdef HAVE_TAIL_RING
1842	if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
1843	kStratInitChangeTailRing(strat);
1844	#endif
1845	if (BVERBOSE(23))
1846	{
1847	if (test_PosInT!=NULL) strat->posInT=test_PosInT;
1848	if (test_PosInL!=NULL) strat->posInL=test_PosInL;
1849	kDebugPrint(strat);
1850	}
1851
1852
1853	#ifdef KDEBUG
1854	//kDebugPrint(strat);
1855	#endif
1856	/* compute------------------------------------------------------- */
1857	while (strat->Ll >= 0)
1858	{
1859	if (strat->Ll > lrmax) lrmax =strat->Ll;/stat./
1860	#ifdef KDEBUG
1861	if (TEST_OPT_DEBUG) messageSets(strat);
1862	#endif
1863	if (strat->Ll== 0) strat->interpt=TRUE;
1864	/*
1865	if (TEST_OPT_DEGBOUND
1866	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1867	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
1868	{
1869
1870	//stops computation if
1871	// 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
1872	//a predefined number Kstd1_deg
1873	while ((strat->Ll >= 0)
1874	&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1875	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
1876	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
1877	)
1878	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1879	if (strat->Ll<0) break;
1880	else strat->noClearS=TRUE;
1881	}
1882	*/
1883	if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
1884	{
1885	strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
1886	#if F5C
1887	// 1. interreduction of the current standard basis
1888	// 2. generation of new principal syzygy rules for syzCriterion
1889	f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
1890	lrmax, reduc, Q, w, hilb );
1891	#endif
1892	// initialize new syzygy rules for the next iteration step
1893	initSyzRules(strat);
1894
1895	}
1896	/*********************************************************************
1897	* interrreduction step is done, we can go on with the next iteration
1898	* step of the signature-based algorithm
1899	********************************************************************/
1900	/* picks the last element from the lazyset L */
1901	strat->P = strat->L[strat->Ll];
1902	strat->Ll--;
1903	/* reduction of the element chosen from L */
1904
1905	if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1)) {
1906	//#if 1
1907	#ifdef DEBUGF5
1908	Print("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
1909	Print("-------------------------------------------------\n");
1910	pWrite(strat->P.sig);
1911	pWrite(pHead(strat->P.p));
1912	pWrite(pHead(strat->P.p1));
1913	pWrite(pHead(strat->P.p2));
1914	Print("-------------------------------------------------\n");
1915	#endif
1916	if (pNext(strat->P.p) == strat->tail)
1917	{
1918	// deletes the short spoly
1919	/*
1920	if (rField_is_Ring(currRing))
1921	pLmDelete(strat->P.p);
1922	else
1923	pLmFree(strat->P.p);
1924	*/
1925	// TODO: needs some masking
1926	// TODO: masking needs to vanish once the signature
1927	// sutff is completely implemented
1928	strat->P.p = NULL;
1929	poly m1 = NULL, m2 = NULL;
1930
1931	// check that spoly creation is ok
1932	while (strat->tailRing != currRing &&
1933	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1934	{
1935	assume(m1 == NULL && m2 == NULL);
1936	// if not, change to a ring where exponents are at least
1937	// large enough
1938	if (!kStratChangeTailRing(strat))
1939	{
1940	WerrorS("OVERFLOW...");
1941	break;
1942	}
1943	}
1944	// create the real one
1945	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
1946	strat->tailRing, m1, m2, strat->R);
1947
1948	}
1949	else if (strat->P.p1 == NULL)
1950	{
1951	if (strat->minim > 0)
1952	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
1953	// for input polys, prepare reduction
1954	strat->P.PrepareRed(strat->use_buckets);
1955	}
1956	if (strat->P.p == NULL && strat->P.t_p == NULL)
1957	{
1958	red_result = 0;
1959	}
1960	else
1961	{
1962	//#if 1
1963	#ifdef DEBUGF5
1964	Print("Poly before red: ");
1965	pWrite(pHead(strat->P.p));
1966	pWrite(strat->P.sig);
1967	#endif
1968	#if SBA_PRODUCT_CRITERION
1969	if (strat->P.prod_crit) {
1970	#if SBA_PRINT_PRODUCT_CRITERION
1971	product_criterion++;
1972	#endif
1973	int pos = posInSyz(strat, strat->P.sig);
1974	enterSyz(strat->P, strat, pos);
1975	if (strat->P.lcm!=NULL)
1976	pLmFree(strat->P.lcm);
1977	red_result = 2;
1978	} else {
1979	red_result = strat->red(&strat->P,strat);
1980	}
1981	#else
1982	red_result = strat->red(&strat->P,strat);
1983	#endif
1984	}
1985	} else {
1986	/*
1987	if (strat->P.lcm != NULL)
1988	pLmFree(strat->P.lcm);
1989	*/
1990	red_result = 2;
1991	}
1992	if (errorreported) break;
1993
1994	//#if 1
1995	#ifdef DEBUGF5
1996	if (red_result != 0) {
1997	Print("Poly after red: ");
1998	pWrite(pHead(strat->P.p));
1999	pWrite(strat->P.GetLmCurrRing());
2000	pWrite(strat->P.sig);
2001	printf("%d\n",red_result);
2002	}
2003	#endif
2004
2005	if (strat->overflow)
2006	{
2007	if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
2008	}
2009
2010	// reduction to non-zero new poly
2011	if (red_result == 1)
2012	{
2013	// get the polynomial (canonicalize bucket, make sure P.p is set)
2014	strat->P.GetP(strat->lmBin);
2015
2016	// sig-safe computations may lead to wrong FDeg computation, thus we need
2017	// to recompute it to make sure everything is alright
2018	(strat->P).FDeg = (strat->P).pFDeg();
2019	// in the homogeneous case FDeg >= pFDeg (sugar/honey)
2020	// but now, for entering S, T, we reset it
2021	// in the inhomogeneous case: FDeg == pFDeg
2022	if (strat->homog) strat->initEcart(&(strat->P));
2023
2024	/* statistic */
2025	if (TEST_OPT_PROT) PrintS("s");
2026
2027	//int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2028	// in F5E we know that the last reduced element is already the
2029	// the one with highest signature
2030	int pos = strat->sl+1;
2031
2032	// reduce the tail and normalize poly
2033	// in the ring case we cannot expect LC(f) = 1,
2034	// therefore we call pContent instead of pNorm
2035	#if SBA_TAIL_RED
2036	if (strat->sbaOrder != 2) {
2037	if ((TEST_OPT_INTSTRATEGY) \|\| (rField_is_Ring(currRing)))
2038	{
2039	strat->P.pCleardenom();
2040	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
2041	{
2042	strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2043	strat->P.pCleardenom();
2044	}
2045	}
2046	else
2047	{
2048	strat->P.pNorm();
2049	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
2050	strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2051	}
2052	}
2053	#endif
2054
2055	// remove sigsafe label since it is no longer valid for the next element to
2056	// be reduced
2057	if (strat->sbaOrder == 1)
2058	{
2059	for (int jj = 0; jj<strat->tl+1; jj++)
2060	{
2061	if (pGetComp(strat->T[jj].sig) == strat->currIdx)
2062	{
2063	strat->T[jj].is_sigsafe = FALSE;
2064	}
2065	}
2066	}
2067	else
2068	{
2069	for (int jj = 0; jj<strat->tl+1; jj++)
2070	{
2071	strat->T[jj].is_sigsafe = FALSE;
2072	}
2073	}
2074	#ifdef KDEBUG
2075	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2076	#endif /* KDEBUG */
2077
2078	// min_std stuff
2079	if ((strat->P.p1==NULL) && (strat->minim>0))
2080	{
2081	if (strat->minim==1)
2082	{
2083	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2084	p_Delete(&strat->P.p2, currRing, strat->tailRing);
2085	}
2086	else
2087	{
2088	strat->M->m[minimcnt]=strat->P.p2;
2089	strat->P.p2=NULL;
2090	}
2091	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2092	pNext(strat->M->m[minimcnt])
2093	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2094	strat->tailRing, currRing,
2095	currRing->PolyBin);
2096	minimcnt++;
2097	}
2098
2099	// enter into S, L, and T
2100	//if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
2101	enterT(strat->P, strat);
2102	strat->T[strat->tl].is_sigsafe = FALSE;
2103	/*
2104	printf("hier\n");
2105	pWrite(strat->P.GetLmCurrRing());
2106	pWrite(strat->P.sig);
2107	*/
2108	if (rField_is_Ring(currRing))
2109	superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2110	else
2111	enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2112	// posInS only depends on the leading term
2113	strat->enterS(strat->P, pos, strat, strat->tl);
2114	if(strat->sbaOrder != 1)
2115	{
2116	BOOLEAN overwrite = FALSE;
2117	for (int tk=0; tk<strat->sl+1; tk++)
2118	{
2119	if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
2120	{
2121	//printf("TK %d / %d\n",tk,strat->sl);
2122	overwrite = FALSE;
2123	break;
2124	}
2125	}
2126	//printf("OVERWRITE %d\n",overwrite);
2127	if (overwrite)
2128	{
2129	int cmp = pGetComp(strat->P.sig);
2130	int* vv = (int)omAlloc((currRing->N+1)sizeof(int));
2131	pGetExpV (strat->P.p,vv);
2132	pSetExpV (strat->P.sig, vv);
2133	pSetComp (strat->P.sig,cmp);
2134
2135	strat->P.sevSig = pGetShortExpVector (strat->P.sig);
2136	int i;
2137	LObject Q;
2138	for(int ps=0;ps<strat->sl+1;ps++)
2139	{
2140
2141	strat->newt = TRUE;
2142	if (strat->syzl == strat->syzmax)
2143	{
2144	pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
2145	strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
2146	(strat->syzmax)*sizeof(unsigned long),
2147	((strat->syzmax)+setmaxTinc)
2148	*sizeof(unsigned long));
2149	strat->syzmax += setmaxTinc;
2150	}
2151	Q.sig = pCopy(strat->P.sig);
2152	// add LM(F->m[i]) to the signature to get a Schreyer order
2153	// without changing the underlying polynomial ring at all
2154	if (strat->sbaOrder == 0)
2155	p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
2156	// since p_Add_q() destroys all input
2157	// data we need to recreate help
2158	// each time
2159	// ----------------------------------------------------------
2160	// in the Schreyer order we always know that the multiplied
2161	// module monomial strat->P.sig gives the leading monomial of
2162	// the corresponding principal syzygy
2163	// => we do not need to compute the "real" syzygy completely
2164	poly help = p_Copy(strat->sig[ps],currRing);
2165	p_ExpVectorAdd (help,strat->P.p,currRing);
2166	Q.sig = p_Add_q(Q.sig,help,currRing);
2167	//printf("%d. SYZ ",i+1);
2168	//pWrite(strat->syz[i]);
2169	Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
2170	i = posInSyz(strat, Q.sig);
2171	enterSyz(Q, strat, i);
2172	}
2173	}
2174	}
2175	// deg - idx - lp/rp
2176	// => we need to add syzygies with indices > pGetComp(strat->P.sig)
2177	if(strat->sbaOrder == 0 \|\| strat->sbaOrder == 3)
2178	{
2179	int cmp = pGetComp(strat->P.sig);
2180	int max_cmp = IDELEMS(F);
2181	int* vv = (int)omAlloc((currRing->N+1)sizeof(int));
2182	pGetExpV (strat->P.p,vv);
2183	LObject Q;
2184	int pos;
2185	int idx = p_GetComp(strat->P.sig,currRing);
2186	//printf("++ -- adding syzygies -- ++\n");
2187	// if new element is the first one in this index
2188	if (strat->currIdx < idx) {
2189	for (int i=0; i<strat->sl; ++i) {
2190	Q.sig = p_Copy(strat->P.sig,currRing);
2191	p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
2192	poly help = p_Copy(strat->sig[i],currRing);
2193	p_ExpVectorAdd(help,strat->P.p,currRing);
2194	Q.sig = p_Add_q(Q.sig,help,currRing);
2195	//pWrite(Q.sig);
2196	pos = posInSyz(strat, Q.sig);
2197	enterSyz(Q, strat, pos);
2198	}
2199	strat->currIdx = idx;
2200	} else {
2201	// if the element is not the first one in the given index we build all
2202	// possible syzygies with elements of higher index
2203	for (int i=cmp+1; i<=max_cmp; ++i) {
2204	pos = -1;
2205	for (int j=0; j<strat->sl; ++j) {
2206	if (p_GetComp(strat->sig[j],currRing) == i) {
2207	pos = j;
2208	break;
2209	}
2210	}
2211	if (pos != -1) {
2212	Q.sig = p_One(currRing);
2213	p_SetExpV(Q.sig, vv, currRing);
2214	// F->m[i-1] corresponds to index i
2215	p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
2216	p_SetComp(Q.sig, i, currRing);
2217	poly help = p_Copy(strat->P.sig,currRing);
2218	p_ExpVectorAdd(help,strat->S[pos],currRing);
2219	Q.sig = p_Add_q(Q.sig,help,currRing);
2220	if (strat->sbaOrder == 0) {
2221	if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn) {
2222	pos = posInSyz(strat, Q.sig);
2223	enterSyz(Q, strat, pos);
2224	}
2225	} else {
2226	pos = posInSyz(strat, Q.sig);
2227	enterSyz(Q, strat, pos);
2228	}
2229	}
2230	}
2231	//printf("++ -- done adding syzygies -- ++\n");
2232	}
2233	}
2234	//#if 1
2235	#if DEBUGF50
2236	printf("---------------------------\n");
2237	Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
2238	Print("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
2239	Print("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
2240	#endif
2241	/*
2242	if (newrules)
2243	{
2244	newrules = FALSE;
2245	}
2246	*/
2247	#if 0
2248	int pl=pLength(strat->P.p);
2249	if (pl==1)
2250	{
2251	//if (TEST_OPT_PROT)
2252	//PrintS("<1>");
2253	}
2254	else if (pl==2)
2255	{
2256	//if (TEST_OPT_PROT)
2257	//PrintS("<2>");
2258	}
2259	#endif
2260	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2261	// Print("[%d]",hilbeledeg);
2262	if (strat->P.lcm!=NULL)
2263	#ifdef HAVE_RINGS
2264	pLmDelete(strat->P.lcm);
2265	#else
2266	pLmFree(strat->P.lcm);
2267	#endif
2268	if (strat->sl>srmax) srmax = strat->sl;
2269	}
2270	else
2271	{
2272	// adds signature of the zero reduction to
2273	// strat->syz. This is the leading term of
2274	// syzygy and can be used in syzCriterion()
2275	// the signature is added if and only if the
2276	// pair was not detected by the rewritten criterion in strat->red = redSig
2277	if (red_result!=2) {
2278	#if SBA_PRINT_ZERO_REDUCTIONS
2279	zeroreductions++;
2280	#endif
2281	int pos = posInSyz(strat, strat->P.sig);
2282	enterSyz(strat->P, strat, pos);
2283	//#if 1
2284	#ifdef DEBUGF5
2285	Print("ADDING STUFF TO SYZ : ");
2286	//pWrite(strat->P.p);
2287	pWrite(strat->P.sig);
2288	#endif
2289	}
2290	if (strat->P.p1 == NULL && strat->minim > 0)
2291	{
2292	p_Delete(&strat->P.p2, currRing, strat->tailRing);
2293	}
2294	}
2295
2296	#ifdef KDEBUG
2297	memset(&(strat->P), 0, sizeof(strat->P));
2298	#endif /* KDEBUG */
2299	kTest_TS(strat);
2300	}
2301	#ifdef KDEBUG
2302	if (TEST_OPT_DEBUG) messageSets(strat);
2303	#endif /* KDEBUG */
2304
2305	if (TEST_OPT_SB_1)
2306	{
2307	if(!rField_is_Ring(currRing))
2308	{
2309	int k=1;
2310	int j;
2311	while(k<=strat->sl)
2312	{
2313	j=0;
2314	loop
2315	{
2316	if (j>=k) break;
2317	clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
2318	j++;
2319	}
2320	k++;
2321	}
2322	}
2323	}
2324
2325	/* complete reduction of the standard basis--------- */
2326	if (TEST_OPT_REDSB)
2327	{
2328	completeReduce(strat);
2329	#ifdef HAVE_TAIL_RING
2330	if (strat->completeReduce_retry)
2331	{
2332	// completeReduce needed larger exponents, retry
2333	// to reduce with S (instead of T)
2334	// and in currRing (instead of strat->tailRing)
2335	cleanT(strat);strat->tailRing=currRing;
2336	int i;
2337	for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
2338	completeReduce(strat);
2339	}
2340	#endif
2341	}
2342	else if (TEST_OPT_PROT) PrintLn();
2343
2344	#if SBA_PRINT_SIZE_SYZ
2345	// that is correct, syzl is counting one too far
2346	size_syz = strat->syzl;
2347	#endif
2348	exitSba(strat);
2349	// if (TEST_OPT_WEIGHTM)
2350	// {
2351	// pRestoreDegProcs(pFDegOld, pLDegOld);
2352	// if (ecartWeights)
2353	// {
2354	// omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
2355	// ecartWeights=NULL;
2356	// }
2357	// }
2358	if (TEST_OPT_PROT) messageStat(hilbcount,strat);
2359	if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2360
2361	#if SBA_PRINT_SIZE_G
2362	size_g_non_red = IDELEMS(strat->Shdl);
2363	#endif
2364	if ((strat->sbaOrder == 1 \|\| strat->sbaOrder == 3) && sRing!=currRingOld)
2365	{
2366	rChangeCurrRing (currRingOld);
2367	F0 = idrMoveR (F1, sRing, currRing);
2368	strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
2369	rDelete (sRing);
2370	}
2371	id_DelDiv(strat->Shdl, currRing);
2372	idSkipZeroes(strat->Shdl);
2373	idTest(strat->Shdl);
2374
2375	#if SBA_PRINT_SIZE_G
2376	size_g = IDELEMS(strat->Shdl);
2377	#endif
2378	#ifdef DEBUGF5
2379	printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
2380	int oo = 0;
2381	while (oo<IDELEMS(strat->Shdl))
2382	{
2383	printf(" %d. ",oo+1);
2384	pWrite(pHead(strat->Shdl->m[oo]));
2385	oo++;
2386	}
2387	#endif
2388	#if SBA_PRINT_ZERO_REDUCTIONS
2389	printf("----------------------------------------------------------\n");
2390	printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
2391	zeroreductions = 0;
2392	#endif
2393	#if SBA_PRINT_REDUCTION_STEPS
2394	printf("----------------------------------------------------------\n");
2395	printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
2396	#endif
2397	#if SBA_PRINT_OPERATIONS
2398	printf("OPERATIONS: %ld\n",sba_operations);
2399	#endif
2400	#if SBA_PRINT_REDUCTION_STEPS
2401	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
2402	printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
2403	#endif
2404	#if SBA_PRINT_OPERATIONS
2405	printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
2406	#endif
2407	#if SBA_PRINT_REDUCTION_STEPS
2408	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
2409	printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
2410	sba_interreduction_steps = 0;
2411	sba_reduction_steps = 0;
2412	#endif
2413	#if SBA_PRINT_OPERATIONS
2414	printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
2415	sba_interreduction_operations = 0;
2416	sba_operations = 0;
2417	#endif
2418	#if SBA_PRINT_SIZE_G
2419	printf("----------------------------------------------------------\n");
2420	printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
2421	size_g = 0;
2422	size_g_non_red = 0;
2423	#endif
2424	#if SBA_PRINT_SIZE_SYZ
2425	printf("SIZE OF SYZ: %ld\n",size_syz);
2426	printf("----------------------------------------------------------\n");
2427	size_syz = 0;
2428	#endif
2429	#if SBA_PRINT_PRODUCT_CRITERION
2430	printf("PRODUCT CRITERIA: %ld\n",product_criterion);
2431	product_criterion = 0;
2432	#endif
2433	return (strat->Shdl);
2434	}
2435
2436	poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
2437	{
2438	assume(q!=NULL);
2439	assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
2440
2441	// lazy_reduce flags: can be combined by \|
2442	//#define KSTD_NF_LAZY 1
2443	// do only a reduction of the leading term
2444	//#define KSTD_NF_NONORM 4
2445	// only global: avoid normalization, return a multiply of NF
2446	poly p;
2447
2448	//if ((idIs0(F))&&(Q==NULL))
2449	// return pCopy(q); /F=0/
2450	//strat->ak = idRankFreeModule(F);
2451	/- creating temp data structures------------------- -/
2452	BITSET save1;
2453	SI_SAVE_OPT1(save1);
2454	si_opt_1\|=Sy_bit(OPT_REDTAIL);
2455	initBuchMoraCrit(strat);
2456	strat->initEcart = initEcartBBA;
2457	strat->enterS = enterSBba;
2458	#ifndef NO_BUCKETS
2459	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
2460	#endif
2461	/- set S -/
2462	strat->sl = -1;
2463	/- init local data struct.---------------------------------------- -/
2464	/Shdl=/initS(F,Q,strat);
2465	/- compute------------------------------------------------------- -/
2466	//if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
2467	//{
2468	// for (i=strat->sl;i>=0;i--)
2469	// pNorm(strat->S[i]);
2470	//}
2471	kTest(strat);
2472	if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2473	if (BVERBOSE(23)) kDebugPrint(strat);
2474	int max_ind;
2475	p = redNF(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
2476	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2477	{
2478	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2479	if (rField_is_Ring(currRing))
2480	{
2481	p = redtailBba_Z(p,max_ind,strat);
2482	}
2483	else
2484	{
2485	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
2486	p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
2487	}
2488	}
2489	/- release temp data------------------------------- -/
2490	assume(strat->L==NULL); /* strat->L unused */
2491	assume(strat->B==NULL); /* strat->B unused */
2492	omFree(strat->sevS);
2493	omFree(strat->ecartS);
2494	assume(strat->T==NULL);//omfree(strat->T);
2495	assume(strat->sevT==NULL);//omfree(strat->sevT);
2496	assume(strat->R==NULL);//omfree(strat->R);
2497	omfree(strat->S_2_R);
2498	omfree(strat->fromQ);
2499	idDelete(&strat->Shdl);
2500	SI_RESTORE_OPT1(save1);
2501	if (TEST_OPT_PROT) PrintLn();
2502	return p;
2503	}
2504
2505	ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
2506	{
2507	assume(!idIs0(q));
2508	assume(!(idIs0(F)&&(Q==NULL)));
2509	// lazy_reduce flags: can be combined by \|
2510	//#define KSTD_NF_LAZY 1
2511	// do only a reduction of the leading term
2512	//#define KSTD_NF_NONORM 4
2513	// only global: avoid normalization, return a multiply of NF
2514	poly p;
2515	int i;
2516	ideal res;
2517	int max_ind;
2518
2519	//if (idIs0(q))
2520	// return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2521	//if ((idIs0(F))&&(Q==NULL))
2522	// return idCopy(q); /F=0/
2523	//strat->ak = idRankFreeModule(F);
2524	/- creating temp data structures------------------- -/
2525	BITSET save1;
2526	SI_SAVE_OPT1(save1);
2527	si_opt_1\|=Sy_bit(OPT_REDTAIL);
2528	initBuchMoraCrit(strat);
2529	strat->initEcart = initEcartBBA;
2530	strat->enterS = enterSBba;
2531	/- set S -/
2532	strat->sl = -1;
2533	#ifndef NO_BUCKETS
2534	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
2535	#endif
2536	/- init local data struct.---------------------------------------- -/
2537	/Shdl=/initS(F,Q,strat);
2538	/- compute------------------------------------------------------- -/
2539	res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
2540	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
2541	for (i=IDELEMS(q)-1; i>=0; i--)
2542	{
2543	if (q->m[i]!=NULL)
2544	{
2545	if (TEST_OPT_PROT) { PrintS("r");mflush(); }
2546	p = redNF(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
2547	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2548	{
2549	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2550	if (rField_is_Ring(currRing))
2551	{
2552	p = redtailBba_Z(p,max_ind,strat);
2553	}
2554	else
2555	{
2556	p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
2557	}
2558	}
2559	res->m[i]=p;
2560	}
2561	//else
2562	// res->m[i]=NULL;
2563	}
2564	/- release temp data------------------------------- -/
2565	assume(strat->L==NULL); /* strat->L unused */
2566	assume(strat->B==NULL); /* strat->B unused */
2567	omFree(strat->sevS);
2568	omFree(strat->ecartS);
2569	assume(strat->T==NULL);//omfree(strat->T);
2570	assume(strat->sevT==NULL);//omfree(strat->sevT);
2571	assume(strat->R==NULL);//omfree(strat->R);
2572	omfree(strat->S_2_R);
2573	omfree(strat->fromQ);
2574	idDelete(&strat->Shdl);
2575	SI_RESTORE_OPT1(save1);
2576	if (TEST_OPT_PROT) PrintLn();
2577	return res;
2578	}
2579
2580	#if F5C
2581	/*********************************************************************
2582	* interrreduction step of the signature-based algorithm:
2583	* 1. all strat->S are interpreted as new critical pairs
2584	* 2. those pairs need to be completely reduced by the usual (non sig-
2585	* safe) reduction process (including tail reductions)
2586	* 3. strat->S and strat->T are completely new computed in these steps
2587	********************************************************************/
2588	void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
2589	int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
2590	intvec w,intvec hilb )
2591	{
2592	int Ll_old, red_result = 1;
2593	int pos = 0;
2594	hilbeledeg=1;
2595	hilbcount=0;
2596	minimcnt=0;
2597	srmax = 0; // strat->sl is 0 at this point
2598	reduc = olddeg = lrmax = 0;
2599	// we cannot use strat->T anymore
2600	//cleanT(strat);
2601	//strat->tl = -1;
2602	Ll_old = strat->Ll;
2603	while (strat->tl >= 0)
2604	{
2605	if(!strat->T[strat->tl].is_redundant)
2606	{
2607	LObject h;
2608	h.p = strat->T[strat->tl].p;
2609	h.tailRing = strat->T[strat->tl].tailRing;
2610	h.t_p = strat->T[strat->tl].t_p;
2611	if (h.p!=NULL)
2612	{
2613	if (currRing->OrdSgn==-1)
2614	{
2615	cancelunit(&h);
2616	deleteHC(&h, strat);
2617	}
2618	if (h.p!=NULL)
2619	{
2620	if (TEST_OPT_INTSTRATEGY)
2621	{
2622	//pContent(h.p);
2623	h.pCleardenom(); // also does a pContent
2624	}
2625	else
2626	{
2627	h.pNorm();
2628	}
2629	strat->initEcart(&h);
2630	pos = strat->Ll+1;
2631	h.sev = pGetShortExpVector(h.p);
2632	enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
2633	}
2634	}
2635	}
2636	strat->tl--;
2637	}
2638	strat->sl = -1;
2639	#if 0
2640	//#ifdef HAVE_TAIL_RING
2641	if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2642	kStratInitChangeTailRing(strat);
2643	#endif
2644	//enterpairs(pOne(),0,0,-1,strat,strat->tl);
2645	//strat->sl = -1;
2646	/* picks the last element from the lazyset L */
2647	while (strat->Ll>Ll_old)
2648	{
2649	strat->P = strat->L[strat->Ll];
2650	strat->Ll--;
2651	//#if 1
2652	#ifdef DEBUGF5
2653	Print("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
2654	Print("-------------------------------------------------\n");
2655	pWrite(pHead(strat->P.p));
2656	pWrite(pHead(strat->P.p1));
2657	pWrite(pHead(strat->P.p2));
2658	printf("%d\n",strat->tl);
2659	Print("-------------------------------------------------\n");
2660	#endif
2661	if (pNext(strat->P.p) == strat->tail)
2662	{
2663	// deletes the short spoly
2664	if (rField_is_Ring(currRing))
2665	pLmDelete(strat->P.p);
2666	else
2667	pLmFree(strat->P.p);
2668
2669	// TODO: needs some masking
2670	// TODO: masking needs to vanish once the signature
2671	// sutff is completely implemented
2672	strat->P.p = NULL;
2673	poly m1 = NULL, m2 = NULL;
2674
2675	// check that spoly creation is ok
2676	while (strat->tailRing != currRing &&
2677	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2678	{
2679	assume(m1 == NULL && m2 == NULL);
2680	// if not, change to a ring where exponents are at least
2681	// large enough
2682	if (!kStratChangeTailRing(strat))
2683	{
2684	WerrorS("OVERFLOW...");
2685	break;
2686	}
2687	}
2688	// create the real one
2689	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2690	strat->tailRing, m1, m2, strat->R);
2691	}
2692	else if (strat->P.p1 == NULL)
2693	{
2694	if (strat->minim > 0)
2695	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2696	// for input polys, prepare reduction
2697	strat->P.PrepareRed(strat->use_buckets);
2698	}
2699
2700	if (strat->P.p == NULL && strat->P.t_p == NULL)
2701	{
2702	red_result = 0;
2703	}
2704	else
2705	{
2706	if (TEST_OPT_PROT)
2707	message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2708	&olddeg,&reduc,strat, red_result);
2709
2710	#ifdef DEBUGF5
2711	Print("Poly before red: ");
2712	pWrite(strat->P.p);
2713	#endif
2714	/* complete reduction of the element chosen from L */
2715	red_result = strat->red2(&strat->P,strat);
2716	if (errorreported) break;
2717	}
2718
2719	if (strat->overflow)
2720	{
2721	if (!kStratChangeTailRing(strat)) { Werror("OVERFLOW.."); break;}
2722	}
2723
2724	// reduction to non-zero new poly
2725	if (red_result == 1)
2726	{
2727	// get the polynomial (canonicalize bucket, make sure P.p is set)
2728	strat->P.GetP(strat->lmBin);
2729	// in the homogeneous case FDeg >= pFDeg (sugar/honey)
2730	// but now, for entering S, T, we reset it
2731	// in the inhomogeneous case: FDeg == pFDeg
2732	if (strat->homog) strat->initEcart(&(strat->P));
2733
2734	/* statistic */
2735	if (TEST_OPT_PROT) PrintS("s");
2736
2737	int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2738
2739	// reduce the tail and normalize poly
2740	// in the ring case we cannot expect LC(f) = 1,
2741	// therefore we call pContent instead of pNorm
2742	#if F5CTAILRED
2743	BOOLEAN withT = TRUE;
2744	if ((TEST_OPT_INTSTRATEGY) \|\| (rField_is_Ring(currRing)))
2745	{
2746	strat->P.pCleardenom();
2747	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
2748	{
2749	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2750	strat->P.pCleardenom();
2751	}
2752	}
2753	else
2754	{
2755	strat->P.pNorm();
2756	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
2757	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
2758	}
2759	#endif
2760	#ifdef KDEBUG
2761	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2762	#endif /* KDEBUG */
2763
2764	// min_std stuff
2765	if ((strat->P.p1==NULL) && (strat->minim>0))
2766	{
2767	if (strat->minim==1)
2768	{
2769	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2770	p_Delete(&strat->P.p2, currRing, strat->tailRing);
2771	}
2772	else
2773	{
2774	strat->M->m[minimcnt]=strat->P.p2;
2775	strat->P.p2=NULL;
2776	}
2777	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2778	pNext(strat->M->m[minimcnt])
2779	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2780	strat->tailRing, currRing,
2781	currRing->PolyBin);
2782	minimcnt++;
2783	}
2784
2785	// enter into S, L, and T
2786	// here we need to recompute new signatures, but those are trivial ones
2787	if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
2788	{
2789	enterT(strat->P, strat);
2790	// posInS only depends on the leading term
2791	strat->enterS(strat->P, pos, strat, strat->tl);
2792	//#if 1
2793	#ifdef DEBUGF5
2794	Print("ELEMENT ADDED TO GCURR DURING INTERRED: ");
2795	pWrite(pHead(strat->S[strat->sl]));
2796	pWrite(strat->sig[strat->sl]);
2797	#endif
2798	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2799	}
2800	// Print("[%d]",hilbeledeg);
2801	if (strat->P.lcm!=NULL)
2802	#ifdef HAVE_RINGS
2803	pLmDelete(strat->P.lcm);
2804	#else
2805	pLmFree(strat->P.lcm);
2806	#endif
2807	if (strat->sl>srmax) srmax = strat->sl;
2808	}
2809	else
2810	{
2811	// adds signature of the zero reduction to
2812	// strat->syz. This is the leading term of
2813	// syzygy and can be used in syzCriterion()
2814	// the signature is added if and only if the
2815	// pair was not detected by the rewritten criterion in strat->red = redSig
2816	if (strat->P.p1 == NULL && strat->minim > 0)
2817	{
2818	p_Delete(&strat->P.p2, currRing, strat->tailRing);
2819	}
2820	}
2821
2822	#ifdef KDEBUG
2823	memset(&(strat->P), 0, sizeof(strat->P));
2824	#endif /* KDEBUG */
2825	}
2826	int cc = 0;
2827	while (cc<strat->tl+1)
2828	{
2829	strat->T[cc].sig = pOne();
2830	p_SetComp(strat->T[cc].sig,cc+1,currRing);
2831	strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
2832	strat->sig[cc] = strat->T[cc].sig;
2833	strat->sevSig[cc] = strat->T[cc].sevSig;
2834	strat->T[cc].is_sigsafe = TRUE;
2835	cc++;
2836	}
2837	strat->max_lower_index = strat->tl;
2838	// set current signature index of upcoming iteration step
2839	// NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
2840	// the corresponding syzygy rules correctly
2841	strat->currIdx = cc+1;
2842	for (int cd=strat->Ll; cd>=0; cd--)
2843	{
2844	p_SetComp(strat->L[cd].sig,cc+1,currRing);
2845	cc++;
2846	}
2847	for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
2848	strat->Shdl->m[cc] = NULL;
2849	//#if 1
2850	#if DEBUGF5
2851	Print("------------------- STRAT S ---------------------\n");
2852	cc = 0;
2853	while (cc<strat->tl+1)
2854	{
2855	pWrite(pHead(strat->S[cc]));
2856	pWrite(strat->sig[cc]);
2857	printf("- - - - - -\n");
2858	cc++;
2859	}
2860	Print("-------------------------------------------------\n");
2861	Print("------------------- STRAT T ---------------------\n");
2862	cc = 0;
2863	while (cc<strat->tl+1)
2864	{
2865	pWrite(pHead(strat->T[cc].p));
2866	pWrite(strat->T[cc].sig);
2867	printf("- - - - - -\n");
2868	cc++;
2869	}
2870	Print("-------------------------------------------------\n");
2871	Print("------------------- STRAT L ---------------------\n");
2872	cc = 0;
2873	while (cc<strat->Ll+1)
2874	{
2875	pWrite(pHead(strat->L[cc].p));
2876	pWrite(pHead(strat->L[cc].p1));
2877	pWrite(pHead(strat->L[cc].p2));
2878	pWrite(strat->L[cc].sig);
2879	printf("- - - - - -\n");
2880	cc++;
2881	}
2882	Print("-------------------------------------------------\n");
2883	printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
2884	#endif
2885
2886	}
2887	#endif
2888
2889	/* shiftgb stuff */
2890	#ifdef HAVE_SHIFTBBA
2891
2892
2893	ideal bbaShift(ideal F, ideal Q,intvec w,intvec hilb,kStrategy strat, int uptodeg, int lV)
2894	{
2895	int red_result = 1;
2896	int olddeg,reduc;
2897	int hilbeledeg=1,hilbcount=0,minimcnt=0;
2898	BOOLEAN withT = TRUE; // very important for shifts
2899
2900	initBuchMoraCrit(strat); /set Gebauer, honey, sugarCrit, NO CHANGES /
2901	initBuchMoraPos(strat); /NO CHANGES YET: perhaps later/
2902	initHilbCrit(F,Q,&hilb,strat); /NO CHANGES/
2903	initBbaShift(strat); /* DONE */
2904	/set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair/
2905	/Shdl=/initBuchMoraShift(F, Q,strat); /* updateS with no toT, i.e. no init for T */
2906	updateSShift(strat,uptodeg,lV); /* initializes T */
2907
2908	if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2909	reduc = olddeg = 0;
2910	strat->lV=lV;
2911
2912	#ifndef NO_BUCKETS
2913	if (!TEST_OPT_NOT_BUCKETS)
2914	strat->use_buckets = 1;
2915	#endif
2916
2917	// redtailBBa against T for inhomogenous input
2918	// if (!TEST_OPT_OLDSTD)
2919	// withT = ! strat->homog;
2920
2921	// strat->posInT = posInT_pLength;
2922	kTest_TS(strat);
2923
2924	#ifdef HAVE_TAIL_RING
2925	kStratInitChangeTailRing(strat);
2926	#endif
2927
2928	/* compute------------------------------------------------------- */
2929	while (strat->Ll >= 0)
2930	{
2931	#ifdef KDEBUG
2932	if (TEST_OPT_DEBUG) messageSets(strat);
2933	#endif
2934	if (strat->Ll== 0) strat->interpt=TRUE;
2935	if (TEST_OPT_DEGBOUND
2936	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2937	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2938	{
2939	/*
2940	*stops computation if
2941	* 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2942	*a predefined number Kstd1_deg
2943	*/
2944	while ((strat->Ll >= 0)
2945	&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2946	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2947	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2948	)
2949	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2950	if (strat->Ll<0) break;
2951	else strat->noClearS=TRUE;
2952	}
2953	/* picks the last element from the lazyset L */
2954	strat->P = strat->L[strat->Ll];
2955	strat->Ll--;
2956
2957	if (pNext(strat->P.p) == strat->tail)
2958	{
2959	// deletes the short spoly
2960	pLmFree(strat->P.p);
2961	strat->P.p = NULL;
2962	poly m1 = NULL, m2 = NULL;
2963
2964	// check that spoly creation is ok
2965	while (strat->tailRing != currRing &&
2966	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2967	{
2968	assume(m1 == NULL && m2 == NULL);
2969	// if not, change to a ring where exponents are at least
2970	// large enough
2971	kStratChangeTailRing(strat);
2972	}
2973	// create the real one
2974	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2975	strat->tailRing, m1, m2, strat->R);
2976	}
2977	else if (strat->P.p1 == NULL)
2978	{
2979	if (strat->minim > 0)
2980	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2981	// for input polys, prepare reduction
2982	strat->P.PrepareRed(strat->use_buckets);
2983	}
2984
2985	poly qq;
2986
2987	/* here in the nonhomog case we shrink the new spoly */
2988
2989	if ( ! strat->homog)
2990	{
2991	strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
2992	/* in the nonhomog case we have to shrink the polynomial */
2993	assume(strat->P.t_p!=NULL);
2994	qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
2995	if (qq != NULL)
2996	{
2997	/* we're here if Shrink is nonzero */
2998	// strat->P.p = NULL;
2999	// strat->P.Delete(); /* deletes P.p and P.t_p */ //error
3000	strat->P.p = NULL; // is not set by Delete
3001	strat->P.t_p = qq;
3002	strat->P.GetP(strat->lmBin);
3003	// update sev and length
3004	strat->initEcart(&(strat->P));
3005	strat->P.sev = pGetShortExpVector(strat->P.p);
3006	// strat->P.FDeg = strat->P.pFDeg();
3007	// strat->P.length = strat->P.pLDeg();
3008	// strat->P.pLength =strat->P.GetpLength(); //pLength(strat->P.p);
3009	}
3010	else
3011	{
3012	/* Shrink is zero, like y(1)y(2) - y(1)y(3)*/
3013	#ifdef KDEBUG
3014	if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
3015	#endif
3016	// strat->P.Delete(); // cause error
3017	strat->P.p = NULL;
3018	strat->P.t_p = NULL;
3019	// strat->P.p = NULL; // or delete strat->P.p ?
3020	}
3021	}
3022	/* end shrinking poly in the nonhomog case */
3023
3024	if (strat->P.p == NULL && strat->P.t_p == NULL)
3025	{
3026	red_result = 0;
3027	}
3028	else
3029	{
3030	if (TEST_OPT_PROT)
3031	message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3032	&olddeg,&reduc,strat, red_result);
3033
3034	/* reduction of the element chosen from L */
3035	red_result = strat->red(&strat->P,strat);
3036	}
3037
3038	// reduction to non-zero new poly
3039	if (red_result == 1)
3040	{
3041	/* statistic */
3042	if (TEST_OPT_PROT) PrintS("s");
3043
3044	// get the polynomial (canonicalize bucket, make sure P.p is set)
3045	strat->P.GetP(strat->lmBin);
3046
3047	int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3048
3049	// reduce the tail and normalize poly
3050	if (TEST_OPT_INTSTRATEGY)
3051	{
3052	strat->P.pCleardenom();
3053	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
3054	{
3055	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3056	strat->P.pCleardenom();
3057	}
3058	}
3059	else
3060	{
3061	strat->P.pNorm();
3062	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
3063	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3064	}
3065
3066	// here we must shrink again! and optionally reduce again
3067	// or build shrink into redtailBba!
3068
3069	#ifdef KDEBUG
3070	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3071	#endif
3072
3073	// min_std stuff
3074	if ((strat->P.p1==NULL) && (strat->minim>0))
3075	{
3076	if (strat->minim==1)
3077	{
3078	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3079	p_Delete(&strat->P.p2, currRing, strat->tailRing);
3080	}
3081	else
3082	{
3083	strat->M->m[minimcnt]=strat->P.p2;
3084	strat->P.p2=NULL;
3085	}
3086	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3087	pNext(strat->M->m[minimcnt])
3088	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3089	strat->tailRing, currRing,
3090	currRing->PolyBin);
3091	minimcnt++;
3092	}
3093
3094	/* here in the nonhomog case we shrink the reduced poly AGAIN */
3095
3096	if ( ! strat->homog)
3097	{
3098	strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
3099	/* assume strat->P.t_p != NULL */
3100	/* in the nonhomog case we have to shrink the polynomial */
3101	assume(strat->P.t_p!=NULL); // poly qq defined above
3102	qq = p_Shrink(strat->P.t_p, lV, strat->tailRing); // direct shrink
3103	if (qq != NULL)
3104	{
3105	/* we're here if Shrink is nonzero */
3106	// strat->P.p = NULL;
3107	// strat->P.Delete(); /* deletes P.p and P.t_p */ //error
3108	strat->P.p = NULL; // is not set by Delete
3109	strat->P.t_p = qq;
3110	strat->P.GetP(strat->lmBin);
3111	// update sev and length
3112	strat->initEcart(&(strat->P));
3113	strat->P.sev = pGetShortExpVector(strat->P.p);
3114	}
3115	else
3116	{
3117	/* Shrink is zero, like y(1)y(2) - y(1)y(3)*/
3118	#ifdef PDEBUG
3119	if (TEST_OPT_DEBUG){PrintS("nonzero s shrinks to 0");PrintLn();}
3120	#endif
3121	// strat->P.Delete(); // cause error
3122	strat->P.p = NULL;
3123	strat->P.t_p = NULL;
3124	// strat->P.p = NULL; // or delete strat->P.p ?
3125	goto red_shrink2zero;
3126	}
3127	}
3128	/* end shrinking poly AGAIN in the nonhomog case */
3129
3130
3131	// enter into S, L, and T
3132	//if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
3133	// enterT(strat->P, strat); // this was here before Shift stuff
3134	//enterTShift(LObject p, kStrategy strat, int atT, int uptodeg, int lV); // syntax
3135	// the default value for atT = -1 as in bba
3136	/* strat->P.GetP(); */
3137	// because shifts are counted with .p structure // done before, but ?
3138	enterTShift(strat->P,strat,-1,uptodeg, lV);
3139	enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl,uptodeg,lV);
3140	// enterpairsShift(vw,strat->sl,strat->P.ecart,pos,strat, strat->tl,uptodeg,lV);
3141	// posInS only depends on the leading term
3142	strat->enterS(strat->P, pos, strat, strat->tl);
3143
3144	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3145	// Print("[%d]",hilbeledeg);
3146	if (strat->P.lcm!=NULL) pLmFree(strat->P.lcm);
3147	}
3148	else
3149	{
3150	red_shrink2zero:
3151	if (strat->P.p1 == NULL && strat->minim > 0)
3152	{
3153	p_Delete(&strat->P.p2, currRing, strat->tailRing);
3154	}
3155	}
3156	#ifdef KDEBUG
3157	memset(&(strat->P), 0, sizeof(strat->P));
3158	#endif
3159	kTest_TS(strat);
3160	}
3161	#ifdef KDEBUG
3162	if (TEST_OPT_DEBUG) messageSets(strat);
3163	#endif
3164	/* complete reduction of the standard basis--------- */
3165	/* shift case: look for elt's in S such that they are divisible by elt in T */
3166	// if (TEST_OPT_SB_1)
3167	if (TEST_OPT_REDSB)
3168	{
3169	int k=0;
3170	int j=-1;
3171	while(k<=strat->sl)
3172	{
3173	// loop
3174	// {
3175	// if (j>=k) break;
3176	// clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3177	// j++;
3178	// }
3179	LObject Ln (strat->S[k],currRing, strat->tailRing);
3180	Ln.SetShortExpVector();
3181	j = kFindDivisibleByInT(strat, &Ln, j+1);
3182	if (j<0) { k++; j=-1;}
3183	else
3184	{
3185	if ( pLmCmp(strat->S[k],strat->T[j].p) == 0)
3186	{
3187	j = kFindDivisibleByInT(strat, &Ln, j+1);
3188	if (j<0) { k++; j=-1;}
3189	else
3190	{
3191	deleteInS(k,strat);
3192	}
3193	}
3194	else
3195	{
3196	deleteInS(k,strat);
3197	}
3198	}
3199	}
3200	}
3201
3202	if (TEST_OPT_REDSB)
3203	{ completeReduce(strat, TRUE); //shift: withT = TRUE
3204	if (strat->completeReduce_retry)
3205	{
3206	// completeReduce needed larger exponents, retry
3207	// to reduce with S (instead of T)
3208	// and in currRing (instead of strat->tailRing)
3209	cleanT(strat);strat->tailRing=currRing;
3210	int i;
3211	for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3212	completeReduce(strat, TRUE);
3213	}
3214	}
3215	else if (TEST_OPT_PROT) PrintLn();
3216
3217	/* release temp data-------------------------------- */
3218	exitBuchMora(strat);
3219	// if (TEST_OPT_WEIGHTM)
3220	// {
3221	// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
3222	// if (ecartWeights)
3223	// {
3224	// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
3225	// ecartWeights=NULL;
3226	// }
3227	// }
3228	if (TEST_OPT_PROT) messageStat(hilbcount,strat);
3229	if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3230	return (strat->Shdl);
3231	}
3232
3233
3234	ideal freegb(ideal I, int uptodeg, int lVblock)
3235	{
3236	/* todo main call */
3237
3238	/* assume: ring is prepared, ideal is copied into shifted ring */
3239	/* uptodeg and lVblock are correct - test them! */
3240
3241	/* check whether the ideal is in V */
3242
3243	// if (0)
3244	if (! ideal_isInV(I,lVblock) )
3245	{
3246	WerrorS("The input ideal contains incorrectly encoded elements! ");
3247	return(NULL);
3248	}
3249
3250	// kStrategy strat = new skStrategy;
3251	/* ideal bbaShift(ideal F, ideal Q,intvec w,intvec hilb,kStrategy strat, int uptodeg, int lV) */
3252	/* at the moment:
3253	- no quotient (check)
3254	- no w, no hilb
3255	*/
3256	/* ideal F, ideal Q, tHomog h,intvec ** w, intvec *hilb,int syzComp,
3257	int newIdeal, intvec vw) /
3258	ideal RS = kStdShift(I,NULL, testHomog, NULL,NULL,0,0,NULL, uptodeg, lVblock);
3259	//bbaShift(I,NULL, NULL, NULL, strat, uptodeg, lVblock);
3260	idSkipZeroes(RS);
3261	return(RS);
3262	}
3263
3264	/*2
3265	*reduces h with elements from T choosing the first possible
3266	* element in t with respect to the given pDivisibleBy
3267	*/
3268	int redFirstShift (LObject* h,kStrategy strat)
3269	{
3270	if (h->IsNull()) return 0;
3271
3272	int at, reddeg,d;
3273	int pass = 0;
3274	int j = 0;
3275
3276	if (! strat->homog)
3277	{
3278	d = h->GetpFDeg() + h->ecart;
3279	reddeg = strat->LazyDegree+d;
3280	}
3281	h->SetShortExpVector();
3282	loop
3283	{
3284	j = kFindDivisibleByInT(strat, h);
3285	if (j < 0)
3286	{
3287	h->SetDegStuffReturnLDeg(strat->LDegLast);
3288	return 1;
3289	}
3290
3291	if (!TEST_OPT_INTSTRATEGY)
3292	strat->T[j].pNorm();
3293	#ifdef KDEBUG
3294	if (TEST_OPT_DEBUG)
3295	{
3296	PrintS("reduce ");
3297	h->wrp();
3298	PrintS(" with ");
3299	strat->T[j].wrp();
3300	}
3301	#endif
3302	ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, strat);
3303	if (!h->IsNull())
3304	{
3305	poly qq=p_Shrink(h->GetTP(),strat->lV,strat->tailRing);
3306	h->p=NULL;
3307	h->t_p=qq;
3308	if (qq!=NULL) h->GetP(strat->lmBin);
3309	}
3310
3311	#ifdef KDEBUG
3312	if (TEST_OPT_DEBUG)
3313	{
3314	PrintS(" to ");
3315	wrp(h->p);
3316	PrintLn();
3317	}
3318	#endif
3319	if (h->IsNull())
3320	{
3321	if (h->lcm!=NULL) pLmFree(h->lcm);
3322	h->Clear();
3323	return 0;
3324	}
3325	h->SetShortExpVector();
3326
3327	#if 0
3328	if ((strat->syzComp!=0) && !strat->honey)
3329	{
3330	if ((strat->syzComp>0) &&
3331	(h->Comp() > strat->syzComp))
3332	{
3333	assume(h->MinComp() > strat->syzComp);
3334	#ifdef KDEBUG
3335	if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
3336	#endif
3337	if (strat->homog)
3338	h->SetDegStuffReturnLDeg(strat->LDegLast);
3339	return -2;
3340	}
3341	}
3342	#endif
3343	if (!strat->homog)
3344	{
3345	if (!TEST_OPT_OLDSTD && strat->honey)
3346	{
3347	h->SetpFDeg();
3348	if (strat->T[j].ecart <= h->ecart)
3349	h->ecart = d - h->GetpFDeg();
3350	else
3351	h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
3352
3353	d = h->GetpFDeg() + h->ecart;
3354	}
3355	else
3356	d = h->SetDegStuffReturnLDeg(strat->LDegLast);
3357	/- try to reduce the s-polynomial -/
3358	pass++;
3359	/*
3360	*test whether the polynomial should go to the lazyset L
3361	*-if the degree jumps
3362	*-if the number of pre-defined reductions jumps
3363	*/
3364	if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
3365	&& ((d >= reddeg) \|\| (pass > strat->LazyPass)))
3366	{
3367	h->SetLmCurrRing();
3368	if (strat->posInLDependsOnLength)
3369	h->SetLength(strat->length_pLength);
3370	at = strat->posInL(strat->L,strat->Ll,h,strat);
3371	if (at <= strat->Ll)
3372	{
3373	//int dummy=strat->sl;
3374	/* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
3375	//if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
3376	if (kFindDivisibleByInT(strat, h) < 0)
3377	return 1;
3378	enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
3379	#ifdef KDEBUG
3380	if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
3381	#endif
3382	h->Clear();
3383	return -1;
3384	}
3385	}
3386	if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
3387	{
3388	reddeg = d+1;
3389	Print(".%d",d);mflush();
3390	}
3391	}
3392	}
3393	}
3394
3395	void initBbaShift(kStrategy strat)
3396	{
3397	/* setting global variables ------------------- */
3398	strat->enterS = enterSBba; /* remains as is, we change enterT! */
3399
3400	strat->red = redFirstShift; /* no redHomog ! */
3401
3402	if (currRing->pLexOrder && strat->honey)
3403	strat->initEcart = initEcartNormal;
3404	else
3405	strat->initEcart = initEcartBBA;
3406	if (strat->honey)
3407	strat->initEcartPair = initEcartPairMora;
3408	else
3409	strat->initEcartPair = initEcartPairBba;
3410	// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
3411	// {
3412	// //interred machen Aenderung
3413	// pFDegOld=currRing->pFDeg;
3414	// pLDegOld=pLDeg;
3415	// //h=ggetid("ecart");
3416	// //if ((h!=NULL) /&& (IDTYP(h)==INTVEC_CMD)/)
3417	// //{
3418	// // ecartWeights=iv2array(IDINTVEC(h));
3419	// //}
3420	// //else
3421	// {
3422	// ecartWeights=(short )omAlloc(((currRing->N)+1)sizeof(short));
3423	// /uses automatic computation of the ecartWeights to set them/
3424	// kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights,currRing);
3425	// }
3426	// pRestoreDegProcs(currRing,totaldegreeWecart, maxdegreeWecart);
3427	// if (TEST_OPT_PROT)
3428	// {
3429	// for(int i=1; i<=rVar(currRing); i++)
3430	// Print(" %d",ecartWeights[i]);
3431	// PrintLn();
3432	// mflush();
3433	// }
3434	// }
3435	}
3436	#endif

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

Download in other formats: