Loading...
Searching...
No Matches
sca.cc
Go to the documentation of this file.
#define PLURAL_INTERNAL_DECLARATIONS
#include "kernel/mod2.h"
#include "misc/options.h"
#include "polys/simpleideals.h"
#include "polys/prCopy.h"
#include "polys/nc/sca.h"
#include "polys/nc/gb_hack.h"
#include "kernel/polys.h"
#include "kernel/ideals.h"
#include "kernel/GBEngine/kstd1.h"
#include "kernel/GBEngine/kutil.h"
#include "kernel/GBEngine/nc.h"
/// nc_gr_initBba is needed for sca_gr_bba and gr_bba.
void nc_gr_initBba(ideal F, kStrategy strat); // from gr_kstd2.cc!
void addLObject(LObject& h, kStrategy& strat)
{
if(h.IsNull()) return;
strat->initEcart(&h);
h.sev=0; // pGetShortExpVector(h.p);
// add h into S and L
int pos=posInS(strat, strat->sl, h.p, h.ecart);
if ( (pos <= strat->sl) && (p_ComparePolys(h.p, strat->S[pos], currRing)) )
{
if (TEST_OPT_PROT)
PrintS("d\n");
}
else
{
if (TEST_OPT_INTSTRATEGY)
{
p_Cleardenom(h.p, currRing);
}
else
{
pNorm(h.p);
}
if ((strat->syzComp==0)||(!strat->homog))
{
h.p = redtailBba(h.p,pos-1,strat);
if (TEST_OPT_INTSTRATEGY)
{
p_Cleardenom(h.p,currRing);
}
else
{
pNorm(h.p);
}
}
if(h.IsNull()) return;
// statistic
if (TEST_OPT_PROT)
{
PrintS("s\n");
}
#ifdef KDEBUG
if (TEST_OPT_DEBUG)
{
PrintS("new s:");
wrp(h.p);
PrintLn();
}
#endif
enterpairs(h.p, strat->sl, h.ecart, 0, strat);
pos=0;
if (strat->sl!=-1) pos = posInS(strat, strat->sl, h.p, h.ecart);
strat->enterS(&h, pos, strat, -1);
// enterT(&h, strat); // ?!
kDeleteLcm(&h);
}
}
ideal k_sca_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);
assume( currRing == _currRing );
#if MYTEST
PrintS("<sca_gr_bba>\n");
#endif
assume(rIsSCA(currRing));
#ifndef SING_NDEBUG
idTest(F);
idTest(Q);
#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
const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
ideal tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
ideal tempQ = Q;
if(Q == currRing->qideal)
tempQ = SCAQuotient(currRing);
strat->z2homog = id_IsSCAHomogeneous(tempF, NULL, NULL, currRing); // wCx == wCy == NULL!
// redo: no_prod_crit
const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
strat->no_prod_crit = ! bIsSCA;
// strat->homog = strat->homog && strat->z2homog; // ?
#if MYTEST
{
PrintS("ideal tempF: \n");
idPrint(tempF);
PrintS("ideal tempQ: \n");
idPrint(tempQ);
}
#endif
int olddeg, reduc;
int red_result = 1;
// int hilbeledeg = 1, minimcnt = 0;
int hilbcount = 0;
initBuchMoraCrit(strat); // set Gebauer, honey, sugarCrit
nc_gr_initBba(tempF,strat); // set enterS, red, initEcart, initEcartPair
initBuchMoraPos(strat);
// ?? set spSpolyShort, reduce ???
initBuchMora(tempF, tempQ, strat); // SCAQuotient(currRing) instead of Q == squares!!!!!!!
strat->posInT=posInT110; // !!!
reduc = olddeg = 0;
// compute-------------------------------------------------------
for(; strat->Ll >= 0;
#ifdef KDEBUG
strat->P.lcm = NULL,
#endif
kTest(strat)
)
{
#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) 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);
// assume(pNext(strat->P.p) != strat->tail); // !???
if(strat->P.IsNull()) continue;
if( pNext(strat->P.p) == strat->tail )
{
// deletes the int spoly and computes SPoly
pLmFree(strat->P.p); // ???
strat->P.p = nc_CreateSpoly(strat->P.p1, strat->P.p2, currRing);
}
if(strat->P.IsNull()) continue;
// poly save = NULL;
//
// if(pNext(strat->P.p) != NULL)
// save = p_Copy(strat->P.p, currRing);
strat->initEcart(&strat->P); // remove it?
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 wrt S
strat->red(&strat->P,strat);
if(strat->P.IsNull()) continue;
addLObject(strat->P, strat);
const poly save = strat->P.p;
#ifdef PDEBUG
p_Test(save, currRing);
#endif
assume( save != NULL );
// SCA Specials:
{
const poly p_next = pNext(save);
if( p_next != NULL )
for( unsigned int i = m_iFirstAltVar; i <= m_iLastAltVar; i++ )
if( p_GetExp(save, i, currRing) != 0 )
{
assume(p_GetExp(save, i, currRing) == 1);
const poly tt = sca_pp_Mult_xi_pp(i, p_next, currRing);
#ifdef PDEBUG
p_Test(tt, currRing);
#endif
if( tt == NULL) continue;
LObject h(tt); // h = x_i * P
if (TEST_OPT_INTSTRATEGY)
{
h.pCleardenom(); // also removes Content
}
else
{
h.pNorm();
}
strat->initEcart(&h);
// if (pOrdSgn==-1)
// {
// cancelunit(&h); // tries to cancel a unit
// deleteHC(&h, strat);
// }
// if(h.IsNull()) continue;
// if (TEST_OPT_PROT)
// message((strat->honey ? h.ecart : 0) + h.pFDeg(), &olddeg, &reduc, strat, red_result);
// strat->red(&h, strat); // wrt S
// if(h.IsNull()) continue;
// poly save = p_Copy(h.p, currRing);
int pos;
if (strat->Ll==-1)
pos =0;
else
pos = strat->posInL(strat->L,strat->Ll,&h,strat);
h.sev = pGetShortExpVector(h.p);
enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
// h.p = save;
// addLObject(h, strat);
}
// p_Delete( &save, currRing );
}
} // for(;;)
#ifdef KDEBUG
if (TEST_OPT_DEBUG) messageSets(strat);
#endif
if (TEST_OPT_REDSB){
completeReduce(strat); // ???
}
// release temp data--------------------------------
exitBuchMora(strat);
// if (TEST_OPT_WEIGHTM)
// {
// pRestoreDegProcs(currRing,pFDegOld, pLDegOld);
// if (ecartWeights)
// {
// omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(int));
// ecartWeights=NULL;
// }
// }
if (TEST_OPT_PROT) messageStat(hilbcount,strat);
if (tempQ!=NULL) updateResult(strat->Shdl,tempQ,strat);
id_Delete(&tempF, currRing);
// complete reduction of the standard basis---------
if (TEST_OPT_REDSB){
ideal I = strat->Shdl;
ideal erg = kInterRedOld(I,tempQ);
assume(I!=erg);
id_Delete(&I, currRing);
strat->Shdl = erg;
}
#if MYTEST
// PrintS("</sca_gr_bba>\n");
#endif
if( currRing != save ) rChangeCurrRing(save);
return (strat->Shdl);
}
///////////////////////////////////////////////////////////////////////////////////////
//************* SCA BBA *************************************************************//
///////////////////////////////////////////////////////////////////////////////////////
// Under development!!!
ideal k_sca_bba (const ideal F, const ideal Q, const intvec */*w*/, const bigintmat * /*hilb*/, kStrategy strat, const ring _currRing)
{
const ring save = currRing;
if( currRing != _currRing ) rChangeCurrRing(_currRing);
assume( currRing == _currRing );
#if MYTEST
PrintS("\n\n<sca_bba>\n\n");
#endif
assume(rIsSCA(currRing));
#ifndef SING_NDEBUG
idTest(F);
idTest(Q);
#endif
#if MYTEST
PrintS("\ncurrRing: \n");
rWrite(currRing);
#ifdef RDEBUG
// rDebugPrint(currRing);
#endif
PrintS("\n\nF: \n");
idPrint(F);
PrintS("\n\nQ: \n");
idPrint(Q);
PrintLn();
#endif
const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
ideal tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
ideal tempQ = Q;
if(Q == currRing->qideal)
tempQ = SCAQuotient(currRing);
// Q or tempQ will not be used below :(((
#if MYTEST
PrintS("tempF: \n");
idPrint(tempF);
PrintS("tempQ: \n");
idPrint(tempQ);
#endif
strat->z2homog = id_IsSCAHomogeneous(tempF, NULL, NULL, currRing); // wCx == wCy == NULL!
// redo no_prod_crit:
const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
strat->no_prod_crit = ! bIsSCA;
// strat->homog = strat->homog && strat->z2homog; // ?
int red_result = 1;
int olddeg, reduc;
// int hilbeledeg = 1, minimcnt = 0;
int hilbcount = 0;
BOOLEAN withT = FALSE;
initBuchMoraCrit(strat); // sets Gebauer, honey, sugarCrit // sca - ok???
initBuchMoraPos(strat); // sets strat->posInL, strat->posInT // check!! (Plural's: )
// initHilbCrit(F, Q, &hilb, strat);
// nc_gr_initBba(F,strat);
initBba(strat); // set enterS, red, initEcart, initEcartPair
// set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair
// ?? set spSpolyShort, reduce ???
initBuchMora(tempF, tempQ, strat); // tempQ = Q without squares!!!
// if (strat->minim>0) strat->M = idInit(IDELEMS(F),F->rank);
reduc = olddeg = 0;
#define NO_BUCKETS
#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);
#undef HAVE_TAIL_RING
#ifdef HAVE_TAIL_RING
if(!idIs0(F) &&(!rField_is_Ring())) // create strong gcd poly computes with tailring and S[i] ->to be fixed
kStratInitChangeTailRing(strat);
#endif
///////////////////////////////////////////////////////////////
// SCA:
// due to std( SB, p).
// Note that after initBuchMora :: initSSpecial all these additional
// elements are in S and T (and some pairs are in L, which also has no initial
// elements!!!)
if(TEST_OPT_SB_1)
{
// For all additional elements...
for (int iNewElement = strat->newIdeal; iNewElement < IDELEMS(tempF); iNewElement++)
{
const poly pSave = tempF->m[iNewElement];
if( pSave != NULL )
{
// tempF->m[iNewElement] = NULL;
const poly p_next = pNext(pSave);
if(p_next != NULL)
for( unsigned int i = m_iFirstAltVar; i <= m_iLastAltVar; i++ )
if( p_GetExp(pSave, i, currRing) != 0 )
{
assume(p_GetExp(pSave, i, currRing) == 1);
const poly p_new = sca_pp_Mult_xi_pp(i, p_next, currRing);
#ifdef PDEBUG
p_Test(p_new, currRing);
#endif
if( p_new == NULL) continue;
LObject h(p_new); // h = x_i * strat->P
h.is_special = TRUE;
if (TEST_OPT_INTSTRATEGY)
h.pCleardenom(); // also removes Content
else
h.pNorm();
strat->initEcart(&h);
h.sev = pGetShortExpVector(h.p);
int pos = 0;
if (strat->Ll != -1)
pos = strat->posInL(strat->L,strat->Ll,&h,strat);
enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
}
}
}
}
// compute-------------------------------------------------------
while (strat->Ll >= 0)
{
#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))))
{
#ifdef KDEBUG
// if (TEST_OPT_DEBUG){PrintS("^^^^?");}
#endif
// *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->homog==isHomog) || strat->L[strat->Ll].is_special || ((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)))
)
{
#ifdef KDEBUG
// if (TEST_OPT_DEBUG){PrintS("^^^^^^^^^^^^!!!!");}
#endif
deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
// if (TEST_OPT_PROT) PrintS("^!");
}
if (strat->Ll<0) break;
else strat->noClearS=TRUE;
}
// picks the last element from the lazyset L
strat->P = strat->L[strat->Ll];
strat->Ll--;
// assume(pNext(strat->P.p) != strat->tail);
if(strat->P.IsNull()) continue;
if (pNext(strat->P.p) == strat->tail)
{
// deletes the short spoly
pLmFree(strat->P.p);
strat->P.p = nc_CreateSpoly(strat->P.p1, strat->P.p2, currRing);
if (strat->P.p!=NULL) strat->initEcart(&strat->P);
}// else
if(strat->P.IsNull()) continue;
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 (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);
// reduction to non-zero new poly
if (red_result == 1)
{
// statistic
if (TEST_OPT_PROT) PrintS("s");
// get the polynomial (canonicalize bucket, make sure P.p is set)
strat->P.GetP(strat->lmBin);
int pos = posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
// reduce the tail and normalize poly
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);
}
strat->P.is_normalized=nIsOne(pGetCoeff(strat->P.p));
#ifdef KDEBUG
if (TEST_OPT_DEBUG){PrintS(" ns:");p_wrp(strat->P.p,currRing);PrintLn();}
#endif
// // 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(withT)
{
strat->P.SetpFDeg();
enterT(&strat->P, strat);
}
// L
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 (hilb!=NULL) khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
// Print("[%d]",hilbeledeg);
kDeleteLcm(&strat->P);
// //////////////////////////////////////////////////////////
// SCA:
const poly pSave = strat->P.p;
const poly p_next = pNext(pSave);
// if(0)
if( p_next != NULL )
for( unsigned int i = m_iFirstAltVar; i <= m_iLastAltVar; i++ )
if( p_GetExp(pSave, i, currRing) != 0 )
{
assume(p_GetExp(pSave, i, currRing) == 1);
const poly p_new = sca_pp_Mult_xi_pp(i, p_next, currRing);
#ifdef PDEBUG
p_Test(p_new, currRing);
#endif
if( p_new == NULL) continue;
LObject h(p_new); // h = x_i * strat->P
h.is_special = TRUE;
if (TEST_OPT_INTSTRATEGY)
{
h.pCleardenom(); // also removes Content
}
else
{
h.pNorm();
}
strat->initEcart(&h);
h.sev = pGetShortExpVector(h.p);
int pos = 0;
if (strat->Ll != -1)
pos = strat->posInL(strat->L,strat->Ll,&h,strat);
enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
#if 0
h.sev = pGetShortExpVector(h.p);
strat->initEcart(&h);
h.PrepareRed(strat->use_buckets);
// reduction of the element chosen from L(?)
red_result = strat->red(&h,strat);
// reduction to non-zero new poly
if (red_result != 1) continue;
int pos = posInS(strat,strat->sl,h.p,h.ecart);
// reduce the tail and normalize poly
if (TEST_OPT_INTSTRATEGY)
{
h.pCleardenom();
if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
{
h.p = redtailBba(&(h),pos-1,strat, withT); // !!!
h.pCleardenom();
}
}
else
{
h.pNorm();
if ((TEST_OPT_REDSB)||(TEST_OPT_REDTAIL))
h.p = redtailBba(&(h),pos-1,strat, withT);
}
#ifdef KDEBUG
if (TEST_OPT_DEBUG){PrintS(" N:");h.wrp();PrintLn();}
#endif
// h.PrepareRed(strat->use_buckets); // ???
h.sev = pGetShortExpVector(h.p);
strat->initEcart(&h);
if (strat->Ll==-1)
pos = 0;
else
pos = strat->posInL(strat->L,strat->Ll,&h,strat);
enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
// the end of "#if 0" (comment)
#endif
} // for all x_i \in Ann(lm(P))
} // if red(P) != NULL
// else if (strat->P.p1 == NULL && strat->minim > 0)
// {
// p_Delete(&strat->P.p2, currRing, strat->tailRing);
// }
#ifdef KDEBUG
// memset(&(strat->P), 0, sizeof(strat->P));
#endif
kTest_TS(strat); // even of T is not used!
// Print("\n$\n");
}
#ifdef KDEBUG
if (TEST_OPT_DEBUG) messageSets(strat);
#endif
// complete reduction of the standard basis---------
if (TEST_OPT_REDSB)
{
completeReduce(strat);
}
//release temp data--------------------------------
exitBuchMora(strat); // cleanT!
id_Delete(&tempF, currRing);
// if (TEST_OPT_WEIGHTM)
// {
// pRestoreDegProcs(currRing, pFDegOld, pLDegOld);
// if (ecartWeights)
// {
// omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(short));
// ecartWeights=NULL;
// }
// }
if (TEST_OPT_PROT) messageStat(hilbcount,strat);
if (tempQ!=NULL) updateResult(strat->Shdl,tempQ,strat);
if (TEST_OPT_REDSB) // ???
{
// must be at the very end (after exitBuchMora) as it changes the S set!!!
ideal I = strat->Shdl;
ideal erg = kInterRedOld(I,tempQ);
assume(I!=erg);
id_Delete(&I, currRing);
strat->Shdl = erg;
}
#if MYTEST
PrintS("\n\n</sca_bba>\n\n");
#endif
if( currRing != save ) rChangeCurrRing(save);
return (strat->Shdl);
}
// //////////////////////////////////////////////////////////////////////////////
// sca mora...
// returns TRUE if mora should use buckets, false otherwise
#ifdef MORA_USE_BUCKETS
static BOOLEAN kMoraUseBucket(kStrategy strat)
#else
static BOOLEAN kMoraUseBucket(kStrategy)
#endif
{
#ifdef MORA_USE_BUCKETS
if (TEST_OPT_NOT_BUCKETS)
return FALSE;
if (strat->red == redFirst)
{
#ifdef NO_LDEG
if (!strat->syzComp)
return TRUE;
#else
if ((strat->homog || strat->honey) && !strat->syzComp)
return TRUE;
#endif
}
else
{
assume(strat->red == redEcart);
if (strat->honey && !strat->syzComp)
return TRUE;
}
#endif
return FALSE;
}
// ideal sca_mora (ideal F, ideal Q, intvec *w, intvec *, kStrategy strat)
ideal k_sca_mora(const ideal F, const ideal Q, const intvec */*w*/, const bigintmat *, kStrategy strat, const ring _currRing)
{
const ring save = currRing;
if( currRing != _currRing ) rChangeCurrRing(_currRing);
assume( currRing == _currRing );
assume(rIsSCA(currRing));
const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
ideal tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
ideal tempQ = Q;
if(Q == currRing->qideal)
tempQ = SCAQuotient(currRing);
bool bIdHomog = id_IsSCAHomogeneous(tempF, NULL, NULL, currRing); // wCx == wCy == NULL!
assume( !bIdHomog || strat->homog ); // bIdHomog =====[implies]>>>>> strat->homog
strat->homog = strat->homog && bIdHomog;
#ifdef PDEBUG
assume( strat->homog == bIdHomog );
#endif
strat->update = TRUE;
//- setting global variables ------------------- -
initBuchMoraCrit(strat);
// initHilbCrit(F,NULL,&hilb,strat); // no Q!
initMora(tempF, strat);
initBuchMoraPos(strat);
//Shdl=
initBuchMora(tempF, tempQ, strat); // temp Q, F!
// updateS in initBuchMora has Hecketest
// * and could have put strat->kHEdgdeFound FALSE
strat->use_buckets = kMoraUseBucket(strat);
kTest_TS(strat);
int olddeg = 0;
int reduc = 0;
int red_result = 1;
// int hilbeledeg=1;
int hilbcount=0;
//- compute-------------------------------------------
#undef HAVE_TAIL_RING
#ifdef HAVE_TAIL_RING
// if (strat->homog && strat->red == redFirst)
// kStratInitChangeTailRing(strat);
#endif
// due to std( SB, p)
if(TEST_OPT_SB_1)
{
for (int iNewElement = strat->newIdeal; iNewElement < IDELEMS(tempF); iNewElement++)
{
const poly pSave = tempF->m[iNewElement];
if( pSave != NULL )
{
// tempF->m[iNewElement] = NULL;
const poly p_next = pNext(pSave);
if(p_next != NULL)
for( unsigned int i = m_iFirstAltVar; i <= m_iLastAltVar; i++ )
if( p_GetExp(pSave, i, currRing) != 0 )
{
assume(p_GetExp(pSave, i, currRing) == 1);
const poly p_new = sca_pp_Mult_xi_pp(i, p_next, currRing);
#ifdef PDEBUG
p_Test(p_new, currRing);
#endif
if( p_new == NULL) continue;
LObject h(p_new); // h = x_i * strat->P
if (TEST_OPT_INTSTRATEGY)
h.pCleardenom(); // also removes Content
else
h.pNorm();
strat->initEcart(&h);
h.sev = pGetShortExpVector(h.p);
int pos = 0;
if (strat->Ll != -1)
pos = strat->posInL(strat->L,strat->Ll,&h,strat);
enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
}
}
}
}
while (strat->Ll >= 0)
{
//test_int_std(strat->kIdeal);
#ifdef KDEBUG
if (TEST_OPT_DEBUG) messageSets(strat);
#endif
if (TEST_OPT_DEGBOUND
&& (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
{
// * stops computation if
// * - 24 (degBound)
// * && upper degree is bigger than Kstd1_deg
while ((strat->Ll >= 0)
&& (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
&& (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
)
{
deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
//if (TEST_OPT_PROT)
//{
// PrintS("D"); mflush();
//}
}
if (strat->Ll<0) break;
else strat->noClearS=TRUE;
}
strat->P = strat->L[strat->Ll];// - picks the last element from the lazyset L -
if (strat->Ll==0) strat->interpt=TRUE;
strat->Ll--;
// create the real Spoly
// assume(pNext(strat->P.p) != strat->tail);
if(strat->P.IsNull()) continue;
if( pNext(strat->P.p) == strat->tail )
{
// deletes the int spoly and computes SPoly
pLmFree(strat->P.p); // ???
strat->P.p = nc_CreateSpoly(strat->P.p1, strat->P.p2, currRing);
}
if (strat->P.p1 == NULL)
{
// for input polys, prepare reduction (buckets !)
strat->P.SetLength(strat->length_pLength);
strat->P.PrepareRed(strat->use_buckets);
}
if (!strat->P.IsNull())
{
// might be NULL from noether !!!
if (TEST_OPT_PROT)
message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
// reduce
red_result = strat->red(&strat->P,strat);
}
if (! strat->P.IsNull())
{
strat->P.GetP();
// statistics
if (TEST_OPT_PROT) PrintS("s");
// normalization
if (!TEST_OPT_INTSTRATEGY)
strat->P.pNorm();
// tailreduction
strat->P.p = redtail(&(strat->P),strat->sl,strat);
// set ecart -- might have changed because of tail reductions
if ((!strat->noTailReduction) && (!strat->honey))
strat->initEcart(&strat->P);
// cancel unit
cancelunit(&strat->P);
// for char 0, clear denominators
if (TEST_OPT_INTSTRATEGY)
strat->P.pCleardenom();
// put in T
enterT(&strat->P,strat);
// build new pairs
enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
// put in S
strat->enterS(&strat->P,
posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
strat, strat->tl);
// clear strat->P
kDeleteLcm(&strat->P);
// //////////////////////////////////////////////////////////
// SCA:
const poly pSave = strat->P.p;
const poly p_next = pNext(pSave);
if(p_next != NULL)
for( unsigned int i = m_iFirstAltVar; i <= m_iLastAltVar; i++ )
if( p_GetExp(pSave, i, currRing) != 0 )
{
assume(p_GetExp(pSave, i, currRing) == 1);
const poly p_new = sca_pp_Mult_xi_pp(i, p_next, currRing);
#ifdef PDEBUG
p_Test(p_new, currRing);
#endif
if( p_new == NULL) continue;
LObject h(p_new); // h = x_i * strat->P
if (TEST_OPT_INTSTRATEGY)
h.pCleardenom(); // also removes Content
else
h.pNorm();
strat->initEcart(&h);
h.sev = pGetShortExpVector(h.p);
int pos = 0;
if (strat->Ll != -1)
pos = strat->posInL(strat->L,strat->Ll,&h,strat);
enterL(&strat->L,&strat->Ll,&strat->Lmax,h,pos);
}
#ifdef KDEBUG
// make sure kTest_TS does not complain about strat->P
strat->P.Init();
#endif
}
#if 0
if (strat->kHEdgeFound)
{
if ((TEST_OPT_FINDET)
|| ((TEST_OPT_MULTBOUND) && (scMult0Int((strat->Shdl)) < mu)))
{
// obachman: is this still used ???
// * stops computation if strat->kHEdgeFound and
// * - 27 (finiteDeterminacyTest)
// * or
// * - 23
// * (multBound)
// * && multiplicity of the ideal is smaller then a predefined number mu
while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
}
}
#endif
kTest_TS(strat);
}
// - complete reduction of the standard basis------------------------ -
if (TEST_OPT_REDSB) completeReduce(strat);
// - release temp data------------------------------- -
exitBuchMora(strat);
// - polynomials used for HECKE: HC, noether -
if (TEST_OPT_FINDET)
{
if (strat->kNoether!=NULL)
Kstd1_mu=currRing->pFDeg(strat->kNoether,currRing);
else
Kstd1_mu=-1;
}
if(strat->kNoether!=NULL) pLmFree(&strat->kNoether);
strat->update = TRUE; //???
strat->lastAxis = 0; //???
omFreeSize((ADDRESS)strat->NotUsedAxis,(rVar(currRing)+1)*sizeof(BOOLEAN));
if (TEST_OPT_PROT) messageStat(hilbcount,strat);
// if (TEST_OPT_WEIGHTM)
// {
// pRestoreDegProcs(currRing, pFDegOld, pLDegOld);
// if (ecartWeights)
// {
// omFreeSize((ADDRESS)ecartWeights,(rVar(currRing)+1)*sizeof(short));
// ecartWeights=NULL;
// }
// }
if (tempQ!=NULL) updateResult(strat->Shdl,tempQ,strat);
idTest(strat->Shdl);
id_Delete( &tempF, currRing);
if( currRing != save ) rChangeCurrRing(save);
return (strat->Shdl);
}
BOOLEAN
int BOOLEAN
Definition auxiliary.h:88
TRUE
#define TRUE
Definition auxiliary.h:101
FALSE
#define FALSE
Definition auxiliary.h:97
ADDRESS
void * ADDRESS
Definition auxiliary.h:120
i
int i
Definition cfEzgcd.cc:132
bigintmat
Matrices of numbers.
Definition bigintmat.h:51
intvec
Definition intvec.h:24
skStrategy::syzComp
int syzComp
Definition kutil.h:353
skStrategy::noTailReduction
char noTailReduction
Definition kutil.h:375
skStrategy::Ll
int Ll
Definition kutil.h:350
skStrategy::lmBin
omBin lmBin
Definition kutil.h:343
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::NotUsedAxis
BOOLEAN * NotUsedAxis
Definition kutil.h:331
skStrategy::lastAxis
int lastAxis
Definition kutil.h:354
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::enterS
void(* enterS)(LObject *h, int pos, kStrategy strat, int atR)
Definition kutil.h:285
skStrategy::use_buckets
char use_buckets
Definition kutil.h:380
skStrategy::interpt
char interpt
Definition kutil.h:368
skStrategy::newIdeal
int newIdeal
Definition kutil.h:355
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::z2homog
char z2homog
Definition kutil.h:371
skStrategy::no_prod_crit
char no_prod_crit
Definition kutil.h:391
skStrategy::L
LSet L
Definition kutil.h:326
skStrategy::length_pLength
char length_pLength
Definition kutil.h:384
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::homog
char homog
Definition kutil.h:369
skStrategy::update
char update
Definition kutil.h:378
p_new
static std::vector< std::vector< int > > p_new(ideal Xo, ideal Sigma)
Definition cohomo.cc:3303
gb_hack.h
scMult0Int
long scMult0Int(ideal S, ideal Q)
Definition hdegree.cc:924
ideals.h
idIs0
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
Definition simpleideals.cc:960
idPrint
#define idPrint(id)
Definition ideals.h:46
idTest
#define idTest(id)
Definition ideals.h:47
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
nc.h
kMoraUseBucket
static BOOLEAN kMoraUseBucket(kStrategy)
Definition sca.cc:851
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
k_sca_bba
ideal k_sca_bba(const ideal F, const ideal Q, const intvec *, const bigintmat *, kStrategy strat, const ring _currRing)
Modified modern Sinuglar Buchberger's algorithm.
Definition sca.cc:368
addLObject
void addLObject(LObject &h, kStrategy &strat)
Definition sca.cc:23
k_sca_gr_bba
ideal k_sca_gr_bba(const ideal F, const ideal Q, const intvec *, const bigintmat *, kStrategy strat, const ring _currRing)
Modified Plural's Buchberger's algorithmus.
Definition sca.cc:95
k_sca_mora
ideal k_sca_mora(const ideal F, const ideal Q, const intvec *, const bigintmat *, kStrategy strat, const ring _currRing)
Modified modern Sinuglar Mora's algorithm.
Definition sca.cc:878
initMora
void initMora(ideal F, kStrategy strat)
Definition kstd1.cc:1820
redFirst
int redFirst(LObject *h, kStrategy strat)
Definition kstd1.cc:794
redEcart
int redEcart(LObject *h, kStrategy strat)
Definition kstd1.cc:168
initBba
void initBba(kStrategy strat)
Definition kstd1.cc:1690
kInterRedOld
ideal kInterRedOld(ideal F, const ideal Q)
Definition kstd1.cc:3456
kstd1.h
Kstd1_deg
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:70
Kstd1_mu
EXTERN_VAR int Kstd1_mu
Definition kstd1.h:70
redtail
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition kutil.cc:6836
initBuchMora
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9749
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
kTest_TS
BOOLEAN kTest_TS(kStrategy strat)
Definition kutil.cc:1067
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
initBuchMoraPos
void initBuchMoraPos(kStrategy strat)
Definition kutil.cc:9580
exitBuchMora
void exitBuchMora(kStrategy strat)
Definition kutil.cc:9837
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
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
messageSets
void messageSets(kStrategy strat)
Definition kutil.cc:7536
messageStat
void messageStat(int hilbcount, kStrategy strat)
Definition kutil.cc:7504
cancelunit
void cancelunit(LObject *L, BOOLEAN inNF)
Definition kutil.cc:365
kutil.h
kDeleteLcm
static void kDeleteLcm(LObject *P)
Definition kutil.h:876
LObject
class sLObject LObject
Definition kutil.h:59
rIsSCA
static bool rIsSCA(const ring r)
Definition nc.h:190
nc_CreateSpoly
static poly nc_CreateSpoly(const poly p1, const poly p2, const ring r)
Definition nc.h:241
id_KillSquares
ideal id_KillSquares(const ideal id, const short iFirstAltVar, const short iLastAltVar, const ring r, const bool bSkipZeroes)
Definition sca.cc:1518
sca_pp_Mult_xi_pp
poly sca_pp_Mult_xi_pp(short i, const poly pPoly, const ring rRing)
Definition sca.cc:1201
mu
static matrix mu(matrix A, const ring R)
Definition matpol.cc:2028
mod2.h
assume
#define assume(x)
Definition mod2.h:389
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
nIsOne
#define nIsOne(n)
Definition numbers.h:25
omFreeSize
#define omFreeSize(addr, size)
Definition omAllocDecl.h:260
NULL
#define NULL
Definition omList.c:12
options.h
TEST_OPT_INTSTRATEGY
#define TEST_OPT_INTSTRATEGY
Definition options.h:112
TEST_OPT_REDTAIL
#define TEST_OPT_REDTAIL
Definition options.h:118
TEST_OPT_FINDET
#define TEST_OPT_FINDET
Definition options.h:113
TEST_OPT_OLDSTD
#define TEST_OPT_OLDSTD
Definition options.h:125
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_MULTBOUND
#define TEST_OPT_MULTBOUND
Definition options.h:116
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition options.h:105
TEST_OPT_DEBUG
#define TEST_OPT_DEBUG
Definition options.h:110
TEST_OPT_NOT_BUCKETS
#define TEST_OPT_NOT_BUCKETS
Definition options.h:107
p_ComparePolys
BOOLEAN p_ComparePolys(poly p1, poly p2, const ring r)
returns TRUE if p1 is a skalar multiple of p2 assume p1 != NULL and p2 != NULL
Definition p_polys.cc:4730
p_Cleardenom
poly p_Cleardenom(poly p, const ring r)
Definition p_polys.cc:2893
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_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).
pNorm
void pNorm(poly p)
Definition polys.h:363
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
prCopy.h
PrintS
void PrintS(const char *s)
Definition reporter.cc:288
PrintLn
void PrintLn()
Definition reporter.cc:314
rWrite
void rWrite(ring r, BOOLEAN details)
Definition ring.cc:227
rDebugPrint
void rDebugPrint(const ring r)
Definition ring.cc:4214
rVar
static short rVar(const ring r)
define rVar(r) (r->N)
Definition ring.h:598
rField_is_Ring
#define rField_is_Ring(R)
Definition ring.h:491
sca.h
SCAQuotient
ideal SCAQuotient(const ring r)
Definition sca.h:10
scaLastAltVar
static short scaLastAltVar(ring r)
Definition sca.h:25
scaFirstAltVar
static short scaFirstAltVar(ring r)
Definition sca.h:18
id_IsSCAHomogeneous
static bool id_IsSCAHomogeneous(const ideal id, const intvec *wCx, const intvec *wCy, const ring r)
Definition sca.h:115
id_Delete
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
Definition simpleideals.cc:123
simpleideals.h
IDELEMS
#define IDELEMS(i)
Definition simpleideals.h:23
Q
#define Q
Definition sirandom.c:26
isHomog
@ isHomog
Definition structs.h:33
kStrategy
skStrategy * kStrategy
Definition structs.h:54