Loading...
Searching...
No Matches
gr_kstd2.cc
Go to the documentation of this file.
/****************************************
* Computer Algebra System SINGULAR *
****************************************/
/*
* ABSTRACT - Kernel: noncomm. alg. of Buchberger
*/
#define PLURAL_INTERNAL_DECLARATIONS
#include "kernel/mod2.h"
#ifdef HAVE_PLURAL
#include "misc/options.h"
#include "misc/intvec.h"
#include "polys/weight.h"
#include "kernel/polys.h"
#include "polys/monomials/ring.h"
#include "polys/nc/gb_hack.h"
#include "polys/nc/nc.h"
#include "polys/nc/sca.h"
#include "kernel/ideals.h"
#include "kernel/GBEngine/kstd1.h"
#include "kernel/GBEngine/khstd.h"
//#include "spolys.h"
//#include "cntrlc.h"
#include "kernel/GBEngine/ratgring.h"
#include "kernel/GBEngine/kutil.h"
#include "kernel/GBEngine/nc.h"
#if 0
/*3
* reduction of p2 with p1
* do not destroy p1 and p2
* p1 divides p2 -> for use in NF algorithm
*/
poly gnc_ReduceSpolyNew(const poly p1, poly p2/*,poly spNoether*/, const ring r)
{
return(nc_ReduceSPoly(p1,p_Copy(p2,r)/*,spNoether*/,r));
}
#endif
/*2
*reduces h with elements from T choosing the first possible
* element in t with respect to the given pDivisibleBy
*/
int redGrFirst (LObject* h,kStrategy strat)
{
int at,reddeg,d,i;
int pass = 0;
int j = 0;
d = currRing->pFDeg((*h).p,currRing)+(*h).ecart;
reddeg = strat->LazyDegree+d;
loop
{
if (j > strat->sl)
{
#ifdef KDEBUG
if (TEST_OPT_DEBUG) PrintLn();
#endif
return 0;
}
#ifdef KDEBUG
if (TEST_OPT_DEBUG) Print("%d",j);
#endif
if (pDivisibleBy(strat->S[j],(*h).p))
{
#ifdef KDEBUG
if (TEST_OPT_DEBUG) PrintS("+\n");
#endif
/*
* the polynomial to reduce with is;
* T[j].p
*/
if (!TEST_OPT_INTSTRATEGY)
pNorm(strat->S[j]);
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
wrp(h->p);
PrintS(" with ");
wrp(strat->S[j]);
}
#endif
(*h).p = nc_ReduceSpoly(strat->S[j],(*h).p, currRing);
//spSpolyRed(strat->T[j].p,(*h).p,strat->kNoether);
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS(" to ");
wrp(h->p);
}
#endif
if ((*h).p == NULL)
{
kDeleteLcm(h);
return 0;
}
if (TEST_OPT_INTSTRATEGY)
{
h->pCleardenom();// also removes Content
}
/*computes the ecart*/
d = currRing->pLDeg((*h).p,&((*h).length),currRing);
(*h).FDeg=currRing->pFDeg((*h).p,currRing);
(*h).ecart = d-(*h).FDeg; /*pFDeg((*h).p);*/
if ((strat->syzComp!=0) && !strat->honey)
{
if ((strat->syzComp>0) && (pMinComp((*h).p) > strat->syzComp))
{
#ifdef KDEBUG
if (TEST_OPT_DEBUG) PrintS(" > sysComp\n");
#endif
return 0;
}
}
/*- 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 ((strat->Ll >= 0)
&& ((d >= reddeg) || (pass > strat->LazyPass))
&& !strat->homog)
{
at = strat->posInL(strat->L,strat->Ll,h,strat);
if (at <= strat->Ll)
{
i=strat->sl+1;
do
{
i--;
if (i<0) return 0;
} while (!pDivisibleBy(strat->S[i],(*h).p));
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
#ifdef KDEBUG
if (TEST_OPT_DEBUG) Print(" degree jumped; ->L%d\n",at);
#endif
(*h).p = NULL;
return 0;
}
}
if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d >= reddeg))
{
reddeg = d+1;
Print(".%d",d);mflush();
}
j = 0;
#ifdef KDEBUG
if TEST_OPT_DEBUG PrintLn();
#endif
}
else
{
#ifdef KDEBUG
if (TEST_OPT_DEBUG) PrintS("-");
#endif
j++;
}
}
}
void ratGB_divide_out(poly p)
{
/* extracts monomial content from localized expression */
/* searches for an m (monomial in var 1.. real_var_start-1)
* such that m divides p and divides p by this m if it exist*/
if (p==NULL) return;
poly root=p;
assume(rIsRatGRing(currRing));
poly f=pHead(p);
int i;
for (i=currRing->real_var_start;i<=currRing->real_var_end;i++)
{
pSetExp(f,i,0);
}
loop
{
pIter(p);
if (p==NULL) { pSetm(f); break;}
for (i=1;i<=rVar(currRing);i++)
{
pSetExp(f,i,si_min(pGetExp(f,i),pGetExp(p,i)));
}
}
if (!pIsConstant(f))
{
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("divide out:");p_wrp(f,currRing);
PrintS(" from ");pWrite(root);
}
#endif
p=root;
loop
{
if (p==NULL) break;
for (i=1;i<=rVar(currRing);i++)
{
pSetExp(p,i,pGetExp(p,i)-pGetExp(f,i));
}
pSetm(p);
pIter(p);
}
}
pDelete(&f);
}
#ifdef HAVE_RATGRING
/*2
*reduces h with elements from T choosing the first possible
* element in t with respect to the given pDivisibleBy
* for use in ratGB
*/
int redGrRatGB (LObject* h,kStrategy strat)
{
int at,reddeg,d,i;
int pass = 0;
int j = 0;
int c_j=-1, c_e=-2;
poly c_p=NULL;
assume(strat->tailRing==currRing);
ratGB_divide_out((*h).p);
d = currRing->pFDeg((*h).p,currRing)+(*h).ecart;
reddeg = strat->LazyDegree+d;
if (!TEST_OPT_INTSTRATEGY)
{
h->pCleardenom();// also does a pContentRat
}
loop
{
if (j > strat->sl)
{
if (c_j>=0)
{
/*
* the polynomial to reduce with is;
* S[c_j]
*/
if (!TEST_OPT_INTSTRATEGY)
pNorm(strat->S[c_j]);
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
if (TEST_OPT_DEBUG)
{
wrp(h->p);
Print(" with S[%d]= ",c_j);
wrp(strat->S[c_j]);
}
#endif
//poly hh = nc_CreateSpoly(strat->S[c_j],(*h).p, currRing);
// Print("vor nc_rat_ReduceSpolyNew (ce:%d) ",c_e);wrp(h->p);PrintLn();
//if(c_e==-1)
// c_p = nc_CreateSpoly(pCopy(strat->S[c_j]),pCopy((*h).p), currRing);
//else
// c_p=nc_rat_ReduceSpolyNew(strat->S[c_j],pCopy((*h).p), currRing->real_var_start-1,currRing);
// Print("nach nc_rat_ReduceSpolyNew ");wrp(c_p);PrintLn();
// pDelete(&((*h).p));
c_p=nc_rat_ReduceSpolyNew(strat->S[c_j],(*h).p, currRing->real_var_start-1,currRing);
(*h).p=c_p;
if (!TEST_OPT_INTSTRATEGY)
{
h->pCleardenom();// also removes Content
}
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS(" to ");
wrp(h->p);
PrintLn();
}
#endif
if ((*h).p == NULL)
{
kDeleteLcm(h);
return 0;
}
ratGB_divide_out((*h).p);
d = currRing->pLDeg((*h).p,&((*h).length),currRing);
(*h).FDeg=currRing->pFDeg((*h).p,currRing);
(*h).ecart = d-(*h).FDeg; /*pFDeg((*h).p);*/
/*- try to reduce the s-polynomial again -*/
pass++;
j=0;
c_j=-1; c_e=-2; c_p=NULL;
}
else
{ // nothing found
return 0;
}
}
// first try usual division
if (p_LmDivisibleBy(strat->S[j],(*h).p,currRing))
{
#ifdef KDEBUG
if(TEST_OPT_DEBUG)
{
p_wrp(h->p,currRing); Print(" divisible by S[%d]=",j);
p_wrp(strat->S[j],currRing); PrintS(" e=-1\n");
}
#endif
if ((c_j<0)||(c_e>=0))
{
c_e=-1; c_j=j;
}
}
else
if (p_LmDivisibleByPart(strat->S[j],(*h).p,currRing,
currRing->real_var_start,currRing->real_var_end))
{
int a_e=(p_Totaldegree(strat->S[j],currRing)-currRing->pFDeg(strat->S[j],currRing));
#ifdef KDEBUG
if(TEST_OPT_DEBUG)
{
p_wrp(h->p,currRing); Print(" divisibly by S[%d]=",j);
p_wrp(strat->S[j],currRing); Print(" e=%d\n",a_e);
}
#endif
if ((c_j<0)||(c_e>a_e))
{
c_e=a_e; c_j=j;
//c_p = nc_CreateSpoly(pCopy(strat->S[c_j]),pCopy((*h).p), currRing);
}
/*computes the ecart*/
if ((strat->syzComp!=0) && !strat->honey)
{
if ((strat->syzComp>0) && (pMinComp((*h).p) > strat->syzComp))
{
#ifdef KDEBUG
if (TEST_OPT_DEBUG) PrintS(" > sysComp\n");
#endif
return 0;
}
}
}
else
{
#ifdef KDEBUG
if(TEST_OPT_DEBUG)
{
p_wrp(h->p,currRing); Print(" not divisibly by S[%d]=",j);
p_wrp(strat->S[j],currRing); PrintLn();
}
#endif
}
j++;
}
}
#endif
/*2
* reduction procedure for the homogeneous case
* and the case of a degree-ordering
*/
#if 0
// currently unused
static int nc_redHomog (LObject* h,kStrategy strat)
{
if (strat->tl<0)
{
enterT((*h),strat);
return 1;
}
int j = 0;
if (TEST_OPT_DEBUG)
{
PrintS("red:");
wrp(h->p);
PrintS(" ");
}
loop
{
if (TEST_OPT_DEBUG) Print("%d",j);
if (pDivisibleBy(strat->S[j],(*h).p))
{
if (TEST_OPT_DEBUG)
{
PrintS("+\nwith ");
wrp(strat->S[j]);
}
/*- compute the s-polynomial -*/
(*h).p = nc_ReduceSpoly(strat->S[j],(*h).p,currRing);
if ((*h).p == NULL)
{
if (TEST_OPT_DEBUG) PrintS(" to 0\n");
kDeleteLcm(h);
return 0;
}
/*
* else if (strat->syzComp)
* {
* if (pMinComp((*h).p) > strat->syzComp)
* {
* enterT((*h),strat);
* return;
* }
* }
*/
/*- try to reduce the s-polynomial -*/
j = 0;
}
else
{
if (j >= strat->sl)
{
enterT((*h),strat);
return 1;
}
j++;
}
}
}
#endif
#if 0
/*2
* reduction procedure for the homogeneous case
* and the case of a degree-ordering
*/
static int nc_redHomog0 (LObject* h,kStrategy strat)
{
if (strat->tl<0)
{
enterT((*h),strat);
return 0;
}
int j = 0;
int k = 0;
if (TEST_OPT_DEBUG)
{
PrintS("red:");
wrp(h->p);
PrintS(" ");
}
loop
{
if (TEST_OPT_DEBUG) Print("%d",j);
if (pDivisibleBy(strat->T[j].p,(*h).p))
{
if (TEST_OPT_DEBUG)
{
PrintS("+\nwith ");
wrp(strat->S[j]);
}
/*- compute the s-polynomial -*/
(*h).p = nc_ReduceSpoly(strat->T[j].p,(*h).p,strat->kNoether,currRing);
if ((*h).p == NULL)
{
if (TEST_OPT_DEBUG) PrintS(" to 0\n");
kDeleteLcm(h);
return 0;
}
else
{
if (TEST_OPT_INTSTRATEGY)
{
h->pCleardenom();// also removes Content
}
if (strat->syzComp!=0)
{
if ((strat->syzComp>0) && (pMinComp((*h).p) > strat->syzComp))
{
/*
* (*h).length=pLength0((*h).p);
*/
enterT((*h),strat);
return 0;
}
}
}
/*- try to reduce the s-polynomial -*/
j = 0;
}
else
{
if (j >= strat->tl)
{
if (TEST_OPT_INTSTRATEGY)
{
h->pCleardenom();// also removes Content
}
/*
* (*h).length=pLength0((*h).p);
*/
enterT((*h),strat);
return 0;
}
j++;
}
}
}
/*2
* reduction procedure for the inhomogeneous case
* and not a degree-ordering
*/
static int nc_redLazy (LObject* h,kStrategy strat)
{
if (strat->tl<0)
{
enterT((*h),strat);
return 0;
}
int at,d,i;
int j = 0;
int pass = 0;
int reddeg = currRing->pFDeg((*h).p,currRing);
if (TEST_OPT_DEBUG)
{
PrintS("red:");
wrp(h->p);
PrintS(" ");
}
loop
{
if (TEST_OPT_DEBUG) Print("%d",j);
if (pDivisibleBy(strat->S[j],(*h).p))
{
if (TEST_OPT_DEBUG)
{
PrintS("+\nwith ");
wrp(strat->S[j]);
}
/*- compute the s-polynomial -*/
(*h).p = nc_ReduceSpoly(strat->S[j],(*h).p,strat->kNoether,currRing);
if ((*h).p == NULL)
{
if (TEST_OPT_DEBUG) PrintS(" to 0\n");
kDeleteLcm(h);
return 0;
}
// else if (strat->syzComp)
// {
// if ((strat->syzComp>0) && (pMinComp((*h).p) > strat->syzComp))
// {
// if (TEST_OPT_DEBUG) PrintS(" > syzComp\n");
// if (TEST_OPT_INTSTRATEGY) p_Content(h->p,currRing);
// enterTBba((*h),strat->tl+1,strat);
// return;
// }
// }
else
{
if (TEST_OPT_DEBUG)
{
PrintS("to:");
wrp((*h).p);
PrintLn();
}
if (TEST_OPT_INTSTRATEGY)
{
pCleardenom(h->p);// also removes Content
}
}
/*- try to reduce the s-polynomial -*/
pass++;
d = currRing->pFDeg((*h).p,currRing);
if ((strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
{
at = posInL11(strat->L,strat->Ll,h,strat);
if (at <= strat->Ll)
{
i=strat->sl+1;
do
{
i--;
if (i<0)
{
enterT((*h),strat);
return 0;
}
}
while (!pDivisibleBy(strat->S[i],(*h).p));
if (TEST_OPT_DEBUG) Print(" ->L[%d]\n",at);
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
(*h).p = NULL;
return 0;
}
}
else if ((TEST_OPT_PROT) && (strat->Ll < 0) && (d != reddeg))
{
Print(".%d",d);mflush();
reddeg = d;
}
j = 0;
}
else
{
if (TEST_OPT_DEBUG) PrintS("-");
if (j >= strat->sl)
{
if (TEST_OPT_DEBUG) PrintLn();
if (TEST_OPT_INTSTRATEGY)
{
h->pCleardenom();// also removes Content
}
enterT((*h),strat);
return 0;
}
j++;
}
}
}
/*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
*/
static int nc_redHoney (LObject* h,kStrategy strat)
{
if (strat->tl<0)
{
enterT((*h),strat);
return 0;
}
poly pi;
int i,j,at,reddeg,d,pass,ei;
pass = j = 0;
d = reddeg = currRing->pFDeg((*h).p,currRing)+(*h).ecart;
if (TEST_OPT_DEBUG)
{
PrintS("red:");
wrp((*h).p);
}
loop
{
if (TEST_OPT_DEBUG) Print("%d",j);
if (pDivisibleBy(strat->T[j].p,(*h).p))
{
if (TEST_OPT_DEBUG) PrintS("+");
pi = strat->T[j].p;
ei = strat->T[j].ecart;
/*
* the polynomial to reduce with (up to the moment) is;
* pi with ecart ei
*/
i = j;
loop
{
/*- takes the first possible with respect to ecart -*/
i++;
if (i > strat->tl)
break;
if ((!BTEST1(20)) && (ei <= (*h).ecart))
break;
if (TEST_OPT_DEBUG) Print("%d",i);
if ((strat->T[i].ecart < ei) && pDivisibleBy(strat->T[i].p,(*h).p))
{
if (TEST_OPT_DEBUG) PrintS("+");
/*
* the polynomial to reduce with is now;
*/
pi = strat->T[i].p;
ei = strat->T[i].ecart;
}
else if (TEST_OPT_DEBUG) PrintS("-");
}
/*
* end of search: have to reduce with pi
*/
if (ei > (*h).ecart)
{
/*
* 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);
if (TEST_OPT_DEBUG) Print(" ecart too big: -> L%d\n",at);
(*h).p = NULL;
return 0;
}
}
}
if (TEST_OPT_DEBUG)
{
PrintS("\nwith ");
wrp(pi);
}
if (strat->fromT)
{
strat->fromT=FALSE;
(*h).p = nc_ReduceSpoly(pi,(*h).p,strat->kNoether,currRing);
}
else
(*h).p = nc_ReduceSpoly(pi,(*h).p,strat->kNoether,currRing);
if (TEST_OPT_DEBUG)
{
PrintS(" to ");
wrp((*h).p);
PrintLn();
}
if ((*h).p == NULL)
{
kDeleteLcm(h);
return 0;
}
if (TEST_OPT_INTSTRATEGY)
{
h->pCleardenom();// also does remove Content
}
/* compute the ecart */
if (ei <= (*h).ecart)
(*h).ecart = d-currRing->pFDeg((*h).p,currRing);
else
(*h).ecart = d-currRing->pFDeg((*h).p,currRing)+ei-(*h).ecart;
// if (strat->syzComp)
// {
// if ((strat->syzComp>0) && (pMinComp((*h).p) > strat->syzComp))
// {
// if (TEST_OPT_DEBUG)
// PrintS(" >syzComp\n");
// if (TEST_OPT_INTSTRATEGY) p_Content(h->p,currRing);
// at=strat->posInT(strat->T,strat->tl,(*h));
// enterTBba((*h),at,strat);
// return;
// }
// }
/*
* 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 = currRing->pFDeg((*h).p,currRing)+(*h).ecart;
if ((strat->Ll >= 0) && ((d > reddeg) || (pass > strat->LazyPass)))
{
at = strat->posInL(strat->L,strat->Ll,h,strat);
if (at <= strat->Ll)
{
/*test if h is already standardbasis element*/
i=strat->sl+1;
do
{
i--;
if (i<0)
{
enterT((*h),strat);
return 0;
}
} while (!pDivisibleBy(strat->S[i],(*h).p));
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
if (TEST_OPT_DEBUG)
Print(" degree jumped: -> L%d\n",at);
(*h).p = NULL;
return 0;
}
}
else if (TEST_OPT_PROT && (strat->Ll < 0) && (d > reddeg))
{
reddeg = d;
Print(".%d",d); mflush();
}
j = 0;
}
else
{
if (TEST_OPT_DEBUG) PrintS("-");
if (j >= strat->tl)
{
if (TEST_OPT_DEBUG) PrintLn();
if (TEST_OPT_INTSTRATEGY)
{
h->pCleardenom();// also does remove Content
}
enterT((*h),strat);
return 0;
}
j++;
}
}
}
/*2
* reduction procedure for tests only
* reduces with elements from T and chooses the best possible
*/
static int nc_redBest (LObject* h,kStrategy strat)
{
if (strat->tl<0)
{
enterT((*h),strat);
return 0;
}
int j,jbest,at,reddeg,d,pass;
poly p,ph;
pass = j = 0;
if (strat->honey)
reddeg = currRing->pFDeg((*h).p,currRing)+(*h).ecart;
else
reddeg = currRing->pFDeg((*h).p,currRing);
loop
{
if (pDivisibleBy(strat->T[j].p,(*h).p))
{
/* compute the s-polynomial */
if (!TEST_OPT_INTSTRATEGY) pNorm((*h).p);
#ifdef SDRING
// spSpolyShortBba will not work in the SRING case
if (pSDRING)
{
p=spSpolyCreate(strat->T[j].p,(*h).p,strat->kNoether);
if (p!=NULL) pDelete(&pNext(p));
}
else
#endif
p = nc_CreateShortSpoly(strat->T[j].p,(*h).p);
/* computes only the first monomial of the spoly */
if (p)
{
jbest = j;
/* looking for the best possible reduction */
if ((strat->syzComp==0) || (pMinComp(p) <= strat->syzComp))
{
loop
{
j++;
if (j > strat->tl)
break;
if (pDivisibleBy(strat->T[j].p,(*h).p))
{
#ifdef SDRING
// spSpolyShortBba will not work in the SRING case
if (pSDRING)
{
ph=spSpolyCreate(strat->T[j].p,(*h).p,strat->kNoether);
if (ph!=NULL) pDelete(&pNext(ph));
}
else
#endif
ph = nc_CreateShortSpoly(strat->T[j].p,(*h).p);
if (ph==NULL)
{
pLmFree(p);
pDelete(&((*h).p));
kDeleteLcm(h);
return 0;
}
else if (pLmCmp(ph,p) == -1)
{
pLmFree(p);
p = ph;
jbest = j;
}
else
{
pLmFree(ph);
}
}
}
}
pLmFree(p);
(*h).p = nc_ReduceSpoly(strat->T[jbest].p,(*h).p,strat->kNoether,currRing);
}
else
{
kDeleteLcm(h);
return 0;
}
if (strat->honey && currRing->pLexOrder)
strat->initEcart(h);
/* h.length:=l; */
/* try to reduce the s-polynomial */
// if (strat->syzComp)
// {
// if ((strat->syzComp>0) && (pMinComp((*h).p) > strat->syzComp))
// {
// if (TEST_OPT_DEBUG)
// PrintS(" >syzComp\n");
// if (TEST_OPT_INTSTRATEGY) p_Content(h->p,currRing);
// at=strat->posInT(strat->T,strat->tl,(*h));
// enterTBba((*h),at,strat);
// return;
// }
// }
if (strat->honey || currRing->pLexOrder)
{
pass++;
d = currRing->pFDeg((*h).p,currRing);
if (strat->honey)
d += (*h).ecart;
if ((strat->Ll >= 0) && ((pass > strat->LazyPass) || (d > reddeg)))
{
at = strat->posInL(strat->L,strat->Ll,h,strat);
if (at <= strat->Ll)
{
enterL(&strat->L,&strat->Ll,&strat->Lmax,*h,at);
(*h).p = NULL;
return 0;
}
}
else if (TEST_OPT_PROT && (strat->Ll < 0) && (d != reddeg))
{
reddeg = d;
Print("%d.");
mflush();
}
}
j = 0;
}
else
{
if (j >= strat->tl)
{
if (TEST_OPT_INTSTRATEGY)
{
h->pCleardenom();// also removes Content
}
enterT((*h),strat);
return 0;
}
j++;
}
}
}
#endif
#ifdef HAVE_RATGRING
void nc_gr_initBba(ideal F, kStrategy strat)
#else
void nc_gr_initBba(ideal, kStrategy strat)
#endif
{
assume(rIsPluralRing(currRing));
// int i;
// idhdl h;
/* setting global variables ------------------- */
strat->enterS = enterSBba;
/*
if ((BTEST1(20)) && (!strat->honey))
strat->red = nc_redBest;
else if (strat->honey)
strat->red = nc_redHoney;
else if (currRing->pLexOrder && !strat->homog)
strat->red = nc_redLazy;
else if (TEST_OPT_INTSTRATEGY && strat->homog)
strat->red = nc_redHomog0;
else
strat->red = nc_redHomog;
*/
// if (rIsPluralRing(currRing))
strat->red = redGrFirst;
#ifdef HAVE_RATGRING
if (rIsRatGRing(currRing))
{
int ii=IDELEMS(F)-1;
int jj;
BOOLEAN is_rat_id=FALSE;
for(;ii>=0;ii--)
{
for(jj=currRing->real_var_start;jj<=currRing->real_var_end;jj++)
{
if(pGetExp(F->m[ii],jj)>0) { is_rat_id=TRUE; break; }
}
if (is_rat_id) break;
}
if (is_rat_id) strat->red=redGrRatGB;
}
#endif
if (currRing->pLexOrder && strat->honey)
strat->initEcart = initEcartNormal;
else
strat->initEcart = initEcartBBA;
if (strat->honey)
strat->initEcartPair = initEcartPairMora;
else
strat->initEcartPair = initEcartPairBba;
// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
// {
// //interred machen Aenderung
// pFDegOld=currRing->pFDeg;
// pLDegOld=currRing->pLDeg;
// // h=ggetid("ecart");
// // if ((h!=NULL) && (IDTYP(h)==INTVEC_CMD))
// // {
// // ecartWeights=iv2array(IDINTVEC(h));
// // }
// // else
// {
// ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
// /*uses automatic computation of the ecartWeights to set them*/
// kEcartWeights(F->m,IDELEMS(F)-1,ecartWeights);
// }
// currRing->pFDeg=totaldegreeWecart;
// currRing->pLDeg=maxdegreeWecart;
// for(i=1; i<=(currRing->N); i++)
// Print(" %d",ecartWeights[i]);
// PrintLn();
// mflush();
// }
}
#define MYTEST 0
ideal k_gnc_gr_bba(const ideal F, const ideal Q, const intvec *, const bigintmat *, kStrategy strat, const ring _currRing)
{
const ring save = currRing; if( currRing != _currRing ) rChangeCurrRing(_currRing);
#if MYTEST
PrintS("<gnc_gr_bba>\n");
#endif
#ifdef HAVE_PLURAL
#if MYTEST
PrintS("currRing: \n");
rWrite(currRing);
#ifdef RDEBUG
rDebugPrint(currRing);
#endif
PrintS("F: \n");
idPrint(F);
PrintS("Q: \n");
idPrint(Q);
#endif
#endif
assume(currRing->OrdSgn != -1); // no mora!!! it terminates only for global ordering!!! (?)// alternate algebra?
// intvec *w=NULL;
// intvec *hilb=NULL;
int olddeg,reduc;
int red_result=1;
int /*hilbeledeg=1,*/hilbcount=0/*,minimcnt=0*/;
initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
// initHilbCrit(F,Q,&hilb,strat);
/* in plural we don't need Hilb yet */
nc_gr_initBba(F,strat);
initBuchMoraPos(strat);
if (rIsRatGRing(currRing))
{
strat->posInL=posInL0; // by pCmp of lcm
}
/*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
/*Shdl=*/initBuchMora(F, Q,strat);
strat->posInT=posInT110;
reduc = olddeg = 0;
/* compute------------------------------------------------------- */
while (strat->Ll >= 0)
{
if (TEST_OPT_DEBUG) messageSets(strat);
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) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
break;
}
/* picks the last element from the lazyset L */
strat->P = strat->L[strat->Ll];
strat->Ll--;
//kTest(strat);
if (strat->P.p != NULL)
if (pNext(strat->P.p) == strat->tail)
{
/* deletes the short spoly and computes */
pLmFree(strat->P.p);
/* the real one */
// if (ncRingType(currRing)==nc_lie) /* prod crit */
// if(pHasNotCF(strat->P.p1,strat->P.p2))
// {
// strat->cp++;
// /* prod.crit itself in nc_CreateSpoly */
// }
if( ! rIsRatGRing(currRing) )
{
strat->P.p = nc_CreateSpoly(strat->P.p1,strat->P.p2,currRing);
}
#ifdef HAVE_RATGRING
else
{
/* rational case */
strat->P.p = nc_rat_CreateSpoly(strat->P.p1,strat->P.p2,currRing->real_var_start-1,currRing);
}
#endif
#ifdef PDEBUG
p_Test(strat->P.p, currRing);
#endif
#if MYTEST
if (TEST_OPT_DEBUG)
{
PrintS("p1: "); pWrite(strat->P.p1);
PrintS("p2: "); pWrite(strat->P.p2);
PrintS("SPoly: "); pWrite(strat->P.p);
}
#endif
}
if (strat->P.p != NULL)
{
if (TEST_OPT_PROT)
message((strat->honey ? strat->P.ecart : 0) + strat->P.pFDeg(),
&olddeg,&reduc,strat, red_result);
#if MYTEST
if (TEST_OPT_DEBUG)
{
PrintS("p1: "); pWrite(strat->P.p1);
PrintS("p2: "); pWrite(strat->P.p2);
PrintS("SPoly before: "); pWrite(strat->P.p);
}
#endif
/* reduction of the element chosen from L */
strat->red(&strat->P,strat);
#if MYTEST
if (TEST_OPT_DEBUG)
{
PrintS("red SPoly: "); pWrite(strat->P.p);
}
#endif
}
if (strat->P.p != NULL)
{
if (TEST_OPT_PROT)
{
PrintS("s\n");
}
/* enter P.p into s and L */
{
/* quick unit detection in the rational case */
#ifdef HAVE_RATGRING
if( rIsRatGRing(currRing) )
{
if ( p_LmIsConstantRat(strat->P.p, currRing) )
{
#ifdef PDEBUG
PrintS("unit element detected:");
p_wrp(strat->P.p,currRing);
#endif
p_Delete(&strat->P.p,currRing, strat->tailRing);
strat->P.p = pOne();
}
}
#endif
strat->P.sev=0;
int pos=posInS(strat,strat->sl,strat->P.p, strat->P.ecart);
{
if (TEST_OPT_INTSTRATEGY)
{
if ((strat->syzComp==0)||(!strat->homog))
{
#ifdef HAVE_RATGRING
if(!rIsRatGRing(currRing))
#endif
strat->P.p = redtailBba(strat->P.p,pos-1,strat);
}
strat->P.p=p_Cleardenom(strat->P.p, currRing);
}
else
{
pNorm(strat->P.p);
if ((strat->syzComp==0)||(!strat->homog))
{
strat->P.p = redtailBba(strat->P.p,pos-1,strat);
}
}
if (TEST_OPT_DEBUG)
{
PrintS("new s:"); wrp(strat->P.p);
PrintLn();
#if MYTEST
PrintS("s: "); pWrite(strat->P.p);
#endif
}
// kTest(strat);
//
enterpairs(strat->P.p,strat->sl,strat->P.ecart,pos,strat);
if (strat->sl==-1) pos=0;
else pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
strat->enterS(&strat->P,pos,strat,-1);
}
// if (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
}
kDeleteLcm(&strat->P);
}
//kTest(strat);
}
if (TEST_OPT_DEBUG) messageSets(strat);
/* complete reduction of the standard basis--------- */
if (TEST_OPT_SB_1)
{
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++;
}
}
if (TEST_OPT_REDSB)
completeReduce(strat);
/* release temp data-------------------------------- */
exitBuchMora(strat);
// if (TEST_OPT_WEIGHTM)
// {
// currRing->pFDeg=pFDegOld;
// currRing->pLDeg=pLDegOld;
// if (ecartWeights)
// {
// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
// ecartWeights=NULL;
// }
// }
if (TEST_OPT_PROT) messageStat(hilbcount,strat);
if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
#if MYTEST
PrintS("</gnc_gr_bba>\n");
#endif
if( currRing != save ) rChangeCurrRing(save);
return (strat->Shdl);
}
ideal k_gnc_gr_mora(const ideal F, const ideal Q, const intvec *, const bigintmat *, kStrategy strat, const ring _currRing)
{
if ((ncRingType(_currRing)==nc_skew)
|| id_HomIdeal(F,Q,_currRing))
return gnc_gr_bba(F, Q, NULL, NULL, strat, _currRing);
else
{
WerrorS("not implemented: std for inhomogeneous ideasl in local orderings");
return NULL;
}
}
#endif
BOOLEAN
int BOOLEAN
Definition auxiliary.h:88
TRUE
#define TRUE
Definition auxiliary.h:101
FALSE
#define FALSE
Definition auxiliary.h:97
si_min
static int si_min(const int a, const int b)
Definition auxiliary.h:126
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
p
int p
Definition cfModGcd.cc:4086
f
FILE * f
Definition checklibs.c:9
bigintmat
Matrices of numbers.
Definition bigintmat.h:51
intvec
Definition intvec.h:24
skStrategy::syzComp
int syzComp
Definition kutil.h:353
skStrategy::tailRing
ring tailRing
Definition kutil.h:342
skStrategy::Ll
int Ll
Definition kutil.h:350
skStrategy::T
TSet T
Definition kutil.h:325
skStrategy::honey
char honey
Definition kutil.h:374
skStrategy::S
polyset S
Definition kutil.h:305
skStrategy::kNoether
poly kNoether
Definition kutil.h:328
skStrategy::tl
int tl
Definition kutil.h:349
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::Shdl
ideal Shdl
Definition kutil.h:302
skStrategy::initEcartPair
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition kutil.h:286
skStrategy::enterS
void(* enterS)(LObject *h, int pos, kStrategy strat, int atR)
Definition kutil.h:285
skStrategy::interpt
char interpt
Definition kutil.h:368
skStrategy::fromT
char fromT
Definition kutil.h:376
skStrategy::initEcart
void(* initEcart)(TObject *L)
Definition kutil.h:281
skStrategy::P
LObject P
Definition kutil.h:301
skStrategy::Lmax
int Lmax
Definition kutil.h:350
skStrategy::LazyPass
int LazyPass
Definition kutil.h:352
skStrategy::L
LSet L
Definition kutil.h:326
skStrategy::posInT
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition kutil.h:282
skStrategy::red
int(* red)(LObject *L, kStrategy strat)
Definition kutil.h:279
skStrategy::sl
int sl
Definition kutil.h:347
skStrategy::LazyDegree
int LazyDegree
Definition kutil.h:352
skStrategy::sevS
unsigned long * sevS
Definition kutil.h:321
skStrategy::homog
char homog
Definition kutil.h:369
Print
#define Print
Definition emacs.cc:80
j
int j
Definition facHensel.cc:110
WerrorS
void WerrorS(const char *s)
Definition feFopen.cc:24
gb_hack.h
gnc_gr_bba
EXTERN_VAR BBA_Proc gnc_gr_bba
Definition gb_hack.h:10
redGrRatGB
int redGrRatGB(LObject *h, kStrategy strat)
Definition gr_kstd2.cc:223
redGrFirst
int redGrFirst(LObject *h, kStrategy strat)
Definition gr_kstd2.cc:51
nc_gr_initBba
void nc_gr_initBba(ideal F, kStrategy strat)
nc_gr_initBba is needed for sca_gr_bba and gr_bba.
Definition gr_kstd2.cc:950
ratGB_divide_out
void ratGB_divide_out(poly p)
Definition gr_kstd2.cc:170
k_gnc_gr_bba
ideal k_gnc_gr_bba(const ideal F, const ideal Q, const intvec *, const bigintmat *, kStrategy strat, const ring _currRing)
Definition gr_kstd2.cc:1030
k_gnc_gr_mora
ideal k_gnc_gr_mora(const ideal F, const ideal Q, const intvec *, const bigintmat *, kStrategy strat, const ring _currRing)
Definition gr_kstd2.cc:1283
ideals.h
idPrint
#define idPrint(id)
Definition ideals.h:46
intvec.h
h
STATIC_VAR Poly * h
Definition janet.cc:971
redtailBba
KINLINE poly redtailBba(poly p, int pos, kStrategy strat, BOOLEAN normalize)
Definition kInline.h:1212
clearS
KINLINE void clearS(poly p, unsigned long p_sev, int *at, int *k, kStrategy strat)
Definition kInline.h:1235
nc.h
khstd.h
kstd1.h
Kstd1_deg
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:70
initBuchMora
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9749
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
enterL
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition kutil.cc:1269
enterpairs
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4487
initEcartPairMora
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition kutil.cc:1315
initBuchMoraPos
void initBuchMoraPos(kStrategy strat)
Definition kutil.cc:9580
posInL0
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5611
exitBuchMora
void exitBuchMora(kStrategy strat)
Definition kutil.cc:9837
initEcartNormal
void initEcartNormal(TObject *h)
Definition kutil.cc:1293
posInS
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition kutil.cc:4663
enterT
void enterT(LObject *p, kStrategy strat, int atT)
Definition kutil.cc:9143
posInT110
int posInT110(const TSet set, const int length, LObject &p)
Definition kutil.cc:5029
updateResult
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition kutil.cc:10051
deleteInL
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition kutil.cc:1208
initBuchMoraCrit
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9435
completeReduce
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition kutil.cc:10257
messageSets
void messageSets(kStrategy strat)
Definition kutil.cc:7536
initEcartBBA
void initEcartBBA(TObject *h)
Definition kutil.cc:1301
posInL11
int posInL11(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5802
initEcartPairBba
void initEcartPairBba(LObject *Lp, poly, poly, int, int)
Definition kutil.cc:1308
messageStat
void messageStat(int hilbcount, kStrategy strat)
Definition kutil.cc:7504
kutil.h
kDeleteLcm
static void kDeleteLcm(LObject *P)
Definition kutil.h:876
LObject
class sLObject LObject
Definition kutil.h:59
pi
#define pi
Definition libparse.cc:1145
nc.h
nc_CreateSpoly
static poly nc_CreateSpoly(const poly p1, const poly p2, const ring r)
Definition nc.h:241
nc_CreateShortSpoly
poly nc_CreateShortSpoly(poly p1, poly p2, const ring r)
Definition old.gring.cc:1879
nc_skew
@ nc_skew
Definition nc.h:16
ncRingType
static nc_type & ncRingType(nc_struct *p)
Definition nc.h:159
nc_ReduceSpoly
static poly nc_ReduceSpoly(const poly p1, poly p2, const ring r)
Definition nc.h:254
mod2.h
assume
#define assume(x)
Definition mod2.h:389
pIter
#define pIter(p)
Definition monomials.h:37
pNext
#define pNext(p)
Definition monomials.h:36
gnc_ReduceSpolyNew
poly gnc_ReduceSpolyNew(const poly p1, poly p2, const ring r)
Definition old.gring.cc:1399
NULL
#define NULL
Definition omList.c:12
options.h
TEST_OPT_INTSTRATEGY
#define TEST_OPT_INTSTRATEGY
Definition options.h:112
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_PROT
#define TEST_OPT_PROT
Definition options.h:105
BTEST1
#define BTEST1(a)
Definition options.h:34
TEST_OPT_DEBUG
#define TEST_OPT_DEBUG
Definition options.h:110
p_Cleardenom
poly p_Cleardenom(poly p, const ring r)
Definition p_polys.cc:2893
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_LmDivisibleByPart
static BOOLEAN p_LmDivisibleByPart(poly a, poly b, const ring r, const int start, const int end)
Definition p_polys.h:1883
p_Copy
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition p_polys.h:848
p_Totaldegree
static long p_Totaldegree(poly p, const ring r)
Definition p_polys.h:1528
p_Test
#define p_Test(p, r)
Definition p_polys.h:161
p_wrp
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition polys0.cc:373
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).
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
pSetm
#define pSetm(p)
Definition polys.h:272
pIsConstant
#define pIsConstant(p)
like above, except that Comp must be 0
Definition polys.h:239
pNorm
void pNorm(poly p)
Definition polys.h:363
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
pGetExp
#define pGetExp(p, i)
Exponent.
Definition polys.h:42
pDivisibleBy
#define pDivisibleBy(a, b)
returns TRUE, if leading monom of a divides leading monom of b i.e., if there exists a expvector c > ...
Definition polys.h:139
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
pOne
#define pOne()
Definition polys.h:316
pMinComp
#define pMinComp(p)
Definition polys.h:301
nc_rat_CreateSpoly
poly nc_rat_CreateSpoly(poly pp1, poly pp2, int ishift, const ring r)
Definition ratgring.cc:340
p_LmIsConstantRat
BOOLEAN p_LmIsConstantRat(const poly p, const ring r)
Definition ratgring.cc:642
nc_rat_ReduceSpolyNew
poly nc_rat_ReduceSpolyNew(const poly p1, poly p2, int ishift, const ring r)
Definition ratgring.cc:465
ratgring.h
PrintS
void PrintS(const char *s)
Definition reporter.cc:288
PrintLn
void PrintLn()
Definition reporter.cc:314
mflush
#define mflush()
Definition reporter.h:58
rWrite
void rWrite(ring r, BOOLEAN details)
Definition ring.cc:227
rDebugPrint
void rDebugPrint(const ring r)
Definition ring.cc:4214
ring.h
rIsPluralRing
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:406
rIsRatGRing
static BOOLEAN rIsRatGRing(const ring r)
Definition ring.h:433
rVar
static short rVar(const ring r)
define rVar(r) (r->N)
Definition ring.h:598
sca.h
id_HomIdeal
BOOLEAN id_HomIdeal(ideal id, ideal Q, const ring r)
Definition simpleideals.cc:1033
IDELEMS
#define IDELEMS(i)
Definition simpleideals.h:23
Q
#define Q
Definition sirandom.c:26
kStrategy
skStrategy * kStrategy
Definition structs.h:54
loop
#define loop
Definition structs.h:71
weight.h