Context Navigation

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

spielwiese

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

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

Download in other formats: