Loading...
Searching...
No Matches
kspoly.cc
Go to the documentation of this file.
/****************************************
* Computer Algebra System SINGULAR *
****************************************/
/*
* ABSTRACT - Routines for Spoly creation and reductions
*/
// #define PDEBUG 2
#include "kernel/mod2.h"
#include "misc/options.h"
#include "kernel/GBEngine/kutil.h"
#include "coeffs/numbers.h"
#include "polys/monomials/p_polys.h"
#include "polys/templates/p_Procs.h"
#include "polys/nc/nc.h"
#include "kernel/polys.h"
#ifdef HAVE_SHIFTBBA
#include "polys/shiftop.h"
#endif
#ifdef KDEBUG
VAR int red_count = 0;
VAR int create_count = 0;
// define this if reductions are reported on TEST_OPT_DEBUG
#define TEST_OPT_DEBUG_RED
#endif
/***************************************************************
*
* Reduces PR with PW
* Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
*
* returns 0: okay
* 1: tailRing changed
* -1: cannot change tailRing
* 2: cannot change tailRing: strat==NULL
*
***************************************************************/
#ifdef STDZ_EXCHANGE_DURING_REDUCTION
int ksReducePolyZ(LObject* PR,
TObject* PW,
poly spNoether,
number *coef,
kStrategy strat)
{
#ifdef KDEBUG
red_count++;
#ifdef TEST_OPT_DEBUG_RED
// if (TEST_OPT_DEBUG)
// {
// Print("Red %d:", red_count); PR->wrp(); Print(" with:");
// PW->wrp();
// //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
// //pWrite(PR->p);
// }
#endif
#endif
int ret = 0;
ring tailRing = PR->tailRing;
if (strat!=NULL)
{
kTest_L(PR,strat);
kTest_T(PW,strat);
}
poly p1 = PR->GetLmTailRing(); // p2 | p1
poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
p_CheckPolyRing(p1, tailRing);
p_CheckPolyRing(p2, tailRing);
pAssume1(p2 != NULL && p1 != NULL &&
p_DivisibleBy(p2, p1, tailRing));
pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
(p_GetComp(p2, tailRing) == 0 &&
p_MaxComp(pNext(p2),tailRing) == 0));
#ifdef HAVE_PLURAL
if (rIsPluralRing(currRing))
{
// for the time being: we know currRing==strat->tailRing
// no exp-bound checking needed
// (only needed if exp-bound(tailring)<exp-b(currRing))
if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,FALSE);// TODO:reduce
else
{
poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
assume(_p != NULL);
nc_PolyPolyRed(_p, p2,coef, currRing);
if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
PR->pLength=0; // usually not used, GetpLength re-computes it if needed
}
return 0;
}
#endif
if (t2==NULL) // Divisor is just one term, therefore it will
{ // just cancel the leading term
// adjust lead coefficient if needed
if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
{
number bn = pGetCoeff(lm);
number an = pGetCoeff(p2);
int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
p_SetCoeff(lm, bn, tailRing);
if ((ct == 0) || (ct == 2))
PR->Tail_Mult_nn(an);
if (coef != NULL) *coef = an;
else n_Delete(&an, tailRing->cf);
}
PR->LmDeleteAndIter();
if (coef != NULL) *coef = n_Init(1, tailRing->cf);
return 0;
}
p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
//if (tailRing != currRing)
{
// check that reduction does not violate exp bound
while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
{
// undo changes of lm
p_ExpVectorAdd(lm, p2, tailRing);
if (strat == NULL) return 2;
if (! kStratChangeTailRing(strat, PR, PW)) return -1;
tailRing = strat->tailRing;
p1 = PR->GetLmTailRing();
p2 = PW->GetLmTailRing();
t2 = pNext(p2);
lm = p1;
p_ExpVectorSub(lm, p2, tailRing);
ret = 1;
}
}
#ifdef HAVE_SHIFTBBA
poly lmRight;
if (tailRing->isLPring)
{
assume(PR->shift == 0);
assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
}
#endif
// take care of coef business
if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
{
number bn = pGetCoeff(lm);
number an = pGetCoeff(p2);
int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
p_SetCoeff(lm, bn, tailRing);
if ((ct == 0) || (ct == 2))
PR->Tail_Mult_nn(an);
if (coef != NULL) *coef = an;
else n_Delete(&an, tailRing->cf);
}
else
{
if (coef != NULL) *coef = n_Init(1, tailRing->cf);
}
// and finally,
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
}
else
#endif
{
PR->Tail_Minus_mm_Mult_qq(lm, t2, pLength(t2) /*PW->GetpLength() - 1*/, spNoether);
}
assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
PR->LmDeleteAndIter();
return ret;
}
#endif
int ksReducePoly(LObject* PR,
TObject* PW,
poly spNoether,
number *coef,
poly *mon,
kStrategy strat,
BOOLEAN reduce)
{
#ifdef KDEBUG
red_count++;
#ifdef TEST_OPT_DEBUG_RED
// if (TEST_OPT_DEBUG)
// {
// Print("Red %d:", red_count); PR->wrp(); Print(" with:");
// PW->wrp();
// //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
// //pWrite(PR->p);
// }
#endif
#endif
int ret = 0;
ring tailRing = PR->tailRing;
if (strat!=NULL)
{
kTest_L(PR,strat);
kTest_T(PW,strat);
}
poly p1 = PR->GetLmTailRing(); // p2 | p1
poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
p_CheckPolyRing(p1, tailRing);
p_CheckPolyRing(p2, tailRing);
pAssume1(p2 != NULL && p1 != NULL &&
p_DivisibleBy(p2, p1, tailRing));
pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
(p_GetComp(p2, tailRing) == 0 &&
p_MaxComp(pNext(p2),tailRing) == 0));
#ifdef HAVE_PLURAL
if (rIsPluralRing(currRing))
{
// for the time being: we know currRing==strat->tailRing
// no exp-bound checking needed
// (only needed if exp-bound(tailring)<exp-b(currRing))
if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,reduce);
else
{
poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
assume(_p != NULL);
nc_PolyPolyRed(_p, p2,coef, currRing);
if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
PR->pLength=0; // usually not used, GetpLength re-computes it if needed
}
return 0;
}
#endif
if ((t2==NULL)&&(mon==NULL)) // Divisor is just one term, therefore it will
{ // just cancel the leading term
PR->LmDeleteAndIter();
if (coef != NULL) *coef = n_Init(1, tailRing->cf);
return 0;
}
p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
if (tailRing != currRing)
{
// check that reduction does not violate exp bound
while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
{
// undo changes of lm
p_ExpVectorAdd(lm, p2, tailRing);
if (strat == NULL) return 2;
if (! kStratChangeTailRing(strat, PR, PW)) return -1;
tailRing = strat->tailRing;
p1 = PR->GetLmTailRing();
p2 = PW->GetLmTailRing();
t2 = pNext(p2);
lm = p1;
p_ExpVectorSub(lm, p2, tailRing);
ret = 1;
}
}
#ifdef HAVE_SHIFTBBA
poly lmRight=NULL;
if (tailRing->isLPring)
{
assume(PR->shift == 0);
assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
}
#endif
// take care of coef business
if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
{
number bn = pGetCoeff(lm);
number an = pGetCoeff(p2);
int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
if (reduce)
{
if(n_IsMOne(an, tailRing->cf))
{
an=n_InpNeg(an, tailRing->cf);
bn=n_InpNeg(bn, tailRing->cf);
ct+=1;
}
#ifdef KDEBUG
else if(!n_IsOne(an,tailRing->cf))
{
StringSetS("ksReducePoly: ");n_Write(an,tailRing->cf);
StringAppendS("\n");
PrintS(StringEndS());
}
#endif
}
// in case of reduce, do not multiply PR
p_SetCoeff(lm, bn, tailRing);
if ((ct == 0) || (ct == 2))
PR->Tail_Mult_nn(an);
if (coef != NULL) *coef = an;
else n_Delete(&an, tailRing->cf);
}
else
{
if (coef != NULL) *coef = n_Init(1, tailRing->cf);
}
if(mon!=NULL) *mon=pHead(lm);
// and finally,
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
poly tmp=tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing);
PR->Tail_Minus_mm_Mult_qq(lm, tmp, pLength(t2), spNoether);
p_Delete(&tmp,tailRing);
p_Delete(&lm,tailRing);
p_Delete(&lmRight,tailRing);
}
else
#endif
{
PR->Tail_Minus_mm_Mult_qq(lm, t2, pLength(t2) /*PW->GetpLength() - 1*/, spNoether);
}
assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
PR->LmDeleteAndIter();
return ret;
}
#ifdef STDZ_EXCHANGE_DURING_REDUCTION
int ksReducePolyGCD(LObject* PR,
TObject* PW,
poly spNoether,
number *coef,
kStrategy strat)
{
#ifdef KDEBUG
red_count++;
#ifdef TEST_OPT_DEBUG_RED
// if (TEST_OPT_DEBUG)
// {
// Print("Red %d:", red_count); PR->wrp(); Print(" with:");
// PW->wrp();
// //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
// //pWrite(PR->p);
// }
#endif
#endif
int ret = 0;
ring tailRing = PR->tailRing;
if (strat!=NULL)
{
kTest_L(PR,strat);
kTest_T(PW,strat);
}
poly p1 = PR->GetLmTailRing();
poly p2 = PW->GetLmTailRing();
poly t2 = pNext(p2), lm = pOne();
assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
p_CheckPolyRing(p1, tailRing);
p_CheckPolyRing(p2, tailRing);
pAssume1(p2 != NULL && p1 != NULL &&
p_DivisibleBy(p2, p1, tailRing));
pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
(p_GetComp(p2, tailRing) == 0 &&
p_MaxComp(pNext(p2),tailRing) == 0));
#ifdef HAVE_PLURAL
if (rIsPluralRing(currRing))
{
// for the time being: we know currRing==strat->tailRing
// no exp-bound checking needed
// (only needed if exp-bound(tailring)<exp-b(currRing))
if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,TRUE);
else
{
poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
assume(_p != NULL);
nc_PolyPolyRed(_p, p2,coef, currRing);
if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
PR->pLength=0; // usually not used, GetpLength re-computes it if needed
}
return 0;
}
#endif
// check that reduction does not violate exp bound
while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
{
// undo changes of lm
p_ExpVectorAdd(lm, p2, tailRing);
if (strat == NULL) return 2;
if (! kStratChangeTailRing(strat, PR, PW)) return -1;
tailRing = strat->tailRing;
p1 = PR->GetLmTailRing();
p2 = PW->GetLmTailRing();
t2 = pNext(p2);
lm = p1;
p_ExpVectorSub(lm, p2, tailRing);
ret = 1;
}
#ifdef HAVE_SHIFTBBA
poly lmRight;
if (tailRing->isLPring)
{
assume(PR->shift == 0);
assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
}
#endif
number ct, an, bn;
// take care of coef business
if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
{
ct = n_ExtGcd(pGetCoeff(p1), pGetCoeff(p2), &an, &bn, tailRing->cf); // Calculate GCD
if (n_IsZero(an, tailRing->cf) || n_IsZero(bn, tailRing->cf))
{
n_Delete(&an, tailRing->cf);
n_Delete(&bn, tailRing->cf);
n_Delete(&ct, tailRing->cf);
return ret;
}
/* negate bn since we subtract in Tail_Minus_mm_Mult_qq */
bn = n_InpNeg(bn, tailRing->cf);
p_SetCoeff(lm, bn, tailRing);
p_Test(lm,tailRing);
PR->Tail_Mult_nn(an);
}
else
{
if (coef != NULL) *coef = n_Init(1, tailRing->cf);
}
// and finally,
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
}
else
#endif
{
PR->Tail_Minus_mm_Mult_qq(lm, t2, pLength(t2) /*PW->GetpLength() - 1*/, spNoether);
}
assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
pSetCoeff(PR->p, ct);
return ret;
}
#endif
/* Computes a reduction of the lead coefficient only. We have already tested
* that lm(PW) divides lm(PR), but lc(PW) does not divide lc(PR). We have
* computed division with remainder on the lead coefficients, parameter
* coef is the corresponding multiple for PW we need. The new lead
* coefficient, i.e. the remainder of lc division has already been
* set before calling this function. We do not drop the lead term at
* the end, but keep the adjusted, correct lead term. */
int ksReducePolyLC(LObject* PR,
TObject* PW,
poly spNoether,
number *coef,
kStrategy strat)
{
#ifdef KDEBUG
red_count++;
#ifdef TEST_OPT_DEBUG_RED
// if (TEST_OPT_DEBUG)
// {
// Print("Red %d:", red_count); PR->wrp(); Print(" with:");
// PW->wrp();
// //printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
// //pWrite(PR->p);
// }
#endif
#endif
/* printf("PR->P: ");
* p_Write(PR->p, currRing, PR->tailRing); */
int ret = 0;
ring tailRing = PR->tailRing;
if (strat!=NULL)
{
kTest_L(PR,strat);
kTest_T(PW,strat);
}
poly p1 = PR->GetLmTailRing(); // p2 | p1
poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
poly lm = p1; // really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
p_CheckPolyRing(p1, tailRing);
p_CheckPolyRing(p2, tailRing);
pAssume1(p2 != NULL && p1 != NULL &&
p_DivisibleBy(p2, p1, tailRing));
pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
(p_GetComp(p2, tailRing) == 0 &&
p_MaxComp(pNext(p2),tailRing) == 0));
#ifdef HAVE_PLURAL
if (rIsPluralRing(currRing))
{
// for the time being: we know currRing==strat->tailRing
// no exp-bound checking needed
// (only needed if exp-bound(tailring)<exp-b(currRing))
if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,FALSE);
else
{
poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
assume(_p != NULL);
nc_PolyPolyRed(_p, p2,coef, currRing);
if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
PR->pLength=0; // usually not used, GetpLength re-computes it if needed
}
return 0;
}
#endif
p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
p_SetCoeff(lm, n_Init(1, tailRing->cf), tailRing);
while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
{
// undo changes of lm
p_ExpVectorAdd(lm, p2, tailRing);
if (strat == NULL) return 2;
/* if (! kStratChangeTailRing(strat, PR, PW)) return -1; */
tailRing = strat->tailRing;
p1 = PR->GetLmTailRing();
p2 = PW->GetLmTailRing();
lm = p1;
p_ExpVectorSub(lm, p2, tailRing);
ret = 1;
}
#ifdef HAVE_SHIFTBBA
poly lmRight;
if (tailRing->isLPring)
{
assume(PR->shift == 0);
assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
}
#endif
// and finally,
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(p2, lmRight, tailRing), pLength(p2), spNoether);
}
else
#endif
{
PR->Tail_Minus_mm_Mult_qq(lm, p2, pLength(p2) /*PW->GetpLength() - 1*/, spNoether);
}
assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
PR->LmDeleteAndIter();
p_SetCoeff(PR->p, *coef, currRing);
#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
if (TEST_OPT_DEBUG)
{
Print(" to: "); PR->wrp(); Print("\n");
//printf("\nt^%i ", PR->ecart);pWrite(pHead(PR->p));
}
#endif
return ret;
}
int ksReducePolyBound(LObject* PR,
TObject* PW,
int /*bound*/,
poly spNoether,
number *coef,
kStrategy strat)
{
#ifdef KDEBUG
red_count++;
#ifdef TEST_OPT_DEBUG_RED
if (TEST_OPT_DEBUG)
{
Print("Red %d:", red_count); PR->wrp(); Print(" with:");
PW->wrp();
//printf("\necart(PR)-ecart(PW): %i\n",PR->ecart-PW->ecart);
//pWrite(PR->p);
}
#endif
#endif
int ret = 0;
ring tailRing = PR->tailRing;
if (strat!=NULL)
{
kTest_L(PR,strat);
kTest_T(PW,strat);
}
poly p1 = PR->GetLmTailRing(); // p2 | p1
poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
p_CheckPolyRing(p1, tailRing);
p_CheckPolyRing(p2, tailRing);
pAssume1(p2 != NULL && p1 != NULL &&
p_DivisibleBy(p2, p1, tailRing));
pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
(p_GetComp(p2, tailRing) == 0 &&
p_MaxComp(pNext(p2),tailRing) == 0));
#ifdef HAVE_PLURAL
if (rIsPluralRing(currRing))
{
// for the time being: we know currRing==strat->tailRing
// no exp-bound checking needed
// (only needed if exp-bound(tailring)<exp-b(currRing))
if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,FALSE);
else
{
poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
assume(_p != NULL);
nc_PolyPolyRed(_p, p2,coef, currRing);
if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
PR->pLength=0; // usually not used, GetpLength re-computes it if needed
}
return 0;
}
#endif
if (t2==NULL) // Divisor is just one term, therefore it will
{ // just cancel the leading term
PR->LmDeleteAndIter();
if (coef != NULL) *coef = n_Init(1, tailRing->cf);
return 0;
}
p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
if (tailRing != currRing)
{
// check that reduction does not violate exp bound
while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
{
// undo changes of lm
p_ExpVectorAdd(lm, p2, tailRing);
if (strat == NULL) return 2;
if (! kStratChangeTailRing(strat, PR, PW)) return -1;
tailRing = strat->tailRing;
p1 = PR->GetLmTailRing();
p2 = PW->GetLmTailRing();
t2 = pNext(p2);
lm = p1;
p_ExpVectorSub(lm, p2, tailRing);
ret = 1;
}
}
#ifdef HAVE_SHIFTBBA
poly lmRight;
if (tailRing->isLPring)
{
assume(PR->shift == 0);
assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
}
#endif
// take care of coef business
if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
{
number bn = pGetCoeff(lm);
number an = pGetCoeff(p2);
int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
p_SetCoeff(lm, bn, tailRing);
if ((ct == 0) || (ct == 2))
PR->Tail_Mult_nn(an);
if (coef != NULL) *coef = an;
else n_Delete(&an, tailRing->cf);
}
else
{
if (coef != NULL) *coef = n_Init(1, tailRing->cf);
}
// and finally,
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
}
else
#endif
{
PR->Tail_Minus_mm_Mult_qq(lm, t2, pLength(t2) /*PW->GetpLength() - 1*/, spNoether);
}
assume(PW->GetpLength() == pLength(PW->p != NULL ? PW->p : PW->t_p));
PR->LmDeleteAndIter();
#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
if (TEST_OPT_DEBUG)
{
Print(" to: "); PR->wrp(); Print("\n");
//printf("\nt^%i ", PR->ecart);pWrite(pHead(PR->p));
}
#endif
return ret;
}
/***************************************************************
*
* Reduces PR with PW
* Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
*
***************************************************************/
int ksReducePolySig(LObject* PR,
TObject* PW,
long /*idx*/,
poly spNoether,
number *coef,
kStrategy strat)
{
#ifdef KDEBUG
red_count++;
#ifdef TEST_OPT_DEBUG_RED
if (TEST_OPT_DEBUG)
{
Print("Red %d:", red_count); PR->wrp(); Print(" with:");
PW->wrp();
}
#endif
#endif
int ret = 0;
ring tailRing = PR->tailRing;
if (strat!=NULL)
{
kTest_L(PR,strat);
kTest_T(PW,strat);
}
// signature-based stuff:
// checking for sig-safeness first
// NOTE: This has to be done in the current ring
//
/**********************************************
*
* TODO:
* --------------------------------------------
* if strat->sbaOrder == 1
* Since we are subdividing lower index and
* current index reductions it is enough to
* look at the polynomial part of the signature
* for a check. This should speed-up checking
* a lot!
* if !strat->sbaOrder == 0
* We are not subdividing lower and current index
* due to the fact that we are using the induced
* Schreyer order
*
* nevertheless, this different behaviour is
* taken care of by is_sigsafe
* => one reduction procedure can be used for
* both, the incremental and the non-incremental
* attempt!
* --------------------------------------------
*
*********************************************/
//printf("COMPARE IDX: %ld -- %ld\n",idx,strat->currIdx);
if (!PW->is_sigsafe)
{
poly sigMult = pCopy(PW->sig); // copy signature of reducer
//#if 1
#ifdef DEBUGF5
printf("IN KSREDUCEPOLYSIG: \n");
pWrite(pHead(f1));
pWrite(pHead(f2));
pWrite(sigMult);
printf("--------------\n");
#endif
p_ExpVectorAddSub(sigMult,PR->GetLmCurrRing(),PW->GetLmCurrRing(),currRing);
//#if 1
#ifdef DEBUGF5
printf("------------------- IN KSREDUCEPOLYSIG: --------------------\n");
pWrite(pHead(f1));
pWrite(pHead(f2));
pWrite(sigMult);
pWrite(PR->sig);
printf("--------------\n");
#endif
int sigSafe = p_LmCmp(PR->sig,sigMult,currRing);
// now we can delete the copied polynomial data used for checking for
// sig-safeness of the reduction step
//#if 1
#ifdef DEBUGF5
printf("%d -- %d sig\n",sigSafe,PW->is_sigsafe);
#endif
//pDelete(&f1);
pDelete(&sigMult);
// go on with the computations only if the signature of p2 is greater than the
// signature of fm*p1
if(sigSafe != 1)
{
PR->is_redundant = TRUE;
return 3;
}
//PW->is_sigsafe = TRUE;
}
PR->is_redundant = FALSE;
poly p1 = PR->GetLmTailRing(); // p2 | p1
poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
p_CheckPolyRing(p1, tailRing);
p_CheckPolyRing(p2, tailRing);
pAssume1(p2 != NULL && p1 != NULL &&
p_DivisibleBy(p2, p1, tailRing));
pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
(p_GetComp(p2, tailRing) == 0 &&
p_MaxComp(pNext(p2),tailRing) == 0));
#ifdef HAVE_PLURAL
if (rIsPluralRing(currRing))
{
// for the time being: we know currRing==strat->tailRing
// no exp-bound checking needed
// (only needed if exp-bound(tailring)<exp-b(currRing))
if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,FALSE);
else
{
poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
assume(_p != NULL);
nc_PolyPolyRed(_p, p2, coef, currRing);
if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
PR->pLength=0; // usaully not used, GetpLength re-comoutes it if needed
}
return 0;
}
#endif
if (t2==NULL) // Divisor is just one term, therefore it will
{ // just cancel the leading term
PR->LmDeleteAndIter();
if (coef != NULL) *coef = n_Init(1, tailRing->cf);
return 0;
}
p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
if (tailRing != currRing)
{
// check that reduction does not violate exp bound
while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
{
// undo changes of lm
p_ExpVectorAdd(lm, p2, tailRing);
if (strat == NULL) return 2;
if (! kStratChangeTailRing(strat, PR, PW)) return -1;
tailRing = strat->tailRing;
p1 = PR->GetLmTailRing();
p2 = PW->GetLmTailRing();
t2 = pNext(p2);
lm = p1;
p_ExpVectorSub(lm, p2, tailRing);
ret = 1;
}
}
#ifdef HAVE_SHIFTBBA
poly lmRight;
if (tailRing->isLPring)
{
assume(PR->shift == 0);
assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
}
#endif
// take care of coef business
if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
{
number bn = pGetCoeff(lm);
number an = pGetCoeff(p2);
int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
p_SetCoeff(lm, bn, tailRing);
if ((ct == 0) || (ct == 2))
PR->Tail_Mult_nn(an);
if (coef != NULL) *coef = an;
else n_Delete(&an, tailRing->cf);
}
else
{
if (coef != NULL) *coef = n_Init(1, tailRing->cf);
}
// and finally,
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
}
else
#endif
{
PR->Tail_Minus_mm_Mult_qq(lm, t2, PW->GetpLength() - 1, spNoether);
}
assume(PW->GetpLength() == (int)pLength(PW->p != NULL ? PW->p : PW->t_p));
PR->LmDeleteAndIter();
#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
if (TEST_OPT_DEBUG)
{
Print(" to: "); PR->wrp(); Print("\n");
}
#endif
return ret;
}
int ksReducePolySigRing(LObject* PR,
TObject* PW,
long /*idx*/,
poly spNoether,
number *coef,
kStrategy strat)
{
#ifdef KDEBUG
red_count++;
#ifdef TEST_OPT_DEBUG_RED
if (TEST_OPT_DEBUG)
{
Print("Red %d:", red_count); PR->wrp(); Print(" with:");
PW->wrp();
}
#endif
#endif
int ret = 0;
ring tailRing = PR->tailRing;
if (strat!=NULL)
{
kTest_L(PR,strat);
kTest_T(PW,strat);
}
// signature-based stuff:
// checking for sig-safeness first
// NOTE: This has to be done in the current ring
//
/**********************************************
*
* TODO:
* --------------------------------------------
* if strat->sbaOrder == 1
* Since we are subdividing lower index and
* current index reductions it is enough to
* look at the polynomial part of the signature
* for a check. This should speed-up checking
* a lot!
* if !strat->sbaOrder == 0
* We are not subdividing lower and current index
* due to the fact that we are using the induced
* Schreyer order
*
* nevertheless, this different behaviour is
* taken care of by is_sigsafe
* => one reduction procedure can be used for
* both, the incremental and the non-incremental
* attempt!
* --------------------------------------------
*
*********************************************/
//printf("COMPARE IDX: %ld -- %ld\n",idx,strat->currIdx);
if (!PW->is_sigsafe)
{
poly sigMult = pCopy(PW->sig); // copy signature of reducer
//#if 1
#ifdef DEBUGF5
printf("IN KSREDUCEPOLYSIG: \n");
pWrite(pHead(f1));
pWrite(pHead(f2));
pWrite(sigMult);
printf("--------------\n");
#endif
p_ExpVectorAddSub(sigMult,PR->GetLmCurrRing(),PW->GetLmCurrRing(),currRing);
//I have also to set the leading coefficient for sigMult (in the case of rings)
if(rField_is_Ring(currRing))
{
pSetCoeff(sigMult,nMult(nDiv(pGetCoeff(PR->p),pGetCoeff(PW->p)), pGetCoeff(sigMult)));
if(nIsZero(pGetCoeff(sigMult)))
{
sigMult = NULL;
}
}
//#if 1
#ifdef DEBUGF5
printf("------------------- IN KSREDUCEPOLYSIG: --------------------\n");
pWrite(pHead(f1));
pWrite(pHead(f2));
pWrite(sigMult);
pWrite(PR->sig);
printf("--------------\n");
#endif
int sigSafe;
if(!rField_is_Ring(currRing))
sigSafe = p_LmCmp(PR->sig,sigMult,currRing);
// now we can delete the copied polynomial data used for checking for
// sig-safeness of the reduction step
//#if 1
#ifdef DEBUGF5
printf("%d -- %d sig\n",sigSafe,PW->is_sigsafe);
#endif
if(rField_is_Ring(currRing))
{
// Set the sig
poly origsig = pCopy(PR->sig);
if(sigMult != NULL)
PR->sig = pHead(pSub(PR->sig, sigMult));
//The sigs have the same lm, have to subtract
//It may happen that now the signature is 0 (drop)
if(PR->sig == NULL)
{
strat->sigdrop=TRUE;
}
else
{
if(pLtCmp(PR->sig,origsig) == 1)
{
// do not allow this reduction - it will increase it's signature
// and the partially standard basis is just till the old sig, not the new one
PR->is_redundant = TRUE;
pDelete(&PR->sig);
PR->sig = origsig;
strat->blockred++;
return 3;
}
if(pLtCmp(PR->sig,origsig) == -1)
{
strat->sigdrop=TRUE;
}
}
pDelete(&origsig);
}
//pDelete(&f1);
// go on with the computations only if the signature of p2 is greater than the
// signature of fm*p1
if(sigSafe != 1 && !rField_is_Ring(currRing))
{
PR->is_redundant = TRUE;
return 3;
}
//PW->is_sigsafe = TRUE;
}
PR->is_redundant = FALSE;
poly p1 = PR->GetLmTailRing(); // p2 | p1
poly p2 = PW->GetLmTailRing(); // i.e. will reduce p1 with p2; lm = LT(p1) / LM(p2)
poly t2 = pNext(p2), lm = p1; // t2 = p2 - LT(p2); really compute P = LC(p2)*p1 - LT(p1)/LM(p2)*p2
assume(p1 != NULL && p2 != NULL);// Attention, we have rings and there LC(p2) and LC(p1) are special
p_CheckPolyRing(p1, tailRing);
p_CheckPolyRing(p2, tailRing);
pAssume1(p2 != NULL && p1 != NULL &&
p_DivisibleBy(p2, p1, tailRing));
pAssume1(p_GetComp(p1, tailRing) == p_GetComp(p2, tailRing) ||
(p_GetComp(p2, tailRing) == 0 &&
p_MaxComp(pNext(p2),tailRing) == 0));
#ifdef HAVE_PLURAL
if (rIsPluralRing(currRing))
{
// for the time being: we know currRing==strat->tailRing
// no exp-bound checking needed
// (only needed if exp-bound(tailring)<exp-b(currRing))
if (PR->bucket!=NULL) nc_kBucketPolyRed_Z(PR->bucket, p2,coef,FALSE);
else
{
poly _p = (PR->t_p != NULL ? PR->t_p : PR->p);
assume(_p != NULL);
nc_PolyPolyRed(_p, p2, coef, currRing);
if (PR->t_p!=NULL) PR->t_p=_p; else PR->p=_p;
PR->pLength=0; // usaully not used, GetpLength re-comoutes it if needed
}
return 0;
}
#endif
if (t2==NULL) // Divisor is just one term, therefore it will
{ // just cancel the leading term
PR->LmDeleteAndIter();
if (coef != NULL) *coef = n_Init(1, tailRing->cf);
return 0;
}
p_ExpVectorSub(lm, p2, tailRing); // Calculate the Monomial we must multiply to p2
if (tailRing != currRing)
{
// check that reduction does not violate exp bound
while (PW->max_exp != NULL && !p_LmExpVectorAddIsOk(lm, PW->max_exp, tailRing))
{
// undo changes of lm
p_ExpVectorAdd(lm, p2, tailRing);
if (strat == NULL) return 2;
if (! kStratChangeTailRing(strat, PR, PW)) return -1;
tailRing = strat->tailRing;
p1 = PR->GetLmTailRing();
p2 = PW->GetLmTailRing();
t2 = pNext(p2);
lm = p1;
p_ExpVectorSub(lm, p2, tailRing);
ret = 1;
}
}
#ifdef HAVE_SHIFTBBA
poly lmRight;
if (tailRing->isLPring)
{
assume(PR->shift == 0);
assume(PW->shift == si_max(p_mFirstVblock(PW->p, tailRing) - 1, 0));
k_SplitFrame(lm, lmRight, PW->shift + 1, tailRing);
}
#endif
// take care of coef business
if(rField_is_Ring(currRing))
{
p_SetCoeff(lm, nDiv(pGetCoeff(lm),pGetCoeff(p2)), tailRing);
if (coef != NULL) *coef = n_Init(1, tailRing->cf);
}
else
{
if (! n_IsOne(pGetCoeff(p2), tailRing->cf))
{
number bn = pGetCoeff(lm);
number an = pGetCoeff(p2);
int ct = ksCheckCoeff(&an, &bn, tailRing->cf); // Calculate special LC
p_SetCoeff(lm, bn, tailRing);
if (((ct == 0) || (ct == 2)))
PR->Tail_Mult_nn(an);
if (coef != NULL) *coef = an;
else n_Delete(&an, tailRing->cf);
}
else
{
if (coef != NULL) *coef = n_Init(1, tailRing->cf);
}
}
// and finally,
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
PR->Tail_Minus_mm_Mult_qq(lm, tailRing->p_Procs->pp_Mult_mm(t2, lmRight, tailRing), pLength(t2), spNoether);
}
else
#endif
{
PR->Tail_Minus_mm_Mult_qq(lm, t2, PW->GetpLength() - 1, spNoether);
}
assume(PW->GetpLength() == (int)pLength(PW->p != NULL ? PW->p : PW->t_p));
PR->LmDeleteAndIter();
#if defined(KDEBUG) && defined(TEST_OPT_DEBUG_RED)
if (TEST_OPT_DEBUG)
{
Print(" to: "); PR->wrp(); Print("\n");
}
#endif
return ret;
}
/***************************************************************
*
* Creates S-Poly of p1 and p2
*
*
***************************************************************/
void ksCreateSpoly(LObject* Pair, poly spNoether,
int use_buckets, ring tailRing,
poly m1, poly m2, TObject** R)
{
#ifdef KDEBUG
create_count++;
#endif
poly p1 = Pair->p1;
poly p2 = Pair->p2;
Pair->tailRing = tailRing;
assume(p1 != NULL);
assume(p2 != NULL);
assume(tailRing != NULL);
poly a1 = pNext(p1), a2 = pNext(p2);
number lc1 = pGetCoeff(p1), lc2 = pGetCoeff(p2);
int co=0/*, ct = ksCheckCoeff(&lc1, &lc2, currRing->cf)*/; // gcd and zero divisors
(void) ksCheckCoeff(&lc1, &lc2, currRing->cf);
int l1=0, l2=0;
if (currRing->pCompIndex >= 0)
{
if (__p_GetComp(p1, currRing)!=__p_GetComp(p2, currRing))
{
if (__p_GetComp(p1, currRing)==0)
{
co=1;
p_SetCompP(p1,__p_GetComp(p2, currRing), currRing, tailRing);
}
else
{
co=2;
p_SetCompP(p2, __p_GetComp(p1, currRing), currRing, tailRing);
}
}
}
// get m1 = LCM(LM(p1), LM(p2))/LM(p1)
// m2 = LCM(LM(p1), LM(p2))/LM(p2)
if (m1 == NULL)
k_GetLeadTerms(p1, p2, currRing, m1, m2, tailRing);
#ifdef HAVE_SHIFTBBA
poly m12, m22;
if (tailRing->isLPring)
{
assume(p_mFirstVblock(p1, tailRing) <= 1 || p_mFirstVblock(p2, tailRing) <= 1);
k_SplitFrame(m1, m12, si_max(p_mFirstVblock(p1, tailRing), 1), tailRing);
k_SplitFrame(m2, m22, si_max(p_mFirstVblock(p2, tailRing), 1), tailRing);
// coeffs of m1,m2 are NULL here
}
#endif
pSetCoeff0(m1, lc2);
pSetCoeff0(m2, lc1); // and now, m1 * LT(p1) == m2 * LT(p2)
if (R != NULL)
{
if (Pair->i_r1 == -1)
{
l1 = pLength(p1) - 1;
}
else
{
l1 = (R[Pair->i_r1])->GetpLength() - 1;
}
if ((Pair->i_r2 == -1)||(R[Pair->i_r2]==NULL))
{
l2 = pLength(p2) - 1;
}
else
{
l2 = (R[Pair->i_r2])->GetpLength() - 1;
}
}
// get m2 * a2
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
// m2*a2*m22
poly tmp= tailRing->p_Procs->pp_mm_Mult(a2, m2, tailRing);
a2 = tailRing->p_Procs->pp_Mult_mm(tmp, m22, tailRing);
p_Delete(&tmp,tailRing);
}
else
#endif
if (spNoether != NULL)
{
l2 = -1;
a2 = tailRing->p_Procs->pp_Mult_mm_Noether(a2, m2, spNoether, l2, tailRing);
assume(l2 == (int)pLength(a2));
}
else
{
a2 = tailRing->p_Procs->pp_Mult_mm(a2, m2, tailRing);
}
if (!(rField_is_Domain(currRing))) l2 = pLength(a2);
Pair->SetLmTail(m2, a2, l2, use_buckets, tailRing);
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
// get m2*a2*m22 - m1*a1*m12
poly tmp=tailRing->p_Procs->pp_Mult_mm(a1, m12, tailRing);
Pair->Tail_Minus_mm_Mult_qq(m1, tmp, l1, spNoether);
p_Delete(&tmp,tailRing);
}
else
#endif
{
// get m2*a2 - m1*a1
Pair->Tail_Minus_mm_Mult_qq(m1, a1, l1, spNoether);
}
// Clean-up time
Pair->LmDeleteAndIter();
p_LmDelete(m1, tailRing);
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
// just to be sure, check that the shift is correct
assume(Pair->shift == 0);
assume(si_max(p_mFirstVblock(Pair->p, tailRing) - 1, 0) == Pair->shift); // == 0
p_LmDelete(m12, tailRing);
p_LmDelete(m22, tailRing);
// m2 is already deleted
}
#endif
if (co != 0)
{
if (co==1)
{
p_SetCompP(p1,0, currRing, tailRing);
}
else
{
p_SetCompP(p2,0, currRing, tailRing);
}
}
}
int ksReducePolyTail(LObject* PR, TObject* PW, poly Current, poly spNoether)
{
BOOLEAN ret;
number coef;
poly Lp = PR->GetLmCurrRing();
poly Save = PW->GetLmCurrRing();
pAssume(pIsMonomOf(Lp, Current));
assume(Lp != NULL && Current != NULL && pNext(Current) != NULL);
assume(PR->bucket == NULL);
LObject Red(pNext(Current), PR->tailRing);
TObject With(PW, Lp == Save);
pAssume(!pHaveCommonMonoms(Red.p, With.p));
ret = ksReducePoly(&Red, &With, spNoether, &coef);
if (!ret)
{
if (! n_IsOne(coef, currRing->cf))
{
pNext(Current) = NULL;
if (Current == PR->p && PR->t_p != NULL)
pNext(PR->t_p) = NULL;
PR->Mult_nn(coef);
}
n_Delete(&coef, currRing->cf);
pNext(Current) = Red.GetLmTailRing();
if (Current == PR->p && PR->t_p != NULL)
pNext(PR->t_p) = pNext(Current);
}
if (Lp == Save)
With.Delete();
return ret;
}
int ksReducePolyTailBound(LObject* PR, TObject* PW, int bound, poly Current, poly spNoether)
{
BOOLEAN ret;
number coef;
poly Lp = PR->GetLmCurrRing();
poly Save = PW->GetLmCurrRing();
pAssume(pIsMonomOf(Lp, Current));
assume(Lp != NULL && Current != NULL && pNext(Current) != NULL);
assume(PR->bucket == NULL);
LObject Red(pNext(Current), PR->tailRing);
TObject With(PW, Lp == Save);
pAssume(!pHaveCommonMonoms(Red.p, With.p));
ret = ksReducePolyBound(&Red, &With,bound, spNoether, &coef);
if (!ret)
{
if (! n_IsOne(coef, currRing->cf))
{
pNext(Current) = NULL;
if (Current == PR->p && PR->t_p != NULL)
pNext(PR->t_p) = NULL;
PR->Mult_nn(coef);
}
n_Delete(&coef, currRing->cf);
pNext(Current) = Red.GetLmTailRing();
if (Current == PR->p && PR->t_p != NULL)
pNext(PR->t_p) = pNext(Current);
}
if (Lp == Save)
With.Delete();
return ret;
}
/***************************************************************
*
* Auxiliary Routines
*
*
***************************************************************/
/*2
* creates the leading term of the S-polynomial of p1 and p2
* do not destroy p1 and p2
* remarks:
* 1. the coefficient is 0 (p_Init)
* 1. a) in the case of coefficient ring, the coefficient is calculated
* 2. pNext is undefined
*/
//static void bbb() { int i=0; }
poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing)
{
poly a1 = pNext(p1), a2 = pNext(p2);
#ifdef HAVE_SHIFTBBA
int shift1, shift2;
if (tailRing->isLPring)
{
// assume: LM is shifted, tail unshifted
assume(p_FirstVblock(a1, tailRing) <= 1);
assume(p_FirstVblock(a2, tailRing) <= 1);
// save the shift of the LM so we can shift the other monomials on demand
shift1 = p_mFirstVblock(p1, tailRing) - 1;
shift2 = p_mFirstVblock(p2, tailRing) - 1;
}
#endif
long c1=p_GetComp(p1, currRing),c2=p_GetComp(p2, currRing);
long c;
poly m1,m2;
number t1 = NULL,t2 = NULL;
int cm,i;
BOOLEAN equal;
BOOLEAN is_Ring=rField_is_Ring(currRing);
number lc1 = pGetCoeff(p1), lc2 = pGetCoeff(p2);
if (is_Ring)
{
ksCheckCoeff(&lc1, &lc2, currRing->cf); // gcd and zero divisors
if (a1 != NULL) t2 = nMult(pGetCoeff(a1),lc2);
if (a2 != NULL) t1 = nMult(pGetCoeff(a2),lc1);
while (a1 != NULL && nIsZero(t2))
{
pIter(a1);
nDelete(&t2);
if (a1 != NULL) t2 = nMult(pGetCoeff(a1),lc2);
}
while (a2 != NULL && nIsZero(t1))
{
pIter(a2);
nDelete(&t1);
if (a2 != NULL) t1 = nMult(pGetCoeff(a2),lc1);
}
}
#ifdef HAVE_SHIFTBBA
// shift the next monomial on demand
if (tailRing->isLPring)
{
a1 = p_LPCopyAndShiftLM(a1, shift1, tailRing);
a2 = p_LPCopyAndShiftLM(a2, shift2, tailRing);
}
#endif
if (a1==NULL)
{
if(a2!=NULL)
{
m2=p_Init(currRing);
x2:
for (i = (currRing->N); i; i--)
{
c = p_GetExpDiff(p1, p2,i, currRing);
if (c>0)
{
p_SetExp(m2,i,(c+p_GetExp(a2,i,tailRing)),currRing);
}
else
{
p_SetExp(m2,i,p_GetExp(a2,i,tailRing),currRing);
}
}
if ((c1==c2)||(c2!=0))
{
p_SetComp(m2,p_GetComp(a2,tailRing), currRing);
}
else
{
p_SetComp(m2,c1,currRing);
}
p_Setm(m2, currRing);
if (is_Ring)
{
nDelete(&lc1);
nDelete(&lc2);
nDelete(&t2);
pSetCoeff0(m2, t1);
}
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring && (shift2!=0)) /*a1==NULL*/
{
p_LmDelete(a2, tailRing);
}
#endif
return m2;
}
else
{
if (is_Ring)
{
nDelete(&lc1);
nDelete(&lc2);
nDelete(&t1);
nDelete(&t2);
}
return NULL;
}
}
if (a2==NULL)
{
m1=p_Init(currRing);
x1:
for (i = (currRing->N); i; i--)
{
c = p_GetExpDiff(p2, p1,i,currRing);
if (c>0)
{
p_SetExp(m1,i,(c+p_GetExp(a1,i, tailRing)),currRing);
}
else
{
p_SetExp(m1,i,p_GetExp(a1,i, tailRing), currRing);
}
}
if ((c1==c2)||(c1!=0))
{
p_SetComp(m1,p_GetComp(a1,tailRing),currRing);
}
else
{
p_SetComp(m1,c2,currRing);
}
p_Setm(m1, currRing);
if (is_Ring)
{
pSetCoeff0(m1, t2);
nDelete(&lc1);
nDelete(&lc2);
nDelete(&t1);
}
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring && (shift1!=0)) /*a2==NULL*/
{
p_LmDelete(a1, tailRing);
}
#endif
return m1;
}
m1 = p_Init(currRing);
m2 = p_Init(currRing);
loop
{
for (i = (currRing->N); i; i--)
{
c = p_GetExpDiff(p1, p2,i,currRing);
if (c > 0)
{
p_SetExp(m2,i,(c+p_GetExp(a2,i,tailRing)), currRing);
p_SetExp(m1,i,p_GetExp(a1,i, tailRing), currRing);
}
else
{
p_SetExp(m1,i,(p_GetExp(a1,i,tailRing)-c), currRing);
p_SetExp(m2,i,p_GetExp(a2,i, tailRing), currRing);
}
}
if(c1==c2)
{
p_SetComp(m1,p_GetComp(a1, tailRing), currRing);
p_SetComp(m2,p_GetComp(a2, tailRing), currRing);
}
else
{
if(c1!=0)
{
p_SetComp(m1,p_GetComp(a1, tailRing), currRing);
p_SetComp(m2,c1, currRing);
}
else
{
p_SetComp(m2,p_GetComp(a2, tailRing), currRing);
p_SetComp(m1,c2, currRing);
}
}
p_Setm(m1,currRing);
p_Setm(m2,currRing);
cm = p_LmCmp(m1, m2,currRing);
if (cm!=0)
{
if(cm==1)
{
p_LmFree(m2,currRing);
if (is_Ring)
{
pSetCoeff0(m1, t2);
nDelete(&lc1);
nDelete(&lc2);
nDelete(&t1);
}
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
if (shift1!=0) p_LmDelete(a1, tailRing);
if (shift2!=0) p_LmDelete(a2, tailRing);
}
#endif
return m1;
}
else
{
p_LmFree(m1,currRing);
if (is_Ring)
{
pSetCoeff0(m2, t1);
nDelete(&lc1);
nDelete(&lc2);
nDelete(&t2);
}
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
if (shift1!=0) p_LmDelete(a1, tailRing);
if (shift2!=0) p_LmDelete(a2, tailRing);
}
#endif
return m2;
}
}
if (is_Ring)
{
equal = nEqual(t1,t2);
}
else
{
t1 = nMult(pGetCoeff(a2),pGetCoeff(p1));
t2 = nMult(pGetCoeff(a1),pGetCoeff(p2));
equal = nEqual(t1,t2);
nDelete(&t2);
nDelete(&t1);
}
if (!equal)
{
p_LmFree(m2,currRing);
if (is_Ring)
{
pSetCoeff0(m1, nSub(t1, t2));
nDelete(&lc1);
nDelete(&lc2);
nDelete(&t1);
nDelete(&t2);
}
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
if (shift1!=0) p_LmDelete(a1, tailRing);
if (shift2!=0) p_LmDelete(a2, tailRing);
}
#endif
return m1;
}
pIter(a1);
pIter(a2);
if (is_Ring)
{
if (a2 != NULL)
{
nDelete(&t1);
t1 = nMult(pGetCoeff(a2),lc1);
}
if (a1 != NULL)
{
nDelete(&t2);
t2 = nMult(pGetCoeff(a1),lc2);
}
while ((a1 != NULL) && nIsZero(t2))
{
pIter(a1);
if (a1 != NULL)
{
nDelete(&t2);
t2 = nMult(pGetCoeff(a1),lc2);
}
}
while ((a2 != NULL) && nIsZero(t1))
{
pIter(a2);
if (a2 != NULL)
{
nDelete(&t1);
t1 = nMult(pGetCoeff(a2),lc1);
}
}
}
#ifdef HAVE_SHIFTBBA
if (tailRing->isLPring)
{
a1 = p_LPCopyAndShiftLM(a1, shift1, tailRing);
a2 = p_LPCopyAndShiftLM(a2, shift2, tailRing);
}
#endif
if (a2==NULL)
{
p_LmFree(m2,currRing);
if (a1==NULL)
{
if (is_Ring)
{
nDelete(&lc1);
nDelete(&lc2);
nDelete(&t1);
nDelete(&t2);
}
p_LmFree(m1,currRing);
return NULL;
}
goto x1;
}
if (a1==NULL)
{
p_LmFree(m1,currRing);
goto x2;
}
}
}
si_max
static int si_max(const int a, const int b)
Definition auxiliary.h:125
BOOLEAN
int BOOLEAN
Definition auxiliary.h:88
TRUE
#define TRUE
Definition auxiliary.h:101
FALSE
#define FALSE
Definition auxiliary.h:97
reduce
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
Definition cf_ops.cc:660
i
int i
Definition cfEzgcd.cc:132
equal
bool equal
Definition cfModGcd.cc:4134
bound
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
skStrategy::sigdrop
bool sigdrop
Definition kutil.h:357
skStrategy::tailRing
ring tailRing
Definition kutil.h:342
skStrategy::blockred
int blockred
Definition kutil.h:362
n_IsMOne
static FORCE_INLINE BOOLEAN n_IsMOne(number n, const coeffs r)
TRUE iff 'n' represents the additive inverse of the one element, i.e. -1.
Definition coeffs.h:478
n_InpNeg
static FORCE_INLINE number n_InpNeg(number n, const coeffs r)
in-place negation of n MUST BE USED: n = n_InpNeg(n) (no copy is returned)
Definition coeffs.h:560
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_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:461
n_Write
static FORCE_INLINE void n_Write(number n, const coeffs r, const BOOLEAN bShortOut=TRUE)
Definition coeffs.h:594
n_ExtGcd
static FORCE_INLINE number n_ExtGcd(number a, number b, number *s, number *t, const coeffs r)
beware that ExtGCD is only relevant for a few chosen coeff. domains and may perform something unexpec...
Definition coeffs.h:674
n_Init
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition coeffs.h:541
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
VAR
#define VAR
Definition globaldefs.h:5
k_GetLeadTerms
KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r, poly &m1, poly &m2, const ring m_r)
Definition kInline.h:1018
ksCheckCoeff
int ksCheckCoeff(number *a, number *b, const coeffs r)
Definition kbuckets.cc:1504
ksReducePolyLC
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:477
red_count
VAR int red_count
Definition kspoly.cc:25
ksCreateSpoly
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition kspoly.cc:1203
ksReducePolyTail
int ksReducePolyTail(LObject *PR, TObject *PW, poly Current, poly spNoether)
Definition kspoly.cc:1350
ksReducePolyTailBound
int ksReducePolyTailBound(LObject *PR, TObject *PW, int bound, poly Current, poly spNoether)
Definition kspoly.cc:1390
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
ksReducePolyBound
int ksReducePolyBound(LObject *PR, TObject *PW, int, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:590
ksReducePolySigRing
int ksReducePolySigRing(LObject *PR, TObject *PW, long, poly spNoether, number *coef, kStrategy strat)
Definition kspoly.cc:943
ksCreateShortSpoly
poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing)
Definition kspoly.cc:1446
create_count
VAR int create_count
Definition kspoly.cc:26
kStratChangeTailRing
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition kutil.cc:10939
kTest_L
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp, int lpos, TSet T, int tlength)
Definition kutil.cc:916
kTest_T
BOOLEAN kTest_T(TObject *T, kStrategy strat, int i, char TN)
Definition kutil.cc:789
kutil.h
ksReducePolyGCD
int ksReducePolyGCD(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
TObject
class sTObject TObject
Definition kutil.h:58
ksReducePolyZ
int ksReducePolyZ(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
LObject
class sLObject LObject
Definition kutil.h:59
nc.h
nc_kBucketPolyRed_Z
static void nc_kBucketPolyRed_Z(kBucket_pt b, poly p, number *c, BOOLEAN reduce)
Definition nc.h:284
nc_PolyPolyRed
void nc_PolyPolyRed(poly &b, poly p, number *c, const ring r)
Definition old.gring.cc:2238
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
pAssume1
#define pAssume1(cond)
Definition monomials.h:171
pSetCoeff0
#define pSetCoeff0(p, n)
Definition monomials.h:59
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
numbers.h
nDiv
#define nDiv(a, b)
Definition numbers.h:32
nDelete
#define nDelete(n)
Definition numbers.h:16
nIsZero
#define nIsZero(n)
Definition numbers.h:19
nEqual
#define nEqual(n1, n2)
Definition numbers.h:20
nSub
#define nSub(n1, n2)
Definition numbers.h:22
nMult
#define nMult(n1, n2)
Definition numbers.h:17
NULL
#define NULL
Definition omList.c:12
options.h
TEST_OPT_DEBUG
#define TEST_OPT_DEBUG
Definition options.h:110
p_Procs.h
p_polys.h
pLength
static int pLength(poly a)
Definition p_polys.h:190
p_GetExpDiff
static long p_GetExpDiff(poly p1, poly p2, int i, ring r)
Definition p_polys.h:637
p_LmDelete
static void p_LmDelete(poly p, const ring r)
Definition p_polys.h:725
pIsMonomOf
BOOLEAN pIsMonomOf(poly p, poly m)
Definition pDebug.cc:164
p_ExpVectorAdd
static void p_ExpVectorAdd(poly p1, poly p2, const ring r)
Definition p_polys.h:1432
p_SetCompP
static void p_SetCompP(poly p, int i, ring r)
Definition p_polys.h:256
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_LmCmp
static int p_LmCmp(poly p, poly q, const ring r)
Definition p_polys.h:1601
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_DivisibleBy
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition p_polys.h:1921
p_MaxComp
static long p_MaxComp(poly p, ring lmRing, ring tailRing)
Definition p_polys.h:294
p_Delete
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:903
p_CheckPolyRing
BOOLEAN p_CheckPolyRing(poly p, ring r)
Definition pDebug.cc:115
p_LmFree
static void p_LmFree(poly p, ring)
Definition p_polys.h:685
p_Init
static poly p_Init(const ring r, omBin bin)
Definition p_polys.h:1341
pHaveCommonMonoms
BOOLEAN pHaveCommonMonoms(poly p, poly q)
Definition pDebug.cc:174
p_LmExpVectorAddIsOk
static BOOLEAN p_LmExpVectorAddIsOk(const poly p1, const poly p2, const ring r)
Definition p_polys.h:2020
p_Test
#define p_Test(p, r)
Definition p_polys.h:161
p_ExpVectorAddSub
static void p_ExpVectorAddSub(poly p1, poly p2, poly p3, const ring r)
Definition p_polys.h:1477
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
pSetCoeff
#define pSetCoeff(p, n)
deletes old coeff before setting the new one
Definition polys.h:32
pSub
#define pSub(a, b)
Definition polys.h:288
pWrite
void pWrite(poly p)
Definition polys.h:309
pCopy
#define pCopy(p)
return a copy of the poly
Definition polys.h:186
pOne
#define pOne()
Definition polys.h:316
StringSetS
void StringSetS(const char *st)
Definition reporter.cc:128
StringAppendS
void StringAppendS(const char *st)
Definition reporter.cc:107
PrintS
void PrintS(const char *s)
Definition reporter.cc:288
StringEndS
char * StringEndS()
Definition reporter.cc:151
rIsPluralRing
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:406
rField_is_Domain
static BOOLEAN rField_is_Domain(const ring r)
Definition ring.h:493
rField_is_Ring
#define rField_is_Ring(R)
Definition ring.h:491
p_LPCopyAndShiftLM
poly p_LPCopyAndShiftLM(poly p, int sh, const ring r)
Definition shiftgb.cc:35
p_mFirstVblock
int p_mFirstVblock(poly p, const ring ri)
Definition shiftop.cc:478
p_FirstVblock
int p_FirstVblock(poly p, const ring r)
Definition shiftop.cc:456
k_SplitFrame
void k_SplitFrame(poly &m1, poly &m2, int at, const ring r)
Definition shiftop.cc:600
shiftop.h
R
#define R
Definition sirandom.c:27
kStrategy
skStrategy * kStrategy
Definition structs.h:54
loop
#define loop
Definition structs.h:71