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)
 
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. 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, 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 {
352 factor=idInit(1,IDELEMS(quot));
353 setUnit(A->rank,unit);
354 return idCopy(A);
355 }
356 /* ideal or module? */
357 ring orig_ring=currRing;
358 int k=id_RankFreeModule(quot,orig_ring);
359 int lsmod=0;
360 if (k==0) { lsmod=1;k=1;} /*ideal*/
361 /* new ring */
362 ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
363 rSetSyzComp(1,syz_ring);
364 rChangeCurrRing(syz_ring);
365 /* move ideals to new ring */
366 ideal s_quot;
367 ideal s_A;
368 if (orig_ring != syz_ring)
369 {
370 s_quot=idrCopyR_NoSort(quot,orig_ring,syz_ring);
371 s_A=idrCopyR_NoSort(A,orig_ring,syz_ring);
372 }
373 else
374 {
375 s_quot=id_Copy(quot,syz_ring);
376 s_A=id_Copy(A,syz_ring);
377 }
378 /* quot[i] -> quot[i]+e(k+i+1) */
379 for(int i=0;i<IDELEMS(s_quot);i++)
380 {
381 p_Shift(&s_quot->m[i],lsmod,syz_ring);
382 poly p=p_One(syz_ring);
383 p_SetComp(p,k+i+2,syz_ring);
384 p_Setm(p,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);
402 p_SetComp(p,u_k+i,syz_ring);
403 p_Setm(p,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 */
409 ideal rest=kNF(s_quot,syz_ring->qideal,s_A,0,lazyReduce);
410 /* clean s_quot,s_A */
411 id_Delete(&s_quot,syz_ring);
412 id_Delete(&s_A,syz_ring);
413 /* interpret rest: remainder */
414 ideal result=idInit(IDELEMS(rest),1);
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;
433 p_Shift(&result->m[i],-k-lsmod,syz_ring);
434 }
435 /* interpret rest: factors */
436 factor=idInit(IDELEMS(rest),IDELEMS(quot));
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 {
450 *unit=idInit(IDELEMS(A),IDELEMS(A));
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 }
478 id_Delete(&rest,syz_ring);
479 if (orig_ring != syz_ring)
480 {
481 rChangeCurrRing(orig_ring);
482 result=idrMoveR_NoSort(result, syz_ring, orig_ring);
483 factor=idrMoveR(factor, syz_ring, orig_ring);
484 if (unit!=NULL)
485 {
486 *unit=idrMoveR(*unit, syz_ring, orig_ring);
487 }
488 rDelete(syz_ring);
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
Definition: facAbsBiFact.cc:76
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:3186
#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:4430
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:450
void rSetSyzComp(int k, const ring r)
Definition: ring.cc:5138
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
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)
Definition: simpleideals.h:23
#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:1326
void initEcartNormal(TObject *h)
Definition: kutil.cc:1304
#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: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 3400 of file kstd1.cc.

3401{
3402 const ring save = currRing;
3403 if( currRing != _currRing ) rChangeCurrRing(_currRing);
3404 poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3405 if( currRing != save ) rChangeCurrRing(save);
3406 return ret;
3407}
STATIC_VAR jList * Q
Definition: janet.cc:30

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

3766{
3767#ifdef HAVE_PLURAL
3768 if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3769#endif
3772 )
3773 return kInterRedOld(F,Q);
3774
3775 //return kInterRedOld(F,Q);
3776
3777 BITSET save1;
3778 SI_SAVE_OPT1(save1);
3779 //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3781 //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3782 //si_opt_1&= ~Sy_bit(OPT_REDSB);
3783 //extern char * showOption() ;
3784 //Print("%s\n",showOption());
3785
3786 int need_retry;
3787 int counter=3;
3788 ideal res, res1;
3789 int elems;
3790 ideal null=NULL;
3791 if ((Q==NULL) || (!TEST_OPT_REDSB))
3792 {
3793 elems=idElem(F);
3794 res=kInterRedBba(F,Q,need_retry);
3795 }
3796 else
3797 {
3798 ideal FF=idSimpleAdd(F,Q);
3799 res=kInterRedBba(FF,NULL,need_retry);
3800 idDelete(&FF);
3801 null=idInit(1,1);
3802 if (need_retry)
3803 res1=kNF(null,Q,res,0,KSTD_NF_LAZY);
3804 else
3805 res1=kNF(null,Q,res);
3806 idDelete(&res);
3807 res=res1;
3808 need_retry=1;
3809 }
3810 if (idElem(res)<=1) need_retry=0;
3811 while (need_retry && (counter>0))
3812 {
3813 #ifdef KDEBUG
3814 if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3815 #endif
3816 res1=kInterRedBba(res,Q,need_retry);
3817 int new_elems=idElem(res1);
3818 counter -= (new_elems >= elems);
3819 elems = new_elems;
3820 idDelete(&res);
3821 if (idElem(res1)<=1) need_retry=0;
3822 if ((Q!=NULL) && (TEST_OPT_REDSB))
3823 {
3824 if (need_retry)
3825 res=kNF(null,Q,res1,0,KSTD_NF_LAZY);
3826 else
3827 res=kNF(null,Q,res1);
3828 idDelete(&res1);
3829 }
3830 else
3831 res = res1;
3832 if (idElem(res)<=1) need_retry=0;
3833 }
3834 if (null!=NULL) idDelete(&null);
3835 SI_RESTORE_OPT1(save1);
3837 return res;
3838}
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:3505
ideal kInterRedOld(ideal F, const ideal Q)
Definition: kstd1.cc:3413
#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
Definition: simpleideals.h:69
#define BITSET
Definition: structs.h:16

◆ kInterRedOld()

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

Definition at line 3413 of file kstd1.cc.

3414{
3415 int j;
3416 kStrategy strat = new skStrategy;
3417
3418 ideal tempF = F;
3419 ideal tempQ = Q;
3420
3421#ifdef HAVE_PLURAL
3422 if(rIsSCA(currRing))
3423 {
3424 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3425 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3426 tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3427
3428 // this should be done on the upper level!!! :
3429 // tempQ = SCAQuotient(currRing);
3430
3431 if(Q == currRing->qideal)
3432 tempQ = SCAQuotient(currRing);
3433 }
3434#endif
3435
3436// if (TEST_OPT_PROT)
3437// {
3438// writeTime("start InterRed:");
3439// mflush();
3440// }
3441 //strat->syzComp = 0;
3442 strat->kAllAxis = (currRing->ppNoether) != NULL;
3443 strat->kNoether=pCopy((currRing->ppNoether));
3444 strat->ak = id_RankFreeModule(tempF,currRing);
3445 initBuchMoraCrit(strat);
3446 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3447 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3448 strat->enterS = enterSBba;
3449 strat->posInT = posInT17;
3450 strat->initEcart = initEcartNormal;
3451 strat->sl = -1;
3452 strat->tl = -1;
3453 strat->tmax = setmaxT;
3454 strat->T = initT();
3455 strat->R = initR();
3456 strat->sevT = initsevT();
3458 initS(tempF, tempQ, strat);
3459 if (TEST_OPT_REDSB)
3460 strat->noTailReduction=FALSE;
3461 updateS(TRUE,strat);
3463 completeReduce(strat);
3464 //else if (TEST_OPT_PROT) PrintLn();
3465 cleanT(strat);
3466 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
3467 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3468 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3469 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3470 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3471 omfree(strat->sevT);
3472 omfree(strat->S_2_R);
3473 omfree(strat->R);
3474
3475 if (strat->fromQ)
3476 {
3477 for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3478 {
3479 if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3480 }
3481 omFreeSize((ADDRESS)strat->fromQ,IDELEMS(strat->Shdl)*sizeof(int));
3482 }
3483// if (TEST_OPT_PROT)
3484// {
3485// writeTime("end Interred:");
3486// mflush();
3487// }
3488 ideal shdl=strat->Shdl;
3489 idSkipZeroes(shdl);
3490 if (strat->fromQ)
3491 {
3492 strat->fromQ=NULL;
3493 ideal res=kInterRed(shdl,NULL);
3494 idDelete(&shdl);
3495 shdl=res;
3496 }
3497 delete(strat);
3498#ifdef HAVE_PLURAL
3499 if( tempF != F )
3500 id_Delete( &tempF, currRing);
3501#endif
3502 return shdl;
3503}
#define FALSE
Definition: auxiliary.h:96
void * ADDRESS
Definition: auxiliary.h:119
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:3765
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5306
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7635
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:8594
void cleanT(kStrategy strat)
Definition: kutil.cc:565
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9476
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition: kutil.cc:10340
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition: kutil.cc:8829
#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)
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

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

3038{
3039 if(idIs0(F))
3040 {
3041 M=idInit(1,F->rank);
3042 return idInit(1,F->rank);
3043 }
3045 {
3046 ideal sb;
3047 sb = kStd(F, Q, h, w, hilb);
3048 idSkipZeroes(sb);
3049 if(IDELEMS(sb) <= IDELEMS(F))
3050 {
3051 M = idCopy(sb);
3052 idSkipZeroes(M);
3053 return(sb);
3054 }
3055 else
3056 {
3057 M = idCopy(F);
3058 idSkipZeroes(M);
3059 return(sb);
3060 }
3061 }
3062 ideal r=NULL;
3063 int Kstd1_OldDeg = Kstd1_deg,i;
3064 intvec* temp_w=NULL;
3065 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3066 BOOLEAN delete_w=(w==NULL);
3067 BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
3068 kStrategy strat=new skStrategy;
3069
3071 strat->syzComp = syzComp;
3073 strat->LazyPass=20;
3074 else
3075 strat->LazyPass=2;
3076 strat->LazyDegree = 1;
3077 strat->minim=(reduced % 2)+1;
3078 strat->ak = id_RankFreeModule(F,currRing);
3079 if (delete_w)
3080 {
3081 temp_w=new intvec((strat->ak)+1);
3082 w = &temp_w;
3083 }
3084 if (h==testHomog)
3085 {
3086 if (strat->ak == 0)
3087 {
3088 h = (tHomog)idHomIdeal(F,Q);
3089 w=NULL;
3090 }
3091 else
3092 {
3093 h = (tHomog)idHomModule(F,Q,w);
3094 }
3095 }
3096 if (h==isHomog)
3097 {
3098 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3099 {
3100 kModW = *w;
3101 strat->kModW = *w;
3102 assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3103 strat->pOrigFDeg = currRing->pFDeg;
3104 strat->pOrigLDeg = currRing->pLDeg;
3106
3107 toReset = TRUE;
3108 if (reduced>1)
3109 {
3110 Kstd1_OldDeg=Kstd1_deg;
3111 Kstd1_deg = -1;
3112 for (i=IDELEMS(F)-1;i>=0;i--)
3113 {
3114 if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3115 Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3116 }
3117 }
3118 }
3119 currRing->pLexOrder = TRUE;
3120 strat->LazyPass*=2;
3121 }
3122 strat->homog=h;
3123 ideal SB=NULL;
3125 {
3126 r=idMinBase(F,&SB); // SB and M via minbase
3127 strat->M=r;
3128 r=SB;
3129 }
3130 else
3131 {
3132 if (w!=NULL)
3133 r=bba(F,Q,*w,hilb,strat);
3134 else
3135 r=bba(F,Q,NULL,hilb,strat);
3136 }
3137#ifdef KDEBUG
3138 {
3139 int i;
3140 for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3141 }
3142#endif
3143 idSkipZeroes(r);
3144 if (toReset)
3145 {
3147 kModW = NULL;
3148 }
3149 currRing->pLexOrder = b;
3150 if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3151 if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3152 {
3153 M=idInit(1,F->rank);
3154 M->m[0]=pOne();
3155 //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3156 if (strat->M!=NULL) idDelete(&strat->M);
3157 }
3158 else if (strat->M==NULL)
3159 {
3160 M=idInit(1,F->rank);
3161 WarnS("no minimal generating set computed");
3162 }
3163 else
3164 {
3165 idSkipZeroes(strat->M);
3166 M=strat->M;
3167 }
3168 delete(strat);
3169 if (reduced>2)
3170 {
3171 Kstd1_deg=Kstd1_OldDeg;
3172 if (!oldDegBound)
3173 si_opt_1 &= ~Sy_bit(OPT_DEGBOUND);
3174 }
3175 else
3176 {
3177 if (IDELEMS(M)>IDELEMS(r))
3178 {
3179 idDelete(&M);
3180 M=idCopy(r);
3181 }
3182 }
3183 return r;
3184}
CanonicalForm b
Definition: cfModGcd.cc:4103
Definition: intvec.h:23
intvec * kModW
Definition: kutil.h:335
unsigned 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:2449
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:50
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2636
#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 3284 of file kstd1.cc.

3285{
3286 ideal res;
3287 if (TEST_OPT_PROT)
3288 {
3289 Print("(S:%d)",IDELEMS(p));mflush();
3290 }
3291 if (idIs0(p))
3292 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3293
3294 ideal pp = p;
3295#ifdef HAVE_PLURAL
3296 if(rIsSCA(currRing))
3297 {
3298 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3299 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3300 pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3301
3302 if(Q == currRing->qideal)
3304 }
3305#endif
3306
3307 if ((Q!=NULL)&&(idIs0(Q))) Q=NULL;
3308
3309 if ((idIs0(F))&&(Q==NULL))
3310 {
3311#ifdef HAVE_PLURAL
3312 if(p != pp)
3313 return pp;
3314#endif
3315 return idCopy(p); /*F+Q=0*/
3316 }
3317
3318 kStrategy strat=new skStrategy;
3319 strat->syzComp = syzComp;
3321 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3322 {
3323 strat->ak = si_max(strat->ak,(int)F->rank);
3324 }
3325
3327 {
3328#ifdef HAVE_SHIFTBBA
3329 if (currRing->isLPring)
3330 {
3331 WerrorS("No local ordering possible for shift algebra");
3332 return(NULL);
3333 }
3334#endif
3335 res=kNF1(F,Q,pp,strat,lazyReduce);
3336 }
3337 else
3338 res=kNF2(F,Q,pp,strat,lazyReduce);
3339 delete(strat);
3340
3341#ifdef HAVE_PLURAL
3342 if(pp != p)
3344#endif
3345
3346 return res;
3347}
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:3960

◆ kNF() [2/2]

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

Definition at line 3186 of file kstd1.cc.

3187{
3188 if (p==NULL)
3189 return NULL;
3190
3191 poly pp = p;
3192
3193#ifdef HAVE_PLURAL
3194 if(rIsSCA(currRing))
3195 {
3196 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3197 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3198 pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3199
3200 if(Q == currRing->qideal)
3202 }
3203#endif
3204 if((Q!=NULL) &&(idIs0(Q))) Q=NULL;
3205
3206 if ((idIs0(F))&&(Q==NULL))
3207 {
3208#ifdef HAVE_PLURAL
3209 if(p != pp)
3210 return pp;
3211#endif
3212 return pCopy(p); /*F+Q=0*/
3213 }
3214
3215 kStrategy strat=new skStrategy;
3216 strat->syzComp = syzComp;
3218 poly res;
3219
3221 {
3222#ifdef HAVE_SHIFTBBA
3223 if (currRing->isLPring)
3224 {
3225 WerrorS("No local ordering possible for shift algebra");
3226 return(NULL);
3227 }
3228#endif
3229 res=kNF1(F,Q,pp,strat,lazyReduce);
3230 }
3231 else
3232 res=kNF2(F,Q,pp,strat,lazyReduce);
3233 delete(strat);
3234
3235#ifdef HAVE_PLURAL
3236 if(pp != p)
3237 p_Delete(&pp, currRing);
3238#endif
3239 return res;
3240}
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;
2288 SI_SAVE_OPT1(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);
2419 SI_RESTORE_OPT1(save1);
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:6883
void enterT(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9178
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9627
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9278
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition: kutil.cc:294
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9713
#define setmaxTinc
Definition: kutil.h:34
class sLObject LObject
Definition: kutil.h:58
#define omFree(addr)
Definition: omAllocDecl.h:261
#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;
2142 SI_SAVE_OPT1(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);
2266 SI_RESTORE_OPT1(save1);
2267 if (TEST_OPT_PROT) PrintLn();
2268 return p;
2269}
void kDebugPrint(kStrategy strat)
Definition: kutil.cc:11560
#define KSTD_NF_ECART
Definition: kstd1.h:19
BOOLEAN kTest(kStrategy strat)
Definition: kutil.cc:1012
#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 3349 of file kstd1.cc.

3350{
3351 ideal res;
3352 if (TEST_OPT_PROT)
3353 {
3354 Print("(S:%d)",IDELEMS(p));mflush();
3355 }
3356 if (idIs0(p))
3357 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3358
3359 ideal pp = p;
3360#ifdef HAVE_PLURAL
3361 if(rIsSCA(currRing))
3362 {
3363 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3364 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3365 pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3366
3367 if(Q == currRing->qideal)
3369 }
3370#endif
3371
3372 if ((idIs0(F))&&(Q==NULL))
3373 {
3374#ifdef HAVE_PLURAL
3375 if(p != pp)
3376 return pp;
3377#endif
3378 return idCopy(p); /*F+Q=0*/
3379 }
3380
3381 kStrategy strat=new skStrategy;
3382 strat->syzComp = syzComp;
3384 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3385 {
3386 strat->ak = si_max(strat->ak,(int)F->rank);
3387 }
3388
3389 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3390 delete(strat);
3391
3392#ifdef HAVE_PLURAL
3393 if(pp != p)
3395#endif
3396
3397 return res;
3398}
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:4042

◆ kNFBound() [2/2]

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

Definition at line 3242 of file kstd1.cc.

3243{
3244 if (p==NULL)
3245 return NULL;
3246
3247 poly pp = p;
3248
3249#ifdef HAVE_PLURAL
3250 if(rIsSCA(currRing))
3251 {
3252 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3253 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3254 pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3255
3256 if(Q == currRing->qideal)
3258 }
3259#endif
3260
3261 if ((idIs0(F))&&(Q==NULL))
3262 {
3263#ifdef HAVE_PLURAL
3264 if(p != pp)
3265 return pp;
3266#endif
3267 return pCopy(p); /*F+Q=0*/
3268 }
3269
3270 kStrategy strat=new skStrategy;
3271 strat->syzComp = syzComp;
3273 poly res;
3274 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3275 delete(strat);
3276
3277#ifdef HAVE_PLURAL
3278 if(pp != p)
3279 p_Delete(&pp, currRing);
3280#endif
3281 return res;
3282}

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

2636{
2637 if(idIs0(F))
2638 return idInit(1,F->rank);
2640 {
2641 ideal r;
2642 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2643 BOOLEAN delete_w=(w==NULL);
2644 kStrategy strat=new skStrategy;
2645 strat->sbaOrder = sbaOrder;
2646 if (arri!=0)
2647 {
2648 strat->rewCrit1 = arriRewDummy;
2649 strat->rewCrit2 = arriRewCriterion;
2651 }
2652 else
2653 {
2657 }
2658
2660 strat->syzComp = syzComp;
2661 if (TEST_OPT_SB_1)
2662 //if(!rField_is_Ring(currRing)) // always true here
2663 strat->newIdeal = newIdeal;
2665 strat->LazyPass=20;
2666 else
2667 strat->LazyPass=2;
2668 strat->LazyDegree = 1;
2672 strat->ak = id_RankFreeModule(F,currRing);
2673 strat->kModW=kModW=NULL;
2674 strat->kHomW=kHomW=NULL;
2675 if (vw != NULL)
2676 {
2677 currRing->pLexOrder=FALSE;
2678 strat->kHomW=kHomW=vw;
2679 strat->pOrigFDeg = currRing->pFDeg;
2680 strat->pOrigLDeg = currRing->pLDeg;
2682 toReset = TRUE;
2683 }
2684 if (h==testHomog)
2685 {
2686 if (strat->ak == 0)
2687 {
2688 h = (tHomog)idHomIdeal(F,Q);
2689 w=NULL;
2690 }
2691 else if (!TEST_OPT_DEGBOUND)
2692 {
2693 if (w!=NULL)
2694 h = (tHomog)idHomModule(F,Q,w);
2695 else
2696 h = (tHomog)idHomIdeal(F,Q);
2697 }
2698 }
2699 currRing->pLexOrder=b;
2700 if (h==isHomog)
2701 {
2702 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2703 {
2704 strat->kModW = kModW = *w;
2705 if (vw == NULL)
2706 {
2707 strat->pOrigFDeg = currRing->pFDeg;
2708 strat->pOrigLDeg = currRing->pLDeg;
2710 toReset = TRUE;
2711 }
2712 }
2713 currRing->pLexOrder = TRUE;
2714 if (hilb==NULL) strat->LazyPass*=2;
2715 }
2716 strat->homog=h;
2717 #ifdef KDEBUG
2718 idTest(F);
2719 if(Q != NULL)
2720 idTest(Q);
2721 #endif
2722 #ifdef HAVE_PLURAL
2724 {
2725 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2726 strat->no_prod_crit = ! bIsSCA;
2727 if (w!=NULL)
2728 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2729 else
2730 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2731 }
2732 else
2733 #endif
2734 {
2736 {
2737 if (w!=NULL)
2738 r=mora(F,Q,*w,hilb,strat);
2739 else
2740 r=mora(F,Q,NULL,hilb,strat);
2741 }
2742 else
2743 {
2744 strat->sigdrop = FALSE;
2745 if (w!=NULL)
2746 r=sba(F,Q,*w,hilb,strat);
2747 else
2748 r=sba(F,Q,NULL,hilb,strat);
2749 }
2750 }
2751 #ifdef KDEBUG
2752 idTest(r);
2753 #endif
2754 if (toReset)
2755 {
2756 kModW = NULL;
2758 }
2759 currRing->pLexOrder = b;
2760 //Print("%d reductions canceled \n",strat->cel);
2761 //delete(strat);
2762 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2763 return r;
2764 }
2765 else
2766 {
2767 //--------------------------RING CASE-------------------------
2768 assume(sbaOrder == 1);
2769 assume(arri == 0);
2770 ideal r;
2771 r = idCopy(F);
2772 int sbaEnterS = -1;
2773 bool sigdrop = TRUE;
2774 //This is how we set the SBA algorithm;
2775 int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2776 while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2777 && (blockred <= blockedreductions))
2778 {
2779 loops++;
2780 if(loops == 1)
2781 sigdrop = FALSE;
2782 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2783 BOOLEAN delete_w=(w==NULL);
2784 kStrategy strat=new skStrategy;
2785 strat->sbaEnterS = sbaEnterS;
2786 strat->sigdrop = sigdrop;
2787 #if 0
2788 strat->blockred = blockred;
2789 #else
2790 strat->blockred = 0;
2791 #endif
2792 strat->blockredmax = blockedreductions;
2793 //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2794 //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2795 strat->sbaOrder = sbaOrder;
2796 if (arri!=0)
2797 {
2798 strat->rewCrit1 = arriRewDummy;
2799 strat->rewCrit2 = arriRewCriterion;
2801 }
2802 else
2803 {
2807 }
2808
2810 strat->syzComp = syzComp;
2811 if (TEST_OPT_SB_1)
2813 strat->newIdeal = newIdeal;
2815 strat->LazyPass=20;
2816 else
2817 strat->LazyPass=2;
2818 strat->LazyDegree = 1;
2822 strat->ak = id_RankFreeModule(F,currRing);
2823 strat->kModW=kModW=NULL;
2824 strat->kHomW=kHomW=NULL;
2825 if (vw != NULL)
2826 {
2827 currRing->pLexOrder=FALSE;
2828 strat->kHomW=kHomW=vw;
2829 strat->pOrigFDeg = currRing->pFDeg;
2830 strat->pOrigLDeg = currRing->pLDeg;
2832 toReset = TRUE;
2833 }
2834 if (h==testHomog)
2835 {
2836 if (strat->ak == 0)
2837 {
2838 h = (tHomog)idHomIdeal(F,Q);
2839 w=NULL;
2840 }
2841 else if (!TEST_OPT_DEGBOUND)
2842 {
2843 if (w!=NULL)
2844 h = (tHomog)idHomModule(F,Q,w);
2845 else
2846 h = (tHomog)idHomIdeal(F,Q);
2847 }
2848 }
2849 currRing->pLexOrder=b;
2850 if (h==isHomog)
2851 {
2852 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2853 {
2854 strat->kModW = kModW = *w;
2855 if (vw == NULL)
2856 {
2857 strat->pOrigFDeg = currRing->pFDeg;
2858 strat->pOrigLDeg = currRing->pLDeg;
2860 toReset = TRUE;
2861 }
2862 }
2863 currRing->pLexOrder = TRUE;
2864 if (hilb==NULL) strat->LazyPass*=2;
2865 }
2866 strat->homog=h;
2867 #ifdef KDEBUG
2868 idTest(F);
2869 if(Q != NULL)
2870 idTest(Q);
2871 #endif
2872 #ifdef HAVE_PLURAL
2874 {
2875 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2876 strat->no_prod_crit = ! bIsSCA;
2877 if (w!=NULL)
2878 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2879 else
2880 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2881 }
2882 else
2883 #endif
2884 {
2886 {
2887 if (w!=NULL)
2888 r=mora(F,Q,*w,hilb,strat);
2889 else
2890 r=mora(F,Q,NULL,hilb,strat);
2891 }
2892 else
2893 {
2894 if (w!=NULL)
2895 r=sba(r,Q,*w,hilb,strat);
2896 else
2897 {
2898 r=sba(r,Q,NULL,hilb,strat);
2899 }
2900 }
2901 }
2902 #ifdef KDEBUG
2903 idTest(r);
2904 #endif
2905 if (toReset)
2906 {
2907 kModW = NULL;
2909 }
2910 currRing->pLexOrder = b;
2911 //Print("%d reductions canceled \n",strat->cel);
2912 sigdrop = strat->sigdrop;
2913 sbaEnterS = strat->sbaEnterS;
2914 blockred = strat->blockred;
2915 delete(strat);
2916 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2917 }
2918 // Go to std
2919 if(sigdrop || blockred > blockedreductions)
2920 {
2921 r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2922 }
2923 return r;
2924 }
2925}
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
if(!FE_OPT_NO_SHELL_FLAG)(void) system(sys)
#define idTest(id)
Definition: ideals.h:47
KINLINE BOOLEAN arriRewDummy(poly, unsigned long, poly, kStrategy, int)
Definition: kInline.h:1264
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:2994
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition: kutil.cc:6689
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition: kutil.cc:6664
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition: kutil.cc:1952
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition: kutil.cc:6605
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3458
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3217
#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 2449 of file kstd1.cc.

2451{
2452 if(idIs0(F))
2453 return idInit(1,F->rank);
2454
2455 if((Q!=NULL)&&(idIs0(Q))) Q=NULL;
2456#ifdef HAVE_SHIFTBBA
2457 if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
2458#endif
2459
2460 ideal r;
2461 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2462 BOOLEAN delete_w=(w==NULL);
2463 kStrategy strat=new skStrategy;
2464
2465 strat->s_poly=sp;
2467 strat->syzComp = syzComp;
2468 if (TEST_OPT_SB_1
2470 )
2471 strat->newIdeal = newIdeal;
2473 strat->LazyPass=20;
2474 else
2475 strat->LazyPass=2;
2476 strat->LazyDegree = 1;
2477 strat->ak = id_RankFreeModule(F,currRing);
2478 strat->kModW=kModW=NULL;
2479 strat->kHomW=kHomW=NULL;
2480 if (vw != NULL)
2481 {
2482 currRing->pLexOrder=FALSE;
2483 strat->kHomW=kHomW=vw;
2484 strat->pOrigFDeg = currRing->pFDeg;
2485 strat->pOrigLDeg = currRing->pLDeg;
2487 toReset = TRUE;
2488 }
2489 if (h==testHomog)
2490 {
2491 if (strat->ak == 0)
2492 {
2493 h = (tHomog)idHomIdeal(F,Q);
2494 w=NULL;
2495 }
2496 else if (!TEST_OPT_DEGBOUND)
2497 {
2498 if (w!=NULL)
2499 h = (tHomog)idHomModule(F,Q,w);
2500 else
2501 h = (tHomog)idHomIdeal(F,Q);
2502 }
2503 }
2504 currRing->pLexOrder=b;
2505 if (h==isHomog)
2506 {
2507 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2508 {
2509 strat->kModW = kModW = *w;
2510 if (vw == NULL)
2511 {
2512 strat->pOrigFDeg = currRing->pFDeg;
2513 strat->pOrigLDeg = currRing->pLDeg;
2515 toReset = TRUE;
2516 }
2517 }
2518 currRing->pLexOrder = TRUE;
2519 if (hilb==NULL) strat->LazyPass*=2;
2520 }
2521 strat->homog=h;
2522#ifdef KDEBUG
2523 idTest(F);
2524 if (Q!=NULL) idTest(Q);
2525#endif
2526#ifdef HAVE_PLURAL
2528 {
2529 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2530 strat->no_prod_crit = ! bIsSCA;
2531 if (w!=NULL)
2532 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2533 else
2534 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2535 }
2536 else
2537#endif
2538 {
2539 #if PRE_INTEGER_CHECK
2540 //the preinteger check strategy is not for modules
2541 if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2542 {
2543 ideal FCopy = idCopy(F);
2544 poly pFmon = preIntegerCheck(FCopy, Q);
2545 if(pFmon != NULL)
2546 {
2547 idInsertPoly(FCopy, pFmon);
2548 strat->kModW=kModW=NULL;
2549 if (h==testHomog)
2550 {
2551 if (strat->ak == 0)
2552 {
2553 h = (tHomog)idHomIdeal(FCopy,Q);
2554 w=NULL;
2555 }
2556 else if (!TEST_OPT_DEGBOUND)
2557 {
2558 if (w!=NULL)
2559 h = (tHomog)idHomModule(FCopy,Q,w);
2560 else
2561 h = (tHomog)idHomIdeal(FCopy,Q);
2562 }
2563 }
2564 currRing->pLexOrder=b;
2565 if (h==isHomog)
2566 {
2567 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2568 {
2569 strat->kModW = kModW = *w;
2570 if (vw == NULL)
2571 {
2572 strat->pOrigFDeg = currRing->pFDeg;
2573 strat->pOrigLDeg = currRing->pLDeg;
2575 toReset = TRUE;
2576 }
2577 }
2578 currRing->pLexOrder = TRUE;
2579 if (hilb==NULL) strat->LazyPass*=2;
2580 }
2581 strat->homog=h;
2582 }
2583 omTestMemory(1);
2584 if(w == NULL)
2585 {
2587 r=mora(FCopy,Q,NULL,hilb,strat);
2588 else
2589 r=bba(FCopy,Q,NULL,hilb,strat);
2590 }
2591 else
2592 {
2594 r=mora(FCopy,Q,*w,hilb,strat);
2595 else
2596 r=bba(FCopy,Q,*w,hilb,strat);
2597 }
2598 idDelete(&FCopy);
2599 }
2600 else
2601 #endif
2602 {
2603 if(w==NULL)
2604 {
2606 r=mora(F,Q,NULL,hilb,strat);
2607 else
2608 r=bba(F,Q,NULL,hilb,strat);
2609 }
2610 else
2611 {
2613 r=mora(F,Q,*w,hilb,strat);
2614 else
2615 r=bba(F,Q,*w,hilb,strat);
2616 }
2617 }
2618 }
2619#ifdef KDEBUG
2620 idTest(r);
2621#endif
2622 if (toReset)
2623 {
2624 kModW = NULL;
2626 }
2627 currRing->pLexOrder = b;
2628//Print("%d reductions canceled \n",strat->cel);
2629 delete(strat);
2630 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2631 return r;
2632}
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:2928
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:10596
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 2928 of file kstd1.cc.

2930{
2932 assume(idIsInV(F));
2933 ideal r;
2934 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2935 BOOLEAN delete_w=(w==NULL);
2936 kStrategy strat=new skStrategy;
2937 intvec* temp_w=NULL;
2938
2939 strat->rightGB = rightGB;
2940
2942 strat->syzComp = syzComp;
2943 if (TEST_OPT_SB_1)
2945 strat->newIdeal = newIdeal;
2947 strat->LazyPass=20;
2948 else
2949 strat->LazyPass=2;
2950 strat->LazyDegree = 1;
2951 strat->ak = id_RankFreeModule(F,currRing);
2952 strat->kModW=kModW=NULL;
2953 strat->kHomW=kHomW=NULL;
2954 if (vw != NULL)
2955 {
2956 currRing->pLexOrder=FALSE;
2957 strat->kHomW=kHomW=vw;
2958 strat->pOrigFDeg = currRing->pFDeg;
2959 strat->pOrigLDeg = currRing->pLDeg;
2961 toReset = TRUE;
2962 }
2963 if (h==testHomog)
2964 {
2965 if (strat->ak == 0)
2966 {
2967 h = (tHomog)idHomIdeal(F,Q);
2968 w=NULL;
2969 }
2970 else if (!TEST_OPT_DEGBOUND)
2971 {
2972 if (w!=NULL)
2973 h = (tHomog)idHomModule(F,Q,w);
2974 else
2975 h = (tHomog)idHomIdeal(F,Q);
2976 }
2977 }
2978 currRing->pLexOrder=b;
2979 if (h==isHomog)
2980 {
2981 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2982 {
2983 strat->kModW = kModW = *w;
2984 if (vw == NULL)
2985 {
2986 strat->pOrigFDeg = currRing->pFDeg;
2987 strat->pOrigLDeg = currRing->pLDeg;
2989 toReset = TRUE;
2990 }
2991 }
2992 currRing->pLexOrder = TRUE;
2993 if (hilb==NULL) strat->LazyPass*=2;
2994 }
2995 strat->homog=h;
2996#ifdef KDEBUG
2997 idTest(F);
2998#endif
3000 {
3001 /* error: no local ord yet with shifts */
3002 WerrorS("No local ordering possible for shift algebra");
3003 return(NULL);
3004 }
3005 else
3006 {
3007 /* global ordering */
3008 if (w!=NULL)
3009 r=bbaShift(F,Q,*w,hilb,strat);
3010 else
3011 r=bbaShift(F,Q,NULL,hilb,strat);
3012 }
3013#ifdef KDEBUG
3014 idTest(r);
3015#endif
3016 if (toReset)
3017 {
3018 kModW = NULL;
3020 }
3021 currRing->pLexOrder = b;
3022//Print("%d reductions canceled \n",strat->cel);
3023 delete(strat);
3024 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
3025 assume(idIsInV(r));
3026 return r;
3027}
char rightGB
Definition: kutil.h:369
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:4601
#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;
1895 SI_SAVE_OPT1(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)
2060 khCheck(Q,w,hilb,hilbeledeg,hilbcount,strat);
2061 else
2062 khCheckLocInhom(Q,w,hilb,hilbcount,strat);
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));
2108 if ((TEST_OPT_PROT)||(TEST_OPT_DEBUG)) messageStat(hilbcount,strat);
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);
2121 SI_RESTORE_OPT1(save1);
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: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: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:3841
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:7512
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:9800
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:1073
void enterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4509
void initHilbCrit(ideal, ideal, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9458
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L, TObject *T, unsigned long expbound)
Definition: kutil.cc:11021
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:9885
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:4685
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10534
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10128
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:4478
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1215
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11114
void messageSets(kStrategy strat)
Definition: kutil.cc:7585
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7553
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition: kutil.cc:10928
void cancelunit(LObject *L, BOOLEAN inNF)
Definition: kutil.cc:373
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 4965 of file kstd2.cc.

4966{
4968 assume(idIsInV(F));
4969 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4970 idSkipZeroes(RS); // is this even necessary?
4971 assume(idIsInV(RS));
4972 return(RS);
4973}

◆ 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.