Context Navigation

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

spielwiese

Last change on this file since a576b0 was a576b0, checked in by Hans Schoenemann <hannes@…>, 9 years ago
optim. kFindDivisibleByInT
Property mode set to `100644`
File size: 91.6 KB

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

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

Download in other formats: