Context Navigation

source: git/kernel/GBEngine/kstd2.cc @ 22d119e

fieker-DuValspielwiese

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

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

Download in other formats: