Context Navigation

source: git/kernel/kstd2.cc @ b3e94aa

spielwiese

Last change on this file since b3e94aa was b3e94aa, checked in by Christian Eder, 10 years ago
1. implements usage of product criterion in sba (disabled by default, still experimental) 2. adds more detailed debugging printouts for sba (disabled by default)
Property mode set to `100644`
File size: 82.0 KB

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

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

Download in other formats: