Context Navigation

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

spielwiese

Last change on this file since f5850b was f5850b, checked in by Karim Abou Zeid <karim23697@…>, 6 years ago
Adjusted bba to work with the new letterplace multiplication
Property mode set to `100644`
File size: 119.5 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	if (!errorreported)
2230	{
2231	if(rField_is_Ring_Z(currRing))
2232	{
2233	for(int i = 0;i<=strat->sl;i++)
2234	{
2235	if(!nGreaterZero(pGetCoeff(strat->S[i])))
2236	{
2237	strat->S[i] = pNeg(strat->S[i]);
2238	}
2239	}
2240	finalReduceByMon(strat);
2241	for(int i = 0;i<=strat->sl;i++)
2242	{
2243	if(!nGreaterZero(pGetCoeff(strat->S[i])))
2244	{
2245	strat->S[i] = pNeg(strat->S[i]);
2246	}
2247	}
2248	}
2249	else if (rField_is_Ring(currRing))
2250	finalReduceByMon(strat);
2251	}
2252	/* release temp data-------------------------------- */
2253	exitBuchMora(strat);
2254	// if (TEST_OPT_WEIGHTM)
2255	// {
2256	// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
2257	// if (ecartWeights)
2258	// {
2259	// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2260	// ecartWeights=NULL;
2261	// }
2262	// }
2263	if ((TEST_OPT_PROT) \|\| (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2264	SI_RESTORE_OPT1(save);
2265	if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
2266
2267	idTest(strat->Shdl);
2268
2269	return (strat->Shdl);
2270	}
2271
2272	ideal sba (ideal F0, ideal Q,intvec w,intvec hilb,kStrategy strat)
2273	{
2274	// ring order stuff:
2275	// in sba we have (until now) two possibilities:
2276	// 1. an incremental computation w.r.t. (C,monomial order)
2277	// 2. a (possibly non-incremental) computation w.r.t. the
2278	// induced Schreyer order.
2279	// The corresponding orders are computed in sbaRing(), depending
2280	// on the flag strat->sbaOrder
2281	#if SBA_PRINT_ZERO_REDUCTIONS
2282	long zeroreductions = 0;
2283	#endif
2284	#if SBA_PRINT_PRODUCT_CRITERION
2285	long product_criterion = 0;
2286	#endif
2287	#if SBA_PRINT_SIZE_G
2288	int size_g = 0;
2289	int size_g_non_red = 0;
2290	#endif
2291	#if SBA_PRINT_SIZE_SYZ
2292	long size_syz = 0;
2293	#endif
2294	// global variable
2295	#if SBA_PRINT_REDUCTION_STEPS
2296	sba_reduction_steps = 0;
2297	sba_interreduction_steps = 0;
2298	#endif
2299	#if SBA_PRINT_OPERATIONS
2300	sba_operations = 0;
2301	sba_interreduction_operations = 0;
2302	#endif
2303
2304	ideal F1 = F0;
2305	ring sRing, currRingOld;
2306	currRingOld = currRing;
2307	if (strat->sbaOrder == 1 \|\| strat->sbaOrder == 3)
2308	{
2309	sRing = sbaRing(strat);
2310	if (sRing!=currRingOld)
2311	{
2312	rChangeCurrRing (sRing);
2313	F1 = idrMoveR (F0, currRingOld, currRing);
2314	}
2315	}
2316	ideal F;
2317	// sort ideal F
2318	//Put the SigDrop element on the correct position (think of sbaEnterS)
2319	//We also sort them
2320	if(rField_is_Ring(currRing) && strat->sigdrop)
2321	{
2322	#if 1
2323	F = idInit(IDELEMS(F1),F1->rank);
2324	for (int i=0; i<IDELEMS(F1);++i)
2325	F->m[i] = F1->m[i];
2326	if(strat->sbaEnterS >= 0)
2327	{
2328	poly dummy;
2329	dummy = pCopy(F->m[0]); //the sigdrop element
2330	for(int i = 0;i<strat->sbaEnterS;i++)
2331	F->m[i] = F->m[i+1];
2332	F->m[strat->sbaEnterS] = dummy;
2333	}
2334	#else
2335	F = idInit(1,F1->rank);
2336	//printf("\nBefore the initial block sorting:\n");idPrint(F1);
2337	F->m[0] = F1->m[0];
2338	int pos;
2339	if(strat->sbaEnterS >= 0)
2340	{
2341	for(int i=1;i<=strat->sbaEnterS;i++)
2342	{
2343	pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
2344	idInsertPolyOnPos(F,F1->m[i],pos);
2345	}
2346	for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
2347	{
2348	pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
2349	idInsertPolyOnPos(F,F1->m[i],pos);
2350	}
2351	poly dummy;
2352	dummy = pCopy(F->m[0]); //the sigdrop element
2353	for(int i = 0;i<strat->sbaEnterS;i++)
2354	F->m[i] = F->m[i+1];
2355	F->m[strat->sbaEnterS] = dummy;
2356	}
2357	else
2358	{
2359	for(int i=1;i<IDELEMS(F1);i++)
2360	{
2361	pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
2362	idInsertPolyOnPos(F,F1->m[i],pos);
2363	}
2364	}
2365	#endif
2366	//printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
2367	}
2368	else
2369	{
2370	F = idInit(IDELEMS(F1),F1->rank);
2371	intvec *sort = idSort(F1);
2372	for (int i=0; i<sort->length();++i)
2373	F->m[i] = F1->m[(*sort)[i]-1];
2374	if(rField_is_Ring(currRing))
2375	{
2376	// put the monomials after the sbaEnterS polynomials
2377	//printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
2378	int nrmon = 0;
2379	for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
2380	{
2381	//pWrite(F->m[i]);
2382	if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
2383	{
2384	poly mon = F->m[i];
2385	for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
2386	{
2387	F->m[j] = F->m[j-1];
2388	}
2389	F->m[j] = mon;
2390	nrmon++;
2391	}
2392	//idPrint(F);
2393	}
2394	}
2395	}
2396	//printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
2397	if(rField_is_Ring(currRing))
2398	strat->sigdrop = FALSE;
2399	strat->nrsyzcrit = 0;
2400	strat->nrrewcrit = 0;
2401	#if SBA_INTERRED_START
2402	F = kInterRed(F,NULL);
2403	#endif
2404	#if F5DEBUG
2405	printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
2406	rWrite (currRing);
2407	printf("ordSgn = %d\n",currRing->OrdSgn);
2408	printf("\n");
2409	#endif
2410	int srmax,lrmax, red_result = 1;
2411	int olddeg,reduc;
2412	int hilbeledeg=1,hilbcount=0,minimcnt=0;
2413	LObject L;
2414	BOOLEAN withT = TRUE;
2415	strat->max_lower_index = 0;
2416	//initBuchMoraCrit(strat); /set Gebauer, honey, sugarCrit/
2417	initSbaCrit(strat); /set Gebauer, honey, sugarCrit/
2418	initSbaPos(strat);
2419	initHilbCrit(F,Q,&hilb,strat);
2420	initSba(F,strat);
2421	/set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair/
2422	/Shdl=/initSbaBuchMora(F, Q,strat);
2423	idTest(strat->Shdl);
2424	if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
2425	srmax = strat->sl;
2426	reduc = olddeg = lrmax = 0;
2427	#ifndef NO_BUCKETS
2428	if (!TEST_OPT_NOT_BUCKETS)
2429	strat->use_buckets = 1;
2430	#endif
2431
2432	// redtailBBa against T for inhomogenous input
2433	// if (!TEST_OPT_OLDSTD)
2434	// withT = ! strat->homog;
2435
2436	// strat->posInT = posInT_pLength;
2437	kTest_TS(strat);
2438
2439	#ifdef HAVE_TAIL_RING
2440	if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
2441	kStratInitChangeTailRing(strat);
2442	#endif
2443	if (BVERBOSE(23))
2444	{
2445	if (test_PosInT!=NULL) strat->posInT=test_PosInT;
2446	if (test_PosInL!=NULL) strat->posInL=test_PosInL;
2447	kDebugPrint(strat);
2448	}
2449	// We add the elements directly in S from the previous loop
2450	if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
2451	{
2452	for(int i = 0;i<strat->sbaEnterS;i++)
2453	{
2454	//Update: now the element is at the corect place
2455	//i+1 because on the 0 position is the sigdrop element
2456	enterT(strat->L[strat->Ll-(i)],strat);
2457	strat->enterS(strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
2458	}
2459	strat->Ll = strat->Ll - strat->sbaEnterS;
2460	strat->sbaEnterS = -1;
2461	}
2462	kTest_TS(strat);
2463	#ifdef KDEBUG
2464	//kDebugPrint(strat);
2465	#endif
2466	/* compute------------------------------------------------------- */
2467	while (strat->Ll >= 0)
2468	{
2469	if (strat->Ll > lrmax) lrmax =strat->Ll;/stat./
2470	#ifdef KDEBUG
2471	if (TEST_OPT_DEBUG) messageSets(strat);
2472	#endif
2473	if (strat->Ll== 0) strat->interpt=TRUE;
2474	/*
2475	if (TEST_OPT_DEGBOUND
2476	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2477	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
2478	{
2479
2480	//stops computation if
2481	// 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
2482	//a predefined number Kstd1_deg
2483	while ((strat->Ll >= 0)
2484	&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
2485	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
2486	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
2487	)
2488	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2489	if (strat->Ll<0) break;
2490	else strat->noClearS=TRUE;
2491	}
2492	*/
2493	if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
2494	{
2495	strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
2496	#if F5C
2497	// 1. interreduction of the current standard basis
2498	// 2. generation of new principal syzygy rules for syzCriterion
2499	f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
2500	lrmax, reduc, Q, w, hilb );
2501	#endif
2502	// initialize new syzygy rules for the next iteration step
2503	initSyzRules(strat);
2504	}
2505	/*********************************************************************
2506	* interrreduction step is done, we can go on with the next iteration
2507	* step of the signature-based algorithm
2508	********************************************************************/
2509	/* picks the last element from the lazyset L */
2510	strat->P = strat->L[strat->Ll];
2511	strat->Ll--;
2512
2513	if(rField_is_Ring(currRing))
2514	strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
2515	/* reduction of the element chosen from L */
2516	if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1))
2517	{
2518	//#if 1
2519	#ifdef DEBUGF5
2520	PrintS("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
2521	PrintS("-------------------------------------------------\n");
2522	pWrite(strat->P.sig);
2523	pWrite(pHead(strat->P.p));
2524	pWrite(pHead(strat->P.p1));
2525	pWrite(pHead(strat->P.p2));
2526	PrintS("-------------------------------------------------\n");
2527	#endif
2528	if (pNext(strat->P.p) == strat->tail)
2529	{
2530	// deletes the short spoly
2531	/*
2532	if (rField_is_Ring(currRing))
2533	pLmDelete(strat->P.p);
2534	else
2535	pLmFree(strat->P.p);
2536	*/
2537	// TODO: needs some masking
2538	// TODO: masking needs to vanish once the signature
2539	// sutff is completely implemented
2540	strat->P.p = NULL;
2541	poly m1 = NULL, m2 = NULL;
2542
2543	// check that spoly creation is ok
2544	while (strat->tailRing != currRing &&
2545	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
2546	{
2547	assume(m1 == NULL && m2 == NULL);
2548	// if not, change to a ring where exponents are at least
2549	// large enough
2550	if (!kStratChangeTailRing(strat))
2551	{
2552	WerrorS("OVERFLOW...");
2553	break;
2554	}
2555	}
2556	// create the real one
2557	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
2558	strat->tailRing, m1, m2, strat->R);
2559
2560	}
2561	else if (strat->P.p1 == NULL)
2562	{
2563	if (strat->minim > 0)
2564	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
2565	// for input polys, prepare reduction
2566	if(!rField_is_Ring(currRing))
2567	strat->P.PrepareRed(strat->use_buckets);
2568	}
2569	if (strat->P.p == NULL && strat->P.t_p == NULL)
2570	{
2571	red_result = 0;
2572	}
2573	else
2574	{
2575	//#if 1
2576	#ifdef DEBUGF5
2577	PrintS("Poly before red: ");
2578	pWrite(pHead(strat->P.p));
2579	pWrite(strat->P.sig);
2580	#endif
2581	#if SBA_PRODUCT_CRITERION
2582	if (strat->P.prod_crit)
2583	{
2584	#if SBA_PRINT_PRODUCT_CRITERION
2585	product_criterion++;
2586	#endif
2587	int pos = posInSyz(strat, strat->P.sig);
2588	enterSyz(strat->P, strat, pos);
2589	if (strat->P.lcm!=NULL)
2590	pLmFree(strat->P.lcm);
2591	red_result = 2;
2592	}
2593	else
2594	{
2595	red_result = strat->red(&strat->P,strat);
2596	}
2597	#else
2598	red_result = strat->red(&strat->P,strat);
2599	#endif
2600	}
2601	}
2602	else
2603	{
2604	/*
2605	if (strat->P.lcm != NULL)
2606	pLmFree(strat->P.lcm);
2607	*/
2608	red_result = 2;
2609	}
2610	if(rField_is_Ring(currRing))
2611	{
2612	if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
2613	{
2614	strat->P.p = pNeg(strat->P.p);
2615	strat->P.sig = pNeg(strat->P.sig);
2616	}
2617	strat->P.pLength = pLength(strat->P.p);
2618	if(strat->P.sig != NULL)
2619	strat->P.sevSig = pGetShortExpVector(strat->P.sig);
2620	if(strat->P.p != NULL)
2621	strat->P.sev = pGetShortExpVector(strat->P.p);
2622	}
2623	//sigdrop case
2624	if(rField_is_Ring(currRing) && strat->sigdrop)
2625	{
2626	//First reduce it as much as one can
2627	red_result = redRing(&strat->P,strat);
2628	if(red_result == 0)
2629	{
2630	strat->sigdrop = FALSE;
2631	pDelete(&strat->P.sig);
2632	strat->P.sig = NULL;
2633	}
2634	else
2635	{
2636	strat->enterS(strat->P, 0, strat, strat->tl);
2637	if (TEST_OPT_PROT)
2638	PrintS("-");
2639	break;
2640	}
2641	}
2642	if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
2643	{
2644	strat->sigdrop = TRUE;
2645	break;
2646	}
2647
2648	if (errorreported) break;
2649
2650	//#if 1
2651	#ifdef DEBUGF5
2652	if (red_result != 0)
2653	{
2654	PrintS("Poly after red: ");
2655	pWrite(pHead(strat->P.p));
2656	pWrite(strat->P.GetLmCurrRing());
2657	pWrite(strat->P.sig);
2658	printf("%d\n",red_result);
2659	}
2660	#endif
2661	if (TEST_OPT_PROT)
2662	{
2663	if(strat->P.p != NULL)
2664	message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
2665	&olddeg,&reduc,strat, red_result);
2666	else
2667	message((strat->honey ? strat->P.ecart : 0),
2668	&olddeg,&reduc,strat, red_result);
2669	}
2670
2671	if (strat->overflow)
2672	{
2673	if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
2674	}
2675	// reduction to non-zero new poly
2676	if (red_result == 1)
2677	{
2678	// get the polynomial (canonicalize bucket, make sure P.p is set)
2679	strat->P.GetP(strat->lmBin);
2680
2681	// sig-safe computations may lead to wrong FDeg computation, thus we need
2682	// to recompute it to make sure everything is alright
2683	(strat->P).FDeg = (strat->P).pFDeg();
2684	// in the homogeneous case FDeg >= pFDeg (sugar/honey)
2685	// but now, for entering S, T, we reset it
2686	// in the inhomogeneous case: FDeg == pFDeg
2687	if (strat->homog) strat->initEcart(&(strat->P));
2688
2689	/* statistic */
2690	if (TEST_OPT_PROT) PrintS("s");
2691
2692	//int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
2693	// in F5E we know that the last reduced element is already the
2694	// the one with highest signature
2695	int pos = strat->sl+1;
2696
2697	// reduce the tail and normalize poly
2698	// in the ring case we cannot expect LC(f) = 1,
2699	// therefore we call pCleardenom instead of pNorm
2700	#ifdef HAVE_RINGS
2701	poly beforetailred;
2702	if(rField_is_Ring(currRing))
2703	beforetailred = pCopy(strat->P.sig);
2704	#endif
2705	#if SBA_TAIL_RED
2706	if(rField_is_Ring(currRing))
2707	{
2708	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
2709	strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2710	}
2711	else
2712	{
2713	if (strat->sbaOrder != 2)
2714	{
2715	if (TEST_OPT_INTSTRATEGY)
2716	{
2717	strat->P.pCleardenom();
2718	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
2719	{
2720	strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2721	strat->P.pCleardenom();
2722	}
2723	}
2724	else
2725	{
2726	strat->P.pNorm();
2727	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
2728	strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
2729	}
2730	}
2731	}
2732	// It may happen that we have lost the sig in redtailsba
2733	// It cannot reduce to 0 since here we are doing just tail reduction.
2734	// Best case scenerio: remains the leading term
2735	if(rField_is_Ring(currRing) && strat->sigdrop)
2736	{
2737	strat->enterS(strat->P, 0, strat, strat->tl);
2738	break;
2739	}
2740	#endif
2741	if(rField_is_Ring(currRing))
2742	{
2743	if(strat->P.sig == NULL \|\| pLtCmp(beforetailred,strat->P.sig) == 1)
2744	{
2745	strat->sigdrop = TRUE;
2746	//Reduce it as much as you can
2747	red_result = redRing(&strat->P,strat);
2748	if(red_result == 0)
2749	{
2750	//It reduced to 0, cancel the sigdrop
2751	strat->sigdrop = FALSE;
2752	p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
2753	}
2754	else
2755	{
2756	strat->enterS(strat->P, 0, strat, strat->tl);
2757	break;
2758	}
2759	}
2760	p_Delete(&beforetailred,currRing);
2761	// strat->P.p = NULL may appear if we had a sigdrop above and reduced to 0 via redRing
2762	if(strat->P.p == NULL)
2763	goto case_when_red_result_changed;
2764	}
2765	// remove sigsafe label since it is no longer valid for the next element to
2766	// be reduced
2767	if (strat->sbaOrder == 1)
2768	{
2769	for (int jj = 0; jj<strat->tl+1; jj++)
2770	{
2771	if (pGetComp(strat->T[jj].sig) == strat->currIdx)
2772	{
2773	strat->T[jj].is_sigsafe = FALSE;
2774	}
2775	}
2776	}
2777	else
2778	{
2779	for (int jj = 0; jj<strat->tl+1; jj++)
2780	{
2781	strat->T[jj].is_sigsafe = FALSE;
2782	}
2783	}
2784	#ifdef KDEBUG
2785	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
2786	#endif /* KDEBUG */
2787
2788	// min_std stuff
2789	if ((strat->P.p1==NULL) && (strat->minim>0))
2790	{
2791	if (strat->minim==1)
2792	{
2793	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
2794	p_Delete(&strat->P.p2, currRing, strat->tailRing);
2795	}
2796	else
2797	{
2798	strat->M->m[minimcnt]=strat->P.p2;
2799	strat->P.p2=NULL;
2800	}
2801	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
2802	pNext(strat->M->m[minimcnt])
2803	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
2804	strat->tailRing, currRing,
2805	currRing->PolyBin);
2806	minimcnt++;
2807	}
2808
2809	// enter into S, L, and T
2810	//if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
2811	enterT(strat->P, strat);
2812	strat->T[strat->tl].is_sigsafe = FALSE;
2813	/*
2814	printf("hier\n");
2815	pWrite(strat->P.GetLmCurrRing());
2816	pWrite(strat->P.sig);
2817	*/
2818	if (rField_is_Ring(currRing))
2819	superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2820	else
2821	enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
2822	if(rField_is_Ring(currRing) && strat->sigdrop)
2823	break;
2824	if(rField_is_Ring(currRing))
2825	strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
2826	strat->enterS(strat->P, pos, strat, strat->tl);
2827	if(strat->sbaOrder != 1)
2828	{
2829	BOOLEAN overwrite = FALSE;
2830	for (int tk=0; tk<strat->sl+1; tk++)
2831	{
2832	if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
2833	{
2834	//printf("TK %d / %d\n",tk,strat->sl);
2835	overwrite = FALSE;
2836	break;
2837	}
2838	}
2839	//printf("OVERWRITE %d\n",overwrite);
2840	if (overwrite)
2841	{
2842	int cmp = pGetComp(strat->P.sig);
2843	int* vv = (int)omAlloc((currRing->N+1)sizeof(int));
2844	p_GetExpV (strat->P.p,vv,currRing);
2845	p_SetExpV (strat->P.sig, vv,currRing);
2846	p_SetComp (strat->P.sig,cmp,currRing);
2847
2848	strat->P.sevSig = pGetShortExpVector (strat->P.sig);
2849	int i;
2850	LObject Q;
2851	for(int ps=0;ps<strat->sl+1;ps++)
2852	{
2853
2854	strat->newt = TRUE;
2855	if (strat->syzl == strat->syzmax)
2856	{
2857	pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
2858	strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
2859	(strat->syzmax)*sizeof(unsigned long),
2860	((strat->syzmax)+setmaxTinc)
2861	*sizeof(unsigned long));
2862	strat->syzmax += setmaxTinc;
2863	}
2864	Q.sig = pCopy(strat->P.sig);
2865	// add LM(F->m[i]) to the signature to get a Schreyer order
2866	// without changing the underlying polynomial ring at all
2867	if (strat->sbaOrder == 0)
2868	p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
2869	// since p_Add_q() destroys all input
2870	// data we need to recreate help
2871	// each time
2872	// ----------------------------------------------------------
2873	// in the Schreyer order we always know that the multiplied
2874	// module monomial strat->P.sig gives the leading monomial of
2875	// the corresponding principal syzygy
2876	// => we do not need to compute the "real" syzygy completely
2877	poly help = p_Copy(strat->sig[ps],currRing);
2878	p_ExpVectorAdd (help,strat->P.p,currRing);
2879	Q.sig = p_Add_q(Q.sig,help,currRing);
2880	//printf("%d. SYZ ",i+1);
2881	//pWrite(strat->syz[i]);
2882	Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
2883	i = posInSyz(strat, Q.sig);
2884	enterSyz(Q, strat, i);
2885	}
2886	}
2887	}
2888	// deg - idx - lp/rp
2889	// => we need to add syzygies with indices > pGetComp(strat->P.sig)
2890	if(strat->sbaOrder == 0 \|\| strat->sbaOrder == 3)
2891	{
2892	int cmp = pGetComp(strat->P.sig);
2893	int max_cmp = IDELEMS(F);
2894	int* vv = (int)omAlloc((currRing->N+1)sizeof(int));
2895	p_GetExpV (strat->P.p,vv,currRing);
2896	LObject Q;
2897	int pos;
2898	int idx = __p_GetComp(strat->P.sig,currRing);
2899	//printf("++ -- adding syzygies -- ++\n");
2900	// if new element is the first one in this index
2901	if (strat->currIdx < idx)
2902	{
2903	for (int i=0; i<strat->sl; ++i)
2904	{
2905	Q.sig = p_Copy(strat->P.sig,currRing);
2906	p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
2907	poly help = p_Copy(strat->sig[i],currRing);
2908	p_ExpVectorAdd(help,strat->P.p,currRing);
2909	Q.sig = p_Add_q(Q.sig,help,currRing);
2910	//pWrite(Q.sig);
2911	pos = posInSyz(strat, Q.sig);
2912	enterSyz(Q, strat, pos);
2913	}
2914	strat->currIdx = idx;
2915	}
2916	else
2917	{
2918	// if the element is not the first one in the given index we build all
2919	// possible syzygies with elements of higher index
2920	for (int i=cmp+1; i<=max_cmp; ++i)
2921	{
2922	pos = -1;
2923	for (int j=0; j<strat->sl; ++j)
2924	{
2925	if (__p_GetComp(strat->sig[j],currRing) == i)
2926	{
2927	pos = j;
2928	break;
2929	}
2930	}
2931	if (pos != -1)
2932	{
2933	Q.sig = p_One(currRing);
2934	p_SetExpV(Q.sig, vv, currRing);
2935	// F->m[i-1] corresponds to index i
2936	p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
2937	p_SetComp(Q.sig, i, currRing);
2938	poly help = p_Copy(strat->P.sig,currRing);
2939	p_ExpVectorAdd(help,strat->S[pos],currRing);
2940	Q.sig = p_Add_q(Q.sig,help,currRing);
2941	if (strat->sbaOrder == 0)
2942	{
2943	if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn)
2944	{
2945	pos = posInSyz(strat, Q.sig);
2946	enterSyz(Q, strat, pos);
2947	}
2948	}
2949	else
2950	{
2951	pos = posInSyz(strat, Q.sig);
2952	enterSyz(Q, strat, pos);
2953	}
2954	}
2955	}
2956	//printf("++ -- done adding syzygies -- ++\n");
2957	}
2958	}
2959	//#if 1
2960	#if DEBUGF50
2961	printf("---------------------------\n");
2962	Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
2963	PrintS("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
2964	PrintS("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
2965	#endif
2966	/*
2967	if (newrules)
2968	{
2969	newrules = FALSE;
2970	}
2971	*/
2972	#if 0
2973	int pl=pLength(strat->P.p);
2974	if (pl==1)
2975	{
2976	//if (TEST_OPT_PROT)
2977	//PrintS("<1>");
2978	}
2979	else if (pl==2)
2980	{
2981	//if (TEST_OPT_PROT)
2982	//PrintS("<2>");
2983	}
2984	#endif
2985	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2986	// Print("[%d]",hilbeledeg);
2987	if (strat->P.lcm!=NULL)
2988	#ifdef HAVE_RINGS
2989	pLmDelete(strat->P.lcm);
2990	#else
2991	pLmFree(strat->P.lcm);
2992	#endif
2993	if (strat->sl>srmax) srmax = strat->sl;
2994	}
2995	else
2996	{
2997	case_when_red_result_changed:
2998	// adds signature of the zero reduction to
2999	// strat->syz. This is the leading term of
3000	// syzygy and can be used in syzCriterion()
3001	// the signature is added if and only if the
3002	// pair was not detected by the rewritten criterion in strat->red = redSig
3003	if (red_result!=2)
3004	{
3005	#if SBA_PRINT_ZERO_REDUCTIONS
3006	zeroreductions++;
3007	#endif
3008	if(rField_is_Ring(currRing) && strat->P.p == NULL && strat->P.sig == NULL)
3009	{
3010	//Catch the case when p = 0, sig = 0
3011	}
3012	else
3013	{
3014	int pos = posInSyz(strat, strat->P.sig);
3015	enterSyz(strat->P, strat, pos);
3016	//#if 1
3017	#ifdef DEBUGF5
3018	Print("ADDING STUFF TO SYZ : ");
3019	//pWrite(strat->P.p);
3020	pWrite(strat->P.sig);
3021	#endif
3022	}
3023	}
3024	if (strat->P.p1 == NULL && strat->minim > 0)
3025	{
3026	p_Delete(&strat->P.p2, currRing, strat->tailRing);
3027	}
3028	}
3029
3030	#ifdef KDEBUG
3031	memset(&(strat->P), 0, sizeof(strat->P));
3032	#endif /* KDEBUG */
3033	kTest_TS(strat);
3034	}
3035	#if 0
3036	if(strat->sigdrop)
3037	printf("\nSigDrop!\n");
3038	else
3039	printf("\nEnded with no SigDrop\n");
3040	#endif
3041	// Clean strat->P for the next sba call
3042	if(rField_is_Ring(currRing) && strat->sigdrop)
3043	{
3044	//This is used to know how many elements can we directly add to S in the next run
3045	if(strat->P.sig != NULL)
3046	strat->sbaEnterS = pGetComp(strat->P.sig)-1;
3047	//else we already set it at the beggining of the loop
3048	#ifdef KDEBUG
3049	memset(&(strat->P), 0, sizeof(strat->P));
3050	#endif /* KDEBUG */
3051	}
3052	#ifdef KDEBUG
3053	if (TEST_OPT_DEBUG) messageSets(strat);
3054	#endif /* KDEBUG */
3055
3056	if (TEST_OPT_SB_1)
3057	{
3058	if(!rField_is_Ring(currRing))
3059	{
3060	int k=1;
3061	int j;
3062	while(k<=strat->sl)
3063	{
3064	j=0;
3065	loop
3066	{
3067	if (j>=k) break;
3068	clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
3069	j++;
3070	}
3071	k++;
3072	}
3073	}
3074	}
3075	/* complete reduction of the standard basis--------- */
3076	if (TEST_OPT_REDSB)
3077	{
3078	completeReduce(strat);
3079	if (strat->completeReduce_retry)
3080	{
3081	// completeReduce needed larger exponents, retry
3082	// to reduce with S (instead of T)
3083	// and in currRing (instead of strat->tailRing)
3084	#ifdef HAVE_TAIL_RING
3085	if(currRing->bitmask>strat->tailRing->bitmask)
3086	{
3087	strat->completeReduce_retry=FALSE;
3088	cleanT(strat);strat->tailRing=currRing;
3089	int i;
3090	for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3091	completeReduce(strat);
3092	}
3093	if (strat->completeReduce_retry)
3094	#endif
3095	Werror("exponent bound is %ld",currRing->bitmask);
3096	}
3097	}
3098	else if (TEST_OPT_PROT) PrintLn();
3099
3100	#if SBA_PRINT_SIZE_SYZ
3101	// that is correct, syzl is counting one too far
3102	size_syz = strat->syzl;
3103	#endif
3104	// if (TEST_OPT_WEIGHTM)
3105	// {
3106	// pRestoreDegProcs(pFDegOld, pLDegOld);
3107	// if (ecartWeights)
3108	// {
3109	// omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
3110	// ecartWeights=NULL;
3111	// }
3112	// }
3113	if (TEST_OPT_PROT) messageStatSBA(hilbcount,strat);
3114	if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3115	#if SBA_PRINT_SIZE_G
3116	size_g_non_red = IDELEMS(strat->Shdl);
3117	#endif
3118	if(!rField_is_Ring(currRing))
3119	exitSba(strat);
3120	// I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
3121	#ifdef HAVE_RINGS
3122	int k;
3123	if(rField_is_Ring(currRing))
3124	{
3125	//for(k = strat->sl;k>=0;k--)
3126	// {printf("\nS[%i] = %p\n",k,strat->Shdl->m[k]);pWrite(strat->Shdl->m[k]);}
3127	k = strat->Ll;
3128	#if 1
3129	// 1 - adds just the unused ones, 0 - adds everthing
3130	for(;k>=0 && (strat->L[k].p1 != NULL \|\| strat->L[k].p2 != NULL);k--)
3131	{
3132	//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);
3133	deleteInL(strat->L,&strat->Ll,k,strat);
3134	}
3135	#endif
3136	//for(int kk = strat->sl;kk>=0;kk--)
3137	// {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
3138	//idPrint(strat->Shdl);
3139	//printf("\nk = %i\n",k);
3140	for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
3141	{
3142	//printf("\nAdded k = %i\n",k);
3143	strat->enterS(strat->L[k], strat->sl+1, strat, strat->tl);
3144	//printf("\nThis elements was added from L on pos %i\n",strat->sl);pWrite(strat->S[strat->sl]);pWrite(strat->sig[strat->sl]);
3145	}
3146	}
3147	// 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
3148	#if 0
3149	if(strat->sigdrop && rField_is_Ring(currRing))
3150	{
3151	for(k=strat->sl;k>=0;k--)
3152	{
3153	printf("\nsig[%i] = ",i);pWrite(strat->sig[k]);
3154	if(strat->sig[k] == NULL)
3155	strat->sig[k] = pCopy(strat->sig[k-1]);
3156	}
3157	}
3158	#endif
3159	#endif
3160	//Never do this - you will damage S
3161	//idSkipZeroes(strat->Shdl);
3162	//idPrint(strat->Shdl);
3163
3164	if ((strat->sbaOrder == 1 \|\| strat->sbaOrder == 3) && sRing!=currRingOld)
3165	{
3166	rChangeCurrRing (currRingOld);
3167	F0 = idrMoveR (F1, sRing, currRing);
3168	strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
3169	rChangeCurrRing (sRing);
3170	if(rField_is_Ring(currRing))
3171	exitSba(strat);
3172	rChangeCurrRing (currRingOld);
3173	if(strat->tailRing == sRing)
3174	strat->tailRing = currRing;
3175	rDelete (sRing);
3176	}
3177	if(rField_is_Ring(currRing) && !strat->sigdrop)
3178	id_DelDiv(strat->Shdl, currRing);
3179	if(!rField_is_Ring(currRing))
3180	id_DelDiv(strat->Shdl, currRing);
3181	idSkipZeroes(strat->Shdl);
3182	idTest(strat->Shdl);
3183
3184	#if SBA_PRINT_SIZE_G
3185	size_g = IDELEMS(strat->Shdl);
3186	#endif
3187	#ifdef DEBUGF5
3188	printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
3189	int oo = 0;
3190	while (oo<IDELEMS(strat->Shdl))
3191	{
3192	printf(" %d. ",oo+1);
3193	pWrite(pHead(strat->Shdl->m[oo]));
3194	oo++;
3195	}
3196	#endif
3197	#if SBA_PRINT_ZERO_REDUCTIONS
3198	printf("----------------------------------------------------------\n");
3199	printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
3200	zeroreductions = 0;
3201	#endif
3202	#if SBA_PRINT_REDUCTION_STEPS
3203	printf("----------------------------------------------------------\n");
3204	printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
3205	#endif
3206	#if SBA_PRINT_OPERATIONS
3207	printf("OPERATIONS: %ld\n",sba_operations);
3208	#endif
3209	#if SBA_PRINT_REDUCTION_STEPS
3210	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3211	printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
3212	#endif
3213	#if SBA_PRINT_OPERATIONS
3214	printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
3215	#endif
3216	#if SBA_PRINT_REDUCTION_STEPS
3217	printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
3218	printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
3219	sba_interreduction_steps = 0;
3220	sba_reduction_steps = 0;
3221	#endif
3222	#if SBA_PRINT_OPERATIONS
3223	printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
3224	sba_interreduction_operations = 0;
3225	sba_operations = 0;
3226	#endif
3227	#if SBA_PRINT_SIZE_G
3228	printf("----------------------------------------------------------\n");
3229	printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
3230	size_g = 0;
3231	size_g_non_red = 0;
3232	#endif
3233	#if SBA_PRINT_SIZE_SYZ
3234	printf("SIZE OF SYZ: %ld\n",size_syz);
3235	printf("----------------------------------------------------------\n");
3236	size_syz = 0;
3237	#endif
3238	#if SBA_PRINT_PRODUCT_CRITERION
3239	printf("PRODUCT CRITERIA: %ld\n",product_criterion);
3240	product_criterion = 0;
3241	#endif
3242	return (strat->Shdl);
3243	}
3244
3245	poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
3246	{
3247	assume(q!=NULL);
3248	assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3249
3250	// lazy_reduce flags: can be combined by \|
3251	//#define KSTD_NF_LAZY 1
3252	// do only a reduction of the leading term
3253	//#define KSTD_NF_NONORM 4
3254	// only global: avoid normalization, return a multiply of NF
3255	poly p;
3256
3257	//if ((idIs0(F))&&(Q==NULL))
3258	// return pCopy(q); /F=0/
3259	//strat->ak = idRankFreeModule(F);
3260	/- creating temp data structures------------------- -/
3261	BITSET save1;
3262	SI_SAVE_OPT1(save1);
3263	si_opt_1\|=Sy_bit(OPT_REDTAIL);
3264	initBuchMoraCrit(strat);
3265	strat->initEcart = initEcartBBA;
3266	strat->enterS = enterSBba;
3267	#ifndef NO_BUCKETS
3268	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3269	#endif
3270	/- set S -/
3271	strat->sl = -1;
3272	/- init local data struct.---------------------------------------- -/
3273	/Shdl=/initS(F,Q,strat);
3274	/- compute------------------------------------------------------- -/
3275	//if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3276	//{
3277	// for (i=strat->sl;i>=0;i--)
3278	// pNorm(strat->S[i]);
3279	//}
3280	kTest(strat);
3281	if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3282	if (BVERBOSE(23)) kDebugPrint(strat);
3283	int max_ind;
3284	p = redNF(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3285	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3286	{
3287	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3288	if (rField_is_Ring(currRing))
3289	{
3290	p = redtailBba_Z(p,max_ind,strat);
3291	}
3292	else
3293	{
3294	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3295	p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3296	}
3297	}
3298	/- release temp data------------------------------- -/
3299	assume(strat->L==NULL); /* strat->L unused */
3300	assume(strat->B==NULL); /* strat->B unused */
3301	omFree(strat->sevS);
3302	omFree(strat->ecartS);
3303	assume(strat->T==NULL);//omfree(strat->T);
3304	assume(strat->sevT==NULL);//omfree(strat->sevT);
3305	assume(strat->R==NULL);//omfree(strat->R);
3306	omfree(strat->S_2_R);
3307	omfree(strat->fromQ);
3308	idDelete(&strat->Shdl);
3309	SI_RESTORE_OPT1(save1);
3310	if (TEST_OPT_PROT) PrintLn();
3311	return p;
3312	}
3313
3314	poly kNF2Bound (ideal F,ideal Q,poly q,int bound,kStrategy strat, int lazyReduce)
3315	{
3316	assume(q!=NULL);
3317	assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
3318
3319	// lazy_reduce flags: can be combined by \|
3320	//#define KSTD_NF_LAZY 1
3321	// do only a reduction of the leading term
3322	//#define KSTD_NF_NONORM 4
3323	// only global: avoid normalization, return a multiply of NF
3324	poly p;
3325
3326	//if ((idIs0(F))&&(Q==NULL))
3327	// return pCopy(q); /F=0/
3328	//strat->ak = idRankFreeModule(F);
3329	/- creating temp data structures------------------- -/
3330	BITSET save1;
3331	SI_SAVE_OPT1(save1);
3332	si_opt_1\|=Sy_bit(OPT_REDTAIL);
3333	initBuchMoraCrit(strat);
3334	strat->initEcart = initEcartBBA;
3335	strat->enterS = enterSBba;
3336	#ifndef NO_BUCKETS
3337	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3338	#endif
3339	/- set S -/
3340	strat->sl = -1;
3341	/- init local data struct.---------------------------------------- -/
3342	/Shdl=/initS(F,Q,strat);
3343	/- compute------------------------------------------------------- -/
3344	//if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
3345	//{
3346	// for (i=strat->sl;i>=0;i--)
3347	// pNorm(strat->S[i]);
3348	//}
3349	kTest(strat);
3350	if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
3351	if (BVERBOSE(23)) kDebugPrint(strat);
3352	int max_ind;
3353	p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3354	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3355	{
3356	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3357	if (rField_is_Ring(currRing))
3358	{
3359	p = redtailBba_Z(p,max_ind,strat);
3360	}
3361	else
3362	{
3363	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3364	p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
3365	//p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3366	}
3367	}
3368	/- release temp data------------------------------- -/
3369	assume(strat->L==NULL); /* strat->L unused */
3370	assume(strat->B==NULL); /* strat->B unused */
3371	omFree(strat->sevS);
3372	omFree(strat->ecartS);
3373	assume(strat->T==NULL);//omfree(strat->T);
3374	assume(strat->sevT==NULL);//omfree(strat->sevT);
3375	assume(strat->R==NULL);//omfree(strat->R);
3376	omfree(strat->S_2_R);
3377	omfree(strat->fromQ);
3378	idDelete(&strat->Shdl);
3379	SI_RESTORE_OPT1(save1);
3380	if (TEST_OPT_PROT) PrintLn();
3381	return p;
3382	}
3383
3384	ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
3385	{
3386	assume(!idIs0(q));
3387	assume(!(idIs0(F)&&(Q==NULL)));
3388	// lazy_reduce flags: can be combined by \|
3389	//#define KSTD_NF_LAZY 1
3390	// do only a reduction of the leading term
3391	//#define KSTD_NF_NONORM 4
3392	// only global: avoid normalization, return a multiply of NF
3393	poly p;
3394	int i;
3395	ideal res;
3396	int max_ind;
3397
3398	//if (idIs0(q))
3399	// return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3400	//if ((idIs0(F))&&(Q==NULL))
3401	// return idCopy(q); /F=0/
3402	//strat->ak = idRankFreeModule(F);
3403	/- creating temp data structures------------------- -/
3404	BITSET save1;
3405	SI_SAVE_OPT1(save1);
3406	si_opt_1\|=Sy_bit(OPT_REDTAIL);
3407	initBuchMoraCrit(strat);
3408	strat->initEcart = initEcartBBA;
3409	strat->enterS = enterSBba;
3410	/- set S -/
3411	strat->sl = -1;
3412	#ifndef NO_BUCKETS
3413	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3414	#endif
3415	/- init local data struct.---------------------------------------- -/
3416	/Shdl=/initS(F,Q,strat);
3417	/- compute------------------------------------------------------- -/
3418	res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3419	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3420	for (i=IDELEMS(q)-1; i>=0; i--)
3421	{
3422	if (q->m[i]!=NULL)
3423	{
3424	if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3425	p = redNF(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat);
3426	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3427	{
3428	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3429	if (rField_is_Ring(currRing))
3430	{
3431	p = redtailBba_Z(p,max_ind,strat);
3432	}
3433	else
3434	{
3435	p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
3436	}
3437	}
3438	res->m[i]=p;
3439	}
3440	//else
3441	// res->m[i]=NULL;
3442	}
3443	/- release temp data------------------------------- -/
3444	assume(strat->L==NULL); /* strat->L unused */
3445	assume(strat->B==NULL); /* strat->B unused */
3446	omFree(strat->sevS);
3447	omFree(strat->ecartS);
3448	assume(strat->T==NULL);//omfree(strat->T);
3449	assume(strat->sevT==NULL);//omfree(strat->sevT);
3450	assume(strat->R==NULL);//omfree(strat->R);
3451	omfree(strat->S_2_R);
3452	omfree(strat->fromQ);
3453	idDelete(&strat->Shdl);
3454	SI_RESTORE_OPT1(save1);
3455	if (TEST_OPT_PROT) PrintLn();
3456	return res;
3457	}
3458
3459	ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound,kStrategy strat, int lazyReduce)
3460	{
3461	assume(!idIs0(q));
3462	assume(!(idIs0(F)&&(Q==NULL)));
3463	// lazy_reduce flags: can be combined by \|
3464	//#define KSTD_NF_LAZY 1
3465	// do only a reduction of the leading term
3466	//#define KSTD_NF_NONORM 4
3467	// only global: avoid normalization, return a multiply of NF
3468	poly p;
3469	int i;
3470	ideal res;
3471	int max_ind;
3472
3473	//if (idIs0(q))
3474	// return idInit(IDELEMS(q),si_max(q->rank,F->rank));
3475	//if ((idIs0(F))&&(Q==NULL))
3476	// return idCopy(q); /F=0/
3477	//strat->ak = idRankFreeModule(F);
3478	/- creating temp data structures------------------- -/
3479	BITSET save1;
3480	SI_SAVE_OPT1(save1);
3481	si_opt_1\|=Sy_bit(OPT_REDTAIL);
3482	initBuchMoraCrit(strat);
3483	strat->initEcart = initEcartBBA;
3484	strat->enterS = enterSBba;
3485	/- set S -/
3486	strat->sl = -1;
3487	#ifndef NO_BUCKETS
3488	strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
3489	#endif
3490	/- init local data struct.---------------------------------------- -/
3491	/Shdl=/initS(F,Q,strat);
3492	/- compute------------------------------------------------------- -/
3493	res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
3494	si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
3495	for (i=IDELEMS(q)-1; i>=0; i--)
3496	{
3497	if (q->m[i]!=NULL)
3498	{
3499	if (TEST_OPT_PROT) { PrintS("r");mflush(); }
3500	p = redNFBound(pCopy(q->m[i]),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
3501	if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
3502	{
3503	if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
3504	if (rField_is_Ring(currRing))
3505	{
3506	p = redtailBba_Z(p,max_ind,strat);
3507	}
3508	else
3509	{
3510	p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
3511	}
3512	}
3513	res->m[i]=p;
3514	}
3515	//else
3516	// res->m[i]=NULL;
3517	}
3518	/- release temp data------------------------------- -/
3519	assume(strat->L==NULL); /* strat->L unused */
3520	assume(strat->B==NULL); /* strat->B unused */
3521	omFree(strat->sevS);
3522	omFree(strat->ecartS);
3523	assume(strat->T==NULL);//omfree(strat->T);
3524	assume(strat->sevT==NULL);//omfree(strat->sevT);
3525	assume(strat->R==NULL);//omfree(strat->R);
3526	omfree(strat->S_2_R);
3527	omfree(strat->fromQ);
3528	idDelete(&strat->Shdl);
3529	SI_RESTORE_OPT1(save1);
3530	if (TEST_OPT_PROT) PrintLn();
3531	return res;
3532	}
3533
3534	#if F5C
3535	/*********************************************************************
3536	* interrreduction step of the signature-based algorithm:
3537	* 1. all strat->S are interpreted as new critical pairs
3538	* 2. those pairs need to be completely reduced by the usual (non sig-
3539	* safe) reduction process (including tail reductions)
3540	* 3. strat->S and strat->T are completely new computed in these steps
3541	********************************************************************/
3542	void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
3543	int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
3544	intvec w,intvec hilb )
3545	{
3546	int Ll_old, red_result = 1;
3547	int pos = 0;
3548	hilbeledeg=1;
3549	hilbcount=0;
3550	minimcnt=0;
3551	srmax = 0; // strat->sl is 0 at this point
3552	reduc = olddeg = lrmax = 0;
3553	// we cannot use strat->T anymore
3554	//cleanT(strat);
3555	//strat->tl = -1;
3556	Ll_old = strat->Ll;
3557	while (strat->tl >= 0)
3558	{
3559	if(!strat->T[strat->tl].is_redundant)
3560	{
3561	LObject h;
3562	h.p = strat->T[strat->tl].p;
3563	h.tailRing = strat->T[strat->tl].tailRing;
3564	h.t_p = strat->T[strat->tl].t_p;
3565	if (h.p!=NULL)
3566	{
3567	if (currRing->OrdSgn==-1)
3568	{
3569	cancelunit(&h);
3570	deleteHC(&h, strat);
3571	}
3572	if (h.p!=NULL)
3573	{
3574	if (TEST_OPT_INTSTRATEGY)
3575	{
3576	h.pCleardenom(); // also does remove Content
3577	}
3578	else
3579	{
3580	h.pNorm();
3581	}
3582	strat->initEcart(&h);
3583	if(rField_is_Ring(currRing))
3584	pos = posInLF5CRing(strat->L, Ll_old+1,strat->Ll,&h,strat);
3585	else
3586	pos = strat->Ll+1;
3587	h.sev = pGetShortExpVector(h.p);
3588	enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
3589	}
3590	}
3591	}
3592	strat->tl--;
3593	}
3594	strat->sl = -1;
3595	#if 0
3596	//#ifdef HAVE_TAIL_RING
3597	if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
3598	kStratInitChangeTailRing(strat);
3599	#endif
3600	//enterpairs(pOne(),0,0,-1,strat,strat->tl);
3601	//strat->sl = -1;
3602	/* picks the last element from the lazyset L */
3603	while (strat->Ll>Ll_old)
3604	{
3605	strat->P = strat->L[strat->Ll];
3606	strat->Ll--;
3607	//#if 1
3608	#ifdef DEBUGF5
3609	PrintS("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
3610	PrintS("-------------------------------------------------\n");
3611	pWrite(pHead(strat->P.p));
3612	pWrite(pHead(strat->P.p1));
3613	pWrite(pHead(strat->P.p2));
3614	printf("%d\n",strat->tl);
3615	PrintS("-------------------------------------------------\n");
3616	#endif
3617	if (pNext(strat->P.p) == strat->tail)
3618	{
3619	// deletes the short spoly
3620	if (rField_is_Ring(currRing))
3621	pLmDelete(strat->P.p);
3622	else
3623	pLmFree(strat->P.p);
3624
3625	// TODO: needs some masking
3626	// TODO: masking needs to vanish once the signature
3627	// sutff is completely implemented
3628	strat->P.p = NULL;
3629	poly m1 = NULL, m2 = NULL;
3630
3631	// check that spoly creation is ok
3632	while (strat->tailRing != currRing &&
3633	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3634	{
3635	assume(m1 == NULL && m2 == NULL);
3636	// if not, change to a ring where exponents are at least
3637	// large enough
3638	if (!kStratChangeTailRing(strat))
3639	{
3640	WerrorS("OVERFLOW...");
3641	break;
3642	}
3643	}
3644	// create the real one
3645	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3646	strat->tailRing, m1, m2, strat->R);
3647	}
3648	else if (strat->P.p1 == NULL)
3649	{
3650	if (strat->minim > 0)
3651	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3652	// for input polys, prepare reduction
3653	if(!rField_is_Ring(currRing))
3654	strat->P.PrepareRed(strat->use_buckets);
3655	}
3656
3657	if (strat->P.p == NULL && strat->P.t_p == NULL)
3658	{
3659	red_result = 0;
3660	}
3661	else
3662	{
3663	if (TEST_OPT_PROT)
3664	message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
3665	&olddeg,&reduc,strat, red_result);
3666
3667	#ifdef DEBUGF5
3668	PrintS("Poly before red: ");
3669	pWrite(strat->P.p);
3670	#endif
3671	/* complete reduction of the element chosen from L */
3672	red_result = strat->red2(&strat->P,strat);
3673	if (errorreported) break;
3674	}
3675
3676	if (strat->overflow)
3677	{
3678	if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
3679	}
3680
3681	// reduction to non-zero new poly
3682	if (red_result == 1)
3683	{
3684	// get the polynomial (canonicalize bucket, make sure P.p is set)
3685	strat->P.GetP(strat->lmBin);
3686	// in the homogeneous case FDeg >= pFDeg (sugar/honey)
3687	// but now, for entering S, T, we reset it
3688	// in the inhomogeneous case: FDeg == pFDeg
3689	if (strat->homog) strat->initEcart(&(strat->P));
3690
3691	/* statistic */
3692	if (TEST_OPT_PROT) PrintS("s");
3693	int pos;
3694	#if 1
3695	if(!rField_is_Ring(currRing))
3696	pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3697	else
3698	pos = posInSMonFirst(strat,strat->sl,strat->P.p);
3699	#else
3700	pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3701	#endif
3702	// reduce the tail and normalize poly
3703	// in the ring case we cannot expect LC(f) = 1,
3704	// therefore we call pCleardenom instead of pNorm
3705	#if F5CTAILRED
3706	BOOLEAN withT = TRUE;
3707	if ((TEST_OPT_INTSTRATEGY) \|\| (rField_is_Ring(currRing)))
3708	{
3709	strat->P.pCleardenom();
3710	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
3711	{
3712	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3713	strat->P.pCleardenom();
3714	}
3715	}
3716	else
3717	{
3718	strat->P.pNorm();
3719	if ((TEST_OPT_REDSB)\|\|(TEST_OPT_REDTAIL))
3720	strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
3721	}
3722	#endif
3723	#ifdef KDEBUG
3724	if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3725	#endif /* KDEBUG */
3726
3727	// min_std stuff
3728	if ((strat->P.p1==NULL) && (strat->minim>0))
3729	{
3730	if (strat->minim==1)
3731	{
3732	strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
3733	p_Delete(&strat->P.p2, currRing, strat->tailRing);
3734	}
3735	else
3736	{
3737	strat->M->m[minimcnt]=strat->P.p2;
3738	strat->P.p2=NULL;
3739	}
3740	if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
3741	pNext(strat->M->m[minimcnt])
3742	= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
3743	strat->tailRing, currRing,
3744	currRing->PolyBin);
3745	minimcnt++;
3746	}
3747
3748	// enter into S, L, and T
3749	// here we need to recompute new signatures, but those are trivial ones
3750	if ((!TEST_OPT_IDLIFT) \|\| (pGetComp(strat->P.p) <= strat->syzComp))
3751	{
3752	enterT(strat->P, strat);
3753	// posInS only depends on the leading term
3754	strat->enterS(strat->P, pos, strat, strat->tl);
3755	//#if 1
3756	#ifdef DEBUGF5
3757	PrintS("ELEMENT ADDED TO GCURR DURING INTERRED: ");
3758	pWrite(pHead(strat->S[strat->sl]));
3759	pWrite(strat->sig[strat->sl]);
3760	#endif
3761	if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
3762	}
3763	// Print("[%d]",hilbeledeg);
3764	if (strat->P.lcm!=NULL)
3765	#ifdef HAVE_RINGS
3766	pLmDelete(strat->P.lcm);
3767	#else
3768	pLmFree(strat->P.lcm);
3769	#endif
3770	if (strat->sl>srmax) srmax = strat->sl;
3771	}
3772	else
3773	{
3774	// adds signature of the zero reduction to
3775	// strat->syz. This is the leading term of
3776	// syzygy and can be used in syzCriterion()
3777	// the signature is added if and only if the
3778	// pair was not detected by the rewritten criterion in strat->red = redSig
3779	if (strat->P.p1 == NULL && strat->minim > 0)
3780	{
3781	p_Delete(&strat->P.p2, currRing, strat->tailRing);
3782	}
3783	}
3784
3785	#ifdef KDEBUG
3786	memset(&(strat->P), 0, sizeof(strat->P));
3787	#endif /* KDEBUG */
3788	}
3789	int cc = 0;
3790	while (cc<strat->tl+1)
3791	{
3792	strat->T[cc].sig = pOne();
3793	p_SetComp(strat->T[cc].sig,cc+1,currRing);
3794	strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
3795	strat->sig[cc] = strat->T[cc].sig;
3796	strat->sevSig[cc] = strat->T[cc].sevSig;
3797	strat->T[cc].is_sigsafe = TRUE;
3798	cc++;
3799	}
3800	strat->max_lower_index = strat->tl;
3801	// set current signature index of upcoming iteration step
3802	// NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
3803	// the corresponding syzygy rules correctly
3804	strat->currIdx = cc+1;
3805	for (int cd=strat->Ll; cd>=0; cd--)
3806	{
3807	p_SetComp(strat->L[cd].sig,cc+1,currRing);
3808	cc++;
3809	}
3810	for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
3811	strat->Shdl->m[cc] = NULL;
3812	#if 0
3813	printf("\nAfter f5c sorting\n");
3814	for(int i=0;i<=strat->sl;i++)
3815	pWrite(pHead(strat->S[i]));
3816	getchar();
3817	#endif
3818	//#if 1
3819	#if DEBUGF5
3820	PrintS("------------------- STRAT S ---------------------\n");
3821	cc = 0;
3822	while (cc<strat->tl+1)
3823	{
3824	pWrite(pHead(strat->S[cc]));
3825	pWrite(strat->sig[cc]);
3826	printf("- - - - - -\n");
3827	cc++;
3828	}
3829	PrintS("-------------------------------------------------\n");
3830	PrintS("------------------- STRAT T ---------------------\n");
3831	cc = 0;
3832	while (cc<strat->tl+1)
3833	{
3834	pWrite(pHead(strat->T[cc].p));
3835	pWrite(strat->T[cc].sig);
3836	printf("- - - - - -\n");
3837	cc++;
3838	}
3839	PrintS("-------------------------------------------------\n");
3840	PrintS("------------------- STRAT L ---------------------\n");
3841	cc = 0;
3842	while (cc<strat->Ll+1)
3843	{
3844	pWrite(pHead(strat->L[cc].p));
3845	pWrite(pHead(strat->L[cc].p1));
3846	pWrite(pHead(strat->L[cc].p2));
3847	pWrite(strat->L[cc].sig);
3848	printf("- - - - - -\n");
3849	cc++;
3850	}
3851	PrintS("-------------------------------------------------\n");
3852	printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
3853	#endif
3854
3855	}
3856	#endif
3857
3858	/* shiftgb stuff */
3859	#ifdef HAVE_SHIFTBBA
3860
3861
3862	ideal bbaShift(ideal F, ideal Q,intvec w,intvec hilb,kStrategy strat, int uptodeg, int lV)
3863	{
3864	int red_result = 1;
3865	int olddeg,reduc;
3866	int hilbeledeg=1,hilbcount=0,minimcnt=0;
3867	BOOLEAN withT = TRUE; // very important for shifts
3868
3869	initBuchMoraCrit(strat); /set Gebauer, honey, sugarCrit, NO CHANGES /
3870	if(rField_is_Ring(currRing))
3871	initBuchMoraPosRing(strat);
3872	else
3873	initBuchMoraPos(strat); /NO CHANGES YET: perhaps later/
3874	initHilbCrit(F,Q,&hilb,strat); /NO CHANGES/
3875	initBbaShift(strat); /* DONE */
3876	/set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair/
3877	/Shdl=/initBuchMoraShift(F, Q,strat); /* updateS with no toT, i.e. no init for T */
3878	updateSShift(strat,uptodeg,lV); /* initializes T */
3879
3880	if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
3881	reduc = olddeg = 0;
3882	strat->lV=lV;
3883
3884	#ifndef NO_BUCKETS
3885	if (!TEST_OPT_NOT_BUCKETS)
3886	strat->use_buckets = 1;
3887	#endif
3888
3889	// redtailBBa against T for inhomogenous input
3890	// if (!TEST_OPT_OLDSTD)
3891	// withT = ! strat->homog;
3892
3893	// strat->posInT = posInT_pLength;
3894	kTest_TS(strat);
3895
3896	#ifdef HAVE_TAIL_RING
3897	// kStratInitChangeTailRing(strat);
3898	strat->tailRing=currRing;
3899	#endif
3900
3901	/* compute------------------------------------------------------- */
3902	while (strat->Ll >= 0)
3903	{
3904	#ifdef KDEBUG
3905	if (TEST_OPT_DEBUG) messageSets(strat);
3906	#endif
3907	if (strat->Ll== 0) strat->interpt=TRUE;
3908	if (TEST_OPT_DEGBOUND
3909	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
3910	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
3911	{
3912	/*
3913	*stops computation if
3914	* 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
3915	*a predefined number Kstd1_deg
3916	*/
3917	while ((strat->Ll >= 0)
3918	&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
3919	&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
3920	\|\| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
3921	)
3922	deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
3923	if (strat->Ll<0) break;
3924	else strat->noClearS=TRUE;
3925	}
3926	/* picks the last element from the lazyset L */
3927	strat->P = strat->L[strat->Ll];
3928	strat->Ll--;
3929
3930	if (pNext(strat->P.p) == strat->tail)
3931	{
3932	// deletes the short spoly
3933	pLmFree(strat->P.p);
3934	strat->P.p = NULL;
3935	poly m1 = NULL, m2 = NULL;
3936
3937	// check that spoly creation is ok
3938	while (strat->tailRing != currRing &&
3939	!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
3940	{
3941	assume(m1 == NULL && m2 == NULL);
3942	// if not, change to a ring where exponents are at least
3943	// large enough
3944	kStratChangeTailRing(strat);
3945	}
3946	// create the real one
3947	ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
3948	strat->tailRing, m1, m2, strat->R);
3949	}
3950	else if (strat->P.p1 == NULL)
3951	{
3952	if (strat->minim > 0)
3953	strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
3954	// for input polys, prepare reduction
3955	strat->P.PrepareRed(strat->use_buckets);
3956	}
3957
3958	poly qq;
3959
3960	/* here in the nonhomog case we shrink the new spoly */
3961
3962	if ( ! strat->homog)
3963	{
3964	if (!strat->P.IsNull()) {
3965	strat->P.GetP(strat->lmBin); // because shifts are counted with .p structure
3966	}
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: