Context Navigation

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

spielwiese

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

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

Download in other formats: