My Project
Loading...
Searching...
No Matches
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)
 
ideal idDivRem (ideal A, const ideal quot, ideal &factor, ideal *unit, 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.
 
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, const ideal Q)
 
void initMora (ideal F, kStrategy strat)
 
ideal kInterRed (ideal F, const ideal Q=NULL)
 
ideal kInterRedOld (ideal F, const ideal Q=NULL)
 
long kModDeg (poly p, const ring r=currRing)
 
long kHomModDeg (poly p, const 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 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

◆ idDivRem()

ideal idDivRem ( ideal  A,
const ideal  quot,
ideal factor,
ideal unit,
int  lazyReduce = 0 
)

Definition at line 347 of file kLiftstd.cc.

348{
349 /* special cases */
350 if (idIs0(A) || idIs0(quot))
351 {
353 setUnit(A->rank,unit);
354 return idCopy(A);
355 }
356 /* ideal or module? */
359 int lsmod=0;
360 if (k==0) { lsmod=1;k=1;} /*ideal*/
361 /* new ring */
365 /* move ideals to new ring */
367 ideal s_A;
368 if (orig_ring != syz_ring)
369 {
372 }
373 else
374 {
377 }
378 /* quot[i] -> quot[i]+e(k+i+1) */
379 for(int i=0;i<IDELEMS(s_quot);i++)
380 {
382 poly p=p_One(syz_ring);
385 s_quot->m[i]=p_Add_q(s_quot->m[i],p,syz_ring);
386 }
387 s_quot->rank=k+IDELEMS(quot)+1;
388 /* A[i] -> A[i]*e(1) */
389 if (lsmod==1)
390 {
391 for(int i=0;i<IDELEMS(s_A);i++)
392 {
393 p_Shift(&s_A->m[i],1,syz_ring);
394 }
395 }
396 if (unit!=NULL)
397 {
398 int u_k=k+IDELEMS(quot)+2;
399 for(int i=0;i<IDELEMS(s_A);i++)
400 {
401 poly p=p_One(syz_ring);
404 s_A->m[i]=p_Add_q(s_A->m[i],p,syz_ring);
405 }
406 s_A->rank=k+IDELEMS(quot)+IDELEMS(A)+1;
407 }
408 /* normalform */
410 /* clean s_quot,s_A */
413 /* interpret rest: remainder */
415 for(int i=0;i<IDELEMS(rest);i++)
416 {
417 poly p=rest->m[i];
418 poly d=NULL;
419 while(p!=NULL)
420 {
421 poly q=p; pIter(p);
422 pNext(q)=NULL;
423 if (p_GetComp(q,syz_ring)<=k)
424 {
425 result->m[i]=p_Add_q(result->m[i],q,syz_ring);
426 }
427 else
428 {
429 d=p_Add_q(d,q,syz_ring);
430 }
431 }
432 rest->m[i]=d;
434 }
435 /* interpret rest: factors */
437 if (unit==NULL)
438 {
439 for(int i=0;i<IDELEMS(rest);i++)
440 {
441 poly p=rest->m[i];
442 p_Shift(&p,-k-lsmod-1,syz_ring);
443 factor->m[i]=p;
444 factor->m[i]=p_Neg(factor->m[i],syz_ring);
445 rest->m[i]=NULL;
446 }
447 }
448 else
449 {
451 /* comp k+1..u_k-1 -> rest, u_k.. -> unit*/
452 int u_k=k+IDELEMS(quot)+2;
453 for(int i=0;i<IDELEMS(rest);i++)
454 {
455 poly p=rest->m[i];
456 rest->m[i]=NULL;
457 poly d=NULL;
458 while(p!=NULL)
459 {
460 poly q=p; pIter(p);
461 pNext(q)=NULL;
462 if(p_GetComp(q,syz_ring)<u_k)
463 {
464 p_Shift(&q,-k-1,syz_ring);
465 factor->m[i]=p_Add_q(factor->m[i],q,syz_ring);
466 }
467 else
468 {
469 d=p_Add_q(d,q,syz_ring);
470 }
471 }
472 (*unit)->m[i]=d;
473 /*fix sign:*/
474 factor->m[i]=p_Neg(factor->m[i],syz_ring);
475 p_Shift(&(*unit)->m[i],-(IDELEMS(quot)+k+1),syz_ring);
476 }
477 }
479 if (orig_ring != syz_ring)
480 {
484 if (unit!=NULL)
485 {
487 }
489 }
490 return result;
491}
#define TRUE
Definition auxiliary.h:100
int i
Definition cfEzgcd.cc:132
int k
Definition cfEzgcd.cc:99
int p
Definition cfModGcd.cc:4078
return result
CanonicalForm factor
Definition facAbsFact.cc:97
ideal id_Copy(ideal h1, const ring r)
copy an ideal
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
ideal idCopy(ideal A)
Definition ideals.h:60
static void setUnit(int e, ideal *unit)
Definition kLiftstd.cc:334
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition kstd1.cc:3235
#define p_GetComp(p, r)
Definition monomials.h:64
#define pIter(p)
Definition monomials.h:37
#define pNext(p)
Definition monomials.h:36
#define NULL
Definition omList.c:12
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition p_polys.cc:4706
poly p_One(const ring r)
Definition p_polys.cc:1313
static poly p_Neg(poly p, const ring r)
Definition p_polys.h:1107
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:936
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition p_polys.h:247
static void p_Setm(poly p, const ring r)
Definition p_polys.h:233
void rChangeCurrRing(ring r)
Definition polys.cc:15
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition prCopy.cc:248
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition prCopy.cc:261
ideal idrCopyR_NoSort(ideal id, ring src_r, ring dest_r)
Definition prCopy.cc:205
ring rAssure_SyzOrder(const ring r, BOOLEAN complete)
Definition ring.cc:4444
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:450
void rSetSyzComp(int k, const ring r)
Definition ring.cc:5152
ideal idInit(int idsize, int rank)
initialise an ideal / module
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
#define IDELEMS(i)
#define A
Definition sirandom.c:24

◆ initMora()

void initMora ( ideal  F,
kStrategy  strat 
)

!

Definition at line 1819 of file kstd1.cc.

1820{
1821 int i,j;
1822
1823 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1824 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1825 strat->enterS = enterSMora;
1826 strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1827 strat->posInLOld = strat->posInL;
1828 strat->posInLOldFlag = TRUE;
1829 strat->initEcart = initEcartNormal;
1830 strat->kAllAxis = (currRing->ppNoether) != NULL; //!!
1831 if ( currRing->ppNoether != NULL )
1832 {
1833 strat->kNoether = pCopy((currRing->ppNoether));
1834 strat->red = redFirst; /*take the first possible in T*/
1835 if (TEST_OPT_PROT)
1836 {
1837 Print("H(%ld)",p_FDeg(currRing->ppNoether,currRing)+1);
1838 mflush();
1839 }
1840 }
1841 else if (strat->homog)
1842 strat->red = redFirst; /*take the first possible in T*/
1843 else
1844 strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1845 if (currRing->ppNoether != NULL)
1846 {
1847 HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1848 }
1849 else
1850 {
1851 HCord = 32000;/*- very large -*/
1852 }
1853
1855 {
1856 if (rField_is_Z(currRing))
1857 strat->red = redRiloc_Z;
1858 else
1859 strat->red = redRiloc;
1860 }
1861
1862 /*reads the ecartWeights used for Graebes method from the
1863 *intvec ecart and set ecartWeights
1864 */
1865 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1866 {
1867 //interred machen Aenderung
1868 strat->pOrigFDeg=currRing->pFDeg;
1869 strat->pOrigLDeg=currRing->pLDeg;
1870 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1871 /*uses automatic computation of the ecartWeights to set them*/
1873
1875 if (TEST_OPT_PROT)
1876 {
1877 for(i=1; i<=(currRing->N); i++)
1878 Print(" %d",ecartWeights[i]);
1879 PrintLn();
1880 mflush();
1881 }
1882 }
1883 kOptimizeLDeg(currRing->pLDeg, strat);
1884}
int BOOLEAN
Definition auxiliary.h:87
char posInLOldFlag
Definition kutil.h:382
poly kNoether
Definition kutil.h:329
BOOLEAN * NotUsedAxis
Definition kutil.h:332
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.h:284
pFDegProc pOrigFDeg
Definition kutil.h:296
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition kutil.h:288
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition kutil.h:287
char kAllAxis
Definition kutil.h:376
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition kutil.h:286
void(* initEcart)(TObject *L)
Definition kutil.h:280
int(* red)(LObject *L, kStrategy strat)
Definition kutil.h:278
char homog
Definition kutil.h:372
pLDegProc pOrigLDeg
Definition kutil.h:297
#define Print
Definition emacs.cc:80
int j
Definition facHensel.cc:110
int redFirst(LObject *h, kStrategy strat)
Definition kstd1.cc:797
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:387
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1628
int redRiloc_Z(LObject *h, kStrategy strat)
Definition kstd1.cc:568
VAR int HCord
Definition kutil.cc:246
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition kutil.cc:1325
void initEcartNormal(TObject *h)
Definition kutil.cc:1303
#define omAlloc(size)
#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:3637
static long p_FDeg(const poly p, const ring r)
Definition p_polys.h:380
#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_Z(const ring r)
Definition ring.h:509
#define rField_is_Ring(R)
Definition ring.h:485
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 3449 of file kstd1.cc.

3450{
3451 const ring save = currRing;
3453 poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3455 return ret;
3456}
#define Q
Definition sirandom.c:26

◆ kHomModDeg()

long kHomModDeg ( poly  p,
const ring  r = currRing 
)

Definition at line 2436 of file kstd1.cc.

2437{
2438 int i;
2439 long j=0;
2440
2441 for (i=r->N;i>0;i--)
2442 j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2443 if (kModW == NULL) return j;
2444 i = __p_GetComp(p,r);
2445 if (i==0) return j;
2446 return j+(*kModW)[i-1];
2447}
VAR intvec * kModW
Definition kstd1.cc:2424
#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,
const ideal  Q = NULL 
)

Definition at line 3814 of file kstd1.cc.

3815{
3816#ifdef HAVE_PLURAL
3817 if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3818#endif
3821 )
3822 return kInterRedOld(F,Q);
3823
3824 //return kInterRedOld(F,Q);
3825
3826 BITSET save1;
3828 //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3830 //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3831 //si_opt_1&= ~Sy_bit(OPT_REDSB);
3832 //extern char * showOption() ;
3833 //Print("%s\n",showOption());
3834
3835 int need_retry;
3836 int counter=3;
3837 ideal res, res1;
3838 int elems;
3839 ideal null=NULL;
3840 if ((Q==NULL) || (!TEST_OPT_REDSB))
3841 {
3842 elems=idElem(F);
3844 }
3845 else
3846 {
3847 ideal FF=idSimpleAdd(F,Q);
3849 idDelete(&FF);
3850 null=idInit(1,1);
3851 if (need_retry)
3853 else
3854 res1=kNF(null,Q,res);
3855 idDelete(&res);
3856 res=res1;
3857 need_retry=1;
3858 }
3859 if (idElem(res)<=1) need_retry=0;
3860 while (need_retry && (counter>0))
3861 {
3862 #ifdef KDEBUG
3863 if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3864 #endif
3866 int new_elems=idElem(res1);
3867 counter -= (new_elems >= elems);
3868 elems = new_elems;
3869 idDelete(&res);
3870 if (idElem(res1)<=1) need_retry=0;
3871 if ((Q!=NULL) && (TEST_OPT_REDSB))
3872 {
3873 if (need_retry)
3875 else
3876 res=kNF(null,Q,res1);
3877 idDelete(&res1);
3878 }
3879 else
3880 res = res1;
3881 if (idElem(res)<=1) need_retry=0;
3882 }
3883 if (null!=NULL) idDelete(&null);
3886 return res;
3887}
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 kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition kstd1.cc:3554
ideal kInterRedOld(ideal F, const ideal Q)
Definition kstd1.cc:3462
#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:515
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition ring.h:762
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
static int idElem(const ideal F)
number of non-zero polys in F
#define BITSET
Definition structs.h:16

◆ kInterRedOld()

ideal kInterRedOld ( ideal  F,
const ideal  Q = NULL 
)

Definition at line 3462 of file kstd1.cc.

3463{
3464 int j;
3465 kStrategy strat = new skStrategy;
3466
3467 ideal tempF = F;
3468 ideal tempQ = Q;
3469
3470#ifdef HAVE_PLURAL
3471 if(rIsSCA(currRing))
3472 {
3473 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3474 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3476
3477 // this should be done on the upper level!!! :
3478 // tempQ = SCAQuotient(currRing);
3479
3480 if(Q == currRing->qideal)
3482 }
3483#endif
3484
3485// if (TEST_OPT_PROT)
3486// {
3487// writeTime("start InterRed:");
3488// mflush();
3489// }
3490 //strat->syzComp = 0;
3491 strat->kAllAxis = (currRing->ppNoether) != NULL;
3492 strat->kNoether=pCopy((currRing->ppNoether));
3494 initBuchMoraCrit(strat);
3495 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3496 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3497 strat->enterS = enterSBba;
3498 strat->posInT = posInT17;
3499 strat->initEcart = initEcartNormal;
3500 strat->sl = -1;
3501 strat->tl = -1;
3502 strat->tmax = setmaxT;
3503 strat->T = initT();
3504 strat->R = initR();
3505 strat->sevT = initsevT();
3507 initS(tempF, tempQ, strat);
3508 if (TEST_OPT_REDSB)
3509 strat->noTailReduction=FALSE;
3510 updateS(TRUE,strat);
3512 completeReduce(strat);
3513 //else if (TEST_OPT_PROT) PrintLn();
3514 cleanT(strat);
3515 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
3516 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3517 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3518 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3519 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3520 omfree(strat->sevT);
3521 omfree(strat->S_2_R);
3522 omfree(strat->R);
3523
3524 if (strat->fromQ)
3525 {
3526 for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3527 {
3528 if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3529 }
3530 omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
3531 }
3532// if (TEST_OPT_PROT)
3533// {
3534// writeTime("end Interred:");
3535// mflush();
3536// }
3537 ideal shdl=strat->Shdl;
3539 if (strat->fromQ)
3540 {
3541 strat->fromQ=NULL;
3543 idDelete(&shdl);
3544 shdl=res;
3545 }
3546 delete(strat);
3547#ifdef HAVE_PLURAL
3548 if( tempF != F )
3550#endif
3551 return shdl;
3552}
#define FALSE
Definition auxiliary.h:96
int * S_2_R
Definition kutil.h:342
char noTailReduction
Definition kutil.h:378
TSet T
Definition kutil.h:326
intset ecartS
Definition kutil.h:309
char honey
Definition kutil.h:377
int ak
Definition kutil.h:353
TObject ** R
Definition kutil.h:340
int tl
Definition kutil.h:350
unsigned long * sevT
Definition kutil.h:325
ideal Shdl
Definition kutil.h:303
int tmax
Definition kutil.h:350
intset fromQ
Definition kutil.h:321
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition kutil.h:281
int sl
Definition kutil.h:348
unsigned long * sevS
Definition kutil.h:322
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, const ideal Q)
Definition kstd1.cc:3814
int posInT17(const TSet set, const int length, LObject &p)
Definition kutil.cc:5305
void initS(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7634
void updateS(BOOLEAN toT, kStrategy strat)
Definition kutil.cc:8593
void cleanT(kStrategy strat)
Definition kutil.cc:564
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9475
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition kutil.cc:10339
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8828
#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:1518
#define omfree(addr)
#define omFreeSize(addr, size)
#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

◆ 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 3085 of file kstd1.cc.

3087{
3088 if(idIs0(F))
3089 {
3090 M=idInit(1,F->rank);
3091 return idInit(1,F->rank);
3092 }
3094 {
3095 ideal sb;
3096 sb = kStd(F, Q, h, w, hilb);
3098 if(IDELEMS(sb) <= IDELEMS(F))
3099 {
3100 M = idCopy(sb);
3101 idSkipZeroes(M);
3102 return(sb);
3103 }
3104 else
3105 {
3106 M = idCopy(F);
3107 idSkipZeroes(M);
3108 return(sb);
3109 }
3110 }
3111 ideal r=NULL;
3112 int Kstd1_OldDeg = Kstd1_deg,i;
3114 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3117 kStrategy strat=new skStrategy;
3118
3120 strat->syzComp = syzComp;
3122 strat->LazyPass=20;
3123 else
3124 strat->LazyPass=2;
3125 strat->LazyDegree = 1;
3126 strat->minim=(reduced % 2)+1;
3127 strat->ak = id_RankFreeModule(F,currRing);
3128 if (delete_w)
3129 {
3130 temp_w=new intvec((strat->ak)+1);
3131 w = &temp_w;
3132 }
3133 if (h==testHomog)
3134 {
3135 if (strat->ak == 0)
3136 {
3137 h = (tHomog)idHomIdeal(F,Q);
3138 w=NULL;
3139 }
3140 else
3141 {
3142 h = (tHomog)idHomModule(F,Q,w);
3143 }
3144 }
3145 if (h==isHomog)
3146 {
3147 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3148 {
3149 kModW = *w;
3150 strat->kModW = *w;
3151 assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3152 strat->pOrigFDeg = currRing->pFDeg;
3153 strat->pOrigLDeg = currRing->pLDeg;
3155
3156 toReset = TRUE;
3157 if (reduced>1)
3158 {
3160 Kstd1_deg = -1;
3161 for (i=IDELEMS(F)-1;i>=0;i--)
3162 {
3163 if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3164 Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3165 }
3166 }
3167 }
3168 currRing->pLexOrder = TRUE;
3169 strat->LazyPass*=2;
3170 }
3171 strat->homog=h;
3172 ideal SB=NULL;
3174 {
3175 r=idMinBase(F,&SB); // SB and M via minbase
3176 strat->M=r;
3177 r=SB;
3178 }
3179 else
3180 {
3181 if (w!=NULL)
3182 r=bba(F,Q,*w,hilb,strat);
3183 else
3184 r=bba(F,Q,NULL,hilb,strat);
3185 }
3186#ifdef KDEBUG
3187 {
3188 int i;
3189 for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3190 }
3191#endif
3192 idSkipZeroes(r);
3193 if (toReset)
3194 {
3196 kModW = NULL;
3197 }
3198 currRing->pLexOrder = b;
3199 if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3200 if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3201 {
3202 M=idInit(1,F->rank);
3203 M->m[0]=pOne();
3204 //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3205 if (strat->M!=NULL) idDelete(&strat->M);
3206 }
3207 else if (strat->M==NULL)
3208 {
3209 M=idInit(1,F->rank);
3210 WarnS("no minimal generating set computed");
3211 }
3212 else
3213 {
3214 idSkipZeroes(strat->M);
3215 M=strat->M;
3216 }
3217 delete(strat);
3218 if (reduced>2)
3219 {
3221 if (!oldDegBound)
3222 si_opt_1 &= ~Sy_bit(OPT_DEGBOUND);
3223 }
3224 else
3225 {
3226 if (IDELEMS(M)>IDELEMS(r))
3227 {
3228 idDelete(&M);
3229 M=idCopy(r);
3230 }
3231 }
3232 return r;
3233}
CanonicalForm b
Definition cfModGcd.cc:4103
intvec * kModW
Definition kutil.h:335
int syzComp
Definition kutil.h:354
int minim
Definition kutil.h:357
ideal M
Definition kutil.h:305
int LazyPass
Definition kutil.h:353
int LazyDegree
Definition kutil.h:353
#define WarnS
Definition emacs.cc:78
const CanonicalForm & w
Definition facAbsFact.cc:51
ideal idMinBase(ideal h1, ideal *SB)
Definition ideals.cc:51
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
STATIC_VAR Poly * h
Definition janet.cc:971
long kModDeg(poly p, const ring r)
Definition kstd1.cc:2426
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:2483
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:50
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:2626
#define assume(x)
Definition mod2.h:389
#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:3649
#define pTest(p)
Definition polys.h:414
#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:548
#define M
Definition sirandom.c:25
tHomog
Definition structs.h:35
@ isHomog
Definition structs.h:37
@ testHomog
Definition structs.h:38

◆ kModDeg()

long kModDeg ( poly  p,
const ring  r = currRing 
)

Definition at line 2426 of file kstd1.cc.

2427{
2428 long o=p_WDegree(p, r);
2429 long i=__p_GetComp(p, r);
2430 if (i==0) return o;
2431 //assume((i>0) && (i<=kModW->length()));
2432 if (i<=kModW->length())
2433 return o+(*kModW)[i-1];
2434 return o;
2435}
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
long p_WDegree(poly p, const ring r)
Definition p_polys.cc:714

◆ kNF() [1/2]

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

Definition at line 3333 of file kstd1.cc.

3334{
3335 ideal res;
3336 if (TEST_OPT_PROT)
3337 {
3338 Print("(S:%d)",IDELEMS(p));mflush();
3339 }
3340 if (idIs0(p))
3341 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3342
3343 ideal pp = p;
3344#ifdef HAVE_PLURAL
3345 if(rIsSCA(currRing))
3346 {
3347 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3348 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3350
3351 if(Q == currRing->qideal)
3353 }
3354#endif
3355
3356 if ((Q!=NULL)&&(idIs0(Q))) Q=NULL;
3357
3358 if ((idIs0(F))&&(Q==NULL))
3359 {
3360#ifdef HAVE_PLURAL
3361 if(p != pp)
3362 return pp;
3363#endif
3364 return idCopy(p); /*F+Q=0*/
3365 }
3366
3367 kStrategy strat=new skStrategy;
3368 strat->syzComp = syzComp;
3370 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3371 {
3372 strat->ak = si_max(strat->ak,(int)F->rank);
3373 }
3374
3376 {
3377#ifdef HAVE_SHIFTBBA
3378 if (currRing->isLPring)
3379 {
3380 WerrorS("No local ordering possible for shift algebra");
3381 return(NULL);
3382 }
3383#endif
3384 res=kNF1(F,Q,pp,strat,lazyReduce);
3385 }
3386 else
3387 res=kNF2(F,Q,pp,strat,lazyReduce);
3388 delete(strat);
3389
3390#ifdef HAVE_PLURAL
3391 if(pp != p)
3393#endif
3394
3395 return res;
3396}
static int si_max(const int a, const int b)
Definition auxiliary.h:124
CanonicalForm FACTORY_PUBLIC 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:2126
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd2.cc:3950

◆ kNF() [2/2]

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

Definition at line 3235 of file kstd1.cc.

3236{
3237 if (p==NULL)
3238 return NULL;
3239
3240 poly pp = p;
3241
3242#ifdef HAVE_PLURAL
3243 if(rIsSCA(currRing))
3244 {
3245 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3246 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3248
3249 if(Q == currRing->qideal)
3251 }
3252#endif
3253 if((Q!=NULL) &&(idIs0(Q))) Q=NULL;
3254
3255 if ((idIs0(F))&&(Q==NULL))
3256 {
3257#ifdef HAVE_PLURAL
3258 if(p != pp)
3259 return pp;
3260#endif
3261 return pCopy(p); /*F+Q=0*/
3262 }
3263
3264 kStrategy strat=new skStrategy;
3265 strat->syzComp = syzComp;
3267 poly res;
3268
3270 {
3271#ifdef HAVE_SHIFTBBA
3272 if (currRing->isLPring)
3273 {
3274 WerrorS("No local ordering possible for shift algebra");
3275 return(NULL);
3276 }
3277#endif
3278 res=kNF1(F,Q,pp,strat,lazyReduce);
3279 }
3280 else
3281 res=kNF2(F,Q,pp,strat,lazyReduce);
3282 delete(strat);
3283
3284#ifdef HAVE_PLURAL
3285 if(pp != p)
3286 p_Delete(&pp, currRing);
3287#endif
3288 return res;
3289}
poly p_KillSquares(const poly p, const short iFirstAltVar, const short iLastAltVar, const ring r)
Definition sca.cc:1463
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:901
#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 2271 of file kstd1.cc.

2272{
2273 assume(!idIs0(q));
2274 assume(!(idIs0(F)&&(Q==NULL)));
2275
2276// lazy_reduce flags: can be combined by |
2277//#define KSTD_NF_LAZY 1
2278 // do only a reduction of the leading term
2279//#define KSTD_NF_ECART 2
2280 // only local: reduce even with bad ecart
2281 poly p;
2282 int i;
2283 int j;
2284 int o;
2285 LObject h;
2286 ideal res;
2287 BITSET save1;
2289
2290 //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2291 //if ((idIs0(F))&&(Q==NULL))
2292 // return idCopy(q); /*F=0*/
2293 //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2294 /*- creating temp data structures------------------- -*/
2295 //strat->kAllAxis = (currRing->ppNoether) != NULL;
2296 strat->kNoether=pCopy((currRing->ppNoether));
2299 && (0<Kstd1_deg)
2300 && ((strat->kNoether==NULL)
2302 {
2303 pLmDelete(&strat->kNoether);
2304 strat->kNoether=pOne();
2305 pSetExp(strat->kNoether,1, Kstd1_deg+1);
2306 pSetm(strat->kNoether);
2307 //strat->kAllAxis=TRUE;
2308 }
2309 initBuchMoraCrit(strat);
2311 initBuchMoraPosRing(strat);
2312 else
2313 initBuchMoraPos(strat);
2314 initMora(F,strat);
2315 strat->enterS = enterSMoraNF;
2316 /*- set T -*/
2317 strat->tl = -1;
2318 strat->tmax = setmaxT;
2319 strat->T = initT();
2320 strat->R = initR();
2321 strat->sevT = initsevT();
2322 /*- set S -*/
2323 strat->sl = -1;
2324 /*- init local data struct.-------------------------- -*/
2325 /*Shdl=*/initS(F,Q,strat);
2326 if ((strat->ak!=0)
2327 && (strat->kNoether!=NULL))
2328 {
2329 if (strat->ak!=1)
2330 {
2331 pSetComp(strat->kNoether,1);
2332 pSetmComp(strat->kNoether);
2333 poly p=pHead(strat->kNoether);
2334 pSetComp(p,strat->ak);
2335 pSetmComp(p);
2336 p=pAdd(strat->kNoether,p);
2337 strat->kNoether=pNext(p);
2339 }
2340 }
2341 if (((lazyReduce & KSTD_NF_LAZY)==0)
2342 && (!rField_is_Ring(currRing)))
2343 {
2344 for (i=strat->sl; i>=0; i--)
2345 pNorm(strat->S[i]);
2346 }
2347 /*- compute------------------------------------------- -*/
2348 res=idInit(IDELEMS(q),strat->ak);
2349 for (i=0; i<IDELEMS(q); i++)
2350 {
2351 if (q->m[i]!=NULL)
2352 {
2353 p = pCopy(q->m[i]);
2354 deleteHC(&p,&o,&j,strat);
2355 if (p!=NULL)
2356 {
2357 /*- puts the elements of S also to T -*/
2358 for (j=0; j<=strat->sl; j++)
2359 {
2360 h.p = strat->S[j];
2361 h.ecart = strat->ecartS[j];
2362 h.pLength = h.length = pLength(h.p);
2363 if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2364 else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2365 h.sev = strat->sevS[j];
2366 h.SetpFDeg();
2368 enterT_strong(h,strat);
2369 else
2370 enterT(h,strat);
2371 }
2372 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2374 {
2375 p = redMoraNFRing(p,strat, lazyReduce);
2376 }
2377 else
2378 p = redMoraNF(p,strat, lazyReduce);
2379 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2380 {
2381 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2382 p = redtail(p,strat->sl,strat);
2383 }
2384 cleanT(strat);
2385 }
2386 res->m[i]=p;
2387 }
2388 //else
2389 // res->m[i]=NULL;
2390 }
2391 /*- release temp data------------------------------- -*/
2392 assume(strat->L==NULL); /*strat->L unused */
2393 assume(strat->B==NULL); /*strat->B unused */
2394 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2395 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2396 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2397 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2398 omFree(strat->sevT);
2399 omFree(strat->S_2_R);
2400 omFree(strat->R);
2401 if ((Q!=NULL)&&(strat->fromQ!=NULL))
2402 {
2404 omFreeSize((ADDRESS)strat->fromQ,i*sizeof(int));
2405 strat->fromQ=NULL;
2406 }
2407 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2408// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2409// {
2410// pFDeg=strat->pOrigFDeg;
2411// pLDeg=strat->pOrigLDeg;
2412// if (ecartWeights)
2413// {
2414// omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2415// ecartWeights=NULL;
2416// }
2417// }
2418 idDelete(&strat->Shdl);
2420 if (TEST_OPT_PROT) PrintLn();
2421 return res;
2422}
polyset S
Definition kutil.h:306
LSet B
Definition kutil.h:328
LSet L
Definition kutil.h:327
void initMora(ideal F, kStrategy strat)
Definition kstd1.cc:1819
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1681
static poly redMoraNFRing(poly h, kStrategy strat, int flag)
Definition kstd1.cc:1083
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition kstd1.cc:978
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition kutil.cc:6882
void enterT(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9177
void initBuchMoraPos(kStrategy strat)
Definition kutil.cc:9626
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9277
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition kutil.cc:293
void initBuchMoraPosRing(kStrategy strat)
Definition kutil.cc:9712
#define setmaxTinc
Definition kutil.h:34
class sLObject LObject
Definition kutil.h:58
#define omFree(addr)
#define OPT_REDTAIL
Definition options.h:91
#define TEST_OPT_STAIRCASEBOUND
Definition options.h:115
static int pLength(poly a)
Definition p_polys.h:190
static void p_LmDelete(poly p, const ring r)
Definition p_polys.h:723
#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
void pNorm(poly p)
Definition polys.h:362
#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
#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 2126 of file kstd1.cc.

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

◆ kNFBound() [1/2]

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

Definition at line 3398 of file kstd1.cc.

3399{
3400 ideal res;
3401 if (TEST_OPT_PROT)
3402 {
3403 Print("(S:%d)",IDELEMS(p));mflush();
3404 }
3405 if (idIs0(p))
3406 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3407
3408 ideal pp = p;
3409#ifdef HAVE_PLURAL
3410 if(rIsSCA(currRing))
3411 {
3412 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3413 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3415
3416 if(Q == currRing->qideal)
3418 }
3419#endif
3420
3421 if ((idIs0(F))&&(Q==NULL))
3422 {
3423#ifdef HAVE_PLURAL
3424 if(p != pp)
3425 return pp;
3426#endif
3427 return idCopy(p); /*F+Q=0*/
3428 }
3429
3430 kStrategy strat=new skStrategy;
3431 strat->syzComp = syzComp;
3433 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3434 {
3435 strat->ak = si_max(strat->ak,(int)F->rank);
3436 }
3437
3438 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3439 delete(strat);
3440
3441#ifdef HAVE_PLURAL
3442 if(pp != p)
3444#endif
3445
3446 return res;
3447}
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:4032

◆ kNFBound() [2/2]

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

Definition at line 3291 of file kstd1.cc.

3292{
3293 if (p==NULL)
3294 return NULL;
3295
3296 poly pp = p;
3297
3298#ifdef HAVE_PLURAL
3299 if(rIsSCA(currRing))
3300 {
3301 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3302 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3304
3305 if(Q == currRing->qideal)
3307 }
3308#endif
3309
3310 if ((idIs0(F))&&(Q==NULL))
3311 {
3312#ifdef HAVE_PLURAL
3313 if(p != pp)
3314 return pp;
3315#endif
3316 return pCopy(p); /*F+Q=0*/
3317 }
3318
3319 kStrategy strat=new skStrategy;
3320 strat->syzComp = syzComp;
3322 poly res;
3323 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3324 delete(strat);
3325
3326#ifdef HAVE_PLURAL
3327 if(pp != p)
3328 p_Delete(&pp, currRing);
3329#endif
3330 return res;
3331}

◆ 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 2684 of file kstd1.cc.

2686{
2687 if(idIs0(F))
2688 return idInit(1,F->rank);
2690 {
2691 ideal r;
2692 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2694 kStrategy strat=new skStrategy;
2695 strat->sbaOrder = sbaOrder;
2696 if (arri!=0)
2697 {
2698 strat->rewCrit1 = arriRewDummy;
2699 strat->rewCrit2 = arriRewCriterion;
2701 }
2702 else
2703 {
2707 }
2708
2710 strat->syzComp = syzComp;
2711 if (TEST_OPT_SB_1)
2712 //if(!rField_is_Ring(currRing)) // always true here
2713 strat->newIdeal = newIdeal;
2715 strat->LazyPass=20;
2716 else
2717 strat->LazyPass=2;
2718 strat->LazyDegree = 1;
2722 strat->ak = id_RankFreeModule(F,currRing);
2723 strat->kModW=kModW=NULL;
2724 strat->kHomW=kHomW=NULL;
2725 if (vw != NULL)
2726 {
2727 currRing->pLexOrder=FALSE;
2728 strat->kHomW=kHomW=vw;
2729 strat->pOrigFDeg = currRing->pFDeg;
2730 strat->pOrigLDeg = currRing->pLDeg;
2732 toReset = TRUE;
2733 }
2734 if (h==testHomog)
2735 {
2736 if (strat->ak == 0)
2737 {
2738 h = (tHomog)idHomIdeal(F,Q);
2739 w=NULL;
2740 }
2741 else if (!TEST_OPT_DEGBOUND)
2742 {
2743 if (w!=NULL)
2744 h = (tHomog)idHomModule(F,Q,w);
2745 else
2746 h = (tHomog)idHomIdeal(F,Q);
2747 }
2748 }
2749 currRing->pLexOrder=b;
2750 if (h==isHomog)
2751 {
2752 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2753 {
2754 strat->kModW = kModW = *w;
2755 if (vw == NULL)
2756 {
2757 strat->pOrigFDeg = currRing->pFDeg;
2758 strat->pOrigLDeg = currRing->pLDeg;
2760 toReset = TRUE;
2761 }
2762 }
2763 currRing->pLexOrder = TRUE;
2764 if (hilb==NULL) strat->LazyPass*=2;
2765 }
2766 strat->homog=h;
2767 #ifdef KDEBUG
2768 idTest(F);
2769 if(Q != NULL)
2770 idTest(Q);
2771 #endif
2772 #ifdef HAVE_PLURAL
2774 {
2775 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2776 strat->no_prod_crit = ! bIsSCA;
2777 if (w!=NULL)
2778 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2779 else
2780 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2781 }
2782 else
2783 #endif
2784 {
2786 {
2787 if (w!=NULL)
2788 r=mora(F,Q,*w,hilb,strat);
2789 else
2790 r=mora(F,Q,NULL,hilb,strat);
2791 }
2792 else
2793 {
2794 strat->sigdrop = FALSE;
2795 if (w!=NULL)
2796 r=sba(F,Q,*w,hilb,strat);
2797 else
2798 r=sba(F,Q,NULL,hilb,strat);
2799 }
2800 }
2801 #ifdef KDEBUG
2802 idTest(r);
2803 #endif
2804 if (toReset)
2805 {
2806 kModW = NULL;
2808 }
2809 currRing->pLexOrder = b;
2810 //Print("%d reductions canceled \n",strat->cel);
2811 //delete(strat);
2812 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2813 return r;
2814 }
2815 else
2816 {
2817 //--------------------------RING CASE-------------------------
2818 assume(sbaOrder == 1);
2819 assume(arri == 0);
2820 ideal r;
2821 r = idCopy(F);
2822 int sbaEnterS = -1;
2823 bool sigdrop = TRUE;
2824 //This is how we set the SBA algorithm;
2825 int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2826 while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2827 && (blockred <= blockedreductions))
2828 {
2829 loops++;
2830 if(loops == 1)
2831 sigdrop = FALSE;
2832 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2834 kStrategy strat=new skStrategy;
2835 strat->sbaEnterS = sbaEnterS;
2836 strat->sigdrop = sigdrop;
2837 #if 0
2838 strat->blockred = blockred;
2839 #else
2840 strat->blockred = 0;
2841 #endif
2843 //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2844 //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2845 strat->sbaOrder = sbaOrder;
2846 if (arri!=0)
2847 {
2848 strat->rewCrit1 = arriRewDummy;
2849 strat->rewCrit2 = arriRewCriterion;
2851 }
2852 else
2853 {
2857 }
2858
2860 strat->syzComp = syzComp;
2861 if (TEST_OPT_SB_1)
2863 strat->newIdeal = newIdeal;
2865 strat->LazyPass=20;
2866 else
2867 strat->LazyPass=2;
2868 strat->LazyDegree = 1;
2872 strat->ak = id_RankFreeModule(F,currRing);
2873 strat->kModW=kModW=NULL;
2874 strat->kHomW=kHomW=NULL;
2875 if (vw != NULL)
2876 {
2877 currRing->pLexOrder=FALSE;
2878 strat->kHomW=kHomW=vw;
2879 strat->pOrigFDeg = currRing->pFDeg;
2880 strat->pOrigLDeg = currRing->pLDeg;
2882 toReset = TRUE;
2883 }
2884 if (h==testHomog)
2885 {
2886 if (strat->ak == 0)
2887 {
2888 h = (tHomog)idHomIdeal(F,Q);
2889 w=NULL;
2890 }
2891 else if (!TEST_OPT_DEGBOUND)
2892 {
2893 if (w!=NULL)
2894 h = (tHomog)idHomModule(F,Q,w);
2895 else
2896 h = (tHomog)idHomIdeal(F,Q);
2897 }
2898 }
2899 currRing->pLexOrder=b;
2900 if (h==isHomog)
2901 {
2902 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2903 {
2904 strat->kModW = kModW = *w;
2905 if (vw == NULL)
2906 {
2907 strat->pOrigFDeg = currRing->pFDeg;
2908 strat->pOrigLDeg = currRing->pLDeg;
2910 toReset = TRUE;
2911 }
2912 }
2913 currRing->pLexOrder = TRUE;
2914 if (hilb==NULL) strat->LazyPass*=2;
2915 }
2916 strat->homog=h;
2917 #ifdef KDEBUG
2918 idTest(F);
2919 if(Q != NULL)
2920 idTest(Q);
2921 #endif
2922 #ifdef HAVE_PLURAL
2924 {
2925 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2926 strat->no_prod_crit = ! bIsSCA;
2927 if (w!=NULL)
2928 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2929 else
2930 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2931 }
2932 else
2933 #endif
2934 {
2936 {
2937 if (w!=NULL)
2938 r=mora(F,Q,*w,hilb,strat);
2939 else
2940 r=mora(F,Q,NULL,hilb,strat);
2941 }
2942 else
2943 {
2944 if (w!=NULL)
2945 r=sba(r,Q,*w,hilb,strat);
2946 else
2947 {
2948 r=sba(r,Q,NULL,hilb,strat);
2949 }
2950 }
2951 }
2952 #ifdef KDEBUG
2953 idTest(r);
2954 #endif
2955 if (toReset)
2956 {
2957 kModW = NULL;
2959 }
2960 currRing->pLexOrder = b;
2961 //Print("%d reductions canceled \n",strat->cel);
2962 sigdrop = strat->sigdrop;
2963 sbaEnterS = strat->sbaEnterS;
2964 blockred = strat->blockred;
2965 delete(strat);
2966 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2967 }
2968 // Go to std
2969 if(sigdrop || blockred > blockedreductions)
2970 {
2971 r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2972 }
2973 return r;
2974 }
2975}
bool sigdrop
Definition kutil.h:359
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition kutil.h:291
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:293
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:295
intvec * kHomW
Definition kutil.h:336
int blockred
Definition kutil.h:364
unsigned sbaOrder
Definition kutil.h:316
int blockredmax
Definition kutil.h:365
int newIdeal
Definition kutil.h:356
char z2homog
Definition kutil.h:374
char no_prod_crit
Definition kutil.h:394
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition kutil.h:290
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:294
int sbaEnterS
Definition kutil.h:362
#define idTest(id)
Definition ideals.h:47
KINLINE BOOLEAN arriRewDummy(poly, unsigned long, poly, kStrategy, int)
Definition kInline.h:1263
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, const ring r)
Definition kstd1.cc:2436
ideal mora(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd1.cc:1888
VAR intvec * kHomW
Definition kstd1.cc:2424
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:2984
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition kutil.cc:6688
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition kutil.cc:6663
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition kutil.cc:1951
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition kutil.cc:6604
void chainCritOpt_1(poly, int, kStrategy strat)
Definition kutil.cc:3457
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition kutil.cc:3216
#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 2483 of file kstd1.cc.

2485{
2486 if(idIs0(F))
2487 return idInit(1,F->rank);
2488
2489 if((Q!=NULL)&&(idIs0(Q))) Q=NULL;
2490#ifdef HAVE_SHIFTBBA
2491 if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
2492#endif
2493
2494 /* test HC precomputation*/
2495 poly save_noether=currRing->ppNoether;
2496 int ak = id_RankFreeModule(F,currRing);
2497 if((ak==0)
2498 && (h!=isHomog)
2499 && (w==NULL)
2500 && (hilb==NULL)
2501 && (vw==NULL)
2502 && (newIdeal==0)
2503 && (sp==NULL)
2507 currRing->ppNoether=kTryHC(F,Q);
2508
2509 ideal r;
2510 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2512 kStrategy strat=new skStrategy;
2513
2514 strat->s_poly=sp;
2516 strat->syzComp = syzComp;
2517 if (TEST_OPT_SB_1
2519 )
2520 strat->newIdeal = newIdeal;
2522 strat->LazyPass=20;
2523 else
2524 strat->LazyPass=2;
2525 strat->LazyDegree = 1;
2526 strat->ak = ak;
2527 strat->kModW=kModW=NULL;
2528 strat->kHomW=kHomW=NULL;
2529 if (vw != NULL)
2530 {
2531 currRing->pLexOrder=FALSE;
2532 strat->kHomW=kHomW=vw;
2533 strat->pOrigFDeg = currRing->pFDeg;
2534 strat->pOrigLDeg = currRing->pLDeg;
2536 toReset = TRUE;
2537 }
2538 if (h==testHomog)
2539 {
2540 if (strat->ak == 0)
2541 {
2542 h = (tHomog)idHomIdeal(F,Q);
2543 w=NULL;
2544 }
2545 else if (!TEST_OPT_DEGBOUND)
2546 {
2547 if (w!=NULL)
2548 h = (tHomog)idHomModule(F,Q,w);
2549 else
2550 h = (tHomog)idHomIdeal(F,Q);
2551 }
2552 }
2553 currRing->pLexOrder=b;
2554 if (h==isHomog)
2555 {
2556 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2557 {
2558 strat->kModW = kModW = *w;
2559 if (vw == NULL)
2560 {
2561 strat->pOrigFDeg = currRing->pFDeg;
2562 strat->pOrigLDeg = currRing->pLDeg;
2564 toReset = TRUE;
2565 }
2566 }
2567 currRing->pLexOrder = TRUE;
2568 if (hilb==NULL) strat->LazyPass*=2;
2569 }
2570 strat->homog=h;
2571#ifdef KDEBUG
2572 idTest(F);
2573 if (Q!=NULL) idTest(Q);
2574#endif
2575#ifdef HAVE_PLURAL
2577 {
2578 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2579 strat->no_prod_crit = ! bIsSCA;
2580 if (w!=NULL)
2581 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2582 else
2583 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2584 }
2585 else
2586#endif
2587 {
2588 #if PRE_INTEGER_CHECK
2589 //the preinteger check strategy is not for modules
2590 if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2591 {
2592 ideal FCopy = idCopy(F);
2593 poly pFmon = preIntegerCheck(FCopy, Q);
2594 if(pFmon != NULL)
2595 {
2597 strat->kModW=kModW=NULL;
2598 if (h==testHomog)
2599 {
2600 if (strat->ak == 0)
2601 {
2603 w=NULL;
2604 }
2605 else if (!TEST_OPT_DEGBOUND)
2606 {
2607 if (w!=NULL)
2609 else
2611 }
2612 }
2613 currRing->pLexOrder=b;
2614 if (h==isHomog)
2615 {
2616 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2617 {
2618 strat->kModW = kModW = *w;
2619 if (vw == NULL)
2620 {
2621 strat->pOrigFDeg = currRing->pFDeg;
2622 strat->pOrigLDeg = currRing->pLDeg;
2624 toReset = TRUE;
2625 }
2626 }
2627 currRing->pLexOrder = TRUE;
2628 if (hilb==NULL) strat->LazyPass*=2;
2629 }
2630 strat->homog=h;
2631 }
2632 omTestMemory(1);
2633 if(w == NULL)
2634 {
2636 r=mora(FCopy,Q,NULL,hilb,strat);
2637 else
2638 r=bba(FCopy,Q,NULL,hilb,strat);
2639 }
2640 else
2641 {
2643 r=mora(FCopy,Q,*w,hilb,strat);
2644 else
2645 r=bba(FCopy,Q,*w,hilb,strat);
2646 }
2647 idDelete(&FCopy);
2648 }
2649 else
2650 #endif
2651 {
2652 if(w==NULL)
2653 {
2655 r=mora(F,Q,NULL,hilb,strat);
2656 else
2657 r=bba(F,Q,NULL,hilb,strat);
2658 }
2659 else
2660 {
2662 r=mora(F,Q,*w,hilb,strat);
2663 else
2664 r=bba(F,Q,*w,hilb,strat);
2665 }
2666 }
2667 }
2668#ifdef KDEBUG
2669 idTest(r);
2670#endif
2671 if (toReset)
2672 {
2673 kModW = NULL;
2675 }
2676 currRing->pLexOrder = b;
2677//Print("%d reductions canceled \n",strat->cel);
2678 delete(strat);
2679 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2680 currRing->ppNoether=save_noether;
2681 return r;
2682}
s_poly_proc_t s_poly
Definition kutil.h:300
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition coeffs.h:813
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:2978
static poly kTryHC(ideal F, ideal Q)
Definition kstd1.cc:2449
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:10595
omError_t omTestMemory(int check_level)
Definition omDebug.c:94
BOOLEAN rOrd_is_ds(const ring r)
Definition ring.cc:2033
static BOOLEAN rIsLPRing(const ring r)
Definition ring.h:411
static BOOLEAN rField_is_Q(const ring r)
Definition ring.h:506

◆ 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 2978 of file kstd1.cc.

2980{
2982 assume(idIsInV(F));
2983 ideal r;
2984 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2986 kStrategy strat=new skStrategy;
2987
2988 strat->rightGB = rightGB;
2989
2991 strat->syzComp = syzComp;
2992 if (TEST_OPT_SB_1)
2994 strat->newIdeal = newIdeal;
2996 strat->LazyPass=20;
2997 else
2998 strat->LazyPass=2;
2999 strat->LazyDegree = 1;
3000 strat->ak = id_RankFreeModule(F,currRing);
3001 strat->kModW=kModW=NULL;
3002 strat->kHomW=kHomW=NULL;
3003 if (vw != NULL)
3004 {
3005 currRing->pLexOrder=FALSE;
3006 strat->kHomW=kHomW=vw;
3007 strat->pOrigFDeg = currRing->pFDeg;
3008 strat->pOrigLDeg = currRing->pLDeg;
3010 toReset = TRUE;
3011 }
3012 if (h==testHomog)
3013 {
3014 if (strat->ak == 0)
3015 {
3016 h = (tHomog)idHomIdeal(F,Q);
3017 w=NULL;
3018 }
3019 else if (!TEST_OPT_DEGBOUND)
3020 {
3021 if (w!=NULL)
3022 h = (tHomog)idHomModule(F,Q,w);
3023 else
3024 h = (tHomog)idHomIdeal(F,Q);
3025 }
3026 }
3027 currRing->pLexOrder=b;
3028 if (h==isHomog)
3029 {
3030 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3031 {
3032 strat->kModW = kModW = *w;
3033 if (vw == NULL)
3034 {
3035 strat->pOrigFDeg = currRing->pFDeg;
3036 strat->pOrigLDeg = currRing->pLDeg;
3038 toReset = TRUE;
3039 }
3040 }
3041 currRing->pLexOrder = TRUE;
3042 if (hilb==NULL) strat->LazyPass*=2;
3043 }
3044 strat->homog=h;
3045#ifdef KDEBUG
3046 idTest(F);
3047#endif
3049 {
3050 /* error: no local ord yet with shifts */
3051 WerrorS("No local ordering possible for shift algebra");
3052 return(NULL);
3053 }
3054 else
3055 {
3056 /* global ordering */
3057 if (w!=NULL)
3058 r=bbaShift(F,Q,*w,hilb,strat);
3059 else
3060 r=bbaShift(F,Q,NULL,hilb,strat);
3061 }
3062#ifdef KDEBUG
3063 idTest(r);
3064#endif
3065 if (toReset)
3066 {
3067 kModW = NULL;
3069 }
3070 currRing->pLexOrder = b;
3071//Print("%d reductions canceled \n",strat->cel);
3072 delete(strat);
3073 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
3074 assume(idIsInV(r));
3075 return r;
3076}
char rightGB
Definition kutil.h:369
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:4591
#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 1888 of file kstd1.cc.

1889{
1890 int olddeg = 0;
1891 int reduc = 0;
1892 int red_result = 1;
1893 int hilbeledeg=1,hilbcount=0;
1894 BITSET save1;
1897 {
1898 si_opt_1 &= ~Sy_bit(OPT_REDSB);
1899 si_opt_1 &= ~Sy_bit(OPT_REDTAIL);
1900 }
1901
1902 strat->update = TRUE;
1903 /*- setting global variables ------------------- -*/
1904 initBuchMoraCrit(strat);
1905 initHilbCrit(F,Q,&hilb,strat);
1906 initMora(F,strat);
1908 initBuchMoraPosRing(strat);
1909 else
1910 initBuchMoraPos(strat);
1911 /*Shdl=*/initBuchMora(F,Q,strat);
1912 if (TEST_OPT_FASTHC) missingAxis(&strat->lastAxis,strat);
1913 /*updateS in initBuchMora has Hecketest
1914 * and could have put strat->kHEdgdeFound FALSE*/
1915 if (TEST_OPT_FASTHC && (strat->lastAxis) && strat->posInLOldFlag)
1916 {
1917 strat->posInLOld = strat->posInL;
1918 strat->posInLOldFlag = FALSE;
1919 strat->posInL = posInL10;
1920 updateL(strat);
1921 reorderL(strat);
1922 }
1923 kTest_TS(strat);
1924 strat->use_buckets = kMoraUseBucket(strat);
1925
1926#ifdef HAVE_TAIL_RING
1927 if (strat->homog && strat->red == redFirst)
1928 if(!idIs0(F) &&(!rField_is_Ring(currRing)))
1930#endif
1931
1932 if (BVERBOSE(23))
1933 {
1934 kDebugPrint(strat);
1935 }
1936//deleteInL(strat->L,&strat->Ll,1,strat);
1937//deleteInL(strat->L,&strat->Ll,0,strat);
1938
1939 /*- compute-------------------------------------------*/
1940 while (strat->Ll >= 0)
1941 {
1942 #ifdef KDEBUG
1943 if (TEST_OPT_DEBUG) messageSets(strat);
1944 #endif
1945 if (siCntrlc)
1946 {
1947 while (strat->Ll >= 0)
1948 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1949 strat->noClearS=TRUE;
1950 }
1952 && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg))
1953 {
1954 /*
1955 * stops computation if
1956 * - 24 (degBound)
1957 * && upper degree is bigger than Kstd1_deg
1958 */
1959 while ((strat->Ll >= 0)
1960 && (strat->L[strat->Ll].p1!=NULL) && (strat->L[strat->Ll].p2!=NULL)
1961 && (strat->L[strat->Ll].ecart+strat->L[strat->Ll].GetpFDeg()> Kstd1_deg)
1962 )
1963 {
1964 deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
1965 //if (TEST_OPT_PROT)
1966 //{
1967 // PrintS("D"); mflush();
1968 //}
1969 }
1970 if (strat->Ll<0) break;
1971 else strat->noClearS=TRUE;
1972 }
1973 strat->P = strat->L[strat->Ll];/*- picks the last element from the lazyset L -*/
1974 if (strat->Ll==0) strat->interpt=TRUE;
1975 strat->Ll--;
1976 // create the real Spoly
1977 if (pNext(strat->P.p) == strat->tail)
1978 {
1979 /*- deletes the short spoly and computes -*/
1981 pLmDelete(strat->P.p);
1982 else
1983 pLmFree(strat->P.p);
1984 strat->P.p = NULL;
1985 poly m1 = NULL, m2 = NULL;
1986 // check that spoly creation is ok
1987 while (strat->tailRing != currRing &&
1988 !kCheckSpolyCreation(&(strat->P), strat, m1, m2))
1989 {
1990 assume(m1 == NULL && m2 == NULL);
1991 // if not, change to a ring where exponents are large enough
1992 kStratChangeTailRing(strat);
1993 }
1994 /* create the real one */
1995 ksCreateSpoly(&(strat->P), strat->kNoetherTail(), strat->use_buckets,
1996 strat->tailRing, m1, m2, strat->R);
1997 if (!strat->use_buckets)
1998 strat->P.SetLength(strat->length_pLength);
1999 }
2000 else if (strat->P.p1 == NULL)
2001 {
2002 // for input polys, prepare reduction (buckets !)
2003 strat->P.SetLength(strat->length_pLength);
2004 strat->P.PrepareRed(strat->use_buckets);
2005 }
2006
2007 // the s-poly
2008 if (!strat->P.IsNull())
2009 {
2010 // might be NULL from noether !!!
2011 if (TEST_OPT_PROT)
2012 message(strat->P.ecart+strat->P.GetpFDeg(),&olddeg,&reduc,strat, red_result);
2013 // reduce
2014 red_result = strat->red(&strat->P,strat);
2015 }
2016
2017 // the reduced s-poly
2018 if (! strat->P.IsNull())
2019 {
2020 strat->P.GetP();
2021 // statistics
2022 if (TEST_OPT_PROT) PrintS("s");
2023 // normalization
2025 strat->P.pCleardenom();
2026 else
2027 strat->P.pNorm();
2028 // tailreduction
2029 strat->P.p = redtail(&(strat->P),strat->sl,strat);
2030 if (strat->P.p==NULL)
2031 {
2032 WerrorS("exponent overflow - wrong ordering");
2033 return(idInit(1,1));
2034 }
2035 // set ecart -- might have changed because of tail reductions
2036 if ((!strat->noTailReduction) && (!strat->honey))
2037 strat->initEcart(&strat->P);
2038 // cancel unit
2039 cancelunit(&strat->P);
2040 // for char 0, clear denominators
2041 if ((strat->P.p->next==NULL) /* i.e. cancelunit did something*/
2043 strat->P.pCleardenom();
2044
2045 strat->P.SetShortExpVector();
2046 enterT(strat->P,strat);
2047 // build new pairs
2049 superenterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2050 else
2051 enterpairs(strat->P.p,strat->sl,strat->P.ecart,0,strat, strat->tl);
2052 // put in S
2053 strat->enterS(strat->P,
2054 posInS(strat,strat->sl,strat->P.p, strat->P.ecart),
2055 strat, strat->tl);
2056 // apply hilbert criterion
2057 if (hilb!=NULL)
2058 {
2059 if (strat->homog==isHomog)
2061 else
2063 }
2064
2065 // clear strat->P
2066 kDeleteLcm(&strat->P);
2067
2068#ifdef KDEBUG
2069 // make sure kTest_TS does not complain about strat->P
2070 strat->P.Clear();
2071#endif
2072 }
2073 if (strat->kAllAxis)
2074 {
2075 if ((TEST_OPT_FINDET)
2076 || ((TEST_OPT_MULTBOUND) && (scMult0Int(strat->Shdl,NULL) < Kstd1_mu)))
2077 {
2078 // obachman: is this still used ???
2079 /*
2080 * stops computation if strat->kAllAxis and
2081 * - 27 (finiteDeterminacyTest)
2082 * or
2083 * - 23
2084 * (multBound)
2085 * && multiplicity of the ideal is smaller then a predefined number mu
2086 */
2087 while (strat->Ll >= 0) deleteInL(strat->L,&strat->Ll,strat->Ll,strat);
2088 }
2089 }
2090 kTest_TS(strat);
2091 }
2092 /*- complete reduction of the standard basis------------------------ -*/
2093 if (TEST_OPT_REDSB) completeReduce(strat);
2094 else if (TEST_OPT_PROT) PrintLn();
2095 /*- release temp data------------------------------- -*/
2096 exitBuchMora(strat);
2097 /*- polynomials used for HECKE: HC, noether -*/
2098 if (TEST_OPT_FINDET)
2099 {
2100 if (strat->kNoether!=NULL)
2101 Kstd1_mu=currRing->pFDeg(strat->kNoether,currRing);
2102 else
2103 Kstd1_mu=-1;
2104 }
2105 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2106 if (strat->kNoether!=NULL) pLmDelete(&strat->kNoether);
2107 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2109// if (TEST_OPT_WEIGHTM)
2110// {
2111// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2112// if (ecartWeights)
2113// {
2114// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2115// ecartWeights=NULL;
2116// }
2117// }
2118 if(nCoeff_is_Z(currRing->cf))
2119 finalReduceByMon(strat);
2120 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2122 idTest(strat->Shdl);
2123 return (strat->Shdl);
2124}
KINLINE poly kNoetherTail()
Definition kInline.h:66
ring tailRing
Definition kutil.h:343
int Ll
Definition kutil.h:351
int lastAxis
Definition kutil.h:355
poly tail
Definition kutil.h:334
char use_buckets
Definition kutil.h:383
char interpt
Definition kutil.h:371
LObject P
Definition kutil.h:302
char noClearS
Definition kutil.h:402
char length_pLength
Definition kutil.h:387
char update
Definition kutil.h:381
long scMult0Int(ideal S, ideal Q)
Definition hdegree.cc:950
void khCheckLocInhom(ideal Q, intvec *w, intvec *hilb, int &count, kStrategy strat)
Definition khstd.cc:244
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:1208
void missingAxis(int *last, kStrategy strat)
Definition kstd1.cc:1284
void reorderL(kStrategy strat)
Definition kstd1.cc:1226
int posInL10(const LSet set, const int length, LObject *p, const kStrategy strat)
Definition kstd1.cc:1365
static BOOLEAN kMoraUseBucket(kStrategy strat)
Definition kstd1.cc:3890
void updateL(kStrategy strat)
Definition kstd1.cc:1398
EXTERN_VAR int Kstd1_mu
Definition kstd1.h:50
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition kutil.cc:7511
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9799
BOOLEAN kTest_TS(kStrategy strat)
Definition kutil.cc:1072
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4508
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition kutil.cc:9457
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition kutil.cc:11020
void exitBuchMora(kStrategy strat)
Definition kutil.cc:9884
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition kutil.cc:4684
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition kutil.cc:10533
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition kutil.cc:10127
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:4477
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition kutil.cc:1214
void kStratInitChangeTailRing(kStrategy strat)
Definition kutil.cc:11113
void messageSets(kStrategy strat)
Definition kutil.cc:7584
void messageStat(int hilbcount, kStrategy strat)
Definition kutil.cc:7552
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition kutil.cc:10927
void cancelunit(LObject *L, BOOLEAN inNF)
Definition kutil.cc:372
static void kDeleteLcm(LObject *P)
Definition kutil.h:880
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,
const ideal  Q 
)

Definition at line 4955 of file kstd2.cc.

4956{
4958 assume(idIsInV(F));
4959 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4960 idSkipZeroes(RS); // is this even necessary?
4961 assume(idIsInV(RS));
4962 return(RS);
4963}

◆ stdred()

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

Variable Documentation

◆ kHomW

Definition at line 71 of file kstd1.h.

◆ kModW

Definition at line 70 of file kstd1.h.

◆ kOptions

EXTERN_VAR BITSET kOptions

Definition at line 52 of file kstd1.h.

◆ Kstd1_deg

EXTERN_VAR int Kstd1_deg

Definition at line 50 of file kstd1.h.

◆ Kstd1_mu

EXTERN_VAR int Kstd1_mu

Definition at line 50 of file kstd1.h.

◆ validOpts

EXTERN_VAR BITSET validOpts

Definition at line 54 of file kstd1.h.