Context Navigation

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

spielwiese

Last change on this file since e21795 was e21795, checked in by Hans Schoenemann <hannes@…>, 8 years ago
moved rField_is_Ring out of loops
Property mode set to `100644`
File size: 93.8 KB

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

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

Download in other formats: