Context Navigation

source: git/kernel/GBEngine/kstd2.cc @ 67e0dc

spielwiese

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

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

Download in other formats: