My Project
Macros | Typedefs | Functions | Variables
kstd1.h File Reference
#include "kernel/structs.h"
#include "polys/monomials/ring.h"

Go to the source code of this file.

Macros

#define KSTD_NF_LAZY   1
 
#define KSTD_NF_ECART   2
 
#define KSTD_NF_NONORM   4
 

Typedefs

typedef BOOLEAN(* s_poly_proc_t) (kStrategy strat)
 

Functions

ideal mora (ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
 
poly kNF1 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
 
ideal kNF1 (ideal F, ideal Q, ideal q, kStrategy strat, int lazyReduce)
 
poly kNF (ideal F, ideal Q, poly p, int syzComp=0, int lazyReduce=0)
 
ideal kNF (ideal F, ideal Q, ideal p, int syzComp=0, int lazyReduce=0)
 
poly kNFBound (ideal F, ideal Q, poly p, int bound, int syzComp=0, int lazyReduce=0)
 
ideal kNFBound (ideal F, ideal Q, ideal p, int bound, int syzComp=0, int lazyReduce=0)
 
poly k_NF (ideal F, ideal Q, poly p, int syzComp, int lazyReduce, const ring _currRing)
 NOTE: this is just a wrapper which sets currRing for the actual kNF call. More...
 
ideal kSba (ideal F, ideal Q, tHomog h, intvec **mw, int incremental=0, int arri=0, intvec *hilb=NULL, int syzComp=0, int newIdeal=0, intvec *vw=NULL)
 
ideal kStd (ideal F, ideal Q, tHomog h, intvec **mw, intvec *hilb=NULL, int syzComp=0, int newIdeal=0, intvec *vw=NULL, s_poly_proc_t sp=NULL)
 
ideal kStdShift (ideal F, ideal Q, tHomog h, intvec **mw, intvec *hilb=NULL, int syzComp=0, int newIdeal=0, intvec *vw=NULL, BOOLEAN rightGB=FALSE)
 
ideal rightgb (ideal F, ideal Q)
 
void initMora (ideal F, kStrategy strat)
 
ideal kInterRed (ideal F, ideal Q=NULL)
 
ideal kInterRedOld (ideal F, ideal Q=NULL)
 
long kModDeg (poly p, ring r=currRing)
 
long kHomModDeg (poly p, ring r=currRing)
 
ideal stdred (ideal F, ideal Q, tHomog h, intvec **w)
 
ideal kMin_std (ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb=NULL, int syzComp=0, int reduced=0)
 
BOOLEAN kVerify (ideal F, ideal Q)
 

Variables

EXTERN_VAR int LazyPass
 
EXTERN_VAR int LazyDegree
 
EXTERN_VAR int Kstd1_mu
 
EXTERN_VAR int Kstd1_deg
 
EXTERN_VAR BITSET kOptions
 
EXTERN_VAR BITSET validOpts
 
EXTERN_VAR intveckModW
 
EXTERN_VAR intveckHomW
 

Macro Definition Documentation

◆ KSTD_NF_ECART

#define KSTD_NF_ECART   2

Definition at line 19 of file kstd1.h.

◆ KSTD_NF_LAZY

#define KSTD_NF_LAZY   1

Definition at line 17 of file kstd1.h.

◆ KSTD_NF_NONORM

#define KSTD_NF_NONORM   4

Definition at line 21 of file kstd1.h.

Typedef Documentation

◆ s_poly_proc_t

typedef BOOLEAN(* s_poly_proc_t) (kStrategy strat)

Definition at line 14 of file kstd1.h.

Function Documentation

◆ initMora()

void initMora ( ideal  F,
kStrategy  strat 
)

Definition at line 1798 of file kstd1.cc.

1799{
1800 int i,j;
1801
1802 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1803 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1804 strat->enterS = enterSMora;
1805 strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1806 strat->posInLOld = strat->posInL;
1807 strat->posInLOldFlag = TRUE;
1808 strat->initEcart = initEcartNormal;
1809 strat->kHEdgeFound = (currRing->ppNoether) != NULL;
1810 if ( strat->kHEdgeFound )
1811 strat->kNoether = pCopy((currRing->ppNoether));
1812 else if (strat->kHEdgeFound || strat->homog)
1813 strat->red = redFirst; /*take the first possible in T*/
1814 else
1815 strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1816 if (strat->kHEdgeFound)
1817 {
1818 strat->HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1819 strat->posInT = posInT2;
1820 }
1821 else
1822 {
1823 strat->HCord = 32000;/*- very large -*/
1824 }
1825
1826 if (rField_is_Ring(currRing)) {
1827 if (rField_is_Z(currRing))
1828 strat->red = redRiloc_Z;
1829 else
1830 strat->red = redRiloc;
1831 }
1832
1833 /*reads the ecartWeights used for Graebes method from the
1834 *intvec ecart and set ecartWeights
1835 */
1836 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1837 {
1838 //interred machen Aenderung
1839 strat->pOrigFDeg=currRing->pFDeg;
1840 strat->pOrigLDeg=currRing->pLDeg;
1841 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1842 /*uses automatic computation of the ecartWeights to set them*/
1844
1846 if (TEST_OPT_PROT)
1847 {
1848 for(i=1; i<=(currRing->N); i++)
1849 Print(" %d",ecartWeights[i]);
1850 PrintLn();
1851 mflush();
1852 }
1853 }
1854 kOptimizeLDeg(currRing->pLDeg, strat);
1855}
#define NULL
Definition: auxiliary.h:104
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
int i
Definition: cfEzgcd.cc:132
char posInLOldFlag
Definition: kutil.h:386
poly kNoether
Definition: kutil.h:331
BOOLEAN * NotUsedAxis
Definition: kutil.h:335
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:285
pFDegProc pOrigFDeg
Definition: kutil.h:297
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:289
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:288
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:287
void(* initEcart)(TObject *L)
Definition: kutil.h:281
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:282
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:279
char kHEdgeFound
Definition: kutil.h:380
int HCord
Definition: kutil.h:358
char homog
Definition: kutil.h:376
pLDegProc pOrigLDeg
Definition: kutil.h:298
#define Print
Definition: emacs.cc:80
int j
Definition: facHensel.cc:110
int redFirst(LObject *h, kStrategy strat)
Definition: kstd1.cc:786
int redEcart(LObject *h, kStrategy strat)
Definition: kstd1.cc:169
static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
Definition: kstd1.cc:100
int redRiloc(LObject *h, kStrategy strat)
Definition: kstd1.cc:385
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1606
int redRiloc_Z(LObject *h, kStrategy strat)
Definition: kstd1.cc:566
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4962
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition: kutil.cc:1347
void initEcartNormal(TObject *h)
Definition: kutil.cc:1325
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define TEST_OPT_WEIGHTM
Definition: options.h:121
#define TEST_OPT_PROT
Definition: options.h:103
void pSetDegProcs(ring r, pFDegProc new_FDeg, pLDegProc new_lDeg)
Definition: p_polys.cc:3707
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
#define pCopy(p)
return a copy of the poly
Definition: polys.h:185
void PrintLn()
Definition: reporter.cc:310
#define mflush()
Definition: reporter.h:58
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:486
static BOOLEAN rField_is_Z(const ring r)
Definition: ring.h:511
#define IDELEMS(i)
Definition: simpleideals.h:23
long totaldegreeWecart(poly p, ring r)
Definition: weight.cc:217
long maxdegreeWecart(poly p, int *l, ring r)
Definition: weight.cc:247
void kEcartWeights(poly *s, int sl, short *eweight, const ring R)
Definition: weight.cc:182
EXTERN_VAR short * ecartWeights
Definition: weight.h:12

◆ k_NF()

poly k_NF ( ideal  F,
ideal  Q,
poly  p,
int  syzComp,
int  lazyReduce,
const ring  _currRing 
)

NOTE: this is just a wrapper which sets currRing for the actual kNF call.

Definition at line 3380 of file kstd1.cc.

3381{
3382 const ring save = currRing;
3383 if( currRing != _currRing ) rChangeCurrRing(_currRing);
3384 poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3385 if( currRing != save ) rChangeCurrRing(save);
3386 return ret;
3387}
int p
Definition: cfModGcd.cc:4080
STATIC_VAR jList * Q
Definition: janet.cc:30
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:3169
void rChangeCurrRing(ring r)
Definition: polys.cc:15

◆ kHomModDeg()

long kHomModDeg ( poly  p,
ring  r = currRing 
)

Definition at line 2417 of file kstd1.cc.

2418{
2419 int i;
2420 long j=0;
2421
2422 for (i=r->N;i>0;i--)
2423 j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2424 if (kModW == NULL) return j;
2425 i = __p_GetComp(p,r);
2426 if (i==0) return j;
2427 return j+(*kModW)[i-1];
2428}
VAR intvec * kModW
Definition: kstd1.cc:2405
#define __p_GetComp(p, r)
Definition: monomials.h:63
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:469

◆ kInterRed()

ideal kInterRed ( ideal  F,
ideal  Q = NULL 
)

Definition at line 3745 of file kstd1.cc.

3746{
3747#ifdef HAVE_PLURAL
3748 if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3749#endif
3752 )
3753 return kInterRedOld(F,Q);
3754
3755 //return kInterRedOld(F,Q);
3756
3757 BITSET save1;
3758 SI_SAVE_OPT1(save1);
3759 //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3761 //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3762 //si_opt_1&= ~Sy_bit(OPT_REDSB);
3763 //extern char * showOption() ;
3764 //Print("%s\n",showOption());
3765
3766 int need_retry;
3767 int counter=3;
3768 ideal res, res1;
3769 int elems;
3770 ideal null=NULL;
3771 if ((Q==NULL) || (!TEST_OPT_REDSB))
3772 {
3773 elems=idElem(F);
3774 res=kInterRedBba(F,Q,need_retry);
3775 }
3776 else
3777 {
3778 ideal FF=idSimpleAdd(F,Q);
3779 res=kInterRedBba(FF,NULL,need_retry);
3780 idDelete(&FF);
3781 null=idInit(1,1);
3782 if (need_retry)
3783 res1=kNF(null,Q,res,0,KSTD_NF_LAZY);
3784 else
3785 res1=kNF(null,Q,res);
3786 idDelete(&res);
3787 res=res1;
3788 need_retry=1;
3789 }
3790 if (idElem(res)<=1) need_retry=0;
3791 while (need_retry && (counter>0))
3792 {
3793 #ifdef KDEBUG
3794 if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3795 #endif
3796 res1=kInterRedBba(res,Q,need_retry);
3797 int new_elems=idElem(res1);
3798 counter -= (new_elems >= elems);
3799 elems = new_elems;
3800 idDelete(&res);
3801 if (idElem(res1)<=1) need_retry=0;
3802 if ((Q!=NULL) && (TEST_OPT_REDSB))
3803 {
3804 if (need_retry)
3805 res=kNF(null,Q,res1,0,KSTD_NF_LAZY);
3806 else
3807 res=kNF(null,Q,res1);
3808 idDelete(&res1);
3809 }
3810 else
3811 res = res1;
3812 if (idElem(res)<=1) need_retry=0;
3813 }
3814 if (null!=NULL) idDelete(&null);
3815 SI_RESTORE_OPT1(save1);
3817 return res;
3818}
CanonicalForm res
Definition: facAbsFact.cc:60
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
#define idSimpleAdd(A, B)
Definition: ideals.h:42
ideal kInterRedOld(ideal F, ideal Q)
Definition: kstd1.cc:3393
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition: kstd1.cc:3485
#define KSTD_NF_LAZY
Definition: kstd1.h:17
VAR unsigned si_opt_1
Definition: options.c:5
#define SI_SAVE_OPT1(A)
Definition: options.h:21
#define SI_RESTORE_OPT1(A)
Definition: options.h:24
#define OPT_REDTHROUGH
Definition: options.h:82
#define Sy_bit(x)
Definition: options.h:31
#define TEST_OPT_REDSB
Definition: options.h:104
#define TEST_OPT_DEBUG
Definition: options.h:108
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:400
static BOOLEAN rField_is_numeric(const ring r)
Definition: ring.h:517
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:762
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
int idElem(const ideal F)
count non-zero elements
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define BITSET
Definition: structs.h:20

◆ kInterRedOld()

ideal kInterRedOld ( ideal  F,
ideal  Q = NULL 
)

Definition at line 3393 of file kstd1.cc.

3394{
3395 int j;
3396 kStrategy strat = new skStrategy;
3397
3398 ideal tempF = F;
3399 ideal tempQ = Q;
3400
3401#ifdef HAVE_PLURAL
3402 if(rIsSCA(currRing))
3403 {
3404 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3405 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3406 tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3407
3408 // this should be done on the upper level!!! :
3409 // tempQ = SCAQuotient(currRing);
3410
3411 if(Q == currRing->qideal)
3412 tempQ = SCAQuotient(currRing);
3413 }
3414#endif
3415
3416// if (TEST_OPT_PROT)
3417// {
3418// writeTime("start InterRed:");
3419// mflush();
3420// }
3421 //strat->syzComp = 0;
3422 strat->kHEdgeFound = (currRing->ppNoether) != NULL;
3423 strat->kNoether=pCopy((currRing->ppNoether));
3424 strat->ak = id_RankFreeModule(tempF,currRing);
3425 initBuchMoraCrit(strat);
3426 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3427 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3428 strat->enterS = enterSBba;
3429 strat->posInT = posInT17;
3430 strat->initEcart = initEcartNormal;
3431 strat->sl = -1;
3432 strat->tl = -1;
3433 strat->tmax = setmaxT;
3434 strat->T = initT();
3435 strat->R = initR();
3436 strat->sevT = initsevT();
3438 initS(tempF, tempQ, strat);
3439 if (TEST_OPT_REDSB)
3440 strat->noTailReduction=FALSE;
3441 updateS(TRUE,strat);
3443 completeReduce(strat);
3444 //else if (TEST_OPT_PROT) PrintLn();
3445 cleanT(strat);
3446 if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
3447 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3448 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3449 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3450 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3451 omfree(strat->sevT);
3452 omfree(strat->S_2_R);
3453 omfree(strat->R);
3454
3455 if (strat->fromQ)
3456 {
3457 for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3458 {
3459 if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3460 }
3461 omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
3462 }
3463// if (TEST_OPT_PROT)
3464// {
3465// writeTime("end Interred:");
3466// mflush();
3467// }
3468 ideal shdl=strat->Shdl;
3469 idSkipZeroes(shdl);
3470 if (strat->fromQ)
3471 {
3472 strat->fromQ=NULL;
3473 ideal res=kInterRed(shdl,NULL);
3474 idDelete(&shdl);
3475 shdl=res;
3476 }
3477 delete(strat);
3478#ifdef HAVE_PLURAL
3479 if( tempF != F )
3480 id_Delete( &tempF, currRing);
3481#endif
3482 return shdl;
3483}
#define FALSE
Definition: auxiliary.h:96
void * ADDRESS
Definition: auxiliary.h:119
int * S_2_R
Definition: kutil.h:345
char noTailReduction
Definition: kutil.h:382
TSet T
Definition: kutil.h:327
intset ecartS
Definition: kutil.h:310
char honey
Definition: kutil.h:381
int ak
Definition: kutil.h:356
TObject ** R
Definition: kutil.h:343
poly kHEdge
Definition: kutil.h:330
int tl
Definition: kutil.h:353
unsigned long * sevT
Definition: kutil.h:326
ideal Shdl
Definition: kutil.h:304
int tmax
Definition: kutil.h:353
intset fromQ
Definition: kutil.h:322
int sl
Definition: kutil.h:351
unsigned long * sevS
Definition: kutil.h:323
KINLINE TSet initT()
Definition: kInline.h:84
KINLINE TObject ** initR()
Definition: kInline.h:95
KINLINE unsigned long * initsevT()
Definition: kInline.h:100
ideal kInterRed(ideal F, ideal Q)
Definition: kstd1.cc:3745
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5394
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7829
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:8788
void cleanT(kStrategy strat)
Definition: kutil.cc:545
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9670
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10532
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:9023
#define setmaxT
Definition: kutil.h:33
class sTObject TObject
Definition: kutil.h:57
static bool rIsSCA(const ring r)
Definition: nc.h:190
ideal id_KillSquares(const ideal id, const short iFirstAltVar, const short iLastAltVar, const ring r, const bool bSkipZeroes)
Definition: sca.cc:1520
#define omfree(addr)
Definition: omAllocDecl.h:237
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define TEST_OPT_INTSTRATEGY
Definition: options.h:110
#define pDelete(p_ptr)
Definition: polys.h:186
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:70
ideal SCAQuotient(const ring r)
Definition: sca.h:10
static short scaLastAltVar(ring r)
Definition: sca.h:25
static short scaFirstAltVar(ring r)
Definition: sca.h:18
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s

◆ kMin_std()

ideal kMin_std ( ideal  F,
ideal  Q,
tHomog  h,
intvec **  w,
ideal &  M,
intvec hilb = NULL,
int  syzComp = 0,
int  reduced = 0 
)

Definition at line 3020 of file kstd1.cc.

3022{
3023 if(idIs0(F))
3024 {
3025 M=idInit(1,F->rank);
3026 return idInit(1,F->rank);
3027 }
3029 {
3030 ideal sb;
3031 sb = kStd(F, Q, h, w, hilb);
3032 idSkipZeroes(sb);
3033 if(IDELEMS(sb) <= IDELEMS(F))
3034 {
3035 M = idCopy(sb);
3036 idSkipZeroes(M);
3037 return(sb);
3038 }
3039 else
3040 {
3041 M = idCopy(F);
3042 idSkipZeroes(M);
3043 return(sb);
3044 }
3045 }
3046 ideal r=NULL;
3047 int Kstd1_OldDeg = Kstd1_deg,i;
3048 intvec* temp_w=NULL;
3049 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3050 BOOLEAN delete_w=(w==NULL);
3051 BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
3052 kStrategy strat=new skStrategy;
3053
3055 strat->syzComp = syzComp;
3057 strat->LazyPass=20;
3058 else
3059 strat->LazyPass=2;
3060 strat->LazyDegree = 1;
3061 strat->minim=(reduced % 2)+1;
3062 strat->ak = id_RankFreeModule(F,currRing);
3063 if (delete_w)
3064 {
3065 temp_w=new intvec((strat->ak)+1);
3066 w = &temp_w;
3067 }
3068 if (h==testHomog)
3069 {
3070 if (strat->ak == 0)
3071 {
3072 h = (tHomog)idHomIdeal(F,Q);
3073 w=NULL;
3074 }
3075 else
3076 {
3077 h = (tHomog)idHomModule(F,Q,w);
3078 }
3079 }
3080 if (h==isHomog)
3081 {
3082 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3083 {
3084 kModW = *w;
3085 strat->kModW = *w;
3086 assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3087 strat->pOrigFDeg = currRing->pFDeg;
3088 strat->pOrigLDeg = currRing->pLDeg;
3090
3091 toReset = TRUE;
3092 if (reduced>1)
3093 {
3094 Kstd1_OldDeg=Kstd1_deg;
3095 Kstd1_deg = -1;
3096 for (i=IDELEMS(F)-1;i>=0;i--)
3097 {
3098 if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3099 Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3100 }
3101 }
3102 }
3103 currRing->pLexOrder = TRUE;
3104 strat->LazyPass*=2;
3105 }
3106 strat->homog=h;
3108 {
3109 if (w!=NULL)
3110 r=mora(F,Q,*w,hilb,strat);
3111 else
3112 r=mora(F,Q,NULL,hilb,strat);
3113 }
3114 else
3115 {
3116 if (w!=NULL)
3117 r=bba(F,Q,*w,hilb,strat);
3118 else
3119 r=bba(F,Q,NULL,hilb,strat);
3120 }
3121#ifdef KDEBUG
3122 {
3123 int i;
3124 for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3125 }
3126#endif
3127 idSkipZeroes(r);
3128 if (toReset)
3129 {
3131 kModW = NULL;
3132 }
3133 currRing->pLexOrder = b;
3134 HCord=strat->HCord;
3135 if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3136 if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3137 {
3138 M=idInit(1,F->rank);
3139 M->m[0]=pOne();
3140 //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3141 if (strat->M!=NULL) idDelete(&strat->M);
3142 }
3143 else if (strat->M==NULL)
3144 {
3145 M=idInit(1,F->rank);
3146 WarnS("no minimal generating set computed");
3147 }
3148 else
3149 {
3150 idSkipZeroes(strat->M);
3151 M=strat->M;
3152 }
3153 delete(strat);
3154 if (reduced>2)
3155 {
3156 Kstd1_deg=Kstd1_OldDeg;
3157 if (!oldDegBound)
3158 si_opt_1 &= ~Sy_bit(OPT_DEGBOUND);
3159 }
3160 else
3161 {
3162 if (IDELEMS(M)>IDELEMS(r)) {
3163 idDelete(&M);
3164 M=idCopy(r); }
3165 }
3166 return r;
3167}
CanonicalForm b
Definition: cfModGcd.cc:4105
Definition: intvec.h:23
intvec * kModW
Definition: kutil.h:338
int syzComp
Definition: kutil.h:357
int minim
Definition: kutil.h:361
ideal M
Definition: kutil.h:306
int LazyPass
Definition: kutil.h:356
int LazyDegree
Definition: kutil.h:356
#define WarnS
Definition: emacs.cc:78
const CanonicalForm & w
Definition: facAbsFact.cc:51
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
static BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition: ideals.h:96
static BOOLEAN idHomIdeal(ideal id, ideal Q=NULL)
Definition: ideals.h:91
ideal idCopy(ideal A)
Definition: ideals.h:60
STATIC_VAR Poly * h
Definition: janet.cc:971
ideal mora(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd1.cc:1859
long kModDeg(poly p, ring r)
Definition: kstd1.cc:2407
ideal kStd(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
Definition: kstd1.cc:2430
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:49
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2374
VAR int HCord
Definition: kutil.cc:246
#define assume(x)
Definition: mod2.h:387
#define TEST_OPT_DEGBOUND
Definition: options.h:113
#define TEST_OPT_RETURN_SB
Definition: options.h:112
#define OPT_DEGBOUND
Definition: options.h:90
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition: p_polys.cc:3719
#define pTest(p)
Definition: polys.h:415
#define pIsConstant(p)
like above, except that Comp must be 0
Definition: polys.h:238
#define pOne()
Definition: polys.h:315
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:550
#define M
Definition: sirandom.c:25
tHomog
Definition: structs.h:40
@ isHomog
Definition: structs.h:42
@ testHomog
Definition: structs.h:43

◆ kModDeg()

long kModDeg ( poly  p,
ring  r = currRing 
)

Definition at line 2407 of file kstd1.cc.

2408{
2409 long o=p_WDegree(p, r);
2410 long i=__p_GetComp(p, r);
2411 if (i==0) return o;
2412 //assume((i>0) && (i<=kModW->length()));
2413 if (i<=kModW->length())
2414 return o+(*kModW)[i-1];
2415 return o;
2416}
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
long p_WDegree(poly p, const ring r)
Definition: p_polys.cc:709

◆ kNF() [1/2]

ideal kNF ( ideal  F,
ideal  Q,
ideal  p,
int  syzComp = 0,
int  lazyReduce = 0 
)

Definition at line 3266 of file kstd1.cc.

3267{
3268 ideal res;
3269 if (TEST_OPT_PROT)
3270 {
3271 Print("(S:%d)",IDELEMS(p));mflush();
3272 }
3273 if (idIs0(p))
3274 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3275
3276 ideal pp = p;
3277#ifdef HAVE_PLURAL
3278 if(rIsSCA(currRing))
3279 {
3280 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3281 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3282 pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3283
3284 if(Q == currRing->qideal)
3286 }
3287#endif
3288
3289 if ((idIs0(F))&&(Q==NULL))
3290 {
3291#ifdef HAVE_PLURAL
3292 if(p != pp)
3293 return pp;
3294#endif
3295 return idCopy(p); /*F+Q=0*/
3296 }
3297
3298 kStrategy strat=new skStrategy;
3299 strat->syzComp = syzComp;
3301 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3302 {
3303 strat->ak = si_max(strat->ak,(int)F->rank);
3304 }
3305
3307 {
3308#ifdef HAVE_SHIFTBBA
3309 if (currRing->isLPring)
3310 {
3311 WerrorS("No local ordering possible for shift algebra");
3312 return(NULL);
3313 }
3314#endif
3315 res=kNF1(F,Q,pp,strat,lazyReduce);
3316 }
3317 else
3318 res=kNF2(F,Q,pp,strat,lazyReduce);
3319 delete(strat);
3320
3321#ifdef HAVE_PLURAL
3322 if(pp != p)
3324#endif
3325
3326 return res;
3327}
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
void WerrorS(const char *s)
Definition: feFopen.cc:24
poly kNF1(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd1.cc:2108
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3701

◆ kNF() [2/2]

poly kNF ( ideal  F,
ideal  Q,
poly  p,
int  syzComp = 0,
int  lazyReduce = 0 
)

Definition at line 3169 of file kstd1.cc.

3170{
3171 if (p==NULL)
3172 return NULL;
3173
3174 poly pp = p;
3175
3176#ifdef HAVE_PLURAL
3177 if(rIsSCA(currRing))
3178 {
3179 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3180 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3181 pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3182
3183 if(Q == currRing->qideal)
3185 }
3186#endif
3187
3188 if ((idIs0(F))&&(Q==NULL))
3189 {
3190#ifdef HAVE_PLURAL
3191 if(p != pp)
3192 return pp;
3193#endif
3194 return pCopy(p); /*F+Q=0*/
3195 }
3196
3197 kStrategy strat=new skStrategy;
3198 strat->syzComp = syzComp;
3200 poly res;
3201
3203 {
3204#ifdef HAVE_SHIFTBBA
3205 if (currRing->isLPring)
3206 {
3207 WerrorS("No local ordering possible for shift algebra");
3208 return(NULL);
3209 }
3210#endif
3211 res=kNF1(F,Q,pp,strat,lazyReduce);
3212 }
3213 else
3214 res=kNF2(F,Q,pp,strat,lazyReduce);
3215 delete(strat);
3216
3217#ifdef HAVE_PLURAL
3218 if(pp != p)
3219 p_Delete(&pp, currRing);
3220#endif
3221 return res;
3222}
poly p_KillSquares(const poly p, const short iFirstAltVar, const short iLastAltVar, const ring r)
Definition: sca.cc:1465
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:861
#define pMaxComp(p)
Definition: polys.h:299

◆ kNF1() [1/2]

ideal kNF1 ( ideal  F,
ideal  Q,
ideal  q,
kStrategy  strat,
int  lazyReduce 
)

Definition at line 2252 of file kstd1.cc.

2253{
2254 assume(!idIs0(q));
2255 assume(!(idIs0(F)&&(Q==NULL)));
2256
2257// lazy_reduce flags: can be combined by |
2258//#define KSTD_NF_LAZY 1
2259 // do only a reduction of the leading term
2260//#define KSTD_NF_ECART 2
2261 // only local: recude even with bad ecart
2262 poly p;
2263 int i;
2264 int j;
2265 int o;
2266 LObject h;
2267 ideal res;
2268 BITSET save1;
2269 SI_SAVE_OPT1(save1);
2270
2271 //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2272 //if ((idIs0(F))&&(Q==NULL))
2273 // return idCopy(q); /*F=0*/
2274 //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2275 /*- creating temp data structures------------------- -*/
2276 strat->kHEdgeFound = (currRing->ppNoether) != NULL;
2277 strat->kNoether=pCopy((currRing->ppNoether));
2280 && (0<Kstd1_deg)
2281 && ((!strat->kHEdgeFound)
2283 {
2284 pLmDelete(&strat->kNoether);
2285 strat->kNoether=pOne();
2286 pSetExp(strat->kNoether,1, Kstd1_deg+1);
2287 pSetm(strat->kNoether);
2288 strat->kHEdgeFound=TRUE;
2289 }
2290 initBuchMoraCrit(strat);
2292 initBuchMoraPosRing(strat);
2293 else
2294 initBuchMoraPos(strat);
2295 initMora(F,strat);
2296 strat->enterS = enterSMoraNF;
2297 /*- set T -*/
2298 strat->tl = -1;
2299 strat->tmax = setmaxT;
2300 strat->T = initT();
2301 strat->R = initR();
2302 strat->sevT = initsevT();
2303 /*- set S -*/
2304 strat->sl = -1;
2305 /*- init local data struct.-------------------------- -*/
2306 /*Shdl=*/initS(F,Q,strat);
2307 if ((strat->ak!=0)
2308 && (strat->kHEdgeFound))
2309 {
2310 if (strat->ak!=1)
2311 {
2312 pSetComp(strat->kNoether,1);
2313 pSetmComp(strat->kNoether);
2314 poly p=pHead(strat->kNoether);
2315 pSetComp(p,strat->ak);
2316 pSetmComp(p);
2317 p=pAdd(strat->kNoether,p);
2318 strat->kNoether=pNext(p);
2320 }
2321 }
2322 if (TEST_OPT_INTSTRATEGY && ((lazyReduce & KSTD_NF_LAZY)==0))
2323 {
2324 for (i=strat->sl; i>=0; i--)
2325 pNorm(strat->S[i]);
2326 }
2327 /*- compute------------------------------------------- -*/
2328 res=idInit(IDELEMS(q),strat->ak);
2329 for (i=0; i<IDELEMS(q); i++)
2330 {
2331 if (q->m[i]!=NULL)
2332 {
2333 p = pCopy(q->m[i]);
2334 deleteHC(&p,&o,&j,strat);
2335 if (p!=NULL)
2336 {
2337 /*- puts the elements of S also to T -*/
2338 for (j=0; j<=strat->sl; j++)
2339 {
2340 h.p = strat->S[j];
2341 h.ecart = strat->ecartS[j];
2342 h.pLength = h.length = pLength(h.p);
2343 if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2344 else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2345 h.sev = strat->sevS[j];
2346 h.SetpFDeg();
2348 enterT_strong(h,strat);
2349 else
2350 enterT(h,strat);
2351 }
2352 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2354 {
2355 p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
2356 }
2357 else
2358 p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2359 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2360 {
2361 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2362 p = redtail(p,strat->sl,strat);
2363 }
2364 cleanT(strat);
2365 }
2366 res->m[i]=p;
2367 }
2368 //else
2369 // res->m[i]=NULL;
2370 }
2371 /*- release temp data------------------------------- -*/
2372 assume(strat->L==NULL); /*strat->L unsed */
2373 assume(strat->B==NULL); /*strat->B unused */
2374 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2375 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2376 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2377 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2378 omFree(strat->sevT);
2379 omFree(strat->S_2_R);
2380 omFree(strat->R);
2381 if ((Q!=NULL)&&(strat->fromQ!=NULL))
2382 {
2384 omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2385 strat->fromQ=NULL;
2386 }
2387 if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
2388 if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2389// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2390// {
2391// pFDeg=strat->pOrigFDeg;
2392// pLDeg=strat->pOrigLDeg;
2393// if (ecartWeights)
2394// {
2395// omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2396// ecartWeights=NULL;
2397// }
2398// }
2399 idDelete(&strat->Shdl);
2400 SI_RESTORE_OPT1(save1);
2401 if (TEST_OPT_PROT) PrintLn();
2402 return res;
2403}
polyset S
Definition: kutil.h:307
LSet B
Definition: kutil.h:329
LSet L
Definition: kutil.h:328
void initMora(ideal F, kStrategy strat)
Definition: kstd1.cc:1798
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kstd1.cc:1660
static poly redMoraNFRing(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:1067
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition: kstd1.cc:967
#define KSTD_NF_ECART
Definition: kstd1.h:19
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:7069
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9372
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9822
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9472
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition: kutil.cc:254
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9908
#define setmaxTinc
Definition: kutil.h:34
class sLObject LObject
Definition: kutil.h:58
#define pNext(p)
Definition: monomials.h:36
#define omFree(addr)
Definition: omAllocDecl.h:261
#define OPT_REDTAIL
Definition: options.h:91
#define TEST_OPT_STAIRCASEBOUND
Definition: options.h:115
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:711
static unsigned pLength(poly a)
Definition: p_polys.h:191
#define pAdd(p, q)
Definition: polys.h:203
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition: polys.h:67
#define pSetm(p)
Definition: polys.h:271
#define pSetComp(p, v)
Definition: polys.h:38
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
Definition: polys.h:152
#define pSetmComp(p)
TODO:
Definition: polys.h:273
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:363
#define pSetExp(p, i, v)
Definition: polys.h:42
#define pWTotaldegree(p)
Definition: polys.h:283
void PrintS(const char *s)
Definition: reporter.cc:284

◆ kNF1() [2/2]

poly kNF1 ( ideal  F,
ideal  Q,
poly  q,
kStrategy  strat,
int  lazyReduce 
)

Definition at line 2108 of file kstd1.cc.

2109{
2110 assume(q!=NULL);
2111 assume(!(idIs0(F)&&(Q==NULL)));
2112
2113// lazy_reduce flags: can be combined by |
2114//#define KSTD_NF_LAZY 1
2115 // do only a reduction of the leading term
2116//#define KSTD_NF_ECART 2
2117 // only local: recude even with bad ecart
2118 poly p;
2119 int i;
2120 int j;
2121 int o;
2122 LObject h;
2123 BITSET save1;
2124 SI_SAVE_OPT1(save1);
2125
2126 //if ((idIs0(F))&&(Q==NULL))
2127 // return pCopy(q); /*F=0*/
2128 //strat->ak = si_max(idRankFreeModule(F),pMaxComp(q));
2129 /*- creating temp data structures------------------- -*/
2130 strat->kHEdgeFound = (currRing->ppNoether) != NULL;
2131 strat->kNoether = pCopy((currRing->ppNoether));
2133 si_opt_1&=~Sy_bit(OPT_INTSTRATEGY);
2135 && (! TEST_V_DEG_STOP)
2136 && (0<Kstd1_deg)
2137 && ((!strat->kHEdgeFound)
2139 {
2140 pLmDelete(&strat->kNoether);
2141 strat->kNoether=pOne();
2142 pSetExp(strat->kNoether,1, Kstd1_deg+1);
2143 pSetm(strat->kNoether);
2144 strat->kHEdgeFound=TRUE;
2145 }
2146 initBuchMoraCrit(strat);
2148 initBuchMoraPosRing(strat);
2149 else
2150 initBuchMoraPos(strat);
2151 initMora(F,strat);
2152 strat->enterS = enterSMoraNF;
2153 /*- set T -*/
2154 strat->tl = -1;
2155 strat->tmax = setmaxT;
2156 strat->T = initT();
2157 strat->R = initR();
2158 strat->sevT = initsevT();
2159 /*- set S -*/
2160 strat->sl = -1;
2161 /*- init local data struct.-------------------------- -*/
2162 /*Shdl=*/initS(F,Q,strat);
2163 if ((strat->ak!=0)
2164 && (strat->kHEdgeFound))
2165 {
2166 if (strat->ak!=1)
2167 {
2168 pSetComp(strat->kNoether,1);
2169 pSetmComp(strat->kNoether);
2170 poly p=pHead(strat->kNoether);
2171 pSetComp(p,strat->ak);
2172 pSetmComp(p);
2173 p=pAdd(strat->kNoether,p);
2174 strat->kNoether=pNext(p);
2176 }
2177 }
2178 if ((lazyReduce & KSTD_NF_LAZY)==0)
2179 {
2180 for (i=strat->sl; i>=0; i--)
2181 pNorm(strat->S[i]);
2182 }
2183 /*- puts the elements of S also to T -*/
2184 for (i=0; i<=strat->sl; i++)
2185 {
2186 h.p = strat->S[i];
2187 h.ecart = strat->ecartS[i];
2188 if (strat->sevS[i] == 0) strat->sevS[i] = pGetShortExpVector(h.p);
2189 else assume(strat->sevS[i] == pGetShortExpVector(h.p));
2190 h.length = pLength(h.p);
2191 h.sev = strat->sevS[i];
2192 h.SetpFDeg();
2193 enterT(h,strat);
2194 }
2195#ifdef KDEBUG
2196// kDebugPrint(strat);
2197#endif
2198 /*- compute------------------------------------------- -*/
2199 p = pCopy(q);
2200 deleteHC(&p,&o,&j,strat);
2201 kTest(strat);
2202 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2203 if (BVERBOSE(23)) kDebugPrint(strat);
2205 {
2206 if (p!=NULL) p = redMoraNFRing(p,strat, lazyReduce & KSTD_NF_ECART);
2207 }
2208 else
2209 {
2210 if (p!=NULL) p = redMoraNF(p,strat, lazyReduce & KSTD_NF_ECART);
2211 }
2212 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2213 {
2214 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2215 p = redtail(p,strat->sl,strat);
2216 }
2217 /*- release temp data------------------------------- -*/
2218 cleanT(strat);
2219 assume(strat->L==NULL); /*strat->L unsed */
2220 assume(strat->B==NULL); /*strat->B unused */
2221 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2222 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2223 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2224 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2225 omFree(strat->sevT);
2226 omFree(strat->S_2_R);
2227 omFree(strat->R);
2228
2229 if ((Q!=NULL)&&(strat->fromQ!=NULL))
2230 {
2231 i=((IDELEMS(Q)+IDELEMS(F)+15)/16)*16;
2232 omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2233 strat->fromQ=NULL;
2234 }
2235 if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
2236 if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2237// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2238// {
2239// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2240// if (ecartWeights)
2241// {
2242// omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2243// ecartWeights=NULL;
2244// }
2245// }
2246 idDelete(&strat->Shdl);
2247 SI_RESTORE_OPT1(save1);
2248 if (TEST_OPT_PROT) PrintLn();
2249 return p;
2250}
void kDebugPrint(kStrategy strat)
Definition: kutil.cc:11753
BOOLEAN kTest(kStrategy strat)
Definition: kutil.cc:1010
#define OPT_INTSTRATEGY
Definition: options.h:92
#define BVERBOSE(a)
Definition: options.h:34
#define TEST_V_DEG_STOP
Definition: options.h:138

◆ kNFBound() [1/2]

ideal kNFBound ( ideal  F,
ideal  Q,
ideal  p,
int  bound,
int  syzComp = 0,
int  lazyReduce = 0 
)

Definition at line 3329 of file kstd1.cc.

3330{
3331 ideal res;
3332 if (TEST_OPT_PROT)
3333 {
3334 Print("(S:%d)",IDELEMS(p));mflush();
3335 }
3336 if (idIs0(p))
3337 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3338
3339 ideal pp = p;
3340#ifdef HAVE_PLURAL
3341 if(rIsSCA(currRing))
3342 {
3343 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3344 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3345 pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3346
3347 if(Q == currRing->qideal)
3349 }
3350#endif
3351
3352 if ((idIs0(F))&&(Q==NULL))
3353 {
3354#ifdef HAVE_PLURAL
3355 if(p != pp)
3356 return pp;
3357#endif
3358 return idCopy(p); /*F+Q=0*/
3359 }
3360
3361 kStrategy strat=new skStrategy;
3362 strat->syzComp = syzComp;
3364 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3365 {
3366 strat->ak = si_max(strat->ak,(int)F->rank);
3367 }
3368
3369 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3370 delete(strat);
3371
3372#ifdef HAVE_PLURAL
3373 if(pp != p)
3375#endif
3376
3377 return res;
3378}
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
poly kNF2Bound(ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3783

◆ kNFBound() [2/2]

poly kNFBound ( ideal  F,
ideal  Q,
poly  p,
int  bound,
int  syzComp = 0,
int  lazyReduce = 0 
)

Definition at line 3224 of file kstd1.cc.

3225{
3226 if (p==NULL)
3227 return NULL;
3228
3229 poly pp = p;
3230
3231#ifdef HAVE_PLURAL
3232 if(rIsSCA(currRing))
3233 {
3234 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3235 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3236 pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3237
3238 if(Q == currRing->qideal)
3240 }
3241#endif
3242
3243 if ((idIs0(F))&&(Q==NULL))
3244 {
3245#ifdef HAVE_PLURAL
3246 if(p != pp)
3247 return pp;
3248#endif
3249 return pCopy(p); /*F+Q=0*/
3250 }
3251
3252 kStrategy strat=new skStrategy;
3253 strat->syzComp = syzComp;
3255 poly res;
3256 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3257 delete(strat);
3258
3259#ifdef HAVE_PLURAL
3260 if(pp != p)
3261 p_Delete(&pp, currRing);
3262#endif
3263 return res;
3264}

◆ kSba()

ideal kSba ( ideal  F,
ideal  Q,
tHomog  h,
intvec **  mw,
int  incremental = 0,
int  arri = 0,
intvec hilb = NULL,
int  syzComp = 0,
int  newIdeal = 0,
intvec vw = NULL 
)

Definition at line 2615 of file kstd1.cc.

2617{
2618 if(idIs0(F))
2619 return idInit(1,F->rank);
2621 {
2622 ideal r;
2623 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2624 BOOLEAN delete_w=(w==NULL);
2625 kStrategy strat=new skStrategy;
2626 strat->sbaOrder = sbaOrder;
2627 if (arri!=0)
2628 {
2629 strat->rewCrit1 = arriRewDummy;
2630 strat->rewCrit2 = arriRewCriterion;
2632 }
2633 else
2634 {
2638 }
2639
2641 strat->syzComp = syzComp;
2642 if (TEST_OPT_SB_1)
2643 //if(!rField_is_Ring(currRing)) // always true here
2644 strat->newIdeal = newIdeal;
2646 strat->LazyPass=20;
2647 else
2648 strat->LazyPass=2;
2649 strat->LazyDegree = 1;
2653 strat->ak = id_RankFreeModule(F,currRing);
2654 strat->kModW=kModW=NULL;
2655 strat->kHomW=kHomW=NULL;
2656 if (vw != NULL)
2657 {
2658 currRing->pLexOrder=FALSE;
2659 strat->kHomW=kHomW=vw;
2660 strat->pOrigFDeg = currRing->pFDeg;
2661 strat->pOrigLDeg = currRing->pLDeg;
2663 toReset = TRUE;
2664 }
2665 if (h==testHomog)
2666 {
2667 if (strat->ak == 0)
2668 {
2669 h = (tHomog)idHomIdeal(F,Q);
2670 w=NULL;
2671 }
2672 else if (!TEST_OPT_DEGBOUND)
2673 {
2674 if (w!=NULL)
2675 h = (tHomog)idHomModule(F,Q,w);
2676 else
2677 h = (tHomog)idHomIdeal(F,Q);
2678 }
2679 }
2680 currRing->pLexOrder=b;
2681 if (h==isHomog)
2682 {
2683 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2684 {
2685 strat->kModW = kModW = *w;
2686 if (vw == NULL)
2687 {
2688 strat->pOrigFDeg = currRing->pFDeg;
2689 strat->pOrigLDeg = currRing->pLDeg;
2691 toReset = TRUE;
2692 }
2693 }
2694 currRing->pLexOrder = TRUE;
2695 if (hilb==NULL) strat->LazyPass*=2;
2696 }
2697 strat->homog=h;
2698 #ifdef KDEBUG
2699 idTest(F);
2700 if(Q != NULL)
2701 idTest(Q);
2702 #endif
2703 #ifdef HAVE_PLURAL
2705 {
2706 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2707 strat->no_prod_crit = ! bIsSCA;
2708 if (w!=NULL)
2709 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2710 else
2711 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2712 }
2713 else
2714 #endif
2715 {
2717 {
2718 if (w!=NULL)
2719 r=mora(F,Q,*w,hilb,strat);
2720 else
2721 r=mora(F,Q,NULL,hilb,strat);
2722 }
2723 else
2724 {
2725 strat->sigdrop = FALSE;
2726 if (w!=NULL)
2727 r=sba(F,Q,*w,hilb,strat);
2728 else
2729 r=sba(F,Q,NULL,hilb,strat);
2730 }
2731 }
2732 #ifdef KDEBUG
2733 idTest(r);
2734 #endif
2735 if (toReset)
2736 {
2737 kModW = NULL;
2739 }
2740 currRing->pLexOrder = b;
2741 //Print("%d reductions canceled \n",strat->cel);
2742 HCord=strat->HCord;
2743 //delete(strat);
2744 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2745 return r;
2746 }
2747 else
2748 {
2749 //--------------------------RING CASE-------------------------
2750 assume(sbaOrder == 1);
2751 assume(arri == 0);
2752 ideal r;
2753 r = idCopy(F);
2754 int sbaEnterS = -1;
2755 bool sigdrop = TRUE;
2756 //This is how we set the SBA algorithm;
2757 int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2758 while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2759 && (blockred <= blockedreductions))
2760 {
2761 loops++;
2762 if(loops == 1)
2763 sigdrop = FALSE;
2764 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2765 BOOLEAN delete_w=(w==NULL);
2766 kStrategy strat=new skStrategy;
2767 strat->sbaEnterS = sbaEnterS;
2768 strat->sigdrop = sigdrop;
2769 #if 0
2770 strat->blockred = blockred;
2771 #else
2772 strat->blockred = 0;
2773 #endif
2774 strat->blockredmax = blockedreductions;
2775 //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2776 //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2777 strat->sbaOrder = sbaOrder;
2778 if (arri!=0)
2779 {
2780 strat->rewCrit1 = arriRewDummy;
2781 strat->rewCrit2 = arriRewCriterion;
2783 }
2784 else
2785 {
2789 }
2790
2792 strat->syzComp = syzComp;
2793 if (TEST_OPT_SB_1)
2795 strat->newIdeal = newIdeal;
2797 strat->LazyPass=20;
2798 else
2799 strat->LazyPass=2;
2800 strat->LazyDegree = 1;
2804 strat->ak = id_RankFreeModule(F,currRing);
2805 strat->kModW=kModW=NULL;
2806 strat->kHomW=kHomW=NULL;
2807 if (vw != NULL)
2808 {
2809 currRing->pLexOrder=FALSE;
2810 strat->kHomW=kHomW=vw;
2811 strat->pOrigFDeg = currRing->pFDeg;
2812 strat->pOrigLDeg = currRing->pLDeg;
2814 toReset = TRUE;
2815 }
2816 if (h==testHomog)
2817 {
2818 if (strat->ak == 0)
2819 {
2820 h = (tHomog)idHomIdeal(F,Q);
2821 w=NULL;
2822 }
2823 else if (!TEST_OPT_DEGBOUND)
2824 {
2825 if (w!=NULL)
2826 h = (tHomog)idHomModule(F,Q,w);
2827 else
2828 h = (tHomog)idHomIdeal(F,Q);
2829 }
2830 }
2831 currRing->pLexOrder=b;
2832 if (h==isHomog)
2833 {
2834 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2835 {
2836 strat->kModW = kModW = *w;
2837 if (vw == NULL)
2838 {
2839 strat->pOrigFDeg = currRing->pFDeg;
2840 strat->pOrigLDeg = currRing->pLDeg;
2842 toReset = TRUE;
2843 }
2844 }
2845 currRing->pLexOrder = TRUE;
2846 if (hilb==NULL) strat->LazyPass*=2;
2847 }
2848 strat->homog=h;
2849 #ifdef KDEBUG
2850 idTest(F);
2851 if(Q != NULL)
2852 idTest(Q);
2853 #endif
2854 #ifdef HAVE_PLURAL
2856 {
2857 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2858 strat->no_prod_crit = ! bIsSCA;
2859 if (w!=NULL)
2860 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2861 else
2862 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2863 }
2864 else
2865 #endif
2866 {
2868 {
2869 if (w!=NULL)
2870 r=mora(F,Q,*w,hilb,strat);
2871 else
2872 r=mora(F,Q,NULL,hilb,strat);
2873 }
2874 else
2875 {
2876 if (w!=NULL)
2877 r=sba(r,Q,*w,hilb,strat);
2878 else
2879 {
2880 r=sba(r,Q,NULL,hilb,strat);
2881 }
2882 }
2883 }
2884 #ifdef KDEBUG
2885 idTest(r);
2886 #endif
2887 if (toReset)
2888 {
2889 kModW = NULL;
2891 }
2892 currRing->pLexOrder = b;
2893 //Print("%d reductions canceled \n",strat->cel);
2894 HCord=strat->HCord;
2895 sigdrop = strat->sigdrop;
2896 sbaEnterS = strat->sbaEnterS;
2897 blockred = strat->blockred;
2898 delete(strat);
2899 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2900 }
2901 // Go to std
2902 if(sigdrop || blockred > blockedreductions)
2903 {
2904 r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2905 }
2906 return r;
2907 }
2908}
if(both_non_zero==0)
Definition: cfEzgcd.cc:91
bool sigdrop
Definition: kutil.h:363
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:292
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:294
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:296
intvec * kHomW
Definition: kutil.h:339
int blockred
Definition: kutil.h:368
unsigned sbaOrder
Definition: kutil.h:317
int blockredmax
Definition: kutil.h:369
int newIdeal
Definition: kutil.h:360
char z2homog
Definition: kutil.h:378
char no_prod_crit
Definition: kutil.h:398
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.h:291
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:295
int sbaEnterS
Definition: kutil.h:366
#define idTest(id)
Definition: ideals.h:47
KINLINE BOOLEAN arriRewDummy(poly, unsigned long, poly, kStrategy, int)
Definition: kInline.h:1230
static ideal nc_GB(const ideal F, const ideal Q, const intvec *w, const intvec *hilb, kStrategy strat, const ring r)
Definition: nc.h:27
long kHomModDeg(poly p, ring r)
Definition: kstd1.cc:2417
VAR intvec * kHomW
Definition: kstd1.cc:2405
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2734
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition: kutil.cc:6876
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition: kutil.cc:6851
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition: kutil.cc:1975
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition: kutil.cc:6792
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3476
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3240
#define TEST_OPT_SB_1
Definition: options.h:119

◆ kStd()

ideal kStd ( ideal  F,
ideal  Q,
tHomog  h,
intvec **  mw,
intvec hilb = NULL,
int  syzComp = 0,
int  newIdeal = 0,
intvec vw = NULL,
s_poly_proc_t  sp = NULL 
)

Definition at line 2430 of file kstd1.cc.

2432{
2433 if(idIs0(F))
2434 return idInit(1,F->rank);
2435
2436#ifdef HAVE_SHIFTBBA
2437 if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
2438#endif
2439
2440 ideal r;
2441 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2442 BOOLEAN delete_w=(w==NULL);
2443 kStrategy strat=new skStrategy;
2444
2445 strat->s_poly=sp;
2447 strat->syzComp = syzComp;
2448 if (TEST_OPT_SB_1
2450 )
2451 strat->newIdeal = newIdeal;
2453 strat->LazyPass=20;
2454 else
2455 strat->LazyPass=2;
2456 strat->LazyDegree = 1;
2457 strat->ak = id_RankFreeModule(F,currRing);
2458 strat->kModW=kModW=NULL;
2459 strat->kHomW=kHomW=NULL;
2460 if (vw != NULL)
2461 {
2462 currRing->pLexOrder=FALSE;
2463 strat->kHomW=kHomW=vw;
2464 strat->pOrigFDeg = currRing->pFDeg;
2465 strat->pOrigLDeg = currRing->pLDeg;
2467 toReset = TRUE;
2468 }
2469 if (h==testHomog)
2470 {
2471 if (strat->ak == 0)
2472 {
2473 h = (tHomog)idHomIdeal(F,Q);
2474 w=NULL;
2475 }
2476 else if (!TEST_OPT_DEGBOUND)
2477 {
2478 if (w!=NULL)
2479 h = (tHomog)idHomModule(F,Q,w);
2480 else
2481 h = (tHomog)idHomIdeal(F,Q);
2482 }
2483 }
2484 currRing->pLexOrder=b;
2485 if (h==isHomog)
2486 {
2487 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2488 {
2489 strat->kModW = kModW = *w;
2490 if (vw == NULL)
2491 {
2492 strat->pOrigFDeg = currRing->pFDeg;
2493 strat->pOrigLDeg = currRing->pLDeg;
2495 toReset = TRUE;
2496 }
2497 }
2498 currRing->pLexOrder = TRUE;
2499 if (hilb==NULL) strat->LazyPass*=2;
2500 }
2501 strat->homog=h;
2502#ifdef KDEBUG
2503 idTest(F);
2504 if (Q!=NULL) idTest(Q);
2505#endif
2506#ifdef HAVE_PLURAL
2508 {
2509 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2510 strat->no_prod_crit = ! bIsSCA;
2511 if (w!=NULL)
2512 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2513 else
2514 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2515 }
2516 else
2517#endif
2518 {
2519 #if PRE_INTEGER_CHECK
2520 //the preinteger check strategy is not for modules
2521 if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2522 {
2523 ideal FCopy = idCopy(F);
2524 poly pFmon = preIntegerCheck(FCopy, Q);
2525 if(pFmon != NULL)
2526 {
2527 idInsertPoly(FCopy, pFmon);
2528 strat->kModW=kModW=NULL;
2529 if (h==testHomog)
2530 {
2531 if (strat->ak == 0)
2532 {
2533 h = (tHomog)idHomIdeal(FCopy,Q);
2534 w=NULL;
2535 }
2536 else if (!TEST_OPT_DEGBOUND)
2537 {
2538 if (w!=NULL)
2539 h = (tHomog)idHomModule(FCopy,Q,w);
2540 else
2541 h = (tHomog)idHomIdeal(FCopy,Q);
2542 }
2543 }
2544 currRing->pLexOrder=b;
2545 if (h==isHomog)
2546 {
2547 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2548 {
2549 strat->kModW = kModW = *w;
2550 if (vw == NULL)
2551 {
2552 strat->pOrigFDeg = currRing->pFDeg;
2553 strat->pOrigLDeg = currRing->pLDeg;
2555 toReset = TRUE;
2556 }
2557 }
2558 currRing->pLexOrder = TRUE;
2559 if (hilb==NULL) strat->LazyPass*=2;
2560 }
2561 strat->homog=h;
2562 }
2563 omTestMemory(1);
2564 if(w == NULL)
2565 {
2567 r=mora(FCopy,Q,NULL,hilb,strat);
2568 else
2569 r=bba(FCopy,Q,NULL,hilb,strat);
2570 }
2571 else
2572 {
2574 r=mora(FCopy,Q,*w,hilb,strat);
2575 else
2576 r=bba(FCopy,Q,*w,hilb,strat);
2577 }
2578 idDelete(&FCopy);
2579 }
2580 else
2581 #endif
2582 {
2583 if(w==NULL)
2584 {
2586 r=mora(F,Q,NULL,hilb,strat);
2587 else
2588 r=bba(F,Q,NULL,hilb,strat);
2589 }
2590 else
2591 {
2593 r=mora(F,Q,*w,hilb,strat);
2594 else
2595 r=bba(F,Q,*w,hilb,strat);
2596 }
2597 }
2598 }
2599#ifdef KDEBUG
2600 idTest(r);
2601#endif
2602 if (toReset)
2603 {
2604 kModW = NULL;
2606 }
2607 currRing->pLexOrder = b;
2608//Print("%d reductions canceled \n",strat->cel);
2609 HCord=strat->HCord;
2610 delete(strat);
2611 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2612 return r;
2613}
s_poly_proc_t s_poly
Definition: kutil.h:301
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition: coeffs.h:840
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, intvec *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition: kstd1.cc:2911
poly preIntegerCheck(const ideal Forig, const ideal Q)
used for GB over ZZ: look for constant and monomial elements in the ideal background: any known const...
Definition: kutil.cc:10780
omError_t omTestMemory(int check_level)
Definition: omDebug.c:94
static BOOLEAN rIsLPRing(const ring r)
Definition: ring.h:411

◆ kStdShift()

ideal kStdShift ( ideal  F,
ideal  Q,
tHomog  h,
intvec **  mw,
intvec hilb = NULL,
int  syzComp = 0,
int  newIdeal = 0,
intvec vw = NULL,
BOOLEAN  rightGB = FALSE 
)

Definition at line 2911 of file kstd1.cc.

2913{
2915 assume(idIsInV(F));
2916 ideal r;
2917 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2918 BOOLEAN delete_w=(w==NULL);
2919 kStrategy strat=new skStrategy;
2920 intvec* temp_w=NULL;
2921
2922 strat->rightGB = rightGB;
2923
2925 strat->syzComp = syzComp;
2926 if (TEST_OPT_SB_1)
2928 strat->newIdeal = newIdeal;
2930 strat->LazyPass=20;
2931 else
2932 strat->LazyPass=2;
2933 strat->LazyDegree = 1;
2934 strat->ak = id_RankFreeModule(F,currRing);
2935 strat->kModW=kModW=NULL;
2936 strat->kHomW=kHomW=NULL;
2937 if (vw != NULL)
2938 {
2939 currRing->pLexOrder=FALSE;
2940 strat->kHomW=kHomW=vw;
2941 strat->pOrigFDeg = currRing->pFDeg;
2942 strat->pOrigLDeg = currRing->pLDeg;
2944 toReset = TRUE;
2945 }
2946 if (h==testHomog)
2947 {
2948 if (strat->ak == 0)
2949 {
2950 h = (tHomog)idHomIdeal(F,Q);
2951 w=NULL;
2952 }
2953 else if (!TEST_OPT_DEGBOUND)
2954 {
2955 if (w!=NULL)
2956 h = (tHomog)idHomModule(F,Q,w);
2957 else
2958 h = (tHomog)idHomIdeal(F,Q);
2959 }
2960 }
2961 currRing->pLexOrder=b;
2962 if (h==isHomog)
2963 {
2964 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2965 {
2966 strat->kModW = kModW = *w;
2967 if (vw == NULL)
2968 {
2969 strat->pOrigFDeg = currRing->pFDeg;
2970 strat->pOrigLDeg = currRing->pLDeg;
2972 toReset = TRUE;
2973 }
2974 }
2975 currRing->pLexOrder = TRUE;
2976 if (hilb==NULL) strat->LazyPass*=2;
2977 }
2978 strat->homog=h;
2979#ifdef KDEBUG
2980 idTest(F);
2981#endif
2983 {
2984 /* error: no local ord yet with shifts */
2985 WerrorS("No local ordering possible for shift algebra");
2986 return(NULL);
2987 }
2988 else
2989 {
2990 /* global ordering */
2991 if (w!=NULL)
2992 r=bbaShift(F,Q,*w,hilb,strat);
2993 else
2994 r=bbaShift(F,Q,NULL,hilb,strat);
2995 }
2996#ifdef KDEBUG
2997 idTest(r);
2998#endif
2999 if (toReset)
3000 {
3001 kModW = NULL;
3003 }
3004 currRing->pLexOrder = b;
3005//Print("%d reductions canceled \n",strat->cel);
3006 HCord=strat->HCord;
3007 delete(strat);
3008 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
3009 assume(idIsInV(r));
3010 return r;
3011}
char rightGB
Definition: kutil.h:373
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:4345
#define idIsInV(I)
Definition: shiftop.h:49

◆ kVerify()

BOOLEAN kVerify ( ideal  F,
ideal  Q 
)

◆ mora()

ideal mora ( ideal  F,
ideal  Q,
intvec w,
intvec hilb,
kStrategy  strat 
)

Definition at line 1859 of file kstd1.cc.

1860{
1861 int olddeg = 0;
1862 int reduc = 0;
1863 int red_result = 1;
1864 int hilbeledeg=1,hilbcount=0;
1865 BITSET save1;
1866 SI_SAVE_OPT1(save1);
1868 {
1869 si_opt_1 &= ~Sy_bit(OPT_REDSB);
1870 si_opt_1 &= ~Sy_bit(OPT_REDTAIL);
1871 }
1872
1873 strat->update = TRUE;
1874 /*- setting global variables ------------------- -*/
1875 initBuchMoraCrit(strat);
1876 initHilbCrit(F,Q,&hilb,strat);
1877 initMora(F,strat);
1879 initBuchMoraPosRing(strat);
1880 else
1881 initBuchMoraPos(strat);
1882 /*Shdl=*/initBuchMora(F,Q,strat);
1883 if (TEST_OPT_FASTHC) missingAxis(&strat->lastAxis,strat);
1884 /*updateS in initBuchMora has Hecketest
1885 * and could have put strat->kHEdgdeFound FALSE*/
1886 if ((currRing->ppNoether)!=NULL)
1887 {
1888 strat->kHEdgeFound = TRUE;
1889 }
1890 if (strat->kHEdgeFound && strat->update)
1891 {
1892 firstUpdate(strat);
1893 updateLHC(strat);
1894 reorderL(strat);
1895 }
1896 if (TEST_OPT_FASTHC && (strat->lastAxis) && strat->posInLOldFlag)
1897 {
1898 strat->posInLOld = strat->posInL;
1899 strat->posInLOldFlag = FALSE;
1900 strat->posInL = posInL10;
1901 updateL(strat);
1902 reorderL(strat);
1903 }
1904 kTest_TS(strat);
1905 strat->use_buckets = kMoraUseBucket(strat);
1906
1907#ifdef HAVE_TAIL_RING
1908 if (strat->homog && strat->red == redFirst)
1909 if(!idIs0(F) &&(!rField_is_Ring(currRing)))
1911#endif
1912
1913 if (BVERBOSE(23))
1914 {
1915 kDebugPrint(strat);
1916 }
1917//deleteInL(strat->L,&strat->Ll,1,strat);
1918//deleteInL(strat->L,&strat->Ll,0,strat);
1919
1920 /*- compute-------------------------------------------*/
1921 while (strat->Ll >= 0)
1922 {
1923 #ifdef KDEBUG
1924 if (TEST_OPT_DEBUG) messageSets(strat);
1925 #endif
1926 if (siCntrlc)
1927 {
1928 while (strat->Ll >= 0)
1929 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1930 strat->noClearS=TRUE;
1931 }
1933 && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
1934 {
1935 /*
1936 * stops computation if
1937 * - 24 (degBound)
1938 * && upper degree is bigger than Kstd1_deg
1939 */
1940 while ((strat->Ll >= 0)
1941 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1942 && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
1943 )
1944 {
1945 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1946 //if (TEST_OPT_PROT)
1947 //{
1948 // PrintS("D"); mflush();
1949 //}
1950 }
1951 if (strat->Ll<0) break;
1952 else strat->noClearS=TRUE;
1953 }
1954 strat->P = strat->L[strat->Ll];/*- picks the last element from the lazyset L -*/
1955 if (strat->Ll==0) strat->interpt=TRUE;
1956 strat->Ll--;
1957 // create the real Spoly
1958 if (pNext(strat->P.p) == strat->tail)
1959 {
1960 /*- deletes the short spoly and computes -*/
1962 pLmDelete(strat->P.p);
1963 else
1964 pLmFree(strat->P.p);
1965 strat->P.p = NULL;
1966 poly m1 = NULL, m2 = NULL;
1967 // check that spoly creation is ok
1968 while (strat->tailRing != currRing &&
1969 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1970 {
1971 assume(m1 == NULL && m2 == NULL);
1972 // if not, change to a ring where exponents are large enough
1973 kStratChangeTailRing(strat);
1974 }
1975 /* create the real one */
1976 ksCreateSpoly(&(strat->P), strat->kNoetherTail(), strat->use_buckets,
1977 strat->tailRing, m1, m2, strat->R);
1978 if (!strat->use_buckets)
1979 strat->P.SetLength(strat->length_pLength);
1980 }
1981 else if (strat->P.p1 == NULL)
1982 {
1983 // for input polys, prepare reduction (buckets !)
1984 strat->P.SetLength(strat->length_pLength);
1985 strat->P.PrepareRed(strat->use_buckets);
1986 }
1987
1988 // the s-poly
1989 if (!strat->P.IsNull())
1990 {
1991 // might be NULL from noether !!!
1992 if (TEST_OPT_PROT)
1993 message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
1994 // reduce
1995 red_result = strat->red(&strat->P,strat);
1996 }
1997
1998 // the reduced s-poly
1999 if (! strat->P.IsNull())
2000 {
2001 strat->P.GetP();
2002 // statistics
2003 if (TEST_OPT_PROT) PrintS("s");
2004 // normalization
2006 strat->P.pCleardenom();
2007 else
2008 strat->P.pNorm();
2009 // tailreduction
2010 strat->P.p = redtail(&(strat->P),strat->sl,strat);
2011 if (strat->P.p==NULL)
2012 {
2013 WerrorS("expoent overflow - wrong ordering");
2014 return(idInit(1,1));
2015 }
2016 // set ecart -- might have changed because of tail reductions
2017 if ((!strat->noTailReduction) && (!strat->honey))
2018 strat->initEcart(&strat->P);
2019 // cancel unit
2020 cancelunit(&strat->P);
2021 // for char 0, clear denominators
2022 if ((strat->P.p->next==NULL) /* i.e. cancelunit did something*/
2024 strat->P.pCleardenom();
2025
2026 enterT(strat->P,strat);
2027 // build new pairs
2029 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2030 else
2031 enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2032 // put in S
2033 strat->enterS(strat->P,
2034 posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
2035 strat, strat->tl);
2036 // apply hilbert criterion
2037 if (hilb!=NULL)
2038 {
2039 if (strat->homog==isHomog)
2040 khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2041 else
2042 khCheckLocInhom(Q,w,hilb,hilbcount,strat);
2043 }
2044
2045 // clear strat->P
2046 kDeleteLcm(&strat->P);
2047
2048#ifdef KDEBUG
2049 // make sure kTest_TS does not complain about strat->P
2050 strat->P.Clear();
2051#endif
2052 }
2053 if (strat->kHEdgeFound)
2054 {
2055 if ((TEST_OPT_FINDET)
2056 || ((TEST_OPT_MULTBOUND) && (scMult0Int(strat->Shdl,NULL,strat->tailRing) < Kstd1_mu)))
2057 {
2058 // obachman: is this still used ???
2059 /*
2060 * stops computation if strat->kHEdgeFound and
2061 * - 27 (finiteDeterminacyTest)
2062 * or
2063 * - 23
2064 * (multBound)
2065 * && multiplicity of the ideal is smaller then a predefined number mu
2066 */
2067 while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2068 }
2069 }
2070 kTest_TS(strat);
2071 }
2072 /*- complete reduction of the standard basis------------------------ -*/
2073 if (TEST_OPT_REDSB) completeReduce(strat);
2074 else if (TEST_OPT_PROT) PrintLn();
2075 /*- release temp data------------------------------- -*/
2076 exitBuchMora(strat);
2077 /*- polynomials used for HECKE: HC, noether -*/
2078 if (TEST_OPT_FINDET)
2079 {
2080 if (strat->kHEdge!=NULL)
2081 Kstd1_mu=currRing->pFDeg(strat->kHEdge,currRing);
2082 else
2083 Kstd1_mu=-1;
2084 }
2085 if (strat->kHEdge!=NULL) pLmFree(&strat->kHEdge);
2086 strat->update = TRUE; //???
2087 strat->lastAxis = 0; //???
2088 if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2089 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2090 if ((TEST_OPT_PROT)||(TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
2091// if (TEST_OPT_WEIGHTM)
2092// {
2093// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2094// if (ecartWeights)
2095// {
2096// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2097// ecartWeights=NULL;
2098// }
2099// }
2100 if(nCoeff_is_Z(currRing->cf))
2101 finalReduceByMon(strat);
2102 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2103 SI_RESTORE_OPT1(save1);
2104 idTest(strat->Shdl);
2105 return (strat->Shdl);
2106}
KINLINE poly kNoetherTail()
Definition: kInline.h:66
ring tailRing
Definition: kutil.h:346
int Ll
Definition: kutil.h:354
int lastAxis
Definition: kutil.h:359
poly tail
Definition: kutil.h:337
char use_buckets
Definition: kutil.h:387
char interpt
Definition: kutil.h:375
LObject P
Definition: kutil.h:303
char noClearS
Definition: kutil.h:406
char length_pLength
Definition: kutil.h:391
char update
Definition: kutil.h:385
int scMult0Int(ideal S, ideal Q, const ring tailRing)
Definition: hdegree.cc:992
void khCheckLocInhom(ideal Q, intvec *w, intvec *hilb, int &count, kStrategy strat)
Definition: khstd.cc:133
void khCheck(ideal Q, intvec *w, intvec *hilb, int &eledeg, int &count, kStrategy strat)
Definition: khstd.cc:28
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition: kspoly.cc:1167
void firstUpdate(kStrategy strat)
Definition: kstd1.cc:1539
void updateLHC(kStrategy strat)
Definition: kstd1.cc:1446
void missingAxis(int *last, kStrategy strat)
Definition: kstd1.cc:1261
void reorderL(kStrategy strat)
Definition: kstd1.cc:1203
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition: kstd1.cc:1342
static BOOLEAN kMoraUseBucket(kStrategy strat)
Definition: kstd1.cc:3821
void updateL(kStrategy strat)
Definition: kstd1.cc:1375
EXTERN_VAR int Kstd1_mu
Definition: kstd1.h:49
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:7706
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:9995
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:1071
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4525
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9652
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition: kutil.cc:11205
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:10079
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:4701
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10718
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10320
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4494
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1244
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11305
void messageSets(kStrategy strat)
Definition: kutil.cc:7779
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7747
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition: kutil.cc:11112
void cancelunit(LObject *L, BOOLEAN inNF)
Definition: kutil.cc:343
static void kDeleteLcm(LObject *P)
Definition: kutil.h:877
VAR BOOLEAN siCntrlc
Definition: options.c:14
#define TEST_OPT_FINDET
Definition: options.h:111
#define OPT_REDSB
Definition: options.h:76
#define TEST_OPT_MULTBOUND
Definition: options.h:114
#define TEST_OPT_FASTHC
Definition: options.h:109
BOOLEAN rHasMixedOrdering(const ring r)
Definition: ring.h:763

◆ rightgb()

ideal rightgb ( ideal  F,
ideal  Q 
)

Definition at line 4708 of file kstd2.cc.

4709{
4711 assume(idIsInV(F));
4712 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4713 idSkipZeroes(RS); // is this even necessary?
4714 assume(idIsInV(RS));
4715 return(RS);
4716}

◆ stdred()

ideal stdred ( ideal  F,
ideal  Q,
tHomog  h,
intvec **  w 
)

Variable Documentation

◆ kHomW

Definition at line 70 of file kstd1.h.

◆ kModW

Definition at line 69 of file kstd1.h.

◆ kOptions

EXTERN_VAR BITSET kOptions

Definition at line 51 of file kstd1.h.

◆ Kstd1_deg

EXTERN_VAR int Kstd1_deg

Definition at line 49 of file kstd1.h.

◆ Kstd1_mu

EXTERN_VAR int Kstd1_mu

Definition at line 49 of file kstd1.h.

◆ LazyDegree

EXTERN_VAR int LazyDegree

Definition at line 49 of file kstd1.h.

◆ LazyPass

EXTERN_VAR int LazyPass

Definition at line 49 of file kstd1.h.

◆ validOpts

EXTERN_VAR BITSET validOpts

Definition at line 53 of file kstd1.h.