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
 
#define KSTD_NF_NOLF   8
 

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_NOLF

#define KSTD_NF_NOLF   8

Definition at line 23 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 /* NF(A 0 E,quot E 0)
362 * A,quot: 1..k, 0,E: k+1..k+IDELEMS(quot),
363 * E,0: k+IDELEMS(quot)..k+IDELEMS(quot)+IDELEMS(A) */
364 /* new ring */
368 /* move ideals to new ring */
370 ideal s_A;
371 if (orig_ring != syz_ring)
372 {
375 }
376 else
377 {
380 }
381 /* quot[i] -> quot[i]+e(k+i+1) */
382 for(int i=0;i<IDELEMS(s_quot);i++)
383 {
385 poly p=p_One(syz_ring);
388 s_quot->m[i]=p_Add_q(s_quot->m[i],p,syz_ring);
389 }
390 s_quot->rank=k+IDELEMS(quot)+1;
391 /* A[i] -> A[i]*e(1) */
392 if (lsmod==1)
393 {
394 for(int i=0;i<IDELEMS(s_A);i++)
395 {
396 p_Shift(&s_A->m[i],1,syz_ring);
397 }
398 }
399 if (unit!=NULL)
400 {
401 int u_k=k+IDELEMS(quot)+2;
402 for(int i=0;i<IDELEMS(s_A);i++)
403 {
404 poly p=p_One(syz_ring);
407 s_A->m[i]=p_Add_q(s_A->m[i],p,syz_ring);
408 }
409 s_A->rank=k+IDELEMS(quot)+IDELEMS(A)+1;
410 }
411 /* normalform */
412 #if 0
413 PrintS("to reduce:\n");
414 {
415 void ipPrint_MA0(matrix m, const char *name);
417 ipPrint_MA0(m, "A");
419 }
420 PrintS("with:\n");
421 {
422 void ipPrint_MA0(matrix m, const char *name);
424 ipPrint_MA0(m, "B");
426 }
427 #endif
429 #if 0
430 PrintS("result NF:\n");
431 {
432 void ipPrint_MA0(matrix m, const char *name);
434 ipPrint_MA0(m, "A");
436 }
437 #endif
438 /* clean s_quot,s_A */
441 /* interpret rest: remainder */
443 for(int i=0;i<IDELEMS(rest);i++)
444 {
445 poly p=rest->m[i];
446 poly d=NULL;
447 while(p!=NULL)
448 {
449 poly q=p; pIter(p);
450 pNext(q)=NULL;
451 if (p_GetComp(q,syz_ring)<=k)
452 {
453 result->m[i]=p_Add_q(result->m[i],q,syz_ring);
454 }
455 else
456 {
457 d=p_Add_q(d,q,syz_ring);
458 }
459 }
460 rest->m[i]=d;
462 }
463 #if 0
464 PrintS("rest:\n");
465 {
466 void ipPrint_MA0(matrix m, const char *name);
468 ipPrint_MA0(m, "_");
470 }
471 #endif
472 #if 0
473 PrintS("factor+unit:\n");
474 {
475 void ipPrint_MA0(matrix m, const char *name);
477 ipPrint_MA0(m, "_");
479 }
480 #endif
481 /* interpret rest: factors */
483 if (unit==NULL)
484 {
485 for(int i=0;i<IDELEMS(rest);i++)
486 {
487 poly p=rest->m[i];
489 factor->m[i]=p;
490 factor->m[i]=p_Neg(factor->m[i],syz_ring);
491 rest->m[i]=NULL;
492 }
493 }
494 else
495 {
497 /* comp k+1..u_k-1 -> rest, u_k.. -> unit*/
498 int u_k=k+IDELEMS(quot)+2;
499 for(int i=0;i<IDELEMS(rest);i++)
500 {
501 poly p=rest->m[i];
502 rest->m[i]=NULL;
503 poly d=NULL;
504 while(p!=NULL)
505 {
506 poly q=p; pIter(p);
507 pNext(q)=NULL;
508 if(p_GetComp(q,syz_ring)<u_k)
509 {
510 p_Shift(&q,-k-1,syz_ring);
511 factor->m[i]=p_Add_q(factor->m[i],q,syz_ring);
512 }
513 else
514 {
515 d=p_Add_q(d,q,syz_ring);
516 }
517 }
518 (*unit)->m[i]=d;
519 /*fix sign:*/
520 factor->m[i]=p_Neg(factor->m[i],syz_ring);
521 p_Shift(&(*unit)->m[i],-(IDELEMS(quot)+k+1),syz_ring);
522 }
523 }
525 if (orig_ring != syz_ring)
526 {
530 if (unit!=NULL)
531 {
533 }
535 }
536 return result;
537}
#define TRUE
Definition auxiliary.h:100
int m
Definition cfEzgcd.cc:128
int i
Definition cfEzgcd.cc:132
int k
Definition cfEzgcd.cc:99
int p
Definition cfModGcd.cc:4086
return result
CanonicalForm factor
Definition facAbsFact.cc:97
char name(const Variable &v)
Definition factory.h:189
void ipPrint_MA0(matrix m, const char *name)
Definition ipprint.cc:57
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:3237
#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:4756
poly p_One(const ring r)
Definition p_polys.cc:1314
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
void PrintS(const char *s)
Definition reporter.cc:284
ring rAssure_SyzOrder(const ring r, BOOLEAN complete)
Definition ring.cc:4461
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:452
void rSetSyzComp(int k, const ring r)
Definition ring.cc:5169
ideal idInit(int idsize, int rank)
initialise an ideal / module
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
matrix id_Module2Matrix(ideal mod, const ring R)
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 1812 of file kstd1.cc.

1813{
1814 int i,j;
1815
1816 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1817 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1818 strat->enterS = enterSMora;
1819 strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1820 strat->posInLOld = strat->posInL;
1821 strat->posInLOldFlag = TRUE;
1822 strat->initEcart = initEcartNormal;
1823 strat->kAllAxis = (currRing->ppNoether) != NULL;
1824 if ( strat->kAllAxis )
1825 {
1826 strat->kNoether = pCopy((currRing->ppNoether));
1827 if (TEST_OPT_PROT)
1828 {
1829 Print("H(%ld)",p_FDeg(strat->kNoether,currRing)+1);
1830 mflush();
1831 }
1832 }
1833 if (strat->homog)
1834 strat->red = redFirst; /*take the first possible in T*/
1835 else
1836 strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1837 if (strat->kAllAxis)
1838 {
1839 HCord = currRing->pFDeg((strat->kNoether),currRing)+1;
1840 }
1841 else
1842 {
1843 HCord = INT_MAX-3;/*- very large -*/
1844 }
1845
1847 {
1848 if (rField_is_Z(currRing))
1849 strat->red = redRiloc_Z;
1850 else
1851 strat->red = redRiloc;
1852 }
1853
1854 /*reads the ecartWeights used for Graebes method from the
1855 *intvec ecart and set ecartWeights
1856 */
1857 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1858 {
1859 //interred machen Aenderung
1860 strat->pOrigFDeg=currRing->pFDeg;
1861 strat->pOrigLDeg=currRing->pLDeg;
1862 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1863 /*uses automatic computation of the ecartWeights to set them*/
1865
1867 if (TEST_OPT_PROT)
1868 {
1869 for(i=1; i<=(currRing->N); i++)
1870 Print(" %d",ecartWeights[i]);
1871 PrintLn();
1872 mflush();
1873 }
1874 }
1875 kOptimizeLDeg(currRing->pLDeg, strat);
1876}
int BOOLEAN
Definition auxiliary.h:87
char posInLOldFlag
Definition kutil.h:380
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:374
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:370
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:795
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:386
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1621
int redRiloc_Z(LObject *h, kStrategy strat)
Definition kstd1.cc:567
VAR int HCord
Definition kutil.cc:244
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition kutil.cc:1320
void initEcartNormal(TObject *h)
Definition kutil.cc:1298
#define omAlloc(size)
#define TEST_OPT_WEIGHTM
Definition options.h:123
#define TEST_OPT_PROT
Definition options.h:105
void pSetDegProcs(ring r, pFDegProc new_FDeg, pLDegProc new_lDeg)
Definition p_polys.cc:3658
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:514
#define rField_is_Ring(R)
Definition ring.h:490
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 3451 of file kstd1.cc.

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

◆ kHomModDeg()

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

Definition at line 2419 of file kstd1.cc.

2420{
2421 int i;
2422 long j=0;
2423
2424 for (i=r->N;i>0;i--)
2425 j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2426 if (kModW == NULL) return j;
2427 i = __p_GetComp(p,r);
2428 if (i==0) return j;
2429 return j+(*kModW)[i-1];
2430}
VAR intvec * kModW
Definition kstd1.cc:2407
#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 3809 of file kstd1.cc.

3810{
3811#ifdef HAVE_PLURAL
3812 if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3813#endif
3816 )
3817 return kInterRedOld(F,Q);
3818
3819 //return kInterRedOld(F,Q);
3820
3821 BITSET save1;
3823 //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3825 //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3826 //si_opt_1&= ~Sy_bit(OPT_REDSB);
3827 //extern char * showOption() ;
3828 //Print("%s\n",showOption());
3829
3830 int need_retry;
3831 int counter=3;
3832 ideal res, res1;
3833 int elems=0;
3834 ideal null=NULL;
3835 if ((Q==NULL) || (!TEST_OPT_REDSB))
3836 {
3837 elems=idElem(F);
3839 }
3840 else
3841 {
3842 ideal FF=idSimpleAdd(F,Q);
3844 idDelete(&FF);
3845 null=idInit(1,1);
3846 if (need_retry)
3848 else
3849 res1=kNF(null,Q,res);
3850 idDelete(&res);
3851 res=res1;
3852 need_retry=1;
3853 }
3854 if (idElem(res)<=1) need_retry=0;
3855 while (need_retry && (counter>0))
3856 {
3857 #ifdef KDEBUG
3858 if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3859 #endif
3861 int new_elems=idElem(res1);
3862 counter -= (new_elems >= elems);
3863 elems = new_elems;
3864 idDelete(&res);
3865 if (idElem(res1)<=1) need_retry=0;
3866 if ((Q!=NULL) && (TEST_OPT_REDSB))
3867 {
3868 if (need_retry)
3870 else
3871 res=kNF(null,Q,res1);
3872 idDelete(&res1);
3873 }
3874 else
3875 res = res1;
3876 if (idElem(res)<=1) need_retry=0;
3877 }
3878 if (null!=NULL) idDelete(&null);
3881 return res;
3882}
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:3558
ideal kInterRedOld(ideal F, const ideal Q)
Definition kstd1.cc:3464
#define KSTD_NF_LAZY
Definition kstd1.h:17
#define KSTD_NF_NONORM
Definition kstd1.h:21
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:83
#define Sy_bit(x)
Definition options.h:31
#define TEST_OPT_REDSB
Definition options.h:106
#define TEST_OPT_DEBUG
Definition options.h:110
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:405
static BOOLEAN rField_is_numeric(const ring r)
Definition ring.h:520
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition ring.h:767
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 3464 of file kstd1.cc.

3465{
3466 int j;
3467 kStrategy strat = new skStrategy;
3468
3469 ideal tempF = F;
3470 ideal tempQ = Q;
3471
3472#ifdef HAVE_PLURAL
3473 if(rIsSCA(currRing))
3474 {
3475 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3476 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3478
3479 // this should be done on the upper level!!! :
3480 // tempQ = SCAQuotient(currRing);
3481
3482 if(Q == currRing->qideal)
3484 }
3485#endif
3486
3487// if (TEST_OPT_PROT)
3488// {
3489// writeTime("start InterRed:");
3490// mflush();
3491// }
3492 //strat->syzComp = 0;
3493 strat->kAllAxis = (currRing->ppNoether) != NULL;
3494 strat->kNoether=pCopy((currRing->ppNoether));
3496 initBuchMoraCrit(strat);
3497 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3498 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3499 strat->enterS = enterSBba;
3500 strat->posInT = posInT17;
3501 strat->initEcart = initEcartNormal;
3502 strat->sl = -1;
3503 strat->tl = -1;
3504 strat->tmax = setmaxT;
3505 strat->T = initT();
3506 strat->R = initR();
3507 strat->sevT = initsevT();
3509 initS(tempF, tempQ, strat);
3510 if (TEST_OPT_REDSB)
3511 strat->noTailReduction=FALSE;
3512 updateS(TRUE,strat);
3514 completeReduce(strat);
3515 //else if (TEST_OPT_PROT) PrintLn();
3516 cleanT(strat);
3517 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
3518 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3519 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3520 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3521 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3522 omfree(strat->sevT);
3523 omfree(strat->S_2_R);
3524 omfree(strat->R);
3525
3526 if (strat->fromQ)
3527 {
3528 for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3529 {
3530 if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3531 }
3532 omFree((ADDRESS)strat->fromQ);
3533 strat->fromQ=NULL;
3534 }
3535// if (TEST_OPT_PROT)
3536// {
3537// writeTime("end Interred:");
3538// mflush();
3539// }
3540 ideal shdl=strat->Shdl;
3542 if (strat->fromQ)
3543 {
3544 omfree(strat->fromQ);
3545 strat->fromQ=NULL;
3547 idDelete(&shdl);
3548 shdl=res;
3549 }
3550 delete(strat);
3551#ifdef HAVE_PLURAL
3552 if( tempF != F )
3554#endif
3555 return shdl;
3556}
#define FALSE
Definition auxiliary.h:96
int * S_2_R
Definition kutil.h:342
char noTailReduction
Definition kutil.h:376
TSet T
Definition kutil.h:326
intset ecartS
Definition kutil.h:309
char honey
Definition kutil.h:375
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:3809
int posInT17(const TSet set, const int length, LObject &p)
Definition kutil.cc:5283
void initS(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7588
void updateS(BOOLEAN toT, kStrategy strat)
Definition kutil.cc:8553
void cleanT(kStrategy strat)
Definition kutil.cc:563
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9429
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition kutil.cc:10279
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8788
#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 omFree(addr)
#define TEST_OPT_INTSTRATEGY
Definition options.h:112
#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 3086 of file kstd1.cc.

3088{
3089 if(idIs0(F))
3090 {
3091 M=idInit(1,F->rank);
3092 return idInit(1,F->rank);
3093 }
3095 {
3096 ideal sb;
3097 sb = kStd(F, Q, h, w, hilb);
3099 if(IDELEMS(sb) <= IDELEMS(F))
3100 {
3101 M = idCopy(sb);
3102 idSkipZeroes(M);
3103 return(sb);
3104 }
3105 else
3106 {
3107 M = idCopy(F);
3108 idSkipZeroes(M);
3109 return(sb);
3110 }
3111 }
3112 ideal r=NULL;
3113 int Kstd1_OldDeg = Kstd1_deg,i;
3115 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3118 kStrategy strat=new skStrategy;
3119
3121 strat->syzComp = syzComp;
3123 strat->LazyPass=20;
3124 else
3125 strat->LazyPass=2;
3126 strat->LazyDegree = 1;
3127 strat->minim=(reduced % 2)+1;
3128 strat->ak = id_RankFreeModule(F,currRing);
3129 if (delete_w)
3130 {
3131 temp_w=new intvec((strat->ak)+1);
3132 w = &temp_w;
3133 }
3134 if (h==testHomog)
3135 {
3136 if (strat->ak == 0)
3137 {
3138 h = (tHomog)idHomIdeal(F,Q);
3139 w=NULL;
3140 }
3141 else
3142 {
3143 h = (tHomog)idHomModule(F,Q,w);
3144 }
3145 }
3146 if (h==isHomog)
3147 {
3148 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3149 {
3150 kModW = *w;
3151 strat->kModW = *w;
3152 assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3153 strat->pOrigFDeg = currRing->pFDeg;
3154 strat->pOrigLDeg = currRing->pLDeg;
3156
3157 toReset = TRUE;
3158 if (reduced>1)
3159 {
3161 Kstd1_deg = -1;
3162 for (i=IDELEMS(F)-1;i>=0;i--)
3163 {
3164 if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3165 Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3166 }
3167 }
3168 }
3169 currRing->pLexOrder = TRUE;
3170 strat->LazyPass*=2;
3171 }
3172 strat->homog=h;
3173 ideal SB=NULL;
3175 {
3176 r=idMinBase(F,&SB); // SB and M via minbase
3177 strat->M=r;
3178 r=SB;
3179 }
3180 else
3181 {
3182 if (w!=NULL)
3183 r=bba(F,Q,*w,hilb,strat);
3184 else
3185 r=bba(F,Q,NULL,hilb,strat);
3186 }
3187#ifdef KDEBUG
3188 {
3189 int i;
3190 for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3191 }
3192#endif
3193 idSkipZeroes(r);
3194 if (toReset)
3195 {
3197 kModW = NULL;
3198 }
3199 currRing->pLexOrder = b;
3200 if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3201 if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3202 {
3203 M=idInit(1,F->rank);
3204 M->m[0]=pOne();
3205 //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3206 if (strat->M!=NULL) idDelete(&strat->M);
3207 }
3208 else if (strat->M==NULL)
3209 {
3210 M=idInit(1,F->rank);
3211 WarnS("no minimal generating set computed");
3212 }
3213 else
3214 {
3215 idSkipZeroes(strat->M);
3216 M=strat->M;
3217 strat->M=NULL;
3218 }
3219 delete(strat);
3220 if (reduced>2)
3221 {
3223 if (!oldDegBound)
3224 si_opt_1 &= ~Sy_bit(OPT_DEGBOUND);
3225 }
3226 else
3227 {
3228 if (IDELEMS(M)>IDELEMS(r))
3229 {
3230 idDelete(&M);
3231 M=idCopy(r);
3232 }
3233 }
3234 return r;
3235}
CanonicalForm b
Definition cfModGcd.cc:4111
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:2409
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:2484
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:52
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:2622
#define assume(x)
Definition mod2.h:389
#define TEST_OPT_DEGBOUND
Definition options.h:115
#define TEST_OPT_RETURN_SB
Definition options.h:114
#define OPT_DEGBOUND
Definition options.h:91
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition p_polys.cc:3670
#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:553
#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 2409 of file kstd1.cc.

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

◆ kNF() [1/2]

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

Definition at line 3335 of file kstd1.cc.

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

◆ kNF() [2/2]

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

Definition at line 3237 of file kstd1.cc.

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

2259{
2260 assume(!idIs0(q));
2261 assume(!(idIs0(F)&&(Q==NULL)));
2262
2263// lazy_reduce flags: can be combined by |
2264//#define KSTD_NF_LAZY 1
2265 // do only a reduction of the leading term
2266//#define KSTD_NF_ECART 2
2267 // only local: reduce even with bad ecart
2268 poly p;
2269 int i;
2270 int j;
2271 int o;
2272 LObject h;
2273 ideal res;
2274 BITSET save1;
2276
2277 //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2278 //if ((idIs0(F))&&(Q==NULL))
2279 // return idCopy(q); /*F=0*/
2280 //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2281 /*- creating temp data structures------------------- -*/
2282 strat->kAllAxis = (currRing->ppNoether) != NULL;
2283 strat->kNoether=pCopy((currRing->ppNoether));
2286 && (0<Kstd1_deg)
2287 && ((strat->kNoether==NULL)
2289 {
2290 pLmDelete(&strat->kNoether);
2291 strat->kNoether=pOne();
2292 pSetExp(strat->kNoether,1, Kstd1_deg+1);
2293 pSetm(strat->kNoether);
2294 //strat->kAllAxis=TRUE;
2295 }
2296 initBuchMoraCrit(strat);
2298 initBuchMoraPosRing(strat);
2299 else
2300 initBuchMoraPos(strat);
2301 initMora(F,strat);
2302 strat->enterS = enterSMoraNF;
2303 /*- set T -*/
2304 strat->tl = -1;
2305 strat->tmax = setmaxT;
2306 strat->T = initT();
2307 strat->R = initR();
2308 strat->sevT = initsevT();
2309 /*- set S -*/
2310 strat->sl = -1;
2311 /*- init local data struct.-------------------------- -*/
2312 /*Shdl=*/initS(F,Q,strat);
2313 if ((strat->ak!=0)
2314 && (strat->kNoether!=NULL))
2315 {
2316 if (strat->ak!=1)
2317 {
2318 pSetComp(strat->kNoether,1);
2319 pSetmComp(strat->kNoether);
2320 poly p=pHead(strat->kNoether);
2321 pSetComp(p,strat->ak);
2322 pSetmComp(p);
2323 p=pAdd(strat->kNoether,p);
2324 strat->kNoether=pNext(p);
2326 }
2327 }
2328 if (((lazyReduce & KSTD_NF_LAZY)==0)
2329 && (!rField_is_Ring(currRing)))
2330 {
2331 for (i=strat->sl; i>=0; i--)
2332 pNorm(strat->S[i]);
2333 }
2334 /*- compute------------------------------------------- -*/
2335 res=idInit(IDELEMS(q),strat->ak);
2336 for (i=0; i<IDELEMS(q); i++)
2337 {
2338 if (q->m[i]!=NULL)
2339 {
2340 p = pCopy(q->m[i]);
2341 deleteHC(&p,&o,&j,strat);
2342 if (p!=NULL)
2343 {
2344 /*- puts the elements of S also to T -*/
2345 for (j=0; j<=strat->sl; j++)
2346 {
2347 h.p = strat->S[j];
2348 h.ecart = strat->ecartS[j];
2349 h.pLength = h.length = pLength(h.p);
2350 if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2351 else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2352 h.sev = strat->sevS[j];
2353 h.SetpFDeg();
2355 enterT_strong(h,strat);
2356 else
2357 enterT(h,strat);
2358 }
2359 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2361 {
2362 p = redMoraNFRing(p,strat, lazyReduce);
2363 }
2364 else
2365 p = redMoraNF(p,strat, lazyReduce);
2366 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2367 {
2368 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2369 p = redtail(p,strat->sl,strat);
2370 }
2371 cleanT(strat);
2372 }
2373 res->m[i]=p;
2374 }
2375 //else
2376 // res->m[i]=NULL;
2377 }
2378 /*- release temp data------------------------------- -*/
2379 assume(strat->L==NULL); /*strat->L unused */
2380 assume(strat->B==NULL); /*strat->B unused */
2381 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2382 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2383 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2384 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2385 omFree(strat->sevT);
2386 omFree(strat->S_2_R);
2387 omFree(strat->R);
2388 omfree((ADDRESS)strat->fromQ);
2389 strat->fromQ=NULL;
2390 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2391// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2392// {
2393// pFDeg=strat->pOrigFDeg;
2394// pLDeg=strat->pOrigLDeg;
2395// if (ecartWeights)
2396// {
2397// omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2398// ecartWeights=NULL;
2399// }
2400// }
2401 idDelete(&strat->Shdl);
2403 if (TEST_OPT_PROT) PrintLn();
2404 return res;
2405}
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:1812
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1674
static poly redMoraNFRing(poly h, kStrategy strat, int flag)
Definition kstd1.cc:1081
static poly redMoraNF(poly h, kStrategy strat, int flag)
Definition kstd1.cc:977
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition kutil.cc:6838
void enterT(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9137
void initBuchMoraPos(kStrategy strat)
Definition kutil.cc:9574
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9236
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition kutil.cc:291
void initBuchMoraPosRing(kStrategy strat)
Definition kutil.cc:9659
class sLObject LObject
Definition kutil.h:58
#define OPT_REDTAIL
Definition options.h:92
#define TEST_OPT_STAIRCASEBOUND
Definition options.h:117
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

◆ kNF1() [2/2]

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

Definition at line 2117 of file kstd1.cc.

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

◆ kNFBound() [1/2]

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

Definition at line 3400 of file kstd1.cc.

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

◆ kNFBound() [2/2]

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

Definition at line 3293 of file kstd1.cc.

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

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

2690{
2691 if(idIs0(F))
2692 return idInit(1,F->rank);
2694 {
2695 ideal r;
2696 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2698 kStrategy strat=new skStrategy;
2699 strat->sbaOrder = sbaOrder;
2700 if (arri!=0)
2701 {
2702 strat->rewCrit1 = arriRewDummy;
2703 strat->rewCrit2 = arriRewCriterion;
2705 }
2706 else
2707 {
2711 }
2712
2714 strat->syzComp = syzComp;
2715 if (TEST_OPT_SB_1)
2716 //if(!rField_is_Ring(currRing)) // always true here
2717 strat->newIdeal = newIdeal;
2719 strat->LazyPass=20;
2720 else
2721 strat->LazyPass=2;
2722 strat->LazyDegree = 1;
2726 strat->ak = id_RankFreeModule(F,currRing);
2727 strat->kModW=kModW=NULL;
2728 strat->kHomW=kHomW=NULL;
2729 if (vw != NULL)
2730 {
2731 currRing->pLexOrder=FALSE;
2732 strat->kHomW=kHomW=vw;
2733 strat->pOrigFDeg = currRing->pFDeg;
2734 strat->pOrigLDeg = currRing->pLDeg;
2736 toReset = TRUE;
2737 }
2738 if (h==testHomog)
2739 {
2740 if (strat->ak == 0)
2741 {
2742 h = (tHomog)idHomIdeal(F,Q);
2743 w=NULL;
2744 }
2745 else if (!TEST_OPT_DEGBOUND)
2746 {
2747 if (w!=NULL)
2748 h = (tHomog)idHomModule(F,Q,w);
2749 else
2750 h = (tHomog)idHomIdeal(F,Q);
2751 }
2752 }
2753 currRing->pLexOrder=b;
2754 if (h==isHomog)
2755 {
2756 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2757 {
2758 strat->kModW = kModW = *w;
2759 if (vw == NULL)
2760 {
2761 strat->pOrigFDeg = currRing->pFDeg;
2762 strat->pOrigLDeg = currRing->pLDeg;
2764 toReset = TRUE;
2765 }
2766 }
2767 currRing->pLexOrder = TRUE;
2768 if (hilb==NULL) strat->LazyPass*=2;
2769 }
2770 strat->homog=h;
2771 #ifdef KDEBUG
2772 idTest(F);
2773 if(Q != NULL)
2774 idTest(Q);
2775 #endif
2776 #ifdef HAVE_PLURAL
2778 {
2779 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2780 strat->no_prod_crit = ! bIsSCA;
2781 if (w!=NULL)
2782 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2783 else
2784 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2785 }
2786 else
2787 #endif
2788 {
2790 {
2791 if (w!=NULL)
2792 r=mora(F,Q,*w,hilb,strat);
2793 else
2794 r=mora(F,Q,NULL,hilb,strat);
2795 }
2796 else
2797 {
2798 strat->sigdrop = FALSE;
2799 if (w!=NULL)
2800 r=sba(F,Q,*w,hilb,strat);
2801 else
2802 r=sba(F,Q,NULL,hilb,strat);
2803 }
2804 }
2805 #ifdef KDEBUG
2806 idTest(r);
2807 #endif
2808 if (toReset)
2809 {
2810 kModW = NULL;
2812 }
2813 currRing->pLexOrder = b;
2814 //Print("%d reductions canceled \n",strat->cel);
2815 //delete(strat);
2816 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2817 return r;
2818 }
2819 else
2820 {
2821 //--------------------------RING CASE-------------------------
2822 assume(sbaOrder == 1);
2823 assume(arri == 0);
2824 ideal r;
2825 r = idCopy(F);
2826 int sbaEnterS = -1;
2827 bool sigdrop = TRUE;
2828 //This is how we set the SBA algorithm;
2829 int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2830 while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2831 && (blockred <= blockedreductions))
2832 {
2833 loops++;
2834 if(loops == 1)
2835 sigdrop = FALSE;
2836 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2838 kStrategy strat=new skStrategy;
2839 strat->sbaEnterS = sbaEnterS;
2840 strat->sigdrop = sigdrop;
2841 #if 0
2842 strat->blockred = blockred;
2843 #else
2844 strat->blockred = 0;
2845 #endif
2847 //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2848 //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2849 strat->sbaOrder = sbaOrder;
2850 if (arri!=0)
2851 {
2852 strat->rewCrit1 = arriRewDummy;
2853 strat->rewCrit2 = arriRewCriterion;
2855 }
2856 else
2857 {
2861 }
2862
2864 strat->syzComp = syzComp;
2865 if (TEST_OPT_SB_1)
2867 strat->newIdeal = newIdeal;
2869 strat->LazyPass=20;
2870 else
2871 strat->LazyPass=2;
2872 strat->LazyDegree = 1;
2876 strat->ak = id_RankFreeModule(F,currRing);
2877 strat->kModW=kModW=NULL;
2878 strat->kHomW=kHomW=NULL;
2879 if (vw != NULL)
2880 {
2881 currRing->pLexOrder=FALSE;
2882 strat->kHomW=kHomW=vw;
2883 strat->pOrigFDeg = currRing->pFDeg;
2884 strat->pOrigLDeg = currRing->pLDeg;
2886 toReset = TRUE;
2887 }
2888 if (h==testHomog)
2889 {
2890 if (strat->ak == 0)
2891 {
2892 h = (tHomog)idHomIdeal(F,Q);
2893 w=NULL;
2894 }
2895 else if (!TEST_OPT_DEGBOUND)
2896 {
2897 if (w!=NULL)
2898 h = (tHomog)idHomModule(F,Q,w);
2899 else
2900 h = (tHomog)idHomIdeal(F,Q);
2901 }
2902 }
2903 currRing->pLexOrder=b;
2904 if (h==isHomog)
2905 {
2906 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2907 {
2908 strat->kModW = kModW = *w;
2909 if (vw == NULL)
2910 {
2911 strat->pOrigFDeg = currRing->pFDeg;
2912 strat->pOrigLDeg = currRing->pLDeg;
2914 toReset = TRUE;
2915 }
2916 }
2917 currRing->pLexOrder = TRUE;
2918 if (hilb==NULL) strat->LazyPass*=2;
2919 }
2920 strat->homog=h;
2921 #ifdef KDEBUG
2922 idTest(F);
2923 if(Q != NULL)
2924 idTest(Q);
2925 #endif
2926 #ifdef HAVE_PLURAL
2928 {
2929 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2930 strat->no_prod_crit = ! bIsSCA;
2931 if (w!=NULL)
2932 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2933 else
2934 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2935 }
2936 else
2937 #endif
2938 {
2940 {
2941 if (w!=NULL)
2942 r=mora(F,Q,*w,hilb,strat);
2943 else
2944 r=mora(F,Q,NULL,hilb,strat);
2945 }
2946 else
2947 {
2948 if (w!=NULL)
2949 r=sba(r,Q,*w,hilb,strat);
2950 else
2951 {
2952 r=sba(r,Q,NULL,hilb,strat);
2953 }
2954 }
2955 }
2956 #ifdef KDEBUG
2957 idTest(r);
2958 #endif
2959 if (toReset)
2960 {
2961 kModW = NULL;
2963 }
2964 currRing->pLexOrder = b;
2965 //Print("%d reductions canceled \n",strat->cel);
2966 sigdrop = strat->sigdrop;
2967 sbaEnterS = strat->sbaEnterS;
2968 blockred = strat->blockred;
2969 delete(strat);
2970 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2971 }
2972 // Go to std
2973 if(sigdrop || blockred > blockedreductions)
2974 {
2975 r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2976 }
2977 return r;
2978 }
2979}
bool sigdrop
Definition kutil.h:358
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:363
unsigned sbaOrder
Definition kutil.h:316
int blockredmax
Definition kutil.h:364
int newIdeal
Definition kutil.h:356
char z2homog
Definition kutil.h:372
char no_prod_crit
Definition kutil.h:392
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:361
#define idTest(id)
Definition ideals.h:47
KINLINE BOOLEAN arriRewDummy(poly, unsigned long, poly, kStrategy, int)
Definition kInline.h:1255
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:2419
ideal mora(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd1.cc:1880
VAR intvec * kHomW
Definition kstd1.cc:2407
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:2980
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition kutil.cc:6648
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition kutil.cc:6623
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition kutil.cc:1944
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition kutil.cc:6564
void chainCritOpt_1(poly, int, kStrategy strat)
Definition kutil.cc:3450
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition kutil.cc:3209
#define TEST_OPT_SB_1
Definition options.h:121

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

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

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

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

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

◆ rightgb()

ideal rightgb ( ideal  F,
const ideal  Q 
)

Definition at line 4954 of file kstd2.cc.

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

◆ stdred()

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

Variable Documentation

◆ kHomW

Definition at line 73 of file kstd1.h.

◆ kModW

Definition at line 72 of file kstd1.h.

◆ kOptions

EXTERN_VAR BITSET kOptions

Definition at line 54 of file kstd1.h.

◆ Kstd1_deg

EXTERN_VAR int Kstd1_deg

Definition at line 52 of file kstd1.h.

◆ Kstd1_mu

EXTERN_VAR int Kstd1_mu

Definition at line 52 of file kstd1.h.

◆ validOpts

EXTERN_VAR BITSET validOpts

Definition at line 56 of file kstd1.h.