Loading...
Searching...
No Matches
kstd2.cc
Go to the documentation of this file.
/****************************************
* Computer Algebra System SINGULAR *
****************************************/
/*
* ABSTRACT - Kernel: alg. of Buchberger
*/
// #define PDEBUG 2
#include "kernel/mod2.h"
#define GCD_SBA 1
// define if no buckets should be used
// #define NO_BUCKETS
#ifdef HAVE_PLURAL
#define PLURAL_INTERNAL_DECLARATIONS 1
#endif
#define STDZ_EXHANGE_DURING_REDUCTION 0
/***********************************************
* SBA stuff -- start
***********************************************/
#define DEBUGF50 0
#define DEBUGF51 0
#ifdef DEBUGF5
#undef DEBUGF5
//#define DEBUGF5 1
#endif
#define F5C 1
#if F5C
#define F5CTAILRED 1
#endif
#define SBA_INTERRED_START 0
#define SBA_TAIL_RED 1
#define SBA_PRODUCT_CRITERION 0
#define SBA_PRINT_ZERO_REDUCTIONS 0
#define SBA_PRINT_REDUCTION_STEPS 0
#define SBA_PRINT_OPERATIONS 0
#define SBA_PRINT_SIZE_G 0
#define SBA_PRINT_SIZE_SYZ 0
#define SBA_PRINT_PRODUCT_CRITERION 0
// counts sba's reduction steps
#if SBA_PRINT_REDUCTION_STEPS
VAR long sba_reduction_steps;
VAR long sba_interreduction_steps;
#endif
#if SBA_PRINT_OPERATIONS
VAR long sba_operations;
VAR long sba_interreduction_operations;
#endif
/***********************************************
* SBA stuff -- done
***********************************************/
#include "kernel/GBEngine/kutil.h"
#include "misc/options.h"
#include "kernel/polys.h"
#include "kernel/ideals.h"
#include "kernel/GBEngine/kstd1.h"
#include "kernel/GBEngine/khstd.h"
#include "polys/kbuckets.h"
#include "polys/prCopy.h"
#include "polys/weight.h"
#include "misc/intvec.h"
#ifdef HAVE_PLURAL
#include "polys/nc/nc.h"
#endif
// #include "timer.h"
#ifdef HAVE_SHIFTBBA
#include "polys/shiftop.h"
#endif
#ifdef STDZ_EXCHANGE_DURING_REDUCTION
int kFindSameLMInT_Z(const kStrategy strat, const LObject* L, const int start)
{
unsigned long not_sev = ~L->sev;
int j = start;
int o = -1;
const TSet T=strat->T;
const unsigned long* sevT=strat->sevT;
number gcd, ogcd;
if (L->p!=NULL)
{
const ring r=currRing;
const poly p=L->p;
ogcd = pGetCoeff(p);
pAssume(~not_sev == p_GetShortExpVector(p, r));
loop
{
if (j > strat->tl) return o;
if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
{
gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
if (o == -1
|| n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf))
{
ogcd = gcd;
o = j;
}
}
j++;
}
}
else
{
const ring r=strat->tailRing;
const poly p=L->t_p;
ogcd = pGetCoeff(p);
loop
{
if (j > strat->tl) return o;
if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r) && p_LmEqual(T[j].p, p, r))
{
gcd = n_Gcd(pGetCoeff(p), pGetCoeff(T[j].p), r->cf);
if (o == -1
|| n_Greater(n_EucNorm(ogcd, r->cf), n_EucNorm(gcd, r->cf), r->cf))
{
ogcd = gcd;
o = j;
}
}
j++;
}
}
}
#endif
// return -1 if T[0] (w/o coeff) does not divide the leading monomial
// (only for euclidean rings (n_QuotRem)
int kTestDivisibleByT0_Z(const kStrategy strat, const LObject* L)
{
if (strat->tl < 1)
return -1;
unsigned long not_sev = ~L->sev;
const unsigned long sevT0 = strat->sevT[0];
number orest,rest,mult;
if (L->p!=NULL)
{
const poly T0p = strat->T[0].p;
const ring r = currRing;
const poly p = L->p;
orest = pGetCoeff(p);
pAssume(~not_sev == p_GetShortExpVector(p, r));
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if (p_LmShortDivisibleBy(T0p, sevT0, p, not_sev, r))
#else
if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
#endif
{
if (n_QuotRem!=ndQuotRem) /*euclidean ring*/
{
mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
{
n_Delete(&mult,r->cf);
n_Delete(&rest,r->cf);
return 0;
}
n_Delete(&mult,r->cf);
n_Delete(&rest,r->cf);
}
}
}
else
{
const poly T0p = strat->T[0].t_p;
const ring r = strat->tailRing;
const poly p = L->t_p;
orest = pGetCoeff(p);
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if (p_LmShortDivisibleBy(T0p, sevT0,
p, not_sev, r))
#else
if (!(sevT0 & not_sev) && p_LmDivisibleBy(T0p, p, r))
#endif
{
if (n_QuotRem!=ndQuotRem) /*euclidean ring*/
{
mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T0p), &rest, r->cf);
if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
{
n_Delete(&mult,r->cf);
n_Delete(&rest,r->cf);
return 0;
}
n_Delete(&mult,r->cf);
n_Delete(&rest,r->cf);
}
}
}
return -1;
}
int kFindDivisibleByInT_Z(const kStrategy strat, const LObject* L, const int start)
{
unsigned long not_sev = ~L->sev;
int j = start;
int o = -1;
const TSet T=strat->T;
const unsigned long* sevT=strat->sevT;
number rest, orest, mult;
if (L->p!=NULL)
{
const ring r=currRing;
const poly p=L->p;
orest = pGetCoeff(p);
pAssume(~not_sev == p_GetShortExpVector(p, r));
loop
{
if (j > strat->tl) return o;
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if (p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
#else
if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].p, p, r))
#endif
{
mult= n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].p), &rest, r->cf);
if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
{
o = j;
orest = rest;
}
}
j++;
}
}
else
{
const ring r=strat->tailRing;
const poly p=L->t_p;
orest = pGetCoeff(p);
loop
{
if (j > strat->tl) return o;
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
p, not_sev, r))
#else
if (!(sevT[j] & not_sev) && p_LmDivisibleBy(T[j].t_p, p, r))
#endif
{
mult = n_QuotRem(pGetCoeff(p), pGetCoeff(T[j].t_p), &rest, r->cf);
if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
{
o = j;
orest = rest;
}
}
j++;
}
}
}
static int kFindDivisibleByInS_Z(const kStrategy strat, LObject* L)
{
unsigned long not_sev = ~L->sev;
int j = 0;
int o = -1;
const polyset S=strat->S;
const unsigned long* sevS=strat->sevS;
number rest, orest, mult;
L->GetP();
if (L->p!=NULL)
{
const ring r=currRing;
const poly p=L->p;
orest = pGetCoeff(p);
pAssume(~not_sev == p_GetShortExpVector(p, r));
loop
{
if (j > strat->sl) return o;
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if (p_LmShortDivisibleBy(S[j], sevS[j],p, not_sev, r))
#else
if (!(sevS[j] & not_sev) && p_LmDivisibleBy(S[j], p, r))
#endif
{
mult= n_QuotRem(pGetCoeff(p), pGetCoeff(S[j]), &rest, r->cf);
if (!n_IsZero(mult, r->cf) && n_Greater(n_EucNorm(orest, r->cf), n_EucNorm(rest, r->cf), r->cf))
{
o = j;
orest = rest;
}
}
j++;
}
}
else
{
return -1;
}
}
// return -1 if no divisor is found
// number of first divisor, otherwise
int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start)
{
unsigned long not_sev = ~L->sev;
int j = start;
const TSet T=strat->T;
const unsigned long* sevT=strat->sevT;
const ring r=currRing;
const BOOLEAN is_Ring=rField_is_Ring(r);
if (L->p!=NULL)
{
const poly p=L->p;
pAssume(~not_sev == p_GetShortExpVector(p, r));
if(is_Ring)
{
loop
{
if (j > strat->tl) return -1;
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if ((T[j].p!=NULL)
&& p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
#else
if (!(sevT[j] & not_sev)
&& (T[j].p!=NULL)
&& p_LmDivisibleBy(T[j].p, p, r))
#endif
{
if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].p), r->cf))
return j;
}
j++;
}
}
else
{
loop
{
if (j > strat->tl) return -1;
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if ((T[j].p!=NULL)
&& p_LmShortDivisibleBy(T[j].p, sevT[j],p, not_sev, r))
#else
if (!(sevT[j] & not_sev)
&& (T[j].p!=NULL)
&& p_LmDivisibleBy(T[j].p, p, r))
#endif
{
return j;
}
j++;
}
}
}
else
{
const poly p=L->t_p;
const ring r=strat->tailRing;
if(is_Ring)
{
loop
{
if (j > strat->tl) return -1;
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
p, not_sev, r))
#else
if (!(sevT[j] & not_sev) &&
p_LmDivisibleBy(T[j].t_p, p, r))
#endif
{
if(n_DivBy(pGetCoeff(p), pGetCoeff(T[j].t_p), r->cf))
return j;
}
j++;
}
}
else
{
loop
{
if (j > strat->tl) return -1;
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if (p_LmShortDivisibleBy(T[j].t_p, sevT[j],
p, not_sev, r))
#else
if (!(sevT[j] & not_sev) &&
p_LmDivisibleBy(T[j].t_p, p, r))
#endif
{
return j;
}
j++;
}
}
}
}
int kFindDivisibleByInT_ecart(const kStrategy strat, const LObject* L, const int ecart)
{
if (TEST_OPT_LENGTH)
{
int r=-1; // found, but bad ecart
int j=-2; // found, good ecart
int jj=-1; // current search
loop
{
jj=kFindDivisibleByInT(strat,L,jj+1);
if (jj== -1)
{
if (j<0) return r; // nothing with good ecart
else return j; // end of search, return best found
}
else if (r<0) r=jj; // save bad ecart found
if (strat->T[jj].ecart<=ecart) // good enough
{
if (strat->T[jj].pLength<=0)
strat->T[jj].pLength=strat->T[jj].GetpLength();
if (j== -2) j=jj; // first found
else if (strat->T[j].pLength > strat->T[jj].pLength) // jj better then j
j=jj;
if (strat->T[j].pLength<=2) return j; // length already minimal
}
}
}
else
{
int r=-1;
int jj=-1;
loop
{
jj=kFindDivisibleByInT(strat,L,jj+1);
if (jj== -1)
{
return r; // nothing found
}
else if (r== -1) r=jj;
if (strat->T[jj].ecart<=ecart) // good enough
{
return jj;
}
}
}
}
// same as kFindDivisibleByInT, only with set S
int kFindDivisibleByInS(const kStrategy strat, int* max_ind, LObject* L)
{
unsigned long not_sev = ~L->sev;
poly p = L->GetLmCurrRing();
int j = 0;
pAssume(~not_sev == p_GetShortExpVector(p, currRing));
BOOLEAN is_Ring=rField_is_Ring(currRing);
#if 1
int ende;
if (is_Ring
|| (strat->ak>0)
|| currRing->pLexOrder)
ende=strat->sl;
else
{
ende=posInS(strat,*max_ind,p,0)+1;
if (ende>(*max_ind)) ende=(*max_ind);
}
#else
int ende=strat->sl;
#endif
if(is_Ring)
{
loop
{
if (j > ende) return -1;
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
p, not_sev, currRing))
#else
if ( !(strat->sevS[j] & not_sev) &&
p_LmDivisibleBy(strat->S[j], p, currRing))
#endif
{
if(n_DivBy(pGetCoeff(p), pGetCoeff(strat->S[j]), currRing->cf))
return j;
}
j++;
}
}
else
{
loop
{
if (j > ende) return -1;
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
p, not_sev, currRing))
#else
if ( !(strat->sevS[j] & not_sev) &&
p_LmDivisibleBy(strat->S[j], p, currRing))
#endif
{
return j;
}
j++;
}
}
}
// same as above, only with set S
int kFindDivisibleByInS_noCF(const kStrategy strat, int* max_ind, LObject* L)
{
unsigned long not_sev = ~L->sev;
poly p = L->GetLmCurrRing();
int j = 0;
pAssume(~not_sev == p_GetShortExpVector(p, currRing));
BOOLEAN is_Ring=rField_is_Ring(currRing);
#if 1
int ende;
if (is_Ring
|| (strat->ak>0)
|| currRing->pLexOrder)
ende=strat->sl;
else
{
ende=posInS(strat,*max_ind,p,0)+1;
if (ende>(*max_ind)) ende=(*max_ind);
}
#else
int ende=strat->sl;
#endif
loop
{
if (j > ende) return -1;
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
p, not_sev, currRing))
#else
if ( !(strat->sevS[j] & not_sev) &&
p_LmDivisibleBy(strat->S[j], p, currRing))
#endif
{
return j;
}
j++;
}
}
int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L)
{
unsigned long not_sev = ~L->sev;
poly p = L->GetLmCurrRing();
int j = start;
pAssume(~not_sev == p_GetShortExpVector(p, currRing));
#if 1
int ende=max_ind;
#else
int ende=strat->sl;
#endif
loop
{
if (j > ende) return -1;
#if defined(PDEBUG) || defined(PDIV_DEBUG)
if (p_LmShortDivisibleBy(strat->S[j], strat->sevS[j],
p, not_sev, currRing))
#else
if ( !(strat->sevS[j] & not_sev) &&
p_LmDivisibleBy(strat->S[j], p, currRing))
#endif
{
return j;
}
j++;
}
}
static long ind_fact_2(long arg)
{
if (arg <= 0) return 0;
long ind = 0;
if (arg%2 == 1) { arg--; }
while (arg > 0)
{
ind += SI_LOG2_LONG(arg);
arg = arg - 2;
}
return ind;
}
poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
{
// m = currRing->ch
if (input_p == NULL) return NULL;
poly p = input_p;
poly zeroPoly = NULL;
unsigned long a = (unsigned long) pGetCoeff(p);
int k_ind2 = 0;
int a_ind2 = SI_LOG2_LONG(a);
// unsigned long k = 1;
// of interest is only k_ind2, special routine for improvement ... TODO OLIVER
for (int i = 1; i <= leadRing->N; i++)
{
k_ind2 = k_ind2 + ind_fact_2(p_GetExp(p, i, leadRing));
}
a = (unsigned long) pGetCoeff(p);
number tmp1;
poly tmp2, tmp3;
poly lead_mult = p_ISet(1, tailRing);
if (n_GetChar(leadRing->cf) <= k_ind2 + a_ind2)
{
int too_much = k_ind2 + a_ind2 - n_GetChar(leadRing->cf);
int s_exp;
zeroPoly = p_ISet(a, tailRing);
for (int i = 1; i <= leadRing->N; i++)
{
s_exp = p_GetExp(p, i,leadRing);
if (s_exp % 2 != 0)
{
s_exp = s_exp - 1;
}
while ( (0 < SI_LOG2_LONG(s_exp)) && (SI_LOG2_LONG(s_exp) <= too_much) )
{
too_much = too_much - SI_LOG2_LONG(s_exp);
s_exp = s_exp - 2;
}
p_SetExp(lead_mult, i, p_GetExp(p, i,leadRing) - s_exp, tailRing);
for (int j = 1; j <= s_exp; j++)
{
tmp1 = nInit(j);
tmp2 = p_ISet(1, tailRing);
p_SetExp(tmp2, i, 1, tailRing);
p_Setm(tmp2, tailRing);
if (nIsZero(tmp1))
{ // should nowbe obsolet, test ! TODO OLIVER
zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
}
else
{
tmp3 = p_NSet(nCopy(tmp1), tailRing);
zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp3, tmp2, tailRing), tailRing);
}
}
}
p_Setm(lead_mult, tailRing);
zeroPoly = p_Mult_mm(zeroPoly, lead_mult, tailRing);
tmp2 = p_NSet(nCopy(pGetCoeff(zeroPoly)), leadRing);
for (int i = 1; i <= leadRing->N; i++)
{
pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
}
p_Setm(tmp2, leadRing);
zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
pNext(tmp2) = zeroPoly;
return tmp2;
}
/* unsigned long alpha_k = twoPow(leadRing->ch - k_ind2);
if (1 == 0 && alpha_k <= a)
{ // Temporarily disabled, reducing coefficients not compatible with std TODO Oliver
zeroPoly = p_ISet((a / alpha_k)*alpha_k, tailRing);
for (int i = 1; i <= leadRing->N; i++)
{
for (unsigned long j = 1; j <= p_GetExp(p, i, leadRing); j++)
{
tmp1 = nInit(j);
tmp2 = p_ISet(1, tailRing);
p_SetExp(tmp2, i, 1, tailRing);
p_Setm(tmp2, tailRing);
if (nIsZero(tmp1))
{
zeroPoly = p_Mult_q(zeroPoly, tmp2, tailRing);
}
else
{
tmp3 = p_ISet((unsigned long) tmp1, tailRing);
zeroPoly = p_Mult_q(zeroPoly, p_Add_q(tmp2, tmp3, tailRing), tailRing);
}
}
}
tmp2 = p_ISet((unsigned long) pGetCoeff(zeroPoly), leadRing);
for (int i = 1; i <= leadRing->N; i++)
{
pSetExp(tmp2, i, p_GetExp(zeroPoly, i, tailRing));
}
p_Setm(tmp2, leadRing);
zeroPoly = p_LmDeleteAndNext(zeroPoly, tailRing);
pNext(tmp2) = zeroPoly;
return tmp2;
} */
return NULL;
}
/*2
* reduction procedure for the ring coeffs
*/
int redRing_Z (LObject* h,kStrategy strat)
{
if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
if (strat->tl<0) return 1;
int at;
long d;
int j = 0;
int pass = 0;
// TODO warum SetpFDeg notwendig?
h->SetpFDeg();
assume(h->pFDeg() == h->FDeg);
long reddeg = h->GetpFDeg();
h->SetShortExpVector();
loop
{
/* check if a reducer of the lead term exists */
j = kFindDivisibleByInT(strat, h);
if (j < 0)
{
#if STDZ_EXCHANGE_DURING_REDUCTION
/* check if a reducer with the same lead monomial exists */
j = kFindSameLMInT_Z(strat, h);
if (j < 0)
{
#endif
/* check if a reducer of the lead monomial exists, by the above
* check this is a real divisor of the lead monomial */
j = kFindDivisibleByInT_Z(strat, h);
if (j < 0)
{
// over ZZ: cleanup coefficients by complete reduction with monomials
if (rHasLocalOrMixedOrdering(currRing))
postReduceByMon(h, strat);
if(h->p == NULL)
{
if (h->lcm!=NULL) pLmDelete(h->lcm);
h->Clear();
return 0;
}
if(nIsZero(pGetCoeff(h->p))) return 2;
j = kFindDivisibleByInT(strat, h);
if(j < 0)
{
if(strat->tl >= 0)
h->i_r1 = strat->tl;
else
h->i_r1 = -1;
if (h->GetLmTailRing() == NULL)
{
if (h->lcm!=NULL) pLmDelete(h->lcm);
h->Clear();
return 0;
}
return 1;
}
}
else
{
/* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
* => we try to cut down the lead coefficient at least */
/* first copy T[j] in order to multiply it with a coefficient later on */
number mult, rest;
TObject tj = strat->T[j];
tj.Copy();
/* tj.max_exp = strat->T[j].max_exp; */
/* compute division with remainder of lc(h) and lc(T[j]) */
mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(strat->T[j].p),
&rest, currRing->cf);
/* set corresponding new lead coefficient already. we do not
* remove the lead term in ksReducePolyLC, but only apply
* a lead coefficient reduction */
tj.Mult_nn(mult);
ksReducePolyLC(h, &tj, NULL, &rest, strat);
tj.Delete();
tj.Clear();
}
#if STDZ_EXCHANGE_DURING_REDUCTION
}
else
{
/* same lead monomial but lead coefficients do not divide each other:
* change the polys to h <- spoly(h,tj) and h2 <- gpoly(h,tj). */
LObject h2 = *h;
h2.Copy();
ksReducePolyZ(h, &(strat->T[j]), NULL, NULL, strat);
ksReducePolyGCD(&h2, &(strat->T[j]), NULL, NULL, strat);
if (!rHasLocalOrMixedOrdering(currRing))
{
redtailBbaAlsoLC_Z(&h2, j, strat);
}
/* replace h2 for tj in L (already generated pairs with tj), S and T */
replaceInLAndSAndT(h2, j, strat);
}
#endif
}
else
{
ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat);
}
/* printf("\nAfter small red: ");pWrite(h->p); */
if (h->GetLmTailRing() == NULL)
{
if (h->lcm!=NULL) pLmDelete(h->lcm);
#ifdef KDEBUG
h->lcm=NULL;
#endif
h->Clear();
return 0;
}
h->SetShortExpVector();
d = h->SetpFDeg();
/*- try to reduce the s-polynomial -*/
pass++;
if (!TEST_OPT_REDTHROUGH &&
(strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
{
h->SetLmCurrRing();
if (strat->posInLDependsOnLength)
h->SetLength(strat->length_pLength);
at = strat->posInL(strat->L,strat->Ll,h,strat);
if (at <= strat->Ll)
{
#ifdef KDEBUG
if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
#endif
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
h->Clear();
return -1;
}
}
if (d != reddeg)
{
if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
{
if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
{
strat->overflow=TRUE;
//Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
h->GetP();
at = strat->posInL(strat->L,strat->Ll,h,strat);
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
h->Clear();
return -1;
}
}
else if ((TEST_OPT_PROT) && (strat->Ll < 0))
{
Print(".%ld",d);mflush();
reddeg = d;
}
}
}
}
static int redRing_Z_S (LObject* h,kStrategy strat)
{
if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
if (strat->sl<0) return 1;
int j = 0;
int pass = 0;
// TODO warum SetpFDeg notwendig?
h->SetpFDeg();
assume(h->pFDeg() == h->FDeg);
h->SetShortExpVector();
int max_ind=strat->sl;
loop
{
/* check if a reducer of the lead term exists */
max_ind=strat->sl;
j = kFindDivisibleByInS(strat,&max_ind, h);
if (j < 0)
{
#if STDZ_EXCHANGE_DURING_REDUCTION
/* check if a reducer with the same lead monomial exists */
j = kFindSameLMInT_Z(strat, h);
if (j < 0)
{
#endif
/* check if a reducer of the lead monomial exists, by the above
* check this is a real divisor of the lead monomial */
j = kFindDivisibleByInS_Z(strat, h);
if (j < 0)
{
// over ZZ: cleanup coefficients by complete reduction with monomials
if (rHasLocalOrMixedOrdering(currRing))
postReduceByMon(h, strat);
if(h->p == NULL)
{
h->Clear();
return 0;
}
if(nIsZero(pGetCoeff(h->p))) return 2;
max_ind=strat->sl;
j = kFindDivisibleByInS(strat, &max_ind, h);
if(j < 0)
{
if (h->GetLmTailRing() == NULL)
{
h->Clear();
return 0;
}
return 1;
}
}
else
{
/* not(lc(reducer) | lc(poly)) && not(lc(poly) | lc(reducer))
* => we try to cut down the lead coefficient at least */
/* first copy T[j] in order to multiply it with a coefficient later on */
number mult, rest;
TObject tj(pCopy(strat->S[j]));
/* compute division with remainder of lc(h) and lc(S[j]) */
mult = n_QuotRem(pGetCoeff(h->p), pGetCoeff(strat->S[j]),
&rest, currRing->cf);
/* set corresponding new lead coefficient already. we do not
* remove the lead term in ksReducePolyLC, but only apply
* a lead coefficient reduction */
tj.Mult_nn(mult);
ksReducePolyLC(h, &tj, NULL, &rest, strat);
tj.Delete();
tj.Clear();
}
#if STDZ_EXCHANGE_DURING_REDUCTION
}
else
{
/* same lead monomial but lead coefficients do not divide each other:
* change the polys to h <- spoly(h,tj) and h2 <- gpoly(h,tj). */
LObject h2 = *h;
h2.Copy();
TObject tj(strat->S[j]);
ksReducePolyZ(h, &tj, NULL, NULL, strat);
ksReducePolyGCD(&h2, &tj, NULL, NULL, strat);
if (!rHasLocalOrMixedOrdering(currRing))
{
redtailBbaAlsoLC_Z_S(&h2, j, strat);
}
/* replace h2 for tj in L (already generated pairs with tj), S and T */
replaceInLAndSAndT(h2, j, strat);
}
#endif
}
else
{
TObject tj(strat->S[j]);
ksReducePoly(h, &tj, NULL, NULL, NULL, strat);
}
/* printf("\nAfter small red: ");pWrite(h->p); */
if (h->GetLmCurrRing() == NULL)
{
h->Clear();
return 0;
}
h->SetShortExpVector();
h->SetpFDeg();
/*- try to reduce the s-polynomial -*/
pass++;
}
}
int redRing (LObject* h,kStrategy strat)
{
if (strat->tl<0) return 1;
if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
int at/*,i*/;
long d;
int j = 0;
int pass = 0;
// poly zeroPoly = NULL;
// TODO warum SetpFDeg notwendig?
h->SetpFDeg();
assume(h->pFDeg() == h->FDeg);
long reddeg = h->GetpFDeg();
h->SetShortExpVector();
loop
{
j = kFindDivisibleByInT(strat, h);
if (j < 0)
{
// over ZZ: cleanup coefficients by complete reduction with monomials
postReduceByMon(h, strat);
if(h->p == NULL)
{
kDeleteLcm(h);
h->Clear();
return 0;
}
if(nIsZero(pGetCoeff(h->p))) return 2;
j = kFindDivisibleByInT(strat, h);
if(j < 0)
{
if(strat->tl >= 0)
h->i_r1 = strat->tl;
else
h->i_r1 = -1;
if (h->GetLmTailRing() == NULL)
{
kDeleteLcm(h);
h->Clear();
return 0;
}
return 1;
}
}
//printf("\nFound one: ");pWrite(strat->T[j].p);
//enterT(*h, strat);
ksReducePoly(h, &(strat->T[j]), NULL, NULL, NULL, strat); // with debug output
//printf("\nAfter small red: ");pWrite(h->p);
if (h->GetLmTailRing() == NULL)
{
kDeleteLcm(h);
h->Clear();
return 0;
}
h->SetShortExpVector();
d = h->SetpFDeg();
/*- try to reduce the s-polynomial -*/
pass++;
if (!TEST_OPT_REDTHROUGH &&
(strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
{
h->SetLmCurrRing();
if (strat->posInLDependsOnLength)
h->SetLength(strat->length_pLength);
at = strat->posInL(strat->L,strat->Ll,h,strat);
if (at <= strat->Ll)
{
#ifdef KDEBUG
if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
#endif
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at); // NOT RING CHECKED OLIVER
h->Clear();
return -1;
}
}
if (d != reddeg)
{
if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
{
if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
{
strat->overflow=TRUE;
//Print("OVERFLOW in redRing d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
h->GetP();
at = strat->posInL(strat->L,strat->Ll,h,strat);
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
h->Clear();
return -1;
}
}
else if ((TEST_OPT_PROT) && (strat->Ll < 0))
{
Print(".%ld",d);mflush();
reddeg = d;
}
}
}
}
static int redRing_S (LObject* h,kStrategy strat)
{
if (strat->sl<0) return 1;
if (h->IsNull()) return 0; // spoly is zero (can only occur with zero divisors)
int j = 0;
int pass = 0;
// poly zeroPoly = NULL;
h->SetpFDeg();
assume(h->pFDeg() == h->FDeg);
int max_ind;
h->SetShortExpVector();
loop
{
max_ind=strat->sl;
j = kFindDivisibleByInS(strat, &max_ind, h);
if (j < 0)
{
// over ZZ: cleanup coefficients by complete reduction with monomials
postReduceByMon(h, strat);
if(h->p == NULL)
{
h->Clear();
return 0;
}
if(nIsZero(pGetCoeff(h->p))) return 2;
max_ind=strat->sl;
j = kFindDivisibleByInS(strat, &max_ind,h);
if(j < 0)
{
if (h->GetLmTailRing() == NULL)
{
h->Clear();
return 0;
}
return 1;
}
}
//printf("\nFound one: ");pWrite(strat->T[j].p);
//enterT(*h, strat);
TObject tj(strat->S[j]);
ksReducePoly(h, &tj, NULL, NULL, NULL, strat); // with debug output
//printf("\nAfter small red: ");pWrite(h->p);
if (h->GetLmTailRing() == NULL)
{
h->Clear();
return 0;
}
h->SetShortExpVector();
/*- try to reduce the s-polynomial -*/
pass++;
}
}
/*2
* reduction procedure for the homogeneous case
* and the case of a degree-ordering
*/
int redHomog (LObject* h,kStrategy strat)
{
if (strat->tl<0) return 1;
//if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
assume(h->FDeg == h->pFDeg());
poly h_p;
int i,j,at,pass,cnt,ii;
// long reddeg,d;
int li;
BOOLEAN test_opt_length=TEST_OPT_LENGTH;
pass = j = 0;
cnt = RED_CANONICALIZE;
h->SetShortExpVector();
h_p = h->GetLmTailRing();
h->PrepareRed(strat->use_buckets);
loop
{
j = kFindDivisibleByInT(strat, h);
if (j < 0) return 1;
li = strat->T[j].pLength;
ii = j;
/*
* the polynomial to reduce with (up to the moment) is;
* pi with length li
*/
i = j;
#if 1
if (test_opt_length)
{
if (li<=0) li=strat->T[j].GetpLength();
if (li>2)
{
unsigned long not_sev = ~ h->sev;
loop
{
/*- search the shortest possible with respect to length -*/
i++;
if (i > strat->tl)
break;
if ((strat->T[i].pLength < li)
&&
p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
h_p, not_sev, strat->tailRing))
{
/*
* the polynomial to reduce with is now;
*/
li = strat->T[i].pLength;
if (li<=0) li=strat->T[i].GetpLength();
ii = i;
if (li<3) break;
}
}
}
}
#endif
/*
* end of search: have to reduce with pi
*/
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("red:");
h->wrp();
PrintS(" with ");
strat->T[ii].wrp();
}
#endif
assume(strat->fromT == FALSE);
ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
#if SBA_PRINT_REDUCTION_STEPS
sba_interreduction_steps++;
#endif
#if SBA_PRINT_OPERATIONS
sba_interreduction_operations += pLength(strat->T[ii].p);
#endif
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("\nto ");
h->wrp();
PrintLn();
}
#endif
h_p = h->GetLmTailRing();
if (h_p == NULL)
{
kDeleteLcm(h);
return 0;
}
if (UNLIKELY(TEST_OPT_IDLIFT))
{
if (h->p!=NULL)
{
if(p_GetComp(h->p,currRing)>strat->syzComp)
{
h->Delete();
return 0;
}
}
else //if (h->t_p!=NULL)
{
if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
{
h->Delete();
return 0;
}
}
}
#if 0
else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
{
if (h->p!=NULL)
{
if(p_GetComp(h->p,currRing)>strat->syzComp)
{
return 1;
}
}
else // if (h->t_p!=NULL)
{
if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
{
return 1;
}
}
}
#endif
h->SetShortExpVector();
/*
* try to reduce the s-polynomial h
*test first whether h should go to the lazyset L
*-if the degree jumps
*-if the number of pre-defined reductions jumps
*/
cnt--;
pass++;
if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
{
h->SetLmCurrRing();
at = strat->posInL(strat->L,strat->Ll,h,strat);
if (at <= strat->Ll)
{
#ifdef HAVE_SHIFTBBA
if (rIsLPRing(currRing))
{
if (kFindDivisibleByInT(strat, h) < 0)
return 1;
}
else
#endif
{
int dummy=strat->sl;
if (kFindDivisibleByInS(strat, &dummy, h) < 0)
return 1;
}
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
Print(" lazy: -> L%d\n",at);
#endif
h->Clear();
return -1;
}
}
else if (UNLIKELY(cnt==0))
{
h->CanonicalizeP();
cnt=RED_CANONICALIZE;
//if (TEST_OPT_PROT) { PrintS("!");mflush(); }
}
}
}
KINLINE int ksReducePolyTailSig(LObject* PR, TObject* PW, LObject* Red, kStrategy strat)
{
BOOLEAN ret;
number coef;
assume(PR->GetLmCurrRing() != PW->GetLmCurrRing());
if(!rField_is_Ring(currRing))
Red->HeadNormalize();
/*
printf("------------------------\n");
pWrite(Red->GetLmCurrRing());
*/
if(rField_is_Ring(currRing))
ret = ksReducePolySigRing(Red, PW, 1, NULL, &coef, strat);
else
ret = ksReducePolySig(Red, PW, 1, NULL, &coef, strat);
if (!ret)
{
if (! n_IsOne(coef, currRing->cf) && !rField_is_Ring(currRing))
{
PR->Mult_nn(coef);
// HANNES: mark for Normalize
}
n_Delete(&coef, currRing->cf);
}
return ret;
}
/*2
* reduction procedure for signature-based standard
* basis algorithms:
* all reductions have to be sig-safe!
*
* 2 is returned if and only if the pair is rejected by the rewritten criterion
* at exactly this point of the computations. This is the last possible point
* such a check can be done => checks with the biggest set of available
* signatures
*/
int redSig (LObject* h,kStrategy strat)
{
if (strat->tl<0) return 1;
//if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
//printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
assume(h->FDeg == h->pFDeg());
//#if 1
#ifdef DEBUGF5
PrintS("------- IN REDSIG -------\n");
Print("p: ");
pWrite(pHead(h->p));
PrintS("p1: ");
pWrite(pHead(h->p1));
PrintS("p2: ");
pWrite(pHead(h->p2));
PrintS("---------------------------\n");
#endif
poly h_p;
int i,j,at,pass, ii;
int start=0;
int sigSafe;
unsigned long not_sev;
// long reddeg,d;
BOOLEAN test_opt_length=TEST_OPT_LENGTH;
int li;
pass = j = 0;
h->SetShortExpVector();
h_p = h->GetLmTailRing();
not_sev = ~ h->sev;
loop
{
j = kFindDivisibleByInT(strat, h, start);
if (j < 0)
{
return 1;
}
li = strat->T[j].pLength;
if (li<=0) li=strat->T[j].GetpLength();
ii = j;
/*
* the polynomial to reduce with (up to the moment) is;
* pi with length li
*/
i = j;
#if 1
if (test_opt_length)
loop
{
/*- search the shortest possible with respect to length -*/
i++;
if (i > strat->tl)
break;
if (li==1)
break;
if ((strat->T[i].pLength < li)
&&
p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
h_p, not_sev, strat->tailRing))
{
/*
* the polynomial to reduce with is now;
*/
li = strat->T[i].pLength;
if (li<=0) li=strat->T[i].GetpLength();
ii = i;
}
}
start = ii+1;
#endif
/*
* end of search: have to reduce with pi
*/
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("red:");
h->wrp();
PrintS(" with ");
strat->T[ii].wrp();
}
#endif
assume(strat->fromT == FALSE);
//#if 1
#ifdef DEBUGF5
Print("BEFORE REDUCTION WITH %d:\n",ii);
PrintS("--------------------------------\n");
pWrite(h->sig);
pWrite(strat->T[ii].sig);
pWrite(h->GetLmCurrRing());
pWrite(pHead(h->p1));
pWrite(pHead(h->p2));
pWrite(pHead(strat->T[ii].p));
PrintS("--------------------------------\n");
printf("INDEX OF REDUCER T: %d\n",ii);
#endif
sigSafe = ksReducePolySig(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
#if SBA_PRINT_REDUCTION_STEPS
if (sigSafe != 3)
sba_reduction_steps++;
#endif
#if SBA_PRINT_OPERATIONS
if (sigSafe != 3)
sba_operations += pLength(strat->T[ii].p);
#endif
// if reduction has taken place, i.e. the reduction was sig-safe
// otherwise start is already at the next position and the loop
// searching reducers in T goes on from index start
//#if 1
#ifdef DEBUGF5
Print("SigSAFE: %d\n",sigSafe);
#endif
if (sigSafe != 3)
{
// start the next search for reducers in T from the beginning
start = 0;
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("\nto ");
h->wrp();
PrintLn();
}
#endif
h_p = h->GetLmTailRing();
if (h_p == NULL)
{
kDeleteLcm(h);
return 0;
}
h->SetShortExpVector();
not_sev = ~ h->sev;
/*
* try to reduce the s-polynomial h
*test first whether h should go to the lazyset L
*-if the degree jumps
*-if the number of pre-defined reductions jumps
*/
pass++;
if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
{
h->SetLmCurrRing();
at = strat->posInL(strat->L,strat->Ll,h,strat);
if (at <= strat->Ll)
{
int dummy=strat->sl;
if (kFindDivisibleByInS(strat, &dummy, h) < 0)
{
return 1;
}
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
Print(" lazy: -> L%d\n",at);
#endif
h->Clear();
return -1;
}
}
}
}
}
int redSigRing (LObject* h,kStrategy strat)
{
//Since reduce is really bad for SBA we use the following idea:
// We first check if we can build a gcd pair between h and S
//where the sig remains the same and replace h by this gcd poly
assume(rField_is_Ring(currRing));
#if GCD_SBA
while(sbaCheckGcdPair(h,strat))
{
h->sev = pGetShortExpVector(h->p);
}
#endif
poly beforeredsig;
beforeredsig = pCopy(h->sig);
if (strat->tl<0) return 1;
//if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
//printf("FDEGS: %ld -- %ld\n",h->FDeg, h->pFDeg());
assume(h->FDeg == h->pFDeg());
//#if 1
#ifdef DEBUGF5
Print("------- IN REDSIG -------\n");
Print("p: ");
pWrite(pHead(h->p));
Print("p1: ");
pWrite(pHead(h->p1));
Print("p2: ");
pWrite(pHead(h->p2));
Print("---------------------------\n");
#endif
poly h_p;
int i,j,at,pass, ii;
int start=0;
int sigSafe;
unsigned long not_sev;
// long reddeg,d;
int li;
BOOLEAN test_opt_length=TEST_OPT_LENGTH;
pass = j = 0;
h->SetShortExpVector();
h_p = h->GetLmTailRing();
not_sev = ~ h->sev;
loop
{
j = kFindDivisibleByInT(strat, h, start);
if (j < 0)
{
#if GCD_SBA
while(sbaCheckGcdPair(h,strat))
{
h->sev = pGetShortExpVector(h->p);
h->is_redundant = FALSE;
start = 0;
}
#endif
// over ZZ: cleanup coefficients by complete reduction with monomials
postReduceByMonSig(h, strat);
if(h->p == NULL || nIsZero(pGetCoeff(h->p))) return 2;
j = kFindDivisibleByInT(strat, h,start);
if(j < 0)
{
if(strat->tl >= 0)
h->i_r1 = strat->tl;
else
h->i_r1 = -1;
if (h->GetLmTailRing() == NULL)
{
kDeleteLcm(h);
h->Clear();
return 0;
}
//Check for sigdrop after reduction
if(pLtCmp(beforeredsig,h->sig) == 1)
{
strat->sigdrop = TRUE;
//Reduce it as much as you can
int red_result = redRing(h,strat);
if(red_result == 0)
{
//It reduced to 0, cancel the sigdrop
strat->sigdrop = FALSE;
p_Delete(&h->sig,currRing);h->sig = NULL;
return 0;
}
else
{
//strat->enterS(*h, strat->sl+1, strat, strat->tl);
return 0;
}
}
p_Delete(&beforeredsig,currRing);
return 1;
}
}
li = strat->T[j].pLength;
if (li<=0) li=strat->T[j].GetpLength();
ii = j;
/*
* the polynomial to reduce with (up to the moment) is;
* pi with length li
*/
i = j;
if (test_opt_length)
loop
{
/*- search the shortest possible with respect to length -*/
i++;
if (i > strat->tl)
break;
if (li==1)
break;
if ((strat->T[i].pLength < li)
&& n_DivBy(pGetCoeff(h_p),pGetCoeff(strat->T[i].p),currRing->cf)
&& p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
h_p, not_sev, strat->tailRing))
{
/*
* the polynomial to reduce with is now;
*/
li = strat->T[i].pLength;
if (li<=0) li=strat->T[i].GetpLength();
ii = i;
}
}
start = ii+1;
/*
* end of search: have to reduce with pi
*/
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("red:");
h->wrp();
PrintS(" with ");
strat->T[ii].wrp();
}
#endif
assume(strat->fromT == FALSE);
//#if 1
#ifdef DEBUGF5
Print("BEFORE REDUCTION WITH %d:\n",ii);
Print("--------------------------------\n");
pWrite(h->sig);
pWrite(strat->T[ii].sig);
pWrite(h->GetLmCurrRing());
pWrite(pHead(h->p1));
pWrite(pHead(h->p2));
pWrite(pHead(strat->T[ii].p));
Print("--------------------------------\n");
printf("INDEX OF REDUCER T: %d\n",ii);
#endif
sigSafe = ksReducePolySigRing(h, &(strat->T[ii]), strat->S_2_R[ii], NULL, NULL, strat);
if(h->p == NULL && h->sig == NULL)
{
//Trivial case catch
strat->sigdrop = FALSE;
}
#if 0
//If the reducer has the same lt (+ or -) as the other one, reduce it via redRing
//In some cases this proves to be very bad
if(rField_is_Ring(currRing) && h->p != NULL && pLmCmp(h->p,strat->T[ii].p)==0)
{
int red_result = redRing(h,strat);
if(red_result == 0)
{
pDelete(&h->sig);h->sig = NULL;
return 0;
}
else
{
strat->sigdrop = TRUE;
return 1;
}
}
#endif
if(strat->sigdrop)
return 1;
#if SBA_PRINT_REDUCTION_STEPS
if (sigSafe != 3)
sba_reduction_steps++;
#endif
#if SBA_PRINT_OPERATIONS
if (sigSafe != 3)
sba_operations += pLength(strat->T[ii].p);
#endif
// if reduction has taken place, i.e. the reduction was sig-safe
// otherwise start is already at the next position and the loop
// searching reducers in T goes on from index start
//#if 1
#ifdef DEBUGF5
Print("SigSAFE: %d\n",sigSafe);
#endif
if (sigSafe != 3)
{
// start the next search for reducers in T from the beginning
start = 0;
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("\nto ");
h->wrp();
PrintLn();
}
#endif
h_p = h->GetLmTailRing();
if (h_p == NULL)
{
kDeleteLcm(h);
return 0;
}
h->SetShortExpVector();
not_sev = ~ h->sev;
/*
* try to reduce the s-polynomial h
*test first whether h should go to the lazyset L
*-if the degree jumps
*-if the number of pre-defined reductions jumps
*/
pass++;
if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0) && (pass > strat->LazyPass))
{
h->SetLmCurrRing();
at = strat->posInL(strat->L,strat->Ll,h,strat);
if (at <= strat->Ll)
{
int dummy=strat->sl;
if (kFindDivisibleByInS(strat, &dummy, h) < 0)
{
return 1;
}
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
Print(" lazy: -> L%d\n",at);
#endif
h->Clear();
return -1;
}
}
}
}
}
// tail reduction for SBA
poly redtailSba (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
{
strat->redTailChange=FALSE;
if (strat->noTailReduction) return L->GetLmCurrRing();
poly h, p;
p = h = L->GetLmTailRing();
if ((h==NULL) || (pNext(h)==NULL))
return L->GetLmCurrRing();
TObject* With;
// placeholder in case strat->tl < 0
TObject With_s(strat->tailRing);
LObject Ln(pNext(h), strat->tailRing);
Ln.sig = L->sig;
Ln.sevSig = L->sevSig;
Ln.pLength = L->GetpLength() - 1;
pNext(h) = NULL;
if (L->p != NULL) pNext(L->p) = NULL;
L->pLength = 1;
Ln.PrepareRed(strat->use_buckets);
int cnt=REDTAIL_CANONICALIZE;
while(!Ln.IsNull())
{
loop
{
if(rField_is_Ring(currRing) && strat->sigdrop)
break;
Ln.SetShortExpVector();
if (withT)
{
int j;
j = kFindDivisibleByInT(strat, &Ln);
if (j < 0) break;
With = &(strat->T[j]);
}
else
{
With = kFindDivisibleByInS_T(strat, pos, &Ln, &With_s);
if (With == NULL) break;
}
cnt--;
if (cnt==0)
{
cnt=REDTAIL_CANONICALIZE;
/*poly tmp=*/Ln.CanonicalizeP();
if (normalize && !rField_is_Ring(currRing))
{
Ln.Normalize();
//pNormalize(tmp);
//if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
}
}
if (normalize && (!TEST_OPT_INTSTRATEGY) && !rField_is_Ring(currRing) && (!nIsOne(pGetCoeff(With->p))))
{
With->pNorm();
}
strat->redTailChange=TRUE;
int ret = ksReducePolyTailSig(L, With, &Ln, strat);
if(rField_is_Ring(currRing))
L->sig = Ln.sig;
//Because Ln.sig is set to L->sig, but in ksReducePolyTailSig -> ksReducePolySig
// I delete it an then set Ln.sig. Hence L->sig is lost
#if SBA_PRINT_REDUCTION_STEPS
if (ret != 3)
sba_reduction_steps++;
#endif
#if SBA_PRINT_OPERATIONS
if (ret != 3)
sba_operations += pLength(With->p);
#endif
if (ret)
{
// reducing the tail would violate the exp bound
// set a flag and hope for a retry (in bba)
strat->completeReduce_retry=TRUE;
if ((Ln.p != NULL) && (Ln.t_p != NULL)) Ln.p=NULL;
do
{
pNext(h) = Ln.LmExtractAndIter();
pIter(h);
L->pLength++;
} while (!Ln.IsNull());
goto all_done;
}
if (Ln.IsNull()) goto all_done;
if (! withT) With_s.Init(currRing);
if(rField_is_Ring(currRing) && strat->sigdrop)
{
//Cannot break the loop here so easily
break;
}
}
pNext(h) = Ln.LmExtractAndIter();
pIter(h);
if(!rField_is_Ring(currRing))
pNormalize(h);
L->pLength++;
}
all_done:
Ln.Delete();
if (L->p != NULL) pNext(L->p) = pNext(p);
if (strat->redTailChange)
{
L->length = 0;
}
//if (TEST_OPT_PROT) { PrintS("N"); mflush(); }
//L->Normalize(); // HANNES: should have a test
kTest_L(L,strat);
return L->GetLmCurrRing();
}
/*2
* reduction procedure for the inhomogeneous case
* and not a degree-ordering
*/
int redLazy (LObject* h,kStrategy strat)
{
if (strat->tl<0) return 1;
int at,i,ii,li;
int j = 0;
int pass = 0;
int cnt = RED_CANONICALIZE;
assume(h->pFDeg() == h->FDeg);
long reddeg = h->GetpFDeg();
long d;
BOOLEAN test_opt_length=TEST_OPT_LENGTH;
h->SetShortExpVector();
poly h_p = h->GetLmTailRing();
h->PrepareRed(strat->use_buckets);
loop
{
j = kFindDivisibleByInT(strat, h);
if (j < 0) return 1;
li = strat->T[j].pLength;
ii = j;
/*
* the polynomial to reduce with (up to the moment) is;
* pi with length li
*/
i = j;
#if 1
if (test_opt_length)
{
if (li<=0) li=strat->T[j].GetpLength();
if(li>2)
{
unsigned long not_sev = ~ h->sev;
loop
{
/*- search the shortest possible with respect to length -*/
i++;
if (i > strat->tl)
break;
if ((strat->T[i].pLength < li)
&&
p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
h_p, not_sev, strat->tailRing))
{
/*
* the polynomial to reduce with is now;
*/
li = strat->T[i].pLength;
if (li<=0) li=strat->T[i].GetpLength();
ii = i;
if (li<3) break;
}
}
}
}
#endif
/*
* end of search: have to reduce with pi
*/
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("red:");
h->wrp();
PrintS(" with ");
strat->T[ii].wrp();
}
#endif
ksReducePoly(h, &(strat->T[ii]), NULL, NULL, NULL, strat);
#if SBA_PRINT_REDUCTION_STEPS
sba_interreduction_steps++;
#endif
#if SBA_PRINT_OPERATIONS
sba_interreduction_operations += pLength(strat->T[ii].p);
#endif
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("\nto ");
h->wrp();
PrintLn();
}
#endif
h_p=h->GetLmTailRing();
if (h_p == NULL)
{
kDeleteLcm(h);
return 0;
}
if (UNLIKELY(TEST_OPT_IDLIFT))
{
if (h->p!=NULL)
{
if(p_GetComp(h->p,currRing)>strat->syzComp)
{
h->Delete();
return 0;
}
}
else //if (h->t_p!=NULL)
{
if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
{
h->Delete();
return 0;
}
}
}
#if 0
else if ((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ))
{
if (h->p!=NULL)
{
if(p_GetComp(h->p,currRing)>strat->syzComp)
{
return 1;
}
}
else // if (h->t_p!=NULL)
{
if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
{
return 1;
}
}
}
#endif
h->SetShortExpVector();
d = h->SetpFDeg();
/*- try to reduce the s-polynomial -*/
cnt--;
pass++;
if (//!TEST_OPT_REDTHROUGH &&
(strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
{
h->SetLmCurrRing();
at = strat->posInL(strat->L,strat->Ll,h,strat);
if (at <= strat->Ll)
{
#if 1
#ifdef HAVE_SHIFTBBA
if (rIsLPRing(currRing))
{
if (kFindDivisibleByInT(strat, h) < 0)
return 1;
}
else
#endif
{
int dummy=strat->sl;
if (kFindDivisibleByInS(strat, &dummy, h) < 0)
return 1;
}
#endif
#ifdef KDEBUG
if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
#endif
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
h->Clear();
return -1;
}
}
else if (d != reddeg)
{
if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
{
if (h->pTotalDeg() >= (long)strat->tailRing->bitmask)
{
strat->overflow=TRUE;
//Print("OVERFLOW in redLazy d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
h->GetP();
at = strat->posInL(strat->L,strat->Ll,h,strat);
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
h->Clear();
return -1;
}
}
else if ((TEST_OPT_PROT) && (strat->Ll < 0))
{
Print(".%ld",d);mflush();
reddeg = d;
}
}
else if (UNLIKELY(cnt==0))
{
h->CanonicalizeP();
cnt=RED_CANONICALIZE;
//if (TEST_OPT_PROT) { PrintS("!");mflush(); }
}
}
}
/*2
* reduction procedure for the sugar-strategy (honey)
* reduces h with elements from T choosing first possible
* element in T with respect to the given ecart
*/
int redHoney (LObject* h, kStrategy strat)
{
if (strat->tl<0) return 1;
//if (h->GetLmTailRing()==NULL) return 0; // HS: SHOULD NOT BE NEEDED!
assume(h->FDeg == h->pFDeg());
int j,at,pass,ei, ii, h_d;
long reddeg,d;
pass = j = 0;
d = reddeg = h->GetpFDeg() + h->ecart;
h->SetShortExpVector();
h->PrepareRed(strat->use_buckets);
loop
{
j=kFindDivisibleByInT_ecart(strat, h, h->ecart);
if (j < 0) return 1;
ii = j;
ei = strat->T[ii].ecart;
/*
* the polynomial to reduce with (up to the moment) is;
* pi with ecart ei (T[ii])
*/
/*
* end of search: have to reduce with pi
*/
if (UNLIKELY(!TEST_OPT_REDTHROUGH && (pass!=0) && (ei > h->ecart)))
{
h->GetTP(); // clears bucket
h->SetLmCurrRing();
/*
* It is not possible to reduce h with smaller ecart;
* if possible h goes to the lazy-set L,i.e
* if its position in L would be not the last one
*/
if (strat->Ll >= 0) /* L is not empty */
{
at = strat->posInL(strat->L,strat->Ll,h,strat);
if(at <= strat->Ll)
/*- h will not become the next element to reduce -*/
{
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
#endif
h->Clear();
return -1;
}
}
}
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("red:");
h->wrp();
Print("\nwith T[%d]:",ii);
strat->T[ii].wrp();
}
#endif
assume(strat->fromT == FALSE);
ksReducePoly(h,&(strat->T[ii]),strat->kNoetherTail(),NULL,NULL, strat);
#if SBA_PRINT_REDUCTION_STEPS
sba_interreduction_steps++;
#endif
#if SBA_PRINT_OPERATIONS
sba_interreduction_operations += strat->T[ii].pLength;
#endif
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("\nto:");
h->wrp();
PrintLn();
}
#endif
if(h->IsNull())
{
kDeleteLcm(h);
h->Clear();
return 0;
}
if (UNLIKELY(TEST_OPT_IDLIFT))
{
if (h->p!=NULL)
{
if(p_GetComp(h->p,currRing)>strat->syzComp)
{
h->Delete();
return 0;
}
}
else //if (h->t_p!=NULL)
{
if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
{
h->Delete();
return 0;
}
}
}
else
if (UNLIKELY((strat->syzComp > 0)&&(!TEST_OPT_REDTAIL_SYZ)))
{
if (h->p!=NULL)
{
if(p_GetComp(h->p,currRing)>strat->syzComp)
{
return 1;
}
}
else // if (h->t_p!=NULL)
{
if(p_GetComp(h->t_p,strat->tailRing)>strat->syzComp)
{
return 1;
}
}
}
h->SetShortExpVector();
h_d = h->SetpFDeg();
/* compute the ecart */
if (ei <= h->ecart)
h->ecart = d-h_d;
else
h->ecart = d-h_d+ei-h->ecart;
/*
* try to reduce the s-polynomial h
*test first whether h should go to the lazyset L
*-if the degree jumps
*-if the number of pre-defined reductions jumps
*/
pass++;
d = h_d + h->ecart;
if (UNLIKELY(!TEST_OPT_REDTHROUGH
&& (strat->Ll >= 0)
&& ((d > reddeg) || (pass > strat->LazyPass))))
{
h->GetTP(); // clear bucket
h->SetLmCurrRing();
at = strat->posInL(strat->L,strat->Ll,h,strat);
if (at <= strat->Ll)
{
#ifdef HAVE_SHIFTBBA
if (rIsLPRing(currRing))
{
if (kFindDivisibleByInT(strat, h) < 0)
return 1;
}
else
#endif
{
int dummy=strat->sl;
if (kFindDivisibleByInS(strat, &dummy, h) < 0)
return 1;
}
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
Print(" degree jumped: -> L%d\n",at);
#endif
h->Clear();
return -1;
}
}
else if (d > reddeg)
{
if (UNLIKELY(d>=(long)strat->tailRing->bitmask))
{
if (h->pTotalDeg()+h->ecart >= (long)strat->tailRing->bitmask)
{
strat->overflow=TRUE;
//Print("OVERFLOW in redHoney d=%ld, max=%ld\n",d,strat->tailRing->bitmask);
h->GetP();
at = strat->posInL(strat->L,strat->Ll,h,strat);
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
h->Clear();
return -1;
}
}
else if (UNLIKELY(TEST_OPT_PROT && (strat->Ll < 0) ))
{
//h->wrp(); Print("<%d>\n",h->GetpLength());
reddeg = d;
Print(".%ld",d); mflush();
}
}
}
}
/*2
* reduction procedure for the normal form
*/
poly redNF (poly h,int &max_ind,int nonorm,kStrategy strat)
{
if (h==NULL) return NULL;
int j,j_ring;
int cnt=REDNF_CANONICALIZE;
max_ind=strat->sl;
if (0 > strat->sl)
{
return h;
}
LObject P(h);
P.SetShortExpVector();
P.t_p=NULL;
BOOLEAN is_ring = rField_is_Ring(currRing);
if(is_ring) nonorm=TRUE;
#ifdef KDEBUG
// if (TEST_OPT_DEBUG)
// {
// PrintS("redNF: starting S:\n");
// for( j = 0; j <= max_ind; j++ )
// {
// Print("S[%d] (of size: %d): ", j, pSize(strat->S[j]));
// pWrite(strat->S[j]);
// }
// };
#endif
if (rField_is_Z(currRing))
{
redRing_Z_S(&P,strat);
if (P.bucket!=NULL)
{
P.p=kBucketClear(P.bucket);
kBucketDestroy(&P.bucket);
}
return P.p;
}
else if (rField_is_Ring(currRing))
{
redRing_S(&P,strat);
if (P.bucket!=NULL)
{
P.p=kBucketClear(P.bucket);
kBucketDestroy(&P.bucket);
}
return P.p;
}
P.bucket = kBucketCreate(currRing);
kBucketInit(P.bucket,P.p,pLength(P.p));
kbTest(P.bucket);
P.p=kBucketGetLm(P.bucket);
loop
{
j_ring=j=kFindDivisibleByInS_noCF(strat,&max_ind,&P);
while ((j>=0)
&& (nonorm)
&& (!n_DivBy(pGetCoeff(P.p),pGetCoeff(strat->S[j]),currRing->cf)))
j=kFindNextDivisibleByInS(strat,j+1,max_ind,&P);
if (j>=0)
{
int sl=pSize(strat->S[j]);
int jj=j;
loop
{
int sll;
jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
if (jj<0) break;
if ((!nonorm)
|| (n_DivBy(pGetCoeff(P.p),pGetCoeff(strat->S[jj]),currRing->cf)))
{
sll=pSize(strat->S[jj]);
if (sll<sl)
{
#ifdef KDEBUG
if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
#endif
//else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
j=jj;
sl=sll;
}
}
}
if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
{
pNorm(strat->S[j]);
//if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
}
nNormalize(pGetCoeff(P.p));
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("red:");
wrp(P.p);
PrintS(" with ");
wrp(strat->S[j]);
}
#endif
#ifdef HAVE_PLURAL
if (rIsPluralRing(currRing))
{
number coef;
nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef,nonorm);
nDelete(&coef);
}
else
#endif
{
kBucketPolyRedNF(P.bucket,strat->S[j],pLength(strat->S[j]),
strat->kNoether);
}
cnt--;
if (cnt==0)
{
kBucketCanonicalize(P.bucket);
cnt=REDNF_CANONICALIZE;
}
P.p=kBucketGetLm(P.bucket);
//P.t_p=NULL;
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("\nto:");
wrp(P.p);
PrintLn();
}
#endif
if (P.p==NULL)
{
kBucketDestroy(&P.bucket);
return NULL;
}
kbTest(P.bucket);
P.SetShortExpVector();
}
else if (is_ring && (j_ring>=0) && (currRing->cf->cfQuotRem!=ndQuotRem))
{
number r;
number n=n_QuotRem(pGetCoeff(P.p),pGetCoeff(strat->S[j_ring]),&r,currRing->cf);
if(!n_IsZero(n,currRing->cf))
{
poly lm=kBucketGetLm(P.bucket);
poly m=p_Head(lm,currRing);
p_ExpVectorSub(m,strat->S[j_ring],currRing);
if (p_GetComp(strat->S[j_ring], currRing) != p_GetComp(lm, currRing))
{
p_SetComp(m,p_GetComp(lm, currRing),currRing);
}
p_SetCoeff(m,n,currRing);
p_Setm(m,currRing);
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("redi (coeff):");
wrp(P.p);
PrintS(" with ");
wrp(strat->S[j]);
}
#endif
int l=-1;
kBucket_Minus_m_Mult_p(P.bucket,m,strat->S[j_ring],&l);
P.p=kBucketGetLm(P.bucket);
p_Delete(&m,currRing);
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("\nto:");
wrp(P.p);
PrintLn();
}
#endif
}
else
{
n_Delete(&n,currRing->cf);
}
n_Delete(&r,currRing->cf);
P.p=kBucketClear(P.bucket);
kBucketDestroy(&P.bucket);
pNormalize(P.p);
return P.p;
}
else
{
P.p=kBucketClear(P.bucket);
kBucketDestroy(&P.bucket);
pNormalize(P.p);
return P.p;
}
}
}
/*2
* reduction procedure from global case but with jet bound
*/
poly redNFBound (poly h,int &max_ind,int nonorm,kStrategy strat,int bound)
{
h = pJet(h,bound);
if (h==NULL) return NULL;
int j;
max_ind=strat->sl;
if (0 > strat->sl)
{
return h;
}
LObject P(h);
P.SetShortExpVector();
P.bucket = kBucketCreate(currRing);
kBucketInit(P.bucket,P.p,pLength(P.p));
kbTest(P.bucket);
BOOLEAN is_ring = rField_is_Ring(currRing);
loop
{
j=kFindDivisibleByInS(strat,&max_ind,&P);
if (j>=0)
{
if (!is_ring)
{
int sl=pSize(strat->S[j]);
int jj=j;
loop
{
int sll;
jj=kFindNextDivisibleByInS(strat,jj+1,max_ind,&P);
if (jj<0) break;
sll=pSize(strat->S[jj]);
if (sll<sl)
{
#ifdef KDEBUG
if (TEST_OPT_DEBUG) Print("better(S%d:%d -> S%d:%d)\n",j,sl,jj,sll);
#endif
//else if (TEST_OPT_PROT) { PrintS("b"); mflush(); }
j=jj;
sl=sll;
}
}
if ((nonorm==0) && (!nIsOne(pGetCoeff(strat->S[j]))))
{
pNorm(strat->S[j]);
//if (TEST_OPT_PROT) { PrintS("n"); mflush(); }
}
}
nNormalize(pGetCoeff(P.p));
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("red:");
wrp(h);
PrintS(" with ");
wrp(strat->S[j]);
}
#endif
#ifdef HAVE_PLURAL
if (rIsPluralRing(currRing))
{
number coef;
nc_kBucketPolyRed_NF(P.bucket,strat->S[j],&coef,nonorm);
nDelete(&coef);
}
else
#endif
{
kBucketPolyRedNF(P.bucket,strat->S[j],pLength(strat->S[j]),strat->kNoether);
P.p = kBucketClear(P.bucket);
P.p = pJet(P.p,bound);
if(!P.IsNull())
{
kBucketDestroy(&P.bucket);
P.SetShortExpVector();
P.bucket = kBucketCreate(currRing);
kBucketInit(P.bucket,P.p,pLength(P.p));
}
}
h = kBucketGetLm(P.bucket); // FRAGE OLIVER
if (h==NULL)
{
kBucketDestroy(&P.bucket);
return NULL;
}
kbTest(P.bucket);
P.p=h;
P.t_p=NULL;
P.SetShortExpVector();
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("\nto:");
wrp(h);
PrintLn();
}
#endif
}
else
{
P.p=kBucketClear(P.bucket);
kBucketDestroy(&P.bucket);
pNormalize(P.p);
return P.p;
}
}
}
void kDebugPrint(kStrategy strat);
ideal bba (ideal F, ideal Q,intvec *w,bigintmat *hilb,kStrategy strat)
{
int red_result = 1;
int olddeg,reduc;
int hilbeledeg=1,hilbcount=0,minimcnt=0;
BOOLEAN withT = FALSE;
BITSET save;
SI_SAVE_OPT1(save);
initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
if(rField_is_Ring(currRing))
initBuchMoraPosRing(strat);
else
initBuchMoraPos(strat);
initHilbCrit(F,Q,&hilb,strat);
initBba(strat);
/*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
initBuchMora(F, Q,strat);
if(errorreported) return NULL;
if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
reduc = olddeg = 0;
#ifndef NO_BUCKETS
if (!TEST_OPT_NOT_BUCKETS)
strat->use_buckets = 1;
#endif
// redtailBBa against T for inhomogeneous input
if (!TEST_OPT_OLDSTD)
withT = ! strat->homog;
// strat->posInT = posInT_pLength;
#ifdef KDEBUG
kTest_TS(strat);
#endif
#ifdef HAVE_TAIL_RING
if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
kStratInitChangeTailRing(strat);
#endif
#ifdef KDEBUG
//kDebugPrint(strat);
#endif
/* compute------------------------------------------------------- */
while (strat->Ll >= 0)
{
#ifdef KDEBUG
if (TEST_OPT_DEBUG) messageSets(strat);
#endif
if (siCntrlc)
{
while (strat->Ll >= 0)
deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
strat->noClearS=TRUE;
}
if (TEST_OPT_DEGBOUND
&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
|| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
{
/*
*stops computation if
* 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
*a predefined number Kstd1_deg
*/
while ((strat->Ll >= 0)
&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
|| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
)
{
deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
if(TEST_OPT_PROT) PrintS("D");
}
if (strat->Ll<0) break;
else strat->noClearS=TRUE;
}
if (strat->Ll== 0) strat->interpt=TRUE;
/* picks the last element from the lazyset L */
strat->P = strat->L[strat->Ll];
strat->Ll--;
if (pNext(strat->P.p) == strat->tail)
{
// deletes the short spoly
if (rField_is_Ring(currRing))
pLmDelete(strat->P.p);
else
pLmFree(strat->P.p);
strat->P.p = NULL;
poly m1 = NULL, m2 = NULL;
// check that spoly creation is ok
while (strat->tailRing != currRing &&
!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
{
assume(m1 == NULL && m2 == NULL);
// if not, change to a ring where exponents are at least
// large enough
if (!kStratChangeTailRing(strat))
{
WerrorS("OVERFLOW...");
break;
}
}
// create the real one
ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
strat->tailRing, m1, m2, strat->R);
}
else if (strat->P.p1 == NULL)
{
if (strat->minim > 0)
strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
// for input polys, prepare reduction
strat->P.PrepareRed(strat->use_buckets);
}
if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
{
red_result = 0;
}
else
{
if (TEST_OPT_PROT)
message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
&olddeg,&reduc,strat, red_result);
/* reduction of the element chosen from L */
red_result = strat->red(&strat->P,strat);
if (errorreported) break;
}
if (strat->overflow)
{
if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
}
// reduction to non-zero new poly
if (red_result == 1)
{
// get the polynomial (canonicalize bucket, make sure P.p is set)
strat->P.GetP(strat->lmBin);
// in the homogeneous case FDeg >= pFDeg (sugar/honey)
// but now, for entering S, T, we reset it
// in the inhomogeneous case: FDeg == pFDeg
if (strat->homog) strat->initEcart(&(strat->P));
/* statistic */
if (TEST_OPT_PROT) PrintS("s");
int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
// reduce the tail and normalize poly
// in the ring case we cannot expect LC(f) = 1,
strat->redTailChange=FALSE;
/* if we are computing over Z we always want to try and cut down
* the coefficients in the tail terms */
if (rField_is_Z(currRing) && !rHasLocalOrMixedOrdering(currRing))
{
redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
}
if (TEST_OPT_INTSTRATEGY)
{
strat->P.pCleardenom();
if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
{
strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
strat->P.pCleardenom();
if (strat->redTailChange) { strat->P.t_p=NULL; }
}
}
else
{
strat->P.pNorm();
if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
{
strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
if (strat->redTailChange) { strat->P.t_p=NULL; }
}
}
#ifdef KDEBUG
if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
#endif /* KDEBUG */
// min_std stuff
if ((strat->P.p1==NULL) && (strat->minim>0))
{
if (strat->minim==1)
{
strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
p_Delete(&strat->P.p2, currRing, strat->tailRing);
}
else
{
strat->M->m[minimcnt]=strat->P.p2;
strat->P.p2=NULL;
}
if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
pNext(strat->M->m[minimcnt])
= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
strat->tailRing, currRing,
currRing->PolyBin);
minimcnt++;
}
// enter into S, L, and T
if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
{
strat->P.SetShortExpVector();
enterT(&strat->P, strat);
if (rField_is_Ring(currRing))
superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
else
enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
// posInS only depends on the leading term
strat->enterS(&strat->P, pos, strat, strat->tl);
#if 0
int pl=pLength(strat->P.p);
if (pl==1)
{
//if (TEST_OPT_PROT)
//PrintS("<1>");
}
else if (pl==2)
{
//if (TEST_OPT_PROT)
//PrintS("<2>");
}
#endif
}
if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
// Print("[%d]",hilbeledeg);
kDeleteLcm(&strat->P);
if (strat->s_poly!=NULL)
{
// the only valid entries are: strat->P.p,
// strat->tailRing (read-only, keep it)
// (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
if (strat->s_poly(strat))
{
// we are called AFTER enterS, i.e. if we change P
// we have to add it also to S/T
// and add pairs
int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
enterT(&strat->P, strat);
if (rField_is_Ring(currRing))
superenterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
else
enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
strat->enterS(&strat->P, pos, strat, strat->tl);
}
}
}
else if (strat->P.p1 == NULL && strat->minim > 0)
{
p_Delete(&strat->P.p2, currRing, strat->tailRing);
}
#ifdef KDEBUG
strat->P.Init();
kTest_TS(strat);
#endif /* KDEBUG */
}
#ifdef KDEBUG
if (TEST_OPT_DEBUG) messageSets(strat);
#endif /* KDEBUG */
if (TEST_OPT_SB_1)
{
if(!rField_is_Ring(currRing))
{
int k=1;
int j;
while(k<=strat->sl)
{
j=0;
loop
{
if (j>=k) break;
clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
j++;
}
k++;
}
}
}
/* complete reduction of the standard basis--------- */
if (TEST_OPT_REDSB)
{
completeReduce(strat);
if (strat->completeReduce_retry)
{
// completeReduce needed larger exponents, retry
// to reduce with S (instead of T)
// and in currRing (instead of strat->tailRing)
#ifdef HAVE_TAIL_RING
if(currRing->bitmask>strat->tailRing->bitmask)
{
strat->completeReduce_retry=FALSE;
cleanT(strat);strat->tailRing=currRing;
int i;
for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
completeReduce(strat);
}
if (strat->completeReduce_retry)
#endif
Werror("exponent bound is %ld",currRing->bitmask);
}
}
else if (TEST_OPT_PROT) PrintLn();
/* release temp data-------------------------------- */
exitBuchMora(strat);
/* postprocessing for GB over ZZ --------------------*/
if (!errorreported)
{
if(rField_is_Z(currRing))
{
for(int i = 0;i<=strat->sl;i++)
{
if(!nGreaterZero(pGetCoeff(strat->S[i])))
{
strat->S[i] = pNeg(strat->S[i]);
}
}
finalReduceByMon(strat);
for(int i = 0;i<IDELEMS(strat->Shdl);i++)
{
if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
{
strat->S[i] = pNeg(strat->Shdl->m[i]);
}
}
}
//else if (rField_is_Ring(currRing))
// finalReduceByMon(strat);
}
// if (TEST_OPT_WEIGHTM)
// {
// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
// if (ecartWeights)
// {
// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
// ecartWeights=NULL;
// }
// }
if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
SI_RESTORE_OPT1(save);
/* postprocessing for GB over Q-rings ------------------*/
if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
idTest(strat->Shdl);
return (strat->Shdl);
}
ideal sba (ideal F0, ideal Q,intvec *w,bigintmat *hilb,kStrategy strat)
{
// ring order stuff:
// in sba we have (until now) two possibilities:
// 1. an incremental computation w.r.t. (C,monomial order)
// 2. a (possibly non-incremental) computation w.r.t. the
// induced Schreyer order.
// The corresponding orders are computed in sbaRing(), depending
// on the flag strat->sbaOrder
#if SBA_PRINT_ZERO_REDUCTIONS
long zeroreductions = 0;
#endif
#if SBA_PRINT_PRODUCT_CRITERION
long product_criterion = 0;
#endif
#if SBA_PRINT_SIZE_G
int size_g = 0;
int size_g_non_red = 0;
#endif
#if SBA_PRINT_SIZE_SYZ
long size_syz = 0;
#endif
// global variable
#if SBA_PRINT_REDUCTION_STEPS
sba_reduction_steps = 0;
sba_interreduction_steps = 0;
#endif
#if SBA_PRINT_OPERATIONS
sba_operations = 0;
sba_interreduction_operations = 0;
#endif
ideal F1 = F0;
ring currRingOld = currRing;
ring sRing = currRing;
if (strat->sbaOrder == 1 || strat->sbaOrder == 3)
{
sRing = sbaRing(strat);
if (sRing!=currRingOld)
{
rChangeCurrRing (sRing);
F1 = idrMoveR (F0, currRingOld, currRing);
}
}
ideal F;
// sort ideal F
//Put the SigDrop element on the correct position (think of sbaEnterS)
//We also sort them
if(rField_is_Ring(currRing) && strat->sigdrop)
{
#if 1
F = idInit(IDELEMS(F1),F1->rank);
for (int i=0; i<IDELEMS(F1);++i)
F->m[i] = F1->m[i];
if(strat->sbaEnterS >= 0)
{
poly dummy;
dummy = pCopy(F->m[0]); //the sigdrop element
for(int i = 0;i<strat->sbaEnterS;i++)
F->m[i] = F->m[i+1];
F->m[strat->sbaEnterS] = dummy;
}
#else
F = idInit(1,F1->rank);
//printf("\nBefore the initial block sorting:\n");idPrint(F1);
F->m[0] = F1->m[0];
int pos;
if(strat->sbaEnterS >= 0)
{
for(int i=1;i<=strat->sbaEnterS;i++)
{
pos = posInIdealMonFirst(F,F1->m[i],1,strat->sbaEnterS);
idInsertPolyOnPos(F,F1->m[i],pos);
}
for(int i=strat->sbaEnterS+1;i<IDELEMS(F1);i++)
{
pos = posInIdealMonFirst(F,F1->m[i],strat->sbaEnterS+1,IDELEMS(F));
idInsertPolyOnPos(F,F1->m[i],pos);
}
poly dummy;
dummy = pCopy(F->m[0]); //the sigdrop element
for(int i = 0;i<strat->sbaEnterS;i++)
F->m[i] = F->m[i+1];
F->m[strat->sbaEnterS] = dummy;
}
else
{
for(int i=1;i<IDELEMS(F1);i++)
{
pos = posInIdealMonFirst(F,F1->m[i],1,IDELEMS(F));
idInsertPolyOnPos(F,F1->m[i],pos);
}
}
#endif
//printf("\nAfter the initial block sorting:\n");idPrint(F);getchar();
}
else
{
F = idInit(IDELEMS(F1),F1->rank);
intvec *sort = idSort(F1);
for (int i=0; i<sort->length();++i)
F->m[i] = F1->m[(*sort)[i]-1];
if(rField_is_Ring(currRing))
{
// put the monomials after the sbaEnterS polynomials
//printf("\nThis is the ideal before sorting (sbaEnterS = %i)\n",strat->sbaEnterS);idPrint(F);
int nrmon = 0;
for(int i = IDELEMS(F)-1,j;i>strat->sbaEnterS+nrmon+1 ;i--)
{
//pWrite(F->m[i]);
if(F->m[i] != NULL && pNext(F->m[i]) == NULL)
{
poly mon = F->m[i];
for(j = i;j>strat->sbaEnterS+nrmon+1;j--)
{
F->m[j] = F->m[j-1];
}
F->m[j] = mon;
nrmon++;
}
//idPrint(F);
}
}
}
//printf("\nThis is the ideal after sorting\n");idPrint(F);getchar();
if(rField_is_Ring(currRing))
strat->sigdrop = FALSE;
strat->nrsyzcrit = 0;
strat->nrrewcrit = 0;
#if SBA_INTERRED_START
F = kInterRed(F,NULL);
#endif
#if F5DEBUG
printf("SBA COMPUTATIONS DONE IN THE FOLLOWING RING:\n");
rWrite (currRing);
printf("ordSgn = %d\n",currRing->OrdSgn);
printf("\n");
#endif
int srmax,lrmax, red_result = 1;
int olddeg,reduc;
int hilbeledeg=1,hilbcount=0,minimcnt=0;
LObject L;
BOOLEAN withT = TRUE;
strat->max_lower_index = 0;
//initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
initSbaCrit(strat); /*set Gebauer, honey, sugarCrit*/
initSbaPos(strat);
initHilbCrit(F,Q,&hilb,strat);
initSba(F,strat);
/*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
/*Shdl=*/initSbaBuchMora(F, Q,strat);
idTest(strat->Shdl);
if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
srmax = strat->sl;
reduc = olddeg = lrmax = 0;
#ifndef NO_BUCKETS
if (!TEST_OPT_NOT_BUCKETS)
strat->use_buckets = 1;
#endif
// redtailBBa against T for inhomogeneous input
// if (!TEST_OPT_OLDSTD)
// withT = ! strat->homog;
// strat->posInT = posInT_pLength;
kTest_TS(strat);
#ifdef HAVE_TAIL_RING
if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
kStratInitChangeTailRing(strat);
#endif
// We add the elements directly in S from the previous loop
if(rField_is_Ring(currRing) && strat->sbaEnterS >= 0)
{
for(int i = 0;i<strat->sbaEnterS;i++)
{
//Update: now the element is at the correct place
//i+1 because on the 0 position is the sigdrop element
enterT(&strat->L[strat->Ll-(i)],strat);
strat->enterS(&strat->L[strat->Ll-(i)], strat->sl+1, strat, strat->tl);
}
strat->Ll = strat->Ll - strat->sbaEnterS;
strat->sbaEnterS = -1;
}
kTest_TS(strat);
#ifdef KDEBUG
//kDebugPrint(strat);
#endif
/* compute------------------------------------------------------- */
while (strat->Ll >= 0)
{
if (strat->Ll > lrmax) lrmax =strat->Ll;/*stat.*/
#ifdef KDEBUG
if (TEST_OPT_DEBUG) messageSets(strat);
#endif
if (strat->Ll== 0) strat->interpt=TRUE;
/*
if (TEST_OPT_DEGBOUND
&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
|| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
{
//stops computation if
// 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
//a predefined number Kstd1_deg
while ((strat->Ll >= 0)
&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
|| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
)
deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
if (strat->Ll<0) break;
else strat->noClearS=TRUE;
}
*/
if (strat->sbaOrder == 1 && pGetComp(strat->L[strat->Ll].sig) != strat->currIdx)
{
strat->currIdx = pGetComp(strat->L[strat->Ll].sig);
#if F5C
// 1. interreduction of the current standard basis
// 2. generation of new principal syzygy rules for syzCriterion
f5c ( strat, olddeg, minimcnt, hilbeledeg, hilbcount, srmax,
lrmax, reduc, Q, w, hilb );
#endif
// initialize new syzygy rules for the next iteration step
initSyzRules(strat);
}
/*********************************************************************
* interrreduction step is done, we can go on with the next iteration
* step of the signature-based algorithm
********************************************************************/
/* picks the last element from the lazyset L */
strat->P = strat->L[strat->Ll];
strat->Ll--;
if(rField_is_Ring(currRing))
strat->sbaEnterS = pGetComp(strat->P.sig) - 1;
/* reduction of the element chosen from L */
if (!strat->rewCrit2(strat->P.sig, ~strat->P.sevSig, strat->P.GetLmCurrRing(), strat, strat->P.checked+1))
{
//#if 1
#ifdef DEBUGF5
PrintS("SIG OF NEXT PAIR TO HANDLE IN SIG-BASED ALGORITHM\n");
PrintS("-------------------------------------------------\n");
pWrite(strat->P.sig);
pWrite(pHead(strat->P.p));
pWrite(pHead(strat->P.p1));
pWrite(pHead(strat->P.p2));
PrintS("-------------------------------------------------\n");
#endif
if (pNext(strat->P.p) == strat->tail)
{
// deletes the short spoly
/*
if (rField_is_Ring(currRing))
pLmDelete(strat->P.p);
else
pLmFree(strat->P.p);
*/
// TODO: needs some masking
// TODO: masking needs to vanish once the signature
// stuff is completely implemented
strat->P.p = NULL;
poly m1 = NULL, m2 = NULL;
// check that spoly creation is ok
while (strat->tailRing != currRing &&
!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
{
assume(m1 == NULL && m2 == NULL);
// if not, change to a ring where exponents are at least
// large enough
if (!kStratChangeTailRing(strat))
{
WerrorS("OVERFLOW...");
break;
}
}
// create the real one
ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
strat->tailRing, m1, m2, strat->R);
}
else if (strat->P.p1 == NULL)
{
if (strat->minim > 0)
strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
// for input polys, prepare reduction
if(!rField_is_Ring(currRing))
strat->P.PrepareRed(strat->use_buckets);
}
if (strat->P.p == NULL && strat->P.t_p == NULL)
{
red_result = 0;
}
else
{
//#if 1
#ifdef DEBUGF5
PrintS("Poly before red: ");
pWrite(pHead(strat->P.p));
pWrite(strat->P.sig);
#endif
#if SBA_PRODUCT_CRITERION
if (strat->P.prod_crit)
{
#if SBA_PRINT_PRODUCT_CRITERION
product_criterion++;
#endif
int pos = posInSyz(strat, strat->P.sig);
enterSyz(strat->P, strat, pos);
kDeleteLcm(&strat->P);
red_result = 2;
}
else
{
red_result = strat->red(&strat->P,strat);
}
#else
red_result = strat->red(&strat->P,strat);
#endif
}
}
else
{
/*
if (strat->P.lcm != NULL)
pLmFree(strat->P.lcm);
*/
red_result = 2;
}
if(rField_is_Ring(currRing))
{
if(strat->P.sig!= NULL && !nGreaterZero(pGetCoeff(strat->P.sig)))
{
strat->P.p = pNeg(strat->P.p);
strat->P.sig = pNeg(strat->P.sig);
}
strat->P.pLength = pLength(strat->P.p);
if(strat->P.sig != NULL)
strat->P.sevSig = pGetShortExpVector(strat->P.sig);
if(strat->P.p != NULL)
strat->P.sev = pGetShortExpVector(strat->P.p);
}
//sigdrop case
if(rField_is_Ring(currRing) && strat->sigdrop)
{
//First reduce it as much as one can
red_result = redRing(&strat->P,strat);
if(red_result == 0)
{
strat->sigdrop = FALSE;
pDelete(&strat->P.sig);
strat->P.sig = NULL;
}
else
{
strat->enterS(&strat->P, 0, strat, strat->tl);
if (TEST_OPT_PROT)
PrintS("-");
break;
}
}
if(rField_is_Ring(currRing) && strat->blockred > strat->blockredmax)
{
strat->sigdrop = TRUE;
break;
}
if (errorreported) break;
//#if 1
#ifdef DEBUGF5
if (red_result != 0)
{
PrintS("Poly after red: ");
pWrite(pHead(strat->P.p));
pWrite(strat->P.GetLmCurrRing());
pWrite(strat->P.sig);
printf("%d\n",red_result);
}
#endif
if (TEST_OPT_PROT)
{
if(strat->P.p != NULL)
message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
&olddeg,&reduc,strat, red_result);
else
message((strat->honey ? strat->P.ecart : 0),
&olddeg,&reduc,strat, red_result);
}
if (strat->overflow)
{
if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
}
// reduction to non-zero new poly
if (red_result == 1)
{
// get the polynomial (canonicalize bucket, make sure P.p is set)
strat->P.GetP(strat->lmBin);
// sig-safe computations may lead to wrong FDeg computation, thus we need
// to recompute it to make sure everything is alright
(strat->P).FDeg = (strat->P).pFDeg();
// in the homogeneous case FDeg >= pFDeg (sugar/honey)
// but now, for entering S, T, we reset it
// in the inhomogeneous case: FDeg == pFDeg
if (strat->homog) strat->initEcart(&(strat->P));
/* statistic */
if (TEST_OPT_PROT) PrintS("s");
//int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
// in F5E we know that the last reduced element is already the
// the one with highest signature
int pos = strat->sl+1;
// reduce the tail and normalize poly
// in the ring case we cannot expect LC(f) = 1,
poly beforetailred;
if(rField_is_Ring(currRing))
beforetailred = pCopy(strat->P.sig);
#if SBA_TAIL_RED
if(rField_is_Ring(currRing))
{
if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
}
else
{
if (strat->sbaOrder != 2)
{
if (TEST_OPT_INTSTRATEGY)
{
strat->P.pCleardenom();
if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
{
strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
strat->P.pCleardenom();
}
}
else
{
strat->P.pNorm();
if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
strat->P.p = redtailSba(&(strat->P),pos-1,strat, withT);
}
}
}
// It may happen that we have lost the sig in redtailsba
// It cannot reduce to 0 since here we are doing just tail reduction.
// Best case scenario: remains the leading term
if(rField_is_Ring(currRing) && strat->sigdrop)
{
strat->enterS(&strat->P, 0, strat, strat->tl);
break;
}
#endif
if(rField_is_Ring(currRing))
{
if(strat->P.sig == NULL || pLtCmp(beforetailred,strat->P.sig) == 1)
{
strat->sigdrop = TRUE;
//Reduce it as much as you can
red_result = redRing(&strat->P,strat);
if(red_result == 0)
{
//It reduced to 0, cancel the sigdrop
strat->sigdrop = FALSE;
p_Delete(&strat->P.sig,currRing);strat->P.sig = NULL;
}
else
{
strat->enterS(&strat->P, 0, strat, strat->tl);
break;
}
}
p_Delete(&beforetailred,currRing);
// strat->P.p = NULL may appear if we had a sigdrop above and reduced to 0 via redRing
if(strat->P.p == NULL)
goto case_when_red_result_changed;
}
// remove sigsafe label since it is no longer valid for the next element to
// be reduced
if (strat->sbaOrder == 1)
{
for (int jj = 0; jj<strat->tl+1; jj++)
{
if (pGetComp(strat->T[jj].sig) == strat->currIdx)
{
strat->T[jj].is_sigsafe = FALSE;
}
}
}
else
{
for (int jj = 0; jj<strat->tl+1; jj++)
{
strat->T[jj].is_sigsafe = FALSE;
}
}
#ifdef KDEBUG
if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
#endif /* KDEBUG */
// min_std stuff
if ((strat->P.p1==NULL) && (strat->minim>0))
{
if (strat->minim==1)
{
strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
p_Delete(&strat->P.p2, currRing, strat->tailRing);
}
else
{
strat->M->m[minimcnt]=strat->P.p2;
strat->P.p2=NULL;
}
if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
pNext(strat->M->m[minimcnt])
= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
strat->tailRing, currRing,
currRing->PolyBin);
minimcnt++;
}
// enter into S, L, and T
//if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
enterT(&strat->P, strat);
strat->T[strat->tl].is_sigsafe = FALSE;
/*
printf("hier\n");
pWrite(strat->P.GetLmCurrRing());
pWrite(strat->P.sig);
*/
if (rField_is_Ring(currRing))
superenterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
else
enterpairsSig(strat->P.p,strat->P.sig,strat->sl+1,strat->sl,strat->P.ecart,pos,strat, strat->tl);
if(rField_is_Ring(currRing) && strat->sigdrop)
break;
if(rField_is_Ring(currRing))
strat->P.sevSig = p_GetShortExpVector(strat->P.sig,currRing);
strat->enterS(&strat->P, pos, strat, strat->tl);
if(strat->sbaOrder != 1)
{
BOOLEAN overwrite = FALSE;
for (int tk=0; tk<strat->sl+1; tk++)
{
if (pGetComp(strat->sig[tk]) == pGetComp(strat->P.sig))
{
//printf("TK %d / %d\n",tk,strat->sl);
overwrite = FALSE;
break;
}
}
//printf("OVERWRITE %d\n",overwrite);
if (overwrite)
{
int cmp = pGetComp(strat->P.sig);
int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
p_GetExpV (strat->P.p,vv,currRing);
p_SetExpV (strat->P.sig, vv,currRing);
p_SetComp (strat->P.sig,cmp,currRing);
strat->P.sevSig = pGetShortExpVector (strat->P.sig);
int i;
LObject Q;
for(int ps=0;ps<strat->sl+1;ps++)
{
strat->newt = TRUE;
if (strat->syzl == strat->syzmax)
{
pEnlargeSet(&strat->syz,strat->syzmax,setmaxTinc);
strat->sevSyz = (unsigned long*) omRealloc0Size(strat->sevSyz,
(strat->syzmax)*sizeof(unsigned long),
((strat->syzmax)+setmaxTinc)
*sizeof(unsigned long));
strat->syzmax += setmaxTinc;
}
Q.sig = pCopy(strat->P.sig);
// add LM(F->m[i]) to the signature to get a Schreyer order
// without changing the underlying polynomial ring at all
if (strat->sbaOrder == 0)
p_ExpVectorAdd (Q.sig,strat->S[ps],currRing);
// since p_Add_q() destroys all input
// data we need to recreate help
// each time
// ----------------------------------------------------------
// in the Schreyer order we always know that the multiplied
// module monomial strat->P.sig gives the leading monomial of
// the corresponding principal syzygy
// => we do not need to compute the "real" syzygy completely
poly help = p_Copy(strat->sig[ps],currRing);
p_ExpVectorAdd (help,strat->P.p,currRing);
Q.sig = p_Add_q(Q.sig,help,currRing);
//printf("%d. SYZ ",i+1);
//pWrite(strat->syz[i]);
Q.sevSig = p_GetShortExpVector(Q.sig,currRing);
i = posInSyz(strat, Q.sig);
enterSyz(Q, strat, i);
}
}
}
// deg - idx - lp/rp
// => we need to add syzygies with indices > pGetComp(strat->P.sig)
if(strat->sbaOrder == 0 || strat->sbaOrder == 3)
{
int cmp = pGetComp(strat->P.sig);
unsigned max_cmp = IDELEMS(F);
int* vv = (int*)omAlloc((currRing->N+1)*sizeof(int));
p_GetExpV (strat->P.p,vv,currRing);
LObject Q;
int pos;
int idx = __p_GetComp(strat->P.sig,currRing);
//printf("++ -- adding syzygies -- ++\n");
// if new element is the first one in this index
if (strat->currIdx < idx)
{
for (int i=0; i<strat->sl; ++i)
{
Q.sig = p_Copy(strat->P.sig,currRing);
p_ExpVectorAdd(Q.sig,strat->S[i],currRing);
poly help = p_Copy(strat->sig[i],currRing);
p_ExpVectorAdd(help,strat->P.p,currRing);
Q.sig = p_Add_q(Q.sig,help,currRing);
//pWrite(Q.sig);
pos = posInSyz(strat, Q.sig);
enterSyz(Q, strat, pos);
}
strat->currIdx = idx;
}
else
{
// if the element is not the first one in the given index we build all
// possible syzygies with elements of higher index
for (unsigned i=cmp+1; i<=max_cmp; ++i)
{
pos = -1;
for (int j=0; j<strat->sl; ++j)
{
if (__p_GetComp(strat->sig[j],currRing) == i)
{
pos = j;
break;
}
}
if (pos != -1)
{
Q.sig = p_One(currRing);
p_SetExpV(Q.sig, vv, currRing);
// F->m[i-1] corresponds to index i
p_ExpVectorAdd(Q.sig,F->m[i-1],currRing);
p_SetComp(Q.sig, i, currRing);
poly help = p_Copy(strat->P.sig,currRing);
p_ExpVectorAdd(help,strat->S[pos],currRing);
Q.sig = p_Add_q(Q.sig,help,currRing);
if (strat->sbaOrder == 0)
{
if (p_LmCmp(Q.sig,strat->syz[strat->syzl-1],currRing) == -currRing->OrdSgn)
{
pos = posInSyz(strat, Q.sig);
enterSyz(Q, strat, pos);
}
}
else
{
pos = posInSyz(strat, Q.sig);
enterSyz(Q, strat, pos);
}
}
}
//printf("++ -- done adding syzygies -- ++\n");
}
}
//#if 1
#if DEBUGF50
printf("---------------------------\n");
Print(" %d. ELEMENT ADDED TO GCURR:\n",strat->sl+1);
PrintS("LEAD POLY: "); pWrite(pHead(strat->S[strat->sl]));
PrintS("SIGNATURE: "); pWrite(strat->sig[strat->sl]);
#endif
/*
if (newrules)
{
newrules = FALSE;
}
*/
#if 0
int pl=pLength(strat->P.p);
if (pl==1)
{
//if (TEST_OPT_PROT)
//PrintS("<1>");
}
else if (pl==2)
{
//if (TEST_OPT_PROT)
//PrintS("<2>");
}
#endif
if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
// Print("[%d]",hilbeledeg);
kDeleteLcm(&strat->P);
if (strat->sl>srmax) srmax = strat->sl;
}
else
{
case_when_red_result_changed:
// adds signature of the zero reduction to
// strat->syz. This is the leading term of
// syzygy and can be used in syzCriterion()
// the signature is added if and only if the
// pair was not detected by the rewritten criterion in strat->red = redSig
if (red_result!=2)
{
#if SBA_PRINT_ZERO_REDUCTIONS
zeroreductions++;
#endif
if(rField_is_Ring(currRing) && strat->P.p == NULL && strat->P.sig == NULL)
{
//Catch the case when p = 0, sig = 0
}
else
{
int pos = posInSyz(strat, strat->P.sig);
enterSyz(strat->P, strat, pos);
//#if 1
#ifdef DEBUGF5
Print("ADDING STUFF TO SYZ : ");
//pWrite(strat->P.p);
pWrite(strat->P.sig);
#endif
}
}
if (strat->P.p1 == NULL && strat->minim > 0)
{
p_Delete(&strat->P.p2, currRing, strat->tailRing);
}
}
#ifdef KDEBUG
strat->P.Init();
#endif /* KDEBUG */
kTest_TS(strat);
}
#if 0
if(strat->sigdrop)
printf("\nSigDrop!\n");
else
printf("\nEnded with no SigDrop\n");
#endif
// Clean strat->P for the next sba call
if(rField_is_Ring(currRing) && strat->sigdrop)
{
//This is used to know how many elements can we directly add to S in the next run
if(strat->P.sig != NULL)
strat->sbaEnterS = pGetComp(strat->P.sig)-1;
//else we already set it at the beginning of the loop
#ifdef KDEBUG
strat->P.Init();
#endif /* KDEBUG */
}
#ifdef KDEBUG
if (TEST_OPT_DEBUG) messageSets(strat);
#endif /* KDEBUG */
if (TEST_OPT_SB_1)
{
if(!rField_is_Ring(currRing))
{
int k=1;
int j;
while(k<=strat->sl)
{
j=0;
loop
{
if (j>=k) break;
clearS(strat->S[j],strat->sevS[j],&k,&j,strat);
j++;
}
k++;
}
}
}
/* complete reduction of the standard basis--------- */
if (TEST_OPT_REDSB)
{
completeReduce(strat);
if (strat->completeReduce_retry)
{
// completeReduce needed larger exponents, retry
// to reduce with S (instead of T)
// and in currRing (instead of strat->tailRing)
#ifdef HAVE_TAIL_RING
if(currRing->bitmask>strat->tailRing->bitmask)
{
strat->completeReduce_retry=FALSE;
cleanT(strat);strat->tailRing=currRing;
int i;
for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
completeReduce(strat);
}
if (strat->completeReduce_retry)
#endif
Werror("exponent bound is %ld",currRing->bitmask);
}
}
else if (TEST_OPT_PROT) PrintLn();
#if SBA_PRINT_SIZE_SYZ
// that is correct, syzl is counting one too far
size_syz = strat->syzl;
#endif
// if (TEST_OPT_WEIGHTM)
// {
// pRestoreDegProcs(pFDegOld, pLDegOld);
// if (ecartWeights)
// {
// omFreeSize((ADDRESS)ecartWeights,(pVariables+1)*sizeof(short));
// ecartWeights=NULL;
// }
// }
if (TEST_OPT_PROT) messageStatSBA(hilbcount,strat);
if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
#if SBA_PRINT_SIZE_G
size_g_non_red = IDELEMS(strat->Shdl);
#endif
if(!rField_is_Ring(currRing))
exitSba(strat);
// I have to add the initial input polynomials which where not used (p1 and p2 = NULL)
int k;
if(rField_is_Ring(currRing))
{
//for(k = strat->sl;k>=0;k--)
// {printf("\nS[%i] = %p\n",k,strat->Shdl->m[k]);pWrite(strat->Shdl->m[k]);}
k = strat->Ll;
#if 1
// 1 - adds just the unused ones, 0 - adds everything
for(;k>=0 && (strat->L[k].p1 != NULL || strat->L[k].p2 != NULL);k--)
{
//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);
deleteInL(strat->L,&strat->Ll,k,strat);
}
#endif
//for(int kk = strat->sl;kk>=0;kk--)
// {printf("\nS[%i] = %p\n",kk,strat->Shdl->m[kk]);pWrite(strat->Shdl->m[kk]);}
//idPrint(strat->Shdl);
//printf("\nk = %i\n",k);
for(;k>=0 && strat->L[k].p1 == NULL && strat->L[k].p2 == NULL;k--)
{
//printf("\nAdded k = %i\n",k);
strat->enterS(&strat->L[k], strat->sl+1, strat, strat->tl);
//printf("\nThis elements was added from L on pos %i\n",strat->sl);pWrite(strat->S[strat->sl]);pWrite(strat->sig[strat->sl]);
}
}
// 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
#if 0
if(strat->sigdrop && rField_is_Ring(currRing))
{
for(k=strat->sl;k>=0;k--)
{
printf("\nsig[%i] = ",i);pWrite(strat->sig[k]);
if(strat->sig[k] == NULL)
strat->sig[k] = pCopy(strat->sig[k-1]);
}
}
#endif
//Never do this - you will damage S
//idSkipZeroes(strat->Shdl);
//idPrint(strat->Shdl);
if ((strat->sbaOrder == 1 || strat->sbaOrder == 3) && sRing!=currRingOld)
{
rChangeCurrRing (currRingOld);
F0 = idrMoveR (F1, sRing, currRing);
strat->Shdl = idrMoveR_NoSort (strat->Shdl, sRing, currRing);
rChangeCurrRing (sRing);
if(rField_is_Ring(currRing))
exitSba(strat);
rChangeCurrRing (currRingOld);
if(strat->tailRing == sRing)
strat->tailRing = currRing;
rDelete (sRing);
}
if(rField_is_Ring(currRing) && !strat->sigdrop)
id_DelDiv(strat->Shdl, currRing);
if(!rField_is_Ring(currRing))
id_DelDiv(strat->Shdl, currRing);
idSkipZeroes(strat->Shdl);
idTest(strat->Shdl);
#if SBA_PRINT_SIZE_G
size_g = IDELEMS(strat->Shdl);
#endif
#ifdef DEBUGF5
printf("SIZE OF SHDL: %d\n",IDELEMS(strat->Shdl));
int oo = 0;
while (oo<IDELEMS(strat->Shdl))
{
printf(" %d. ",oo+1);
pWrite(pHead(strat->Shdl->m[oo]));
oo++;
}
#endif
#if SBA_PRINT_ZERO_REDUCTIONS
printf("----------------------------------------------------------\n");
printf("ZERO REDUCTIONS: %ld\n",zeroreductions);
zeroreductions = 0;
#endif
#if SBA_PRINT_REDUCTION_STEPS
printf("----------------------------------------------------------\n");
printf("S-REDUCTIONS: %ld\n",sba_reduction_steps);
#endif
#if SBA_PRINT_OPERATIONS
printf("OPERATIONS: %ld\n",sba_operations);
#endif
#if SBA_PRINT_REDUCTION_STEPS
printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
printf("INTERREDUCTIONS: %ld\n",sba_interreduction_steps);
#endif
#if SBA_PRINT_OPERATIONS
printf("INTERREDUCTION OPERATIONS: %ld\n",sba_interreduction_operations);
#endif
#if SBA_PRINT_REDUCTION_STEPS
printf("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - \n");
printf("ALL REDUCTIONS: %ld\n",sba_reduction_steps+sba_interreduction_steps);
sba_interreduction_steps = 0;
sba_reduction_steps = 0;
#endif
#if SBA_PRINT_OPERATIONS
printf("ALL OPERATIONS: %ld\n",sba_operations+sba_interreduction_operations);
sba_interreduction_operations = 0;
sba_operations = 0;
#endif
#if SBA_PRINT_SIZE_G
printf("----------------------------------------------------------\n");
printf("SIZE OF G: %d / %d\n",size_g,size_g_non_red);
size_g = 0;
size_g_non_red = 0;
#endif
#if SBA_PRINT_SIZE_SYZ
printf("SIZE OF SYZ: %ld\n",size_syz);
printf("----------------------------------------------------------\n");
size_syz = 0;
#endif
#if SBA_PRINT_PRODUCT_CRITERION
printf("PRODUCT CRITERIA: %ld\n",product_criterion);
product_criterion = 0;
#endif
return (strat->Shdl);
}
poly kNF2 (ideal F,ideal Q,poly q,kStrategy strat, int lazyReduce)
{
assume(q!=NULL);
assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
// lazy_reduce flags: can be combined by |
//#define KSTD_NF_LAZY 1
// do only a reduction of the leading term
//#define KSTD_NF_NONORM 4
// only global: avoid normalization, return a multiply of NF
//#define KSTD_NF_CANCELUNIT 8
// apply cancelunit to f inf NF(f,I)
//#define KSTD_NF_NOLF 4096
// avoid PrintLn with OPT_PROT
poly p;
//if ((idIs0(F))&&(Q==NULL))
// return pCopy(q); /*F=0*/
//strat->ak = idRankFreeModule(F);
/*- creating temp data structures------------------- -*/
BITSET save1;
SI_SAVE_OPT1(save1);
si_opt_1|=Sy_bit(OPT_REDTAIL);
initBuchMoraCrit(strat);
strat->initEcart = initEcartBBA;
#ifdef HAVE_SHIFTBBA
if (rIsLPRing(currRing))
{
strat->enterS = enterSBbaShift;
}
else
#endif
{
strat->enterS = enterSBba;
}
#ifndef NO_BUCKETS
strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
#endif
/*- set S -*/
strat->sl = -1;
/*- init local data struct.---------------------------------------- -*/
/*Shdl=*/initS(F,Q,strat);
/*- compute------------------------------------------------------- -*/
//if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
//{
// for (i=strat->sl;i>=0;i--)
// pNorm(strat->S[i]);
//}
kTest(strat);
if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
if (BVERBOSE(23)) kDebugPrint(strat);
int max_ind;
p = redNF(pCopy(q),max_ind,(lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat);
if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
{
if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
if (rField_is_Z(currRing)||(rField_is_Zn(currRing)))
{
p = redtailBba_NF(p,strat);
}
else if (rField_is_Ring(currRing))
{
p = redtailBba_Ring(p,max_ind,strat);
}
else
{
si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
}
}
/*- release temp data------------------------------- -*/
assume(strat->L==NULL); /* strat->L unused */
assume(strat->B==NULL); /* strat->B unused */
omFree(strat->sevS);
omFree(strat->ecartS);
assume(strat->T==NULL);//omfree(strat->T);
assume(strat->sevT==NULL);//omfree(strat->sevT);
assume(strat->R==NULL);//omfree(strat->R);
omfree(strat->S_2_R);
omfree(strat->fromQ);
strat->fromQ=NULL;
idDelete(&strat->Shdl);
SI_RESTORE_OPT1(save1);
if (TEST_OPT_PROT && ((lazyReduce &KSTD_NF_NOLF)==0)) PrintLn();
return p;
}
poly kNF2Bound (ideal F,ideal Q,poly q,int bound,kStrategy strat, int lazyReduce)
{
assume(q!=NULL);
assume(!(idIs0(F)&&(Q==NULL))); // NF(q, std(0) in polynomial ring?
// lazy_reduce flags: can be combined by |
//#define KSTD_NF_LAZY 1
// do only a reduction of the leading term
//#define KSTD_NF_NONORM 4
// only global: avoid normalization, return a multiply of NF
poly p;
//if ((idIs0(F))&&(Q==NULL))
// return pCopy(q); /*F=0*/
//strat->ak = idRankFreeModule(F);
/*- creating temp data structures------------------- -*/
BITSET save1;
SI_SAVE_OPT1(save1);
si_opt_1|=Sy_bit(OPT_REDTAIL);
initBuchMoraCrit(strat);
strat->initEcart = initEcartBBA;
strat->enterS = enterSBba;
#ifndef NO_BUCKETS
strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
#endif
/*- set S -*/
strat->sl = -1;
/*- init local data struct.---------------------------------------- -*/
/*Shdl=*/initS(F,Q,strat);
/*- compute------------------------------------------------------- -*/
//if ((TEST_OPT_INTSTRATEGY)&&(lazyReduce==0))
//{
// for (i=strat->sl;i>=0;i--)
// pNorm(strat->S[i]);
//}
kTest(strat);
if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
if (BVERBOSE(23)) kDebugPrint(strat);
int max_ind;
p = redNFBound(pCopy(q),max_ind,lazyReduce & KSTD_NF_NONORM,strat,bound);
if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
{
if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
if (rField_is_Z(currRing)||(rField_is_Zn(currRing)))
{
p = redtailBba_Z(p,max_ind,strat);
}
else if (rField_is_Ring(currRing))
{
p = redtailBba_Ring(p,max_ind,strat);
}
else
{
si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
//p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
}
}
/*- release temp data------------------------------- -*/
assume(strat->L==NULL); /* strat->L unused */
assume(strat->B==NULL); /* strat->B unused */
omFree(strat->sevS);
omFree(strat->ecartS);
assume(strat->T==NULL);//omfree(strat->T);
assume(strat->sevT==NULL);//omfree(strat->sevT);
assume(strat->R==NULL);//omfree(strat->R);
omfree(strat->S_2_R);
omfree(strat->fromQ);
strat->fromQ=NULL;
idDelete(&strat->Shdl);
SI_RESTORE_OPT1(save1);
if (TEST_OPT_PROT) PrintLn();
return p;
}
ideal kNF2 (ideal F,ideal Q,ideal q,kStrategy strat, int lazyReduce)
{
assume(!idIs0(q));
assume(!(idIs0(F)&&(Q==NULL)));
// lazy_reduce flags: can be combined by |
//#define KSTD_NF_LAZY 1
// do only a reduction of the leading term
//#define KSTD_NF_NONORM 4
// only global: avoid normalization, return a multiply of NF
poly p;
int i;
ideal res;
int max_ind;
//if (idIs0(q))
// return idInit(IDELEMS(q),si_max(q->rank,F->rank));
//if ((idIs0(F))&&(Q==NULL))
// return idCopy(q); /*F=0*/
//strat->ak = idRankFreeModule(F);
/*- creating temp data structures------------------- -*/
BITSET save1;
SI_SAVE_OPT1(save1);
si_opt_1|=Sy_bit(OPT_REDTAIL);
initBuchMoraCrit(strat);
strat->initEcart = initEcartBBA;
#ifdef HAVE_SHIFTBBA
if (rIsLPRing(currRing))
{
strat->enterS = enterSBbaShift;
}
else
#endif
{
strat->enterS = enterSBba;
}
/*- set S -*/
strat->sl = -1;
#ifndef NO_BUCKETS
strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
#endif
/*- init local data struct.---------------------------------------- -*/
/*Shdl=*/initS(F,Q,strat);
/*- compute------------------------------------------------------- -*/
res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
for (i=IDELEMS(q)-1; i>=0; i--)
{
if (q->m[i]!=NULL)
{
if (TEST_OPT_PROT) { PrintS("r");mflush(); }
p = redNF(pCopy(q->m[i]),max_ind,
(lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat);
if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
{
if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
if (rField_is_Ring(currRing))
{
p = redtailBba_NF(p,strat);
}
else
{
si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
p = redtailBba(p,max_ind,strat,(lazyReduce & KSTD_NF_NONORM)==0);
}
}
res->m[i]=p;
}
//else
// res->m[i]=NULL;
}
/*- release temp data------------------------------- -*/
assume(strat->L==NULL); /* strat->L unused */
assume(strat->B==NULL); /* strat->B unused */
omFree(strat->sevS);
omFree(strat->ecartS);
assume(strat->T==NULL);//omfree(strat->T);
assume(strat->sevT==NULL);//omfree(strat->sevT);
assume(strat->R==NULL);//omfree(strat->R);
omfree(strat->S_2_R);
omfree(strat->fromQ);
strat->fromQ=NULL;
idDelete(&strat->Shdl);
SI_RESTORE_OPT1(save1);
if (TEST_OPT_PROT) PrintLn();
return res;
}
ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound,kStrategy strat, int lazyReduce)
{
assume(!idIs0(q));
assume(!(idIs0(F)&&(Q==NULL)));
// lazy_reduce flags: can be combined by |
//#define KSTD_NF_LAZY 1
// do only a reduction of the leading term
//#define KSTD_NF_NONORM 4
// only global: avoid normalization, return a multiply of NF
poly p;
int i;
ideal res;
int max_ind;
//if (idIs0(q))
// return idInit(IDELEMS(q),si_max(q->rank,F->rank));
//if ((idIs0(F))&&(Q==NULL))
// return idCopy(q); /*F=0*/
//strat->ak = idRankFreeModule(F);
/*- creating temp data structures------------------- -*/
BITSET save1;
SI_SAVE_OPT1(save1);
si_opt_1|=Sy_bit(OPT_REDTAIL);
initBuchMoraCrit(strat);
strat->initEcart = initEcartBBA;
strat->enterS = enterSBba;
/*- set S -*/
strat->sl = -1;
#ifndef NO_BUCKETS
strat->use_buckets = (!TEST_OPT_NOT_BUCKETS) && (!rIsPluralRing(currRing));
#endif
/*- init local data struct.---------------------------------------- -*/
/*Shdl=*/initS(F,Q,strat);
/*- compute------------------------------------------------------- -*/
res=idInit(IDELEMS(q),si_max(q->rank,F->rank));
for (i=IDELEMS(q)-1; i>=0; i--)
{
if (q->m[i]!=NULL)
{
if (TEST_OPT_PROT) { PrintS("r");mflush(); }
p = redNFBound(pCopy(q->m[i]),max_ind,
(lazyReduce & KSTD_NF_NONORM)==KSTD_NF_NONORM,strat,bound);
if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
{
if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
if (rField_is_Z(currRing)||(rField_is_Zn(currRing)))
{
p = redtailBba_Z(p,max_ind,strat);
}
else if (rField_is_Ring(currRing))
{
p = redtailBba_Ring(p,max_ind,strat);
}
else
{
si_opt_1 &= ~Sy_bit(OPT_INTSTRATEGY);
p = redtailBbaBound(p,max_ind,strat,bound,(lazyReduce & KSTD_NF_NONORM)==0);
}
}
res->m[i]=p;
}
//else
// res->m[i]=NULL;
}
/*- release temp data------------------------------- -*/
assume(strat->L==NULL); /* strat->L unused */
assume(strat->B==NULL); /* strat->B unused */
omFree(strat->sevS);
omFree(strat->ecartS);
assume(strat->T==NULL);//omfree(strat->T);
assume(strat->sevT==NULL);//omfree(strat->sevT);
assume(strat->R==NULL);//omfree(strat->R);
omfree(strat->S_2_R);
omfree(strat->fromQ);
strat->fromQ=NULL;
idDelete(&strat->Shdl);
SI_RESTORE_OPT1(save1);
if (TEST_OPT_PROT) PrintLn();
return res;
}
#if F5C
/*********************************************************************
* interrreduction step of the signature-based algorithm:
* 1. all strat->S are interpreted as new critical pairs
* 2. those pairs need to be completely reduced by the usual (non sig-
* safe) reduction process (including tail reductions)
* 3. strat->S and strat->T are completely new computed in these steps
********************************************************************/
void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
intvec *w,bigintmat *hilb )
{
int Ll_old, red_result = 1;
int pos = 0;
hilbeledeg=1;
hilbcount=0;
minimcnt=0;
srmax = 0; // strat->sl is 0 at this point
reduc = olddeg = lrmax = 0;
// we cannot use strat->T anymore
//cleanT(strat);
//strat->tl = -1;
Ll_old = strat->Ll;
while (strat->tl >= 0)
{
if(!strat->T[strat->tl].is_redundant)
{
LObject h;
h.p = strat->T[strat->tl].p;
h.tailRing = strat->T[strat->tl].tailRing;
h.t_p = strat->T[strat->tl].t_p;
if (h.p!=NULL)
{
if (currRing->OrdSgn==-1)
{
cancelunit(&h);
deleteHC(&h, strat);
}
if (h.p!=NULL)
{
if (TEST_OPT_INTSTRATEGY)
{
h.pCleardenom(); // also does remove Content
}
else
{
h.pNorm();
}
strat->initEcart(&h);
if(rField_is_Ring(currRing))
pos = posInLF5CRing(strat->L, Ll_old+1,strat->Ll,&h,strat);
else
pos = strat->Ll+1;
h.sev = pGetShortExpVector(h.p);
enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
}
}
}
strat->tl--;
}
strat->sl = -1;
#if 0
//#ifdef HAVE_TAIL_RING
if(!rField_is_Ring()) // create strong gcd poly computes with tailring and S[i] ->to be fixed
kStratInitChangeTailRing(strat);
#endif
//enterpairs(pOne(),0,0,-1,strat,strat->tl);
//strat->sl = -1;
/* picks the last element from the lazyset L */
while (strat->Ll>Ll_old)
{
strat->P = strat->L[strat->Ll];
strat->Ll--;
//#if 1
#ifdef DEBUGF5
PrintS("NEXT PAIR TO HANDLE IN INTERRED ALGORITHM\n");
PrintS("-------------------------------------------------\n");
pWrite(pHead(strat->P.p));
pWrite(pHead(strat->P.p1));
pWrite(pHead(strat->P.p2));
printf("%d\n",strat->tl);
PrintS("-------------------------------------------------\n");
#endif
if (pNext(strat->P.p) == strat->tail)
{
// deletes the short spoly
if (rField_is_Ring(currRing))
pLmDelete(strat->P.p);
else
pLmFree(strat->P.p);
// TODO: needs some masking
// TODO: masking needs to vanish once the signature
// stuff is completely implemented
strat->P.p = NULL;
poly m1 = NULL, m2 = NULL;
// check that spoly creation is ok
while (strat->tailRing != currRing &&
!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
{
assume(m1 == NULL && m2 == NULL);
// if not, change to a ring where exponents are at least
// large enough
if (!kStratChangeTailRing(strat))
{
WerrorS("OVERFLOW...");
break;
}
}
// create the real one
ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
strat->tailRing, m1, m2, strat->R);
}
else if (strat->P.p1 == NULL)
{
if (strat->minim > 0)
strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
// for input polys, prepare reduction
if(!rField_is_Ring(currRing))
strat->P.PrepareRed(strat->use_buckets);
}
if (strat->P.p == NULL && strat->P.t_p == NULL)
{
red_result = 0;
}
else
{
if (TEST_OPT_PROT)
message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
&olddeg,&reduc,strat, red_result);
#ifdef DEBUGF5
PrintS("Poly before red: ");
pWrite(strat->P.p);
#endif
/* complete reduction of the element chosen from L */
red_result = strat->red2(&strat->P,strat);
if (errorreported) break;
}
if (strat->overflow)
{
if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
}
// reduction to non-zero new poly
if (red_result == 1)
{
// get the polynomial (canonicalize bucket, make sure P.p is set)
strat->P.GetP(strat->lmBin);
// in the homogeneous case FDeg >= pFDeg (sugar/honey)
// but now, for entering S, T, we reset it
// in the inhomogeneous case: FDeg == pFDeg
if (strat->homog) strat->initEcart(&(strat->P));
/* statistic */
if (TEST_OPT_PROT) PrintS("s");
int pos;
#if 1
if(!rField_is_Ring(currRing))
pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
else
pos = posInSMonFirst(strat,strat->sl,strat->P.p);
#else
pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
#endif
// reduce the tail and normalize poly
// in the ring case we cannot expect LC(f) = 1,
#if F5CTAILRED
BOOLEAN withT = TRUE;
if (TEST_OPT_INTSTRATEGY)
{
strat->P.pCleardenom();
if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
{
strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
strat->P.pCleardenom();
}
}
else
{
strat->P.pNorm();
if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
}
#endif
#ifdef KDEBUG
if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
#endif /* KDEBUG */
// min_std stuff
if ((strat->P.p1==NULL) && (strat->minim>0))
{
if (strat->minim==1)
{
strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
p_Delete(&strat->P.p2, currRing, strat->tailRing);
}
else
{
strat->M->m[minimcnt]=strat->P.p2;
strat->P.p2=NULL;
}
if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
pNext(strat->M->m[minimcnt])
= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
strat->tailRing, currRing,
currRing->PolyBin);
minimcnt++;
}
// enter into S, L, and T
// here we need to recompute new signatures, but those are trivial ones
if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
{
enterT(&strat->P, strat);
// posInS only depends on the leading term
strat->enterS(&strat->P, pos, strat, strat->tl);
//#if 1
#ifdef DEBUGF5
PrintS("ELEMENT ADDED TO GCURR DURING INTERRED: ");
pWrite(pHead(strat->S[strat->sl]));
pWrite(strat->sig[strat->sl]);
#endif
if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
}
// Print("[%d]",hilbeledeg);
kDeleteLcm(&strat->P);
if (strat->sl>srmax) srmax = strat->sl;
}
else
{
// adds signature of the zero reduction to
// strat->syz. This is the leading term of
// syzygy and can be used in syzCriterion()
// the signature is added if and only if the
// pair was not detected by the rewritten criterion in strat->red = redSig
if (strat->P.p1 == NULL && strat->minim > 0)
{
p_Delete(&strat->P.p2, currRing, strat->tailRing);
}
}
#ifdef KDEBUG
strat->P.Init();
#endif /* KDEBUG */
}
int cc = 0;
while (cc<strat->tl+1)
{
strat->T[cc].sig = pOne();
p_SetComp(strat->T[cc].sig,cc+1,currRing);
strat->T[cc].sevSig = pGetShortExpVector(strat->T[cc].sig);
strat->sig[cc] = strat->T[cc].sig;
strat->sevSig[cc] = strat->T[cc].sevSig;
strat->T[cc].is_sigsafe = TRUE;
cc++;
}
strat->max_lower_index = strat->tl;
// set current signature index of upcoming iteration step
// NOTE: this needs to be set here, as otherwise initSyzRules cannot compute
// the corresponding syzygy rules correctly
strat->currIdx = cc+1;
for (int cd=strat->Ll; cd>=0; cd--)
{
p_SetComp(strat->L[cd].sig,cc+1,currRing);
cc++;
}
for (cc=strat->sl+1; cc<IDELEMS(strat->Shdl); ++cc)
strat->Shdl->m[cc] = NULL;
#if 0
printf("\nAfter f5c sorting\n");
for(int i=0;i<=strat->sl;i++)
pWrite(pHead(strat->S[i]));
getchar();
#endif
//#if 1
#if DEBUGF5
PrintS("------------------- STRAT S ---------------------\n");
cc = 0;
while (cc<strat->tl+1)
{
pWrite(pHead(strat->S[cc]));
pWrite(strat->sig[cc]);
printf("- - - - - -\n");
cc++;
}
PrintS("-------------------------------------------------\n");
PrintS("------------------- STRAT T ---------------------\n");
cc = 0;
while (cc<strat->tl+1)
{
pWrite(pHead(strat->T[cc].p));
pWrite(strat->T[cc].sig);
printf("- - - - - -\n");
cc++;
}
PrintS("-------------------------------------------------\n");
PrintS("------------------- STRAT L ---------------------\n");
cc = 0;
while (cc<strat->Ll+1)
{
pWrite(pHead(strat->L[cc].p));
pWrite(pHead(strat->L[cc].p1));
pWrite(pHead(strat->L[cc].p2));
pWrite(strat->L[cc].sig);
printf("- - - - - -\n");
cc++;
}
PrintS("-------------------------------------------------\n");
printf("F5C DONE\nSTRAT SL: %d -- %d\n",strat->sl, strat->currIdx);
#endif
}
#endif
/* shiftgb stuff */
#ifdef HAVE_SHIFTBBA
ideal bbaShift(ideal F, ideal Q,intvec *w,bigintmat *hilb,kStrategy strat)
{
int red_result = 1;
int olddeg,reduc;
int hilbeledeg=1,hilbcount=0,minimcnt=0;
BOOLEAN withT = TRUE; // currently only T contains the shifts
BITSET save;
SI_SAVE_OPT1(save);
initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
if(rField_is_Ring(currRing))
initBuchMoraPosRing(strat);
else
initBuchMoraPos(strat);
initHilbCrit(F,Q,&hilb,strat);
initBba(strat);
/*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
/*Shdl=*/initBuchMora(F, Q,strat);
if (strat->minim>0) strat->M=idInit(IDELEMS(F),F->rank);
reduc = olddeg = 0;
#ifndef NO_BUCKETS
if (!TEST_OPT_NOT_BUCKETS)
strat->use_buckets = 1;
#endif
// redtailBBa against T for inhomogeneous input
// if (!TEST_OPT_OLDSTD)
// withT = ! strat->homog;
// strat->posInT = posInT_pLength;
kTest_TS(strat);
#ifdef HAVE_TAIL_RING
// if(!idIs0(F) &&(!rField_is_Ring(currRing))) // create strong gcd poly computes with tailring and S[i] ->to be fixed
// kStratInitChangeTailRing(strat);
strat->tailRing=currRing;
#endif
#ifdef KDEBUG
//kDebugPrint(strat);
#endif
/* compute------------------------------------------------------- */
while (strat->Ll >= 0)
{
#ifdef KDEBUG
if (TEST_OPT_DEBUG) messageSets(strat);
#endif
if (siCntrlc)
{
while (strat->Ll >= 0)
deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
strat->noClearS=TRUE;
}
if (TEST_OPT_DEGBOUND
&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
|| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))))
{
/*
*stops computation if
* 24 IN test and the degree +ecart of L[strat->Ll] is bigger then
*a predefined number Kstd1_deg
*/
while ((strat->Ll >= 0)
&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
&& ((strat->honey && (strat->L[strat->Ll].ecart+currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg))
|| ((!strat->honey) && (currRing->pFDeg(strat->L[strat->Ll].p,currRing)>Kstd1_deg)))
)
deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
if (strat->Ll<0) break;
else strat->noClearS=TRUE;
}
if (strat->Ll== 0) strat->interpt=TRUE;
/* picks the last element from the lazyset L */
strat->P = strat->L[strat->Ll];
strat->Ll--;
if (pNext(strat->P.p) == strat->tail)
{
// deletes the short spoly
if (rField_is_Ring(currRing))
pLmDelete(strat->P.p);
else
pLmFree(strat->P.p);
strat->P.p = NULL;
poly m1 = NULL, m2 = NULL;
// check that spoly creation is ok
while (strat->tailRing != currRing &&
!kCheckSpolyCreation(&(strat->P), strat, m1, m2))
{
assume(m1 == NULL && m2 == NULL);
// if not, change to a ring where exponents are at least
// large enough
if (!kStratChangeTailRing(strat))
{
WerrorS("OVERFLOW...");
break;
}
}
// create the real one
ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
strat->tailRing, m1, m2, strat->R);
}
else if (strat->P.p1 == NULL)
{
if (strat->minim > 0)
strat->P.p2=p_Copy(strat->P.p, currRing, strat->tailRing);
// for input polys, prepare reduction
strat->P.PrepareRed(strat->use_buckets);
}
if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
{
red_result = 0;
}
else
{
if (TEST_OPT_PROT)
message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
&olddeg,&reduc,strat, red_result);
/* reduction of the element chosen from L */
red_result = strat->red(&strat->P,strat);
if (errorreported) break;
}
if (strat->overflow)
{
if (!kStratChangeTailRing(strat)) { WerrorS("OVERFLOW.."); break;}
}
// reduction to non-zero new poly
if (red_result == 1)
{
// get the polynomial (canonicalize bucket, make sure P.p is set)
strat->P.GetP(strat->lmBin);
// in the homogeneous case FDeg >= pFDeg (sugar/honey)
// but now, for entering S, T, we reset it
// in the inhomogeneous case: FDeg == pFDeg
if (strat->homog) strat->initEcart(&(strat->P));
/* statistic */
if (TEST_OPT_PROT) PrintS("s");
int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
// reduce the tail and normalize poly
// in the ring case we cannot expect LC(f) = 1,
strat->redTailChange=FALSE;
/* if we are computing over Z we always want to try and cut down
* the coefficients in the tail terms */
if (rField_is_Z(currRing) && !rHasLocalOrMixedOrdering(currRing))
{
redtailBbaAlsoLC_Z(&(strat->P), strat->tl, strat);
}
if (TEST_OPT_INTSTRATEGY)
{
strat->P.pCleardenom();
if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
{
strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT,!TEST_OPT_CONTENTSB);
strat->P.pCleardenom();
if (strat->redTailChange)
{
strat->P.t_p=NULL;
strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
}
}
}
else
{
strat->P.pNorm();
if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
{
strat->P.p = redtailBba(&(strat->P),pos-1,strat, withT);
if (strat->redTailChange)
{
strat->P.t_p=NULL;
strat->initEcart(&(strat->P)); // somehow we need this here with letterplace
}
}
}
#ifdef KDEBUG
if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
#endif /* KDEBUG */
// min_std stuff
if ((strat->P.p1==NULL) && (strat->minim>0))
{
if (strat->minim==1)
{
strat->M->m[minimcnt]=p_Copy(strat->P.p,currRing,strat->tailRing);
p_Delete(&strat->P.p2, currRing, strat->tailRing);
}
else
{
strat->M->m[minimcnt]=strat->P.p2;
strat->P.p2=NULL;
}
if (strat->tailRing!=currRing && pNext(strat->M->m[minimcnt])!=NULL)
pNext(strat->M->m[minimcnt])
= strat->p_shallow_copy_delete(pNext(strat->M->m[minimcnt]),
strat->tailRing, currRing,
currRing->PolyBin);
minimcnt++;
}
// enter into S, L, and T
if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
{
enterT(&strat->P, strat);
enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
// posInS only depends on the leading term
strat->enterS(&strat->P, pos, strat, strat->tl);
if (!strat->rightGB)
enterTShift(&strat->P, strat);
}
if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
// Print("[%d]",hilbeledeg);
kDeleteLcm(&strat->P);
if (strat->s_poly!=NULL)
{
// the only valid entries are: strat->P.p,
// strat->tailRing (read-only, keep it)
// (and P->p1, P->p2 (read-only, must set to NULL if P.p is changed)
if (strat->s_poly(strat))
{
// we are called AFTER enterS, i.e. if we change P
// we have to add it also to S/T
// and add pairs
int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
enterT(&strat->P, strat);
enterpairsShift(strat->P.p,strat->sl,strat->P.ecart,pos,strat, strat->tl);
strat->enterS(&strat->P, pos, strat, strat->tl);
if (!strat->rightGB)
enterTShift(&strat->P,strat);
}
}
}
else if (strat->P.p1 == NULL && strat->minim > 0)
{
p_Delete(&strat->P.p2, currRing, strat->tailRing);
}
#ifdef KDEBUG
strat->P.Init();
#endif /* KDEBUG */
kTest_TS(strat);
}
#ifdef KDEBUG
if (TEST_OPT_DEBUG) messageSets(strat);
#endif /* KDEBUG */
/* shift case: look for elt's in S such that they are divisible by elt in T */
if ((TEST_OPT_SB_1 || TEST_OPT_REDSB) && !strat->noClearS) // when is OPT_SB_1 set?
{
if(!rField_is_Ring(currRing))
{
for (int k = 0; k <= strat->sl; ++k)
{
if ((strat->fromQ!=NULL) && (strat->fromQ[k])) continue; // do not reduce Q_k
for (int j = 0; j<=strat->tl; ++j)
{
if (strat->T[j].p!=NULL)
{
// this is like clearS in bba, but we reduce with elements from T, because it contains the shifts too
assume(strat->sevT[j] == pGetShortExpVector(strat->T[j].p));
assume(strat->sevS[k] == pGetShortExpVector(strat->S[k]));
if (pLmShortDivisibleBy(strat->T[j].p, strat->sevT[j], strat->S[k], ~strat->sevS[k]))
{
if (pLmCmp(strat->T[j].p, strat->S[k]) != 0)
{ // check whether LM is different
deleteInS(k, strat);
--k;
break;
}
}
}
}
}
}
}
/* complete reduction of the standard basis--------- */
if (TEST_OPT_REDSB)
{
completeReduce(strat, TRUE); //shift: withT = TRUE
if (strat->completeReduce_retry)
{
// completeReduce needed larger exponents, retry
// to reduce with S (instead of T)
// and in currRing (instead of strat->tailRing)
#ifdef HAVE_TAIL_RING
if(currRing->bitmask>strat->tailRing->bitmask)
{
strat->completeReduce_retry=FALSE;
cleanT(strat);strat->tailRing=currRing;
int i;
for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
WarnS("reduction with S is not yet supported by Letterplace"); // if this ever happens, we'll know
completeReduce(strat);
}
if (strat->completeReduce_retry)
#endif
Werror("exponent bound is %ld",currRing->bitmask);
}
}
else if (TEST_OPT_PROT) PrintLn();
/* release temp data-------------------------------- */
exitBuchMora(strat);
/* postprocessing for GB over ZZ --------------------*/
if (!errorreported)
{
if(rField_is_Z(currRing))
{
for(int i = 0;i<=strat->sl;i++)
{
if(!nGreaterZero(pGetCoeff(strat->S[i])))
{
strat->S[i] = pNeg(strat->S[i]);
}
}
finalReduceByMon(strat);
for(int i = 0;i<IDELEMS(strat->Shdl);i++)
{
if(!nGreaterZero(pGetCoeff(strat->Shdl->m[i])))
{
strat->S[i] = pNeg(strat->Shdl->m[i]);
}
}
}
//else if (rField_is_Ring(currRing))
// finalReduceByMon(strat);
}
// if (TEST_OPT_WEIGHTM)
// {
// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
// if (ecartWeights)
// {
// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
// ecartWeights=NULL;
// }
// }
if ((TEST_OPT_PROT) || (TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
SI_RESTORE_OPT1(save);
/* postprocessing for GB over Q-rings ------------------*/
if ((Q!=NULL)&&(!errorreported)) updateResult(strat->Shdl,Q,strat);
idTest(strat->Shdl);
return (strat->Shdl);
}
#endif
#ifdef HAVE_SHIFTBBA
ideal rightgb(ideal F, const ideal Q)
{
assume(rIsLPRing(currRing));
assume(idIsInV(F));
ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
idSkipZeroes(RS); // is this even necessary?
assume(idIsInV(RS));
return(RS);
}
#endif
/*2
*reduces h with elements from T choosing the first possible
* element in t with respect to the given pDivisibleBy
*/
#ifdef HAVE_SHIFTBBA
int redFirstShift (LObject* h,kStrategy strat)
{
if (h->IsNull()) return 0;
int at, reddeg,d;
int pass = 0;
int j = 0;
if (! strat->homog)
{
d = h->GetpFDeg() + h->ecart;
reddeg = strat->LazyDegree+d;
}
h->SetShortExpVector();
loop
{
j = kFindDivisibleByInT(strat, h);
if (j < 0)
{
h->SetDegStuffReturnLDeg(strat->LDegLast);
return 1;
}
if (!TEST_OPT_INTSTRATEGY)
strat->T[j].pNorm();
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("reduce ");
h->wrp();
PrintS(" with ");
strat->T[j].wrp();
}
#endif
ksReducePoly(h, &(strat->T[j]), strat->kNoetherTail(), NULL, NULL, strat);
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("\nto ");
wrp(h->p);
PrintLn();
}
#endif
if (h->IsNull())
{
kDeleteLcm(h);
h->Clear();
return 0;
}
h->SetShortExpVector();
#if 0
if ((strat->syzComp!=0) && !strat->honey)
{
if ((strat->syzComp>0) &&
(h->Comp() > strat->syzComp))
{
assume(h->MinComp() > strat->syzComp);
#ifdef KDEBUG
if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
#endif
if (strat->homog)
h->SetDegStuffReturnLDeg(strat->LDegLast);
return -2;
}
}
#endif
if (!strat->homog)
{
if (!TEST_OPT_OLDSTD && strat->honey)
{
h->SetpFDeg();
if (strat->T[j].ecart <= h->ecart)
h->ecart = d - h->GetpFDeg();
else
h->ecart = d - h->GetpFDeg() + strat->T[j].ecart - h->ecart;
d = h->GetpFDeg() + h->ecart;
}
else
d = h->SetDegStuffReturnLDeg(strat->LDegLast);
/*- try to reduce the s-polynomial -*/
pass++;
/*
*test whether the polynomial should go to the lazyset L
*-if the degree jumps
*-if the number of pre-defined reductions jumps
*/
if (!TEST_OPT_REDTHROUGH && (strat->Ll >= 0)
&& ((d >= reddeg) || (pass > strat->LazyPass)))
{
h->SetLmCurrRing();
if (strat->posInLDependsOnLength)
h->SetLength(strat->length_pLength);
at = strat->posInL(strat->L,strat->Ll,h,strat);
if (at <= strat->Ll)
{
//int dummy=strat->sl;
/* if (kFindDivisibleByInS(strat,&dummy, h) < 0) */
//if (kFindDivisibleByInT(strat->T,strat->sevT, dummy, h) < 0)
if (kFindDivisibleByInT(strat, h) < 0)
return 1;
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
#endif
h->Clear();
return -1;
}
}
if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
{
reddeg = d+1;
Print(".%d",d);mflush();
}
}
}
}
#endif
BITSET
#define BITSET
Definition auxiliary.h:85
si_max
static int si_max(const int a, const int b)
Definition auxiliary.h:125
UNLIKELY
#define UNLIKELY(X)
Definition auxiliary.h:405
BOOLEAN
int BOOLEAN
Definition auxiliary.h:88
TRUE
#define TRUE
Definition auxiliary.h:101
FALSE
#define FALSE
Definition auxiliary.h:97
l
int l
Definition cfEzgcd.cc:100
m
int m
Definition cfEzgcd.cc:128
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
p
int p
Definition cfModGcd.cc:4086
cd
CanonicalForm cd(bCommonDen(FF))
Definition cfModGcd.cc:4097
sort
static void sort(int **points, int sizePoints)
Definition cfNewtonPolygon.cc:100
bound
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
bigintmat
Matrices of numbers.
Definition bigintmat.h:51
intvec
Definition intvec.h:24
skStrategy::kNoetherTail
KINLINE poly kNoetherTail()
Definition kInline.h:66
skStrategy::sevSyz
unsigned long * sevSyz
Definition kutil.h:322
skStrategy::sigdrop
bool sigdrop
Definition kutil.h:357
skStrategy::syzComp
int syzComp
Definition kutil.h:353
skStrategy::S_2_R
int * S_2_R
Definition kutil.h:341
skStrategy::tailRing
ring tailRing
Definition kutil.h:342
skStrategy::noTailReduction
char noTailReduction
Definition kutil.h:375
skStrategy::currIdx
int currIdx
Definition kutil.h:316
skStrategy::nrsyzcrit
int nrsyzcrit
Definition kutil.h:358
skStrategy::nrrewcrit
int nrrewcrit
Definition kutil.h:359
skStrategy::Ll
int Ll
Definition kutil.h:350
skStrategy::T
TSet T
Definition kutil.h:325
skStrategy::lmBin
omBin lmBin
Definition kutil.h:343
skStrategy::syzmax
int syzmax
Definition kutil.h:348
skStrategy::ecartS
intset ecartS
Definition kutil.h:308
skStrategy::honey
char honey
Definition kutil.h:374
skStrategy::rightGB
char rightGB
Definition kutil.h:366
skStrategy::S
polyset S
Definition kutil.h:305
skStrategy::minim
int minim
Definition kutil.h:356
skStrategy::kNoether
poly kNoether
Definition kutil.h:328
skStrategy::B
LSet B
Definition kutil.h:327
skStrategy::ak
int ak
Definition kutil.h:352
skStrategy::R
TObject ** R
Definition kutil.h:339
skStrategy::M
ideal M
Definition kutil.h:304
skStrategy::tl
int tl
Definition kutil.h:349
skStrategy::red2
int(* red2)(LObject *L, kStrategy strat)
Definition kutil.h:280
skStrategy::sevT
unsigned long * sevT
Definition kutil.h:324
skStrategy::sevSig
unsigned long * sevSig
Definition kutil.h:323
skStrategy::max_lower_index
int max_lower_index
Definition kutil.h:317
skStrategy::tail
poly tail
Definition kutil.h:333
skStrategy::posInL
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.h:283
skStrategy::blockred
int blockred
Definition kutil.h:362
skStrategy::Shdl
ideal Shdl
Definition kutil.h:302
skStrategy::syzl
int syzl
Definition kutil.h:348
skStrategy::sbaOrder
unsigned sbaOrder
Definition kutil.h:315
skStrategy::blockredmax
int blockredmax
Definition kutil.h:363
skStrategy::sig
polyset sig
Definition kutil.h:307
skStrategy::syz
polyset syz
Definition kutil.h:306
skStrategy::LDegLast
char LDegLast
Definition kutil.h:382
skStrategy::enterS
void(* enterS)(LObject *h, int pos, kStrategy strat, int atR)
Definition kutil.h:285
skStrategy::p_shallow_copy_delete
pShallowCopyDeleteProc p_shallow_copy_delete
Definition kutil.h:337
skStrategy::fromQ
intset fromQ
Definition kutil.h:320
skStrategy::newt
char newt
Definition kutil.h:398
skStrategy::use_buckets
char use_buckets
Definition kutil.h:380
skStrategy::interpt
char interpt
Definition kutil.h:368
skStrategy::redTailChange
char redTailChange
Definition kutil.h:396
skStrategy::fromT
char fromT
Definition kutil.h:376
skStrategy::completeReduce_retry
char completeReduce_retry
Definition kutil.h:400
skStrategy::initEcart
void(* initEcart)(TObject *L)
Definition kutil.h:281
skStrategy::P
LObject P
Definition kutil.h:301
skStrategy::noClearS
char noClearS
Definition kutil.h:399
skStrategy::Lmax
int Lmax
Definition kutil.h:350
skStrategy::LazyPass
int LazyPass
Definition kutil.h:352
skStrategy::overflow
char overflow
Definition kutil.h:401
skStrategy::L
LSet L
Definition kutil.h:326
skStrategy::length_pLength
char length_pLength
Definition kutil.h:384
skStrategy::red
int(* red)(LObject *L, kStrategy strat)
Definition kutil.h:279
skStrategy::rewCrit2
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:293
skStrategy::sl
int sl
Definition kutil.h:347
skStrategy::sbaEnterS
int sbaEnterS
Definition kutil.h:360
skStrategy::LazyDegree
int LazyDegree
Definition kutil.h:352
skStrategy::posInLDependsOnLength
char posInLDependsOnLength
Definition kutil.h:386
skStrategy::sevS
unsigned long * sevS
Definition kutil.h:321
skStrategy::homog
char homog
Definition kutil.h:369
skStrategy::s_poly
s_poly_proc_t s_poly
Definition kutil.h:299
n_Gcd
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of 'a' and 'b' in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ,...
Definition coeffs.h:667
n_EucNorm
static FORCE_INLINE number n_EucNorm(number a, const coeffs r)
Definition coeffs.h:678
n_QuotRem
static FORCE_INLINE number n_QuotRem(number a, number b, number *q, const coeffs r)
Definition coeffs.h:684
n_Greater
static FORCE_INLINE BOOLEAN n_Greater(number a, number b, const coeffs r)
ordered fields: TRUE iff 'a' is larger than 'b'; in Z/pZ: TRUE iff la > lb, where la and lb are the l...
Definition coeffs.h:517
n_IsZero
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition coeffs.h:470
n_GetChar
static FORCE_INLINE int n_GetChar(const coeffs r)
Return the characteristic of the coeff. domain.
Definition coeffs.h:450
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:461
n_DivBy
static FORCE_INLINE BOOLEAN n_DivBy(number a, number b, const coeffs r)
test whether 'a' is divisible 'b'; for r encoding a field: TRUE iff 'b' does not represent zero in Z:...
Definition coeffs.h:750
n_IsOne
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition coeffs.h:474
Print
#define Print
Definition emacs.cc:80
WarnS
#define WarnS
Definition emacs.cc:78
res
CanonicalForm res
Definition facAbsFact.cc:60
w
const CanonicalForm & w
Definition facAbsFact.cc:51
tmp1
CFList tmp1
Definition facFqBivar.cc:75
tmp2
CFList tmp2
Definition facFqBivar.cc:75
j
int j
Definition facHensel.cc:110
errorreported
VAR short errorreported
Definition feFopen.cc:23
WerrorS
void WerrorS(const char *s)
Definition feFopen.cc:24
VAR
#define VAR
Definition globaldefs.h:5
ideals.h
idDelete
#define idDelete(H)
delete an ideal
Definition ideals.h:29
idIs0
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
Definition simpleideals.cc:960
idInsertPolyOnPos
BOOLEAN idInsertPolyOnPos(ideal I, poly p, int pos)
insert p into I on position pos
Definition simpleideals.cc:851
idTest
#define idTest(id)
Definition ideals.h:47
idSort
static intvec * idSort(ideal id, BOOLEAN nolex=TRUE)
Definition ideals.h:188
intvec.h
T
STATIC_VAR jList * T
Definition janet.cc:30
h
STATIC_VAR Poly * h
Definition janet.cc:971
redtailBba_Ring
KINLINE poly redtailBba_Ring(poly p, int pos, kStrategy strat)
Definition kInline.h:1224
redtailBba
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition kInline.h:1212
redtailBbaBound
KINLINE poly redtailBbaBound(poly p, int pos, kStrategy strat, int bound, BOOLEAN normalize)
Definition kInline.h:1218
clearS
KINLINE void clearS(poly p, unsigned long p_sev, int *at, int *k, kStrategy strat)
Definition kInline.h:1235
redtailBba_Z
KINLINE poly redtailBba_Z(poly p, int pos, kStrategy strat)
Definition kInline.h:1229
kBucketClear
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition kbuckets.cc:521
kbTest
BOOLEAN kbTest(kBucket_pt bucket)
Tests.
Definition kbuckets.cc:197
kBucket_Minus_m_Mult_p
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNoether)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m assume (*l <= 0 || pLength(p) == *l...
Definition kbuckets.cc:722
kBucketDestroy
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition kbuckets.cc:216
kBucketInit
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition kbuckets.cc:493
kBucketCreate
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition kbuckets.cc:209
kBucketPolyRedNF
void kBucketPolyRedNF(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition kbuckets.cc:1188
kBucketGetLm
const poly kBucketGetLm(kBucket_pt bucket)
Definition kbuckets.cc:506
kbuckets.h
kBucketCanonicalize
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
khCheck
void khCheck(ideal Q, intvec *w, bigintmat *hilb, int &eledeg, int &count, kStrategy strat)
Definition khstd.cc:28
khstd.h
ksReducePolyLC
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:477
ksCreateSpoly
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition kspoly.cc:1203
ksReducePoly
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat, BOOLEAN reduce)
Definition kspoly.cc:187
ksReducePolySig
int ksReducePolySig(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:737
ksReducePolySigRing
int ksReducePolySigRing(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:943
kStdShift
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition kstd1.cc:2964
kInterRed
ideal kInterRed(ideal F, const ideal Q)
Definition kstd1.cc:3802
initBba
void initBba(kStrategy strat)
Definition kstd1.cc:1690
initSba
void initSba(ideal F, kStrategy strat)
Definition kstd1.cc:1750
kstd1.h
KSTD_NF_LAZY
#define KSTD_NF_LAZY
Definition kstd1.h:18
Kstd1_deg
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:70
KSTD_NF_NONORM
#define KSTD_NF_NONORM
Definition kstd1.h:22
KSTD_NF_NOLF
#define KSTD_NF_NOLF
Definition kstd1.h:26
redRing_Z
int redRing_Z(LObject *h, kStrategy strat)
Definition kstd2.cc:720
kFindZeroPoly
poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
Definition kstd2.cc:609
redFirstShift
int redFirstShift(LObject *h, kStrategy strat)
Definition kstd2.cc:4951
kFindDivisibleByInT_Z
int kFindDivisibleByInT_Z(const kStrategy strat, const LObject *L, const int start)
Definition kstd2.cc:209
sba
ideal sba(ideal F0, ideal Q, intvec *w, bigintmat *hilb, kStrategy strat)
Definition kstd2.cc:2971
kFindDivisibleByInS
int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject *L)
return -1 if no divisor is found number of first divisor in S, otherwise
Definition kstd2.cc:464
kTestDivisibleByT0_Z
int kTestDivisibleByT0_Z(const kStrategy strat, const LObject *L)
tests if T[0] divides the leading monomial of L, returns -1 if not
Definition kstd2.cc:142
redNFBound
poly redNFBound(poly h, int &max_ind, int nonorm, kStrategy strat, int bound)
Definition kstd2.cc:2503
kNF2
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd2.cc:3927
kFindDivisibleByInT_ecart
int kFindDivisibleByInT_ecart(const kStrategy strat, const LObject *L, const int ecart)
Definition kstd2.cc:416
redHoney
int redHoney(LObject *h, kStrategy strat)
Definition kstd2.cc:2110
kFindDivisibleByInS_Z
static int kFindDivisibleByInS_Z(const kStrategy strat, LObject *L)
Definition kstd2.cc:272
kFindNextDivisibleByInS
int kFindNextDivisibleByInS(const kStrategy strat, int start, int max_ind, LObject *L)
Definition kstd2.cc:567
ind_fact_2
static long ind_fact_2(long arg)
Definition kstd2.cc:596
redHomog
int redHomog(LObject *h, kStrategy strat)
Definition kstd2.cc:1150
redLazy
int redLazy(LObject *h, kStrategy strat)
Definition kstd2.cc:1905
redSigRing
int redSigRing(LObject *h, kStrategy strat)
Definition kstd2.cc:1536
kFindDivisibleByInS_noCF
int kFindDivisibleByInS_noCF(const kStrategy strat, int *max_ind, LObject *L)
Definition kstd2.cc:527
redtailSba
poly redtailSba(LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
Definition kstd2.cc:1785
ksReducePolyTailSig
KINLINE int ksReducePolyTailSig(LObject *PR, TObject *PW, LObject *Red, kStrategy strat)
Definition kstd2.cc:1331
rightgb
ideal rightgb(ideal F, const ideal Q)
Definition kstd2.cc:4935
redNF
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition kstd2.cc:2307
bbaShift
ideal bbaShift(ideal F, ideal Q, intvec *w, bigintmat *hilb, kStrategy strat)
Definition kstd2.cc:4577
redRing_S
static int redRing_S(LObject *h, kStrategy strat)
Definition kstd2.cc:1090
redSig
int redSig(LObject *h, kStrategy strat)
Definition kstd2.cc:1369
kDebugPrint
void kDebugPrint(kStrategy strat)
Definition kutil.cc:11478
kNF2Bound
poly kNF2Bound(ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
Definition kstd2.cc:4015
redRing
int redRing(LObject *h, kStrategy strat)
Definition kstd2.cc:988
kFindDivisibleByInT
int kFindDivisibleByInT(const kStrategy strat, const LObject *L, const int start)
return -1 if no divisor is found number of first divisor in T, otherwise
Definition kstd2.cc:317
bba
ideal bba(ideal F, ideal Q, intvec *w, bigintmat *hilb, kStrategy strat)
Definition kstd2.cc:2614
redRing_Z_S
static int redRing_Z_S(LObject *h, kStrategy strat)
Definition kstd2.cc:878
f5c
void f5c(kStrategy strat, int &olddeg, int &minimcnt, int &hilbeledeg, int &hilbcount, int &srmax, int &lrmax, int &reduc, ideal Q, intvec *w, bigintmat *hilb)
Definition kstd2.cc:4265
initSbaPos
void initSbaPos(kStrategy strat)
Definition kutil.cc:9863
initBuchMora
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9749
enterSyz
void enterSyz(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9343
enterSBba
void enterSBba(LObject *p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8792
message
void message(int i, int *olddeg, int *reduc, kStrategy strat, int red_result)
Definition kutil.cc:7463
kTest
BOOLEAN kTest(kStrategy strat)
Definition kutil.cc:1004
kFindDivisibleByInS_T
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart)
Definition kutil.cc:6697
kTest_TS
BOOLEAN kTest_TS(kStrategy strat)
Definition kutil.cc:1067
enterpairsSig
void enterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4513
enterL
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition kutil.cc:1269
enterSBbaShift
void enterSBbaShift(LObject *p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8892
enterpairs
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4487
redtailBbaAlsoLC_Z
void redtailBbaAlsoLC_Z(LObject *L, int end_pos, kStrategy strat)
Definition kutil.cc:7140
posInSMonFirst
int posInSMonFirst(const kStrategy strat, const int length, const poly p)
Definition kutil.cc:4764
superenterpairsSig
void superenterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4470
initBuchMoraPos
void initBuchMoraPos(kStrategy strat)
Definition kutil.cc:9580
initS
void initS(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7586
kStratChangeTailRing
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition kutil.cc:10939
sbaRing
ring sbaRing(kStrategy strat, const ring r, BOOLEAN, int)
Definition kutil.cc:11064
postReduceByMon
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition kutil.cc:10682
enterpairsShift
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:12927
kTest_L
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition kutil.cc:916
exitBuchMora
void exitBuchMora(kStrategy strat)
Definition kutil.cc:9837
messageStatSBA
void messageStatSBA(int hilbcount, kStrategy strat)
Definition kutil.cc:7517
posInS
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition kutil.cc:4663
initSyzRules
void initSyzRules(kStrategy strat)
Definition kutil.cc:7933
initSbaBuchMora
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9936
kCheckSpolyCreation
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition kutil.cc:10459
enterT
void enterT(LObject *p, kStrategy strat, int atT)
Definition kutil.cc:9143
cleanT
void cleanT(kStrategy strat)
Definition kutil.cc:557
posInSyz
int posInSyz(const kStrategy strat, poly sig)
Definition kutil.cc:5758
enterTShift
void enterTShift(LObject *p, kStrategy strat, int atT)
Definition kutil.cc:12957
deleteHC
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition kutil.cc:286
updateResult
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition kutil.cc:10051
superenterpairs
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4457
redtailBba_NF
poly redtailBba_NF(poly p, kStrategy strat)
Definition kutil.cc:7350
exitSba
void exitSba(kStrategy strat)
Definition kutil.cc:10011
deleteInL
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition kutil.cc:1208
kStratInitChangeTailRing
void kStratInitChangeTailRing(kStrategy strat)
Definition kutil.cc:11036
initBuchMoraCrit
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9435
completeReduce
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition kutil.cc:10257
initBuchMoraPosRing
void initBuchMoraPosRing(kStrategy strat)
Definition kutil.cc:9664
postReduceByMonSig
void postReduceByMonSig(LObject *h, kStrategy strat)
Definition kutil.cc:10758
messageSets
void messageSets(kStrategy strat)
Definition kutil.cc:7536
deleteInS
void deleteInS(int i, kStrategy strat)
Definition kutil.cc:1132
sbaCheckGcdPair
BOOLEAN sbaCheckGcdPair(LObject *h, kStrategy strat)
Definition kutil.cc:1688
posInLF5CRing
int posInLF5CRing(const LSet set, int start, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5878
initEcartBBA
void initEcartBBA(TObject *h)
Definition kutil.cc:1301
messageStat
void messageStat(int hilbcount, kStrategy strat)
Definition kutil.cc:7504
posInIdealMonFirst
int posInIdealMonFirst(const ideal F, const poly p, int start, int end)
Definition kutil.cc:4841
finalReduceByMon
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition kutil.cc:10847
initSbaCrit
void initSbaCrit(kStrategy strat)
Definition kutil.cc:9498
cancelunit
void cancelunit(LObject *L, BOOLEAN inNF)
Definition kutil.cc:365
initHilbCrit
void initHilbCrit(ideal, ideal, bigintmat **hilb, kStrategy strat)
Definition kutil.cc:9417
kutil.h
ksReducePolyGCD
int ksReducePolyGCD(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
TSet
TObject * TSet
Definition kutil.h:60
setmaxTinc
#define setmaxTinc
Definition kutil.h:35
kFindSameLMInT_Z
int kFindSameLMInT_Z(const kStrategy strat, const LObject *L, const int start=0)
REDNF_CANONICALIZE
#define REDNF_CANONICALIZE
Definition kutil.h:38
kDeleteLcm
static void kDeleteLcm(LObject *P)
Definition kutil.h:876
KINLINE
#define KINLINE
Definition kutil.h:50
RED_CANONICALIZE
#define RED_CANONICALIZE
Definition kutil.h:37
TObject
class sTObject TObject
Definition kutil.h:58
ksReducePolyZ
int ksReducePolyZ(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
REDTAIL_CANONICALIZE
#define REDTAIL_CANONICALIZE
Definition kutil.h:39
LObject
class sLObject LObject
Definition kutil.h:59
help
#define help
Definition libparse.cc:1230
nc.h
nc_kBucketPolyRed_NF
static void nc_kBucketPolyRed_NF(kBucket_pt b, poly p, number *c, BOOLEAN reduce)
Definition nc.h:275
mult
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition minpoly.cc:647
mod2.h
assume
#define assume(x)
Definition mod2.h:389
p_GetComp
#define p_GetComp(p, r)
Definition monomials.h:64
pIter
#define pIter(p)
Definition monomials.h:37
pNext
#define pNext(p)
Definition monomials.h:36
pGetCoeff
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition monomials.h:44
__p_GetComp
#define __p_GetComp(p, r)
Definition monomials.h:63
pAssume
#define pAssume(cond)
Definition monomials.h:90
ndQuotRem
number ndQuotRem(number a, number b, number *r, const coeffs R)
Definition numbers.cc:356
nDelete
#define nDelete(n)
Definition numbers.h:16
nIsZero
#define nIsZero(n)
Definition numbers.h:19
nCopy
#define nCopy(n)
Definition numbers.h:15
nGreaterZero
#define nGreaterZero(n)
Definition numbers.h:27
nIsOne
#define nIsOne(n)
Definition numbers.h:25
nNormalize
#define nNormalize(n)
Definition numbers.h:30
nInit
#define nInit(i)
Definition numbers.h:24
omfree
#define omfree(addr)
Definition omAllocDecl.h:237
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210
omFree
#define omFree(addr)
Definition omAllocDecl.h:261
omRealloc0Size
#define omRealloc0Size(addr, o_size, size)
Definition omAllocDecl.h:221
NULL
#define NULL
Definition omList.c:12
siCntrlc
VAR BOOLEAN siCntrlc
Definition options.c:14
si_opt_1
VAR unsigned si_opt_1
Definition options.c:5
options.h
OPT_INTSTRATEGY
#define OPT_INTSTRATEGY
Definition options.h:93
TEST_OPT_IDLIFT
#define TEST_OPT_IDLIFT
Definition options.h:131
TEST_OPT_INTSTRATEGY
#define TEST_OPT_INTSTRATEGY
Definition options.h:112
BVERBOSE
#define BVERBOSE(a)
Definition options.h:35
TEST_OPT_REDTAIL
#define TEST_OPT_REDTAIL
Definition options.h:118
OPT_REDTAIL
#define OPT_REDTAIL
Definition options.h:92
SI_SAVE_OPT1
#define SI_SAVE_OPT1(A)
Definition options.h:21
SI_RESTORE_OPT1
#define SI_RESTORE_OPT1(A)
Definition options.h:24
TEST_OPT_OLDSTD
#define TEST_OPT_OLDSTD
Definition options.h:125
Sy_bit
#define Sy_bit(x)
Definition options.h:31
TEST_OPT_REDSB
#define TEST_OPT_REDSB
Definition options.h:106
TEST_OPT_DEGBOUND
#define TEST_OPT_DEGBOUND
Definition options.h:115
TEST_OPT_SB_1
#define TEST_OPT_SB_1
Definition options.h:121
TEST_OPT_LENGTH
#define TEST_OPT_LENGTH
Definition options.h:132
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition options.h:105
TEST_OPT_REDTHROUGH
#define TEST_OPT_REDTHROUGH
Definition options.h:124
TEST_OPT_DEBUG
#define TEST_OPT_DEBUG
Definition options.h:110
TEST_OPT_REDTAIL_SYZ
#define TEST_OPT_REDTAIL_SYZ
Definition options.h:119
TEST_OPT_CONTENTSB
#define TEST_OPT_CONTENTSB
Definition options.h:129
TEST_OPT_NOT_BUCKETS
#define TEST_OPT_NOT_BUCKETS
Definition options.h:107
p_ISet
poly p_ISet(long i, const ring r)
returns the poly representing the integer i
Definition p_polys.cc:1298
p_GetShortExpVector
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition p_polys.cc:4934
p_One
poly p_One(const ring r)
Definition p_polys.cc:1314
p_NSet
poly p_NSet(number n, const ring r)
returns the poly representing the number n, destroys n
Definition p_polys.cc:1474
pEnlargeSet
void pEnlargeSet(poly **p, int l, int increment)
Definition p_polys.cc:3821
pLength
static int pLength(poly a)
Definition p_polys.h:190
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:938
p_Mult_q
static poly p_Mult_q(poly p, poly q, const ring r)
Definition p_polys.h:1125
p_ExpVectorAdd
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
Definition p_polys.h:1432
p_LmEqual
#define p_LmEqual(p1, p2, r)
Definition p_polys.h:1744
p_SetExpV
static void p_SetExpV(poly p, int *ev, const ring r)
Definition p_polys.h:1565
p_SetExp
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent @Note: VarOffset encodes the position in p->exp
Definition p_polys.h:490
p_SetComp
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition p_polys.h:249
p_ExpVectorSub
static void p_ExpVectorSub(poly p1, poly p2, const ring r)
Definition p_polys.h:1461
p_Setm
static void p_Setm(poly p, const ring r)
Definition p_polys.h:235
p_SetCoeff
static number p_SetCoeff(poly p, number n, ring r)
Definition p_polys.h:414
p_Head
static poly p_Head(const poly p, const ring r)
copy the (leading) term of p
Definition p_polys.h:862
p_LmCmp
static int p_LmCmp(poly p, poly q, const ring r)
Definition p_polys.h:1601
p_LmShortDivisibleBy
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition p_polys.h:1931
p_GetExp
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent @Note: the integer VarOffset encodes:
Definition p_polys.h:471
p_LmDivisibleBy
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition p_polys.h:1912
p_Delete
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
p_GetExpV
static void p_GetExpV(poly p, int *ev, const ring r)
Definition p_polys.h:1541
p_Mult_mm
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition p_polys.h:1053
p_LmDeleteAndNext
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition p_polys.h:757
p_Copy
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition p_polys.h:848
rChangeCurrRing
void rChangeCurrRing(ring r)
Definition polys.cc:16
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
polys.h
Compatibility layer for legacy polynomial operations (over currRing).
pLtCmp
#define pLtCmp(p, q)
Definition polys.h:124
pDelete
#define pDelete(p_ptr)
Definition polys.h:187
pHead
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition polys.h:68
pNeg
#define pNeg(p)
Definition polys.h:199
pGetComp
#define pGetComp(p)
Component.
Definition polys.h:38
pNorm
void pNorm(poly p)
Definition polys.h:363
pJet
#define pJet(p, m)
Definition polys.h:368
pLmShortDivisibleBy
#define pLmShortDivisibleBy(a, sev_a, b, not_sev_b)
Divisibility tests based on Short Exponent vectors sev_a == pGetShortExpVector(a) not_sev_b == ~ pGet...
Definition polys.h:147
pLmDelete
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition polys.h:77
pGetShortExpVector
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
Definition polys.h:153
wrp
void wrp(poly p)
Definition polys.h:311
pLmFree
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
Definition polys.h:71
pWrite
void pWrite(poly p)
Definition polys.h:309
pNormalize
#define pNormalize(p)
Definition polys.h:318
pSetExp
#define pSetExp(p, i, v)
Definition polys.h:43
pLmCmp
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition polys.h:106
pSize
#define pSize(p)
Definition polys.h:319
pCopy
#define pCopy(p)
return a copy of the poly
Definition polys.h:186
pOne
#define pOne()
Definition polys.h:316
polyset
poly * polyset
Definition polys.h:260
idrMoveR
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition prCopy.cc:248
idrMoveR_NoSort
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition prCopy.cc:261
prCopy.h
PrintS
void PrintS(const char *s)
Definition reporter.cc:288
PrintLn
void PrintLn()
Definition reporter.cc:314
Werror
void Werror(const char *fmt,...)
Definition reporter.cc:189
mflush
#define mflush()
Definition reporter.h:58
rWrite
void rWrite(ring r, BOOLEAN details)
Definition ring.cc:227
rDelete
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:454
rField_is_Z
static BOOLEAN rField_is_Z(const ring r)
Definition ring.h:515
rHasLocalOrMixedOrdering
static BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition ring.h:769
rIsPluralRing
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:406
rField_is_Zn
static BOOLEAN rField_is_Zn(const ring r)
Definition ring.h:518
rIsLPRing
static BOOLEAN rIsLPRing(const ring r)
Definition ring.h:417
rField_is_Ring
#define rField_is_Ring(R)
Definition ring.h:491
shiftop.h
idIsInV
#define idIsInV(I)
Definition shiftop.h:49
SI_LOG2_LONG
static int SI_LOG2_LONG(long v)
Definition si_log2.h:22
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition simpleideals.cc:35
id_DelDiv
void id_DelDiv(ideal id, const ring r)
delete id[j], if LT(j) == coeff*mon*LT(i) and vice versa, i.e., delete id[i], if LT(i) == coeff*mon*L...
Definition simpleideals.cc:463
idSkipZeroes
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
Definition simpleideals.cc:201
IDELEMS
#define IDELEMS(i)
Definition simpleideals.h:23
Q
#define Q
Definition sirandom.c:26
testHomog
@ testHomog
Definition structs.h:34
kStrategy
skStrategy * kStrategy
Definition structs.h:54
loop
#define loop
Definition structs.h:71
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836
weight.h