Context Navigation

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

spielwiese

Last change on this file since 750069 was 750069, checked in by Hans Schoenemann <hannes@…>, 8 years ago
Merge pull request #789 from adipopescu/Reduce_Bound Reduce bound
Property mode set to `100644`
File size: 123.2 KB

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

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

Download in other formats: