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

Go to the source code of this file.

Macros

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

Typedefs

typedef BOOLEAN(* s_poly_proc_t) (kStrategy strat)
 

Functions

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

Variables

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

Macro Definition Documentation

◆ KSTD_NF_ECART

#define KSTD_NF_ECART   2

Definition at line 19 of file kstd1.h.

◆ KSTD_NF_LAZY

#define KSTD_NF_LAZY   1

Definition at line 17 of file kstd1.h.

◆ KSTD_NF_NONORM

#define KSTD_NF_NONORM   4

Definition at line 21 of file kstd1.h.

Typedef Documentation

◆ s_poly_proc_t

typedef BOOLEAN(* s_poly_proc_t) (kStrategy strat)

Definition at line 14 of file kstd1.h.

Function Documentation

◆ idDivRem()

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

Definition at line 347 of file kLiftstd.cc.

348{
349 /* special cases */
350 if (idIs0(A) || idIs0(quot))
351 {
353 setUnit(A->rank,unit);
354 return idCopy(A);
355 }
356 /* ideal or module? */
359 int lsmod=0;
360 if (k==0) { lsmod=1;k=1;} /*ideal*/
361 /* 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:3225
#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:4755
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 1815 of file kstd1.cc.

1816{
1817 int i,j;
1818
1819 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1820 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1821 strat->enterS = enterSMora;
1822 strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1823 strat->posInLOld = strat->posInL;
1824 strat->posInLOldFlag = TRUE;
1825 strat->initEcart = initEcartNormal;
1826 strat->kAllAxis = (currRing->ppNoether) != NULL;
1827 if ( strat->kAllAxis )
1828 {
1829 strat->kNoether = pCopy((currRing->ppNoether));
1830 strat->red = redFirst; /*take the first possible in T*/
1831 if (TEST_OPT_PROT)
1832 {
1833 Print("H(%ld)",p_FDeg(strat->kNoether,currRing)+1);
1834 mflush();
1835 }
1836 }
1837 else if (strat->homog)
1838 strat->red = redFirst; /*take the first possible in T*/
1839 else
1840 strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1841 if (strat->kAllAxis)
1842 {
1843 HCord = currRing->pFDeg((strat->kNoether),currRing)+1;
1844 }
1845 else
1846 {
1847 HCord = 32000;/*- very large -*/
1848 }
1849
1851 {
1852 if (rField_is_Z(currRing))
1853 strat->red = redRiloc_Z;
1854 else
1855 strat->red = redRiloc;
1856 }
1857
1858 /*reads the ecartWeights used for Graebes method from the
1859 *intvec ecart and set ecartWeights
1860 */
1861 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1862 {
1863 //interred machen Aenderung
1864 strat->pOrigFDeg=currRing->pFDeg;
1865 strat->pOrigLDeg=currRing->pLDeg;
1866 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1867 /*uses automatic computation of the ecartWeights to set them*/
1869
1871 if (TEST_OPT_PROT)
1872 {
1873 for(i=1; i<=(currRing->N); i++)
1874 Print(" %d",ecartWeights[i]);
1875 PrintLn();
1876 mflush();
1877 }
1878 }
1879 kOptimizeLDeg(currRing->pLDeg, strat);
1880}
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:1624
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:121
#define TEST_OPT_PROT
Definition options.h:103
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 3439 of file kstd1.cc.

3440{
3441 const ring save = currRing;
3443 poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3445 return ret;
3446}
#define Q
Definition sirandom.c:26

◆ kHomModDeg()

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

Definition at line 2424 of file kstd1.cc.

2425{
2426 int i;
2427 long j=0;
2428
2429 for (i=r->N;i>0;i--)
2430 j+=p_GetExp(p,i,r)*(*kHomW)[i-1];
2431 if (kModW == NULL) return j;
2432 i = __p_GetComp(p,r);
2433 if (i==0) return j;
2434 return j+(*kModW)[i-1];
2435}
VAR intvec * kModW
Definition kstd1.cc:2412
#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 3806 of file kstd1.cc.

3807{
3808#ifdef HAVE_PLURAL
3809 if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3810#endif
3813 )
3814 return kInterRedOld(F,Q);
3815
3816 //return kInterRedOld(F,Q);
3817
3818 BITSET save1;
3820 //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3822 //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3823 //si_opt_1&= ~Sy_bit(OPT_REDSB);
3824 //extern char * showOption() ;
3825 //Print("%s\n",showOption());
3826
3827 int need_retry;
3828 int counter=3;
3829 ideal res, res1;
3830 int elems;
3831 ideal null=NULL;
3832 if ((Q==NULL) || (!TEST_OPT_REDSB))
3833 {
3834 elems=idElem(F);
3836 }
3837 else
3838 {
3839 ideal FF=idSimpleAdd(F,Q);
3841 idDelete(&FF);
3842 null=idInit(1,1);
3843 if (need_retry)
3845 else
3846 res1=kNF(null,Q,res);
3847 idDelete(&res);
3848 res=res1;
3849 need_retry=1;
3850 }
3851 if (idElem(res)<=1) need_retry=0;
3852 while (need_retry && (counter>0))
3853 {
3854 #ifdef KDEBUG
3855 if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3856 #endif
3858 int new_elems=idElem(res1);
3859 counter -= (new_elems >= elems);
3860 elems = new_elems;
3861 idDelete(&res);
3862 if (idElem(res1)<=1) need_retry=0;
3863 if ((Q!=NULL) && (TEST_OPT_REDSB))
3864 {
3865 if (need_retry)
3867 else
3868 res=kNF(null,Q,res1);
3869 idDelete(&res1);
3870 }
3871 else
3872 res = res1;
3873 if (idElem(res)<=1) need_retry=0;
3874 }
3875 if (null!=NULL) idDelete(&null);
3878 return res;
3879}
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:3546
ideal kInterRedOld(ideal F, const ideal Q)
Definition kstd1.cc:3452
#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: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: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 3452 of file kstd1.cc.

3453{
3454 int j;
3455 kStrategy strat = new skStrategy;
3456
3457 ideal tempF = F;
3458 ideal tempQ = Q;
3459
3460#ifdef HAVE_PLURAL
3461 if(rIsSCA(currRing))
3462 {
3463 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3464 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3466
3467 // this should be done on the upper level!!! :
3468 // tempQ = SCAQuotient(currRing);
3469
3470 if(Q == currRing->qideal)
3472 }
3473#endif
3474
3475// if (TEST_OPT_PROT)
3476// {
3477// writeTime("start InterRed:");
3478// mflush();
3479// }
3480 //strat->syzComp = 0;
3481 strat->kAllAxis = (currRing->ppNoether) != NULL;
3482 strat->kNoether=pCopy((currRing->ppNoether));
3484 initBuchMoraCrit(strat);
3485 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3486 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3487 strat->enterS = enterSBba;
3488 strat->posInT = posInT17;
3489 strat->initEcart = initEcartNormal;
3490 strat->sl = -1;
3491 strat->tl = -1;
3492 strat->tmax = setmaxT;
3493 strat->T = initT();
3494 strat->R = initR();
3495 strat->sevT = initsevT();
3497 initS(tempF, tempQ, strat);
3498 if (TEST_OPT_REDSB)
3499 strat->noTailReduction=FALSE;
3500 updateS(TRUE,strat);
3502 completeReduce(strat);
3503 //else if (TEST_OPT_PROT) PrintLn();
3504 cleanT(strat);
3505 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
3506 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3507 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3508 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3509 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3510 omfree(strat->sevT);
3511 omfree(strat->S_2_R);
3512 omfree(strat->R);
3513
3514 if (strat->fromQ)
3515 {
3516 for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3517 {
3518 if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3519 }
3520 omFree((ADDRESS)strat->fromQ);
3521 strat->fromQ=NULL;
3522 }
3523// if (TEST_OPT_PROT)
3524// {
3525// writeTime("end Interred:");
3526// mflush();
3527// }
3528 ideal shdl=strat->Shdl;
3530 if (strat->fromQ)
3531 {
3532 omfree(strat->fromQ);
3533 strat->fromQ=NULL;
3535 idDelete(&shdl);
3536 shdl=res;
3537 }
3538 delete(strat);
3539#ifdef HAVE_PLURAL
3540 if( tempF != F )
3542#endif
3543 return shdl;
3544}
#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:3806
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:8556
void cleanT(kStrategy strat)
Definition kutil.cc:563
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9432
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition kutil.cc:10282
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8791
#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: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 3074 of file kstd1.cc.

3076{
3077 if(idIs0(F))
3078 {
3079 M=idInit(1,F->rank);
3080 return idInit(1,F->rank);
3081 }
3083 {
3084 ideal sb;
3085 sb = kStd(F, Q, h, w, hilb);
3087 if(IDELEMS(sb) <= IDELEMS(F))
3088 {
3089 M = idCopy(sb);
3090 idSkipZeroes(M);
3091 return(sb);
3092 }
3093 else
3094 {
3095 M = idCopy(F);
3096 idSkipZeroes(M);
3097 return(sb);
3098 }
3099 }
3100 ideal r=NULL;
3101 int Kstd1_OldDeg = Kstd1_deg,i;
3103 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3106 kStrategy strat=new skStrategy;
3107
3109 strat->syzComp = syzComp;
3111 strat->LazyPass=20;
3112 else
3113 strat->LazyPass=2;
3114 strat->LazyDegree = 1;
3115 strat->minim=(reduced % 2)+1;
3116 strat->ak = id_RankFreeModule(F,currRing);
3117 if (delete_w)
3118 {
3119 temp_w=new intvec((strat->ak)+1);
3120 w = &temp_w;
3121 }
3122 if (h==testHomog)
3123 {
3124 if (strat->ak == 0)
3125 {
3126 h = (tHomog)idHomIdeal(F,Q);
3127 w=NULL;
3128 }
3129 else
3130 {
3131 h = (tHomog)idHomModule(F,Q,w);
3132 }
3133 }
3134 if (h==isHomog)
3135 {
3136 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3137 {
3138 kModW = *w;
3139 strat->kModW = *w;
3140 assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3141 strat->pOrigFDeg = currRing->pFDeg;
3142 strat->pOrigLDeg = currRing->pLDeg;
3144
3145 toReset = TRUE;
3146 if (reduced>1)
3147 {
3149 Kstd1_deg = -1;
3150 for (i=IDELEMS(F)-1;i>=0;i--)
3151 {
3152 if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3153 Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3154 }
3155 }
3156 }
3157 currRing->pLexOrder = TRUE;
3158 strat->LazyPass*=2;
3159 }
3160 strat->homog=h;
3161 ideal SB=NULL;
3163 {
3164 r=idMinBase(F,&SB); // SB and M via minbase
3165 strat->M=r;
3166 r=SB;
3167 }
3168 else
3169 {
3170 if (w!=NULL)
3171 r=bba(F,Q,*w,hilb,strat);
3172 else
3173 r=bba(F,Q,NULL,hilb,strat);
3174 }
3175#ifdef KDEBUG
3176 {
3177 int i;
3178 for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3179 }
3180#endif
3181 idSkipZeroes(r);
3182 if (toReset)
3183 {
3185 kModW = NULL;
3186 }
3187 currRing->pLexOrder = b;
3188 if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3189 if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3190 {
3191 M=idInit(1,F->rank);
3192 M->m[0]=pOne();
3193 //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3194 if (strat->M!=NULL) idDelete(&strat->M);
3195 }
3196 else if (strat->M==NULL)
3197 {
3198 M=idInit(1,F->rank);
3199 WarnS("no minimal generating set computed");
3200 }
3201 else
3202 {
3203 idSkipZeroes(strat->M);
3204 M=strat->M;
3205 strat->M=NULL;
3206 }
3207 delete(strat);
3208 if (reduced>2)
3209 {
3211 if (!oldDegBound)
3212 si_opt_1 &= ~Sy_bit(OPT_DEGBOUND);
3213 }
3214 else
3215 {
3216 if (IDELEMS(M)>IDELEMS(r))
3217 {
3218 idDelete(&M);
3219 M=idCopy(r);
3220 }
3221 }
3222 return r;
3223}
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:2414
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:2471
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:50
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:2609
#define assume(x)
Definition mod2.h:387
#define TEST_OPT_DEGBOUND
Definition options.h:113
#define TEST_OPT_RETURN_SB
Definition options.h:112
#define OPT_DEGBOUND
Definition options.h:90
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition p_polys.cc: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 2414 of file kstd1.cc.

2415{
2416 long o=p_WDegree(p, r);
2417 long i=__p_GetComp(p, r);
2418 if (i==0) return o;
2419 //assume((i>0) && (i<=kModW->length()));
2420 if (i<=kModW->length())
2421 return o+(*kModW)[i-1];
2422 return o;
2423}
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 3323 of file kstd1.cc.

3324{
3325 ideal res;
3326 if (TEST_OPT_PROT)
3327 {
3328 Print("(S:%d)",IDELEMS(p));mflush();
3329 }
3330 if (idIs0(p))
3331 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3332
3333 ideal pp = p;
3334#ifdef HAVE_PLURAL
3335 if(rIsSCA(currRing))
3336 {
3337 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3338 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3340
3341 if(Q == currRing->qideal)
3343 }
3344#endif
3345
3346 if ((Q!=NULL)&&(idIs0(Q))) Q=NULL;
3347
3348 if ((idIs0(F))&&(Q==NULL))
3349 {
3350#ifdef HAVE_PLURAL
3351 if(p != pp)
3352 return pp;
3353#endif
3354 return idCopy(p); /*F+Q=0*/
3355 }
3356
3357 kStrategy strat=new skStrategy;
3358 strat->syzComp = syzComp;
3360 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3361 {
3362 strat->ak = si_max(strat->ak,(int)F->rank);
3363 }
3364
3366 {
3367#ifdef HAVE_SHIFTBBA
3368 if (currRing->isLPring)
3369 {
3370 WerrorS("No local ordering possible for shift algebra");
3371 return(NULL);
3372 }
3373#endif
3374 res=kNF1(F,Q,pp,strat,lazyReduce);
3375 }
3376 else
3377 res=kNF2(F,Q,pp,strat,lazyReduce);
3378 delete(strat);
3379
3380#ifdef HAVE_PLURAL
3381 if(pp != p)
3383#endif
3384
3385 return res;
3386}
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:2122
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd2.cc:3929

◆ kNF() [2/2]

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

Definition at line 3225 of file kstd1.cc.

3226{
3227 if (p==NULL)
3228 return NULL;
3229
3230 poly pp = p;
3231
3232#ifdef HAVE_PLURAL
3233 if(rIsSCA(currRing))
3234 {
3235 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3236 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3238
3239 if(Q == currRing->qideal)
3241 }
3242#endif
3243 if((Q!=NULL) &&(idIs0(Q))) Q=NULL;
3244
3245 if ((idIs0(F))&&(Q==NULL))
3246 {
3247#ifdef HAVE_PLURAL
3248 if(p != pp)
3249 return pp;
3250#endif
3251 return pCopy(p); /*F+Q=0*/
3252 }
3253
3254 kStrategy strat=new skStrategy;
3255 strat->syzComp = syzComp;
3257 poly res;
3258
3260 {
3261#ifdef HAVE_SHIFTBBA
3262 if (currRing->isLPring)
3263 {
3264 WerrorS("No local ordering possible for shift algebra");
3265 return(NULL);
3266 }
3267#endif
3268 res=kNF1(F,Q,pp,strat,lazyReduce);
3269 }
3270 else
3271 res=kNF2(F,Q,pp,strat,lazyReduce);
3272 delete(strat);
3273
3274#ifdef HAVE_PLURAL
3275 if(pp != p)
3276 p_Delete(&pp, currRing);
3277#endif
3278 return res;
3279}
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 2263 of file kstd1.cc.

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

◆ kNF1() [2/2]

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

Definition at line 2122 of file kstd1.cc.

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

3389{
3390 ideal res;
3391 if (TEST_OPT_PROT)
3392 {
3393 Print("(S:%d)",IDELEMS(p));mflush();
3394 }
3395 if (idIs0(p))
3396 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3397
3398 ideal pp = p;
3399#ifdef HAVE_PLURAL
3400 if(rIsSCA(currRing))
3401 {
3402 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3403 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3405
3406 if(Q == currRing->qideal)
3408 }
3409#endif
3410
3411 if ((idIs0(F))&&(Q==NULL))
3412 {
3413#ifdef HAVE_PLURAL
3414 if(p != pp)
3415 return pp;
3416#endif
3417 return idCopy(p); /*F+Q=0*/
3418 }
3419
3420 kStrategy strat=new skStrategy;
3421 strat->syzComp = syzComp;
3423 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3424 {
3425 strat->ak = si_max(strat->ak,(int)F->rank);
3426 }
3427
3428 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3429 delete(strat);
3430
3431#ifdef HAVE_PLURAL
3432 if(pp != p)
3434#endif
3435
3436 return res;
3437}
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:4012

◆ kNFBound() [2/2]

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

Definition at line 3281 of file kstd1.cc.

3282{
3283 if (p==NULL)
3284 return NULL;
3285
3286 poly pp = p;
3287
3288#ifdef HAVE_PLURAL
3289 if(rIsSCA(currRing))
3290 {
3291 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3292 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3294
3295 if(Q == currRing->qideal)
3297 }
3298#endif
3299
3300 if ((idIs0(F))&&(Q==NULL))
3301 {
3302#ifdef HAVE_PLURAL
3303 if(p != pp)
3304 return pp;
3305#endif
3306 return pCopy(p); /*F+Q=0*/
3307 }
3308
3309 kStrategy strat=new skStrategy;
3310 strat->syzComp = syzComp;
3312 poly res;
3313 res=kNF2Bound(F,Q,pp,bound,strat,lazyReduce);
3314 delete(strat);
3315
3316#ifdef HAVE_PLURAL
3317 if(pp != p)
3318 p_Delete(&pp, currRing);
3319#endif
3320 return res;
3321}

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

2675{
2676 if(idIs0(F))
2677 return idInit(1,F->rank);
2679 {
2680 ideal r;
2681 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2683 kStrategy strat=new skStrategy;
2684 strat->sbaOrder = sbaOrder;
2685 if (arri!=0)
2686 {
2687 strat->rewCrit1 = arriRewDummy;
2688 strat->rewCrit2 = arriRewCriterion;
2690 }
2691 else
2692 {
2696 }
2697
2699 strat->syzComp = syzComp;
2700 if (TEST_OPT_SB_1)
2701 //if(!rField_is_Ring(currRing)) // always true here
2702 strat->newIdeal = newIdeal;
2704 strat->LazyPass=20;
2705 else
2706 strat->LazyPass=2;
2707 strat->LazyDegree = 1;
2711 strat->ak = id_RankFreeModule(F,currRing);
2712 strat->kModW=kModW=NULL;
2713 strat->kHomW=kHomW=NULL;
2714 if (vw != NULL)
2715 {
2716 currRing->pLexOrder=FALSE;
2717 strat->kHomW=kHomW=vw;
2718 strat->pOrigFDeg = currRing->pFDeg;
2719 strat->pOrigLDeg = currRing->pLDeg;
2721 toReset = TRUE;
2722 }
2723 if (h==testHomog)
2724 {
2725 if (strat->ak == 0)
2726 {
2727 h = (tHomog)idHomIdeal(F,Q);
2728 w=NULL;
2729 }
2730 else if (!TEST_OPT_DEGBOUND)
2731 {
2732 if (w!=NULL)
2733 h = (tHomog)idHomModule(F,Q,w);
2734 else
2735 h = (tHomog)idHomIdeal(F,Q);
2736 }
2737 }
2738 currRing->pLexOrder=b;
2739 if (h==isHomog)
2740 {
2741 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2742 {
2743 strat->kModW = kModW = *w;
2744 if (vw == NULL)
2745 {
2746 strat->pOrigFDeg = currRing->pFDeg;
2747 strat->pOrigLDeg = currRing->pLDeg;
2749 toReset = TRUE;
2750 }
2751 }
2752 currRing->pLexOrder = TRUE;
2753 if (hilb==NULL) strat->LazyPass*=2;
2754 }
2755 strat->homog=h;
2756 #ifdef KDEBUG
2757 idTest(F);
2758 if(Q != NULL)
2759 idTest(Q);
2760 #endif
2761 #ifdef HAVE_PLURAL
2763 {
2764 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2765 strat->no_prod_crit = ! bIsSCA;
2766 if (w!=NULL)
2767 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2768 else
2769 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2770 }
2771 else
2772 #endif
2773 {
2775 {
2776 if (w!=NULL)
2777 r=mora(F,Q,*w,hilb,strat);
2778 else
2779 r=mora(F,Q,NULL,hilb,strat);
2780 }
2781 else
2782 {
2783 strat->sigdrop = FALSE;
2784 if (w!=NULL)
2785 r=sba(F,Q,*w,hilb,strat);
2786 else
2787 r=sba(F,Q,NULL,hilb,strat);
2788 }
2789 }
2790 #ifdef KDEBUG
2791 idTest(r);
2792 #endif
2793 if (toReset)
2794 {
2795 kModW = NULL;
2797 }
2798 currRing->pLexOrder = b;
2799 //Print("%d reductions canceled \n",strat->cel);
2800 //delete(strat);
2801 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2802 return r;
2803 }
2804 else
2805 {
2806 //--------------------------RING CASE-------------------------
2807 assume(sbaOrder == 1);
2808 assume(arri == 0);
2809 ideal r;
2810 r = idCopy(F);
2811 int sbaEnterS = -1;
2812 bool sigdrop = TRUE;
2813 //This is how we set the SBA algorithm;
2814 int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2815 while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2816 && (blockred <= blockedreductions))
2817 {
2818 loops++;
2819 if(loops == 1)
2820 sigdrop = FALSE;
2821 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2823 kStrategy strat=new skStrategy;
2824 strat->sbaEnterS = sbaEnterS;
2825 strat->sigdrop = sigdrop;
2826 #if 0
2827 strat->blockred = blockred;
2828 #else
2829 strat->blockred = 0;
2830 #endif
2832 //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2833 //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2834 strat->sbaOrder = sbaOrder;
2835 if (arri!=0)
2836 {
2837 strat->rewCrit1 = arriRewDummy;
2838 strat->rewCrit2 = arriRewCriterion;
2840 }
2841 else
2842 {
2846 }
2847
2849 strat->syzComp = syzComp;
2850 if (TEST_OPT_SB_1)
2852 strat->newIdeal = newIdeal;
2854 strat->LazyPass=20;
2855 else
2856 strat->LazyPass=2;
2857 strat->LazyDegree = 1;
2861 strat->ak = id_RankFreeModule(F,currRing);
2862 strat->kModW=kModW=NULL;
2863 strat->kHomW=kHomW=NULL;
2864 if (vw != NULL)
2865 {
2866 currRing->pLexOrder=FALSE;
2867 strat->kHomW=kHomW=vw;
2868 strat->pOrigFDeg = currRing->pFDeg;
2869 strat->pOrigLDeg = currRing->pLDeg;
2871 toReset = TRUE;
2872 }
2873 if (h==testHomog)
2874 {
2875 if (strat->ak == 0)
2876 {
2877 h = (tHomog)idHomIdeal(F,Q);
2878 w=NULL;
2879 }
2880 else if (!TEST_OPT_DEGBOUND)
2881 {
2882 if (w!=NULL)
2883 h = (tHomog)idHomModule(F,Q,w);
2884 else
2885 h = (tHomog)idHomIdeal(F,Q);
2886 }
2887 }
2888 currRing->pLexOrder=b;
2889 if (h==isHomog)
2890 {
2891 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2892 {
2893 strat->kModW = kModW = *w;
2894 if (vw == NULL)
2895 {
2896 strat->pOrigFDeg = currRing->pFDeg;
2897 strat->pOrigLDeg = currRing->pLDeg;
2899 toReset = TRUE;
2900 }
2901 }
2902 currRing->pLexOrder = TRUE;
2903 if (hilb==NULL) strat->LazyPass*=2;
2904 }
2905 strat->homog=h;
2906 #ifdef KDEBUG
2907 idTest(F);
2908 if(Q != NULL)
2909 idTest(Q);
2910 #endif
2911 #ifdef HAVE_PLURAL
2913 {
2914 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2915 strat->no_prod_crit = ! bIsSCA;
2916 if (w!=NULL)
2917 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2918 else
2919 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2920 }
2921 else
2922 #endif
2923 {
2925 {
2926 if (w!=NULL)
2927 r=mora(F,Q,*w,hilb,strat);
2928 else
2929 r=mora(F,Q,NULL,hilb,strat);
2930 }
2931 else
2932 {
2933 if (w!=NULL)
2934 r=sba(r,Q,*w,hilb,strat);
2935 else
2936 {
2937 r=sba(r,Q,NULL,hilb,strat);
2938 }
2939 }
2940 }
2941 #ifdef KDEBUG
2942 idTest(r);
2943 #endif
2944 if (toReset)
2945 {
2946 kModW = NULL;
2948 }
2949 currRing->pLexOrder = b;
2950 //Print("%d reductions canceled \n",strat->cel);
2951 sigdrop = strat->sigdrop;
2952 sbaEnterS = strat->sbaEnterS;
2953 blockred = strat->blockred;
2954 delete(strat);
2955 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2956 }
2957 // Go to std
2958 if(sigdrop || blockred > blockedreductions)
2959 {
2960 r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2961 }
2962 return r;
2963 }
2964}
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:2424
ideal mora(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd1.cc:1884
VAR intvec * kHomW
Definition kstd1.cc:2412
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:2967
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: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 2471 of file kstd1.cc.

2473{
2474 if(idIs0(F))
2475 return idInit(1,F->rank);
2476
2477 if((Q!=NULL)&&(idIs0(Q))) Q=NULL;
2478#ifdef HAVE_SHIFTBBA
2479 if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
2480#endif
2481
2482 /* test HC precomputation*/
2483 poly save_noether=currRing->ppNoether;
2484 int ak = id_RankFreeModule(F,currRing);
2485 if((ak==0)
2486 && (h!=isHomog)
2487 && (w==NULL)
2488 && (hilb==NULL)
2489 && (vw==NULL)
2490 && (newIdeal==0)
2491 && (sp==NULL)
2495 currRing->ppNoether=kTryHC(F,Q);
2496
2497 ideal r;
2498 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2500 kStrategy strat=new skStrategy;
2501
2502 strat->s_poly=sp;
2504 strat->syzComp = syzComp;
2505 if (TEST_OPT_SB_1
2507 )
2508 strat->newIdeal = newIdeal;
2510 strat->LazyPass=20;
2511 else
2512 strat->LazyPass=2;
2513 strat->LazyDegree = 1;
2514 strat->ak = ak;
2515 strat->kModW=kModW=NULL;
2516 strat->kHomW=kHomW=NULL;
2517 if (vw != NULL)
2518 {
2519 currRing->pLexOrder=FALSE;
2520 strat->kHomW=kHomW=vw;
2521 strat->pOrigFDeg = currRing->pFDeg;
2522 strat->pOrigLDeg = currRing->pLDeg;
2524 toReset = TRUE;
2525 }
2526 if (h==testHomog)
2527 {
2528 if (strat->ak == 0)
2529 {
2530 h = (tHomog)idHomIdeal(F,Q);
2531 w=NULL;
2532 }
2533 else if (!TEST_OPT_DEGBOUND)
2534 {
2535 if (w!=NULL)
2536 h = (tHomog)idHomModule(F,Q,w);
2537 else
2538 h = (tHomog)idHomIdeal(F,Q);
2539 }
2540 }
2541 currRing->pLexOrder=b;
2542 if (h==isHomog)
2543 {
2544 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2545 {
2546 strat->kModW = kModW = *w;
2547 if (vw == NULL)
2548 {
2549 strat->pOrigFDeg = currRing->pFDeg;
2550 strat->pOrigLDeg = currRing->pLDeg;
2552 toReset = TRUE;
2553 }
2554 }
2555 currRing->pLexOrder = TRUE;
2556 if (hilb==NULL) strat->LazyPass*=2;
2557 }
2558 strat->homog=h;
2559#ifdef KDEBUG
2560 idTest(F);
2561 if (Q!=NULL) idTest(Q);
2562#endif
2563#ifdef HAVE_PLURAL
2565 {
2566 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2567 strat->no_prod_crit = ! bIsSCA;
2568 if (w!=NULL)
2569 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2570 else
2571 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2572 }
2573 else
2574#endif
2575 {
2576 #if PRE_INTEGER_CHECK
2577 //the preinteger check strategy is not for modules
2578 if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2579 {
2580 ideal FCopy = idCopy(F);
2581 poly pFmon = preIntegerCheck(FCopy, Q);
2582 if(pFmon != NULL)
2583 {
2585 strat->kModW=kModW=NULL;
2586 if (h==testHomog)
2587 {
2588 if (strat->ak == 0)
2589 {
2591 w=NULL;
2592 }
2593 else if (!TEST_OPT_DEGBOUND)
2594 {
2595 if (w!=NULL)
2597 else
2599 }
2600 }
2601 currRing->pLexOrder=b;
2602 if (h==isHomog)
2603 {
2604 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2605 {
2606 strat->kModW = kModW = *w;
2607 if (vw == NULL)
2608 {
2609 strat->pOrigFDeg = currRing->pFDeg;
2610 strat->pOrigLDeg = currRing->pLDeg;
2612 toReset = TRUE;
2613 }
2614 }
2615 currRing->pLexOrder = TRUE;
2616 if (hilb==NULL) strat->LazyPass*=2;
2617 }
2618 strat->homog=h;
2619 }
2620 omTestMemory(1);
2621 if(w == NULL)
2622 {
2624 r=mora(FCopy,Q,NULL,hilb,strat);
2625 else
2626 r=bba(FCopy,Q,NULL,hilb,strat);
2627 }
2628 else
2629 {
2631 r=mora(FCopy,Q,*w,hilb,strat);
2632 else
2633 r=bba(FCopy,Q,*w,hilb,strat);
2634 }
2635 idDelete(&FCopy);
2636 }
2637 else
2638 #endif
2639 {
2640 if(w==NULL)
2641 {
2643 r=mora(F,Q,NULL,hilb,strat);
2644 else
2645 r=bba(F,Q,NULL,hilb,strat);
2646 }
2647 else
2648 {
2650 r=mora(F,Q,*w,hilb,strat);
2651 else
2652 r=bba(F,Q,*w,hilb,strat);
2653 }
2654 }
2655 }
2656#ifdef KDEBUG
2657 idTest(r);
2658#endif
2659 if (toReset)
2660 {
2661 kModW = NULL;
2663 }
2664 currRing->pLexOrder = b;
2665//Print("%d reductions canceled \n",strat->cel);
2666 delete(strat);
2667 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2668 if (currRing->ppNoether!=save_noether) pLmDelete(&currRing->ppNoether);
2669 currRing->ppNoether=save_noether;
2670 return r;
2671}
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:2967
static poly kTryHC(ideal F, ideal Q)
Definition kstd1.cc:2437
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:10535
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 2967 of file kstd1.cc.

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

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

◆ rightgb()

ideal rightgb ( ideal  F,
const ideal  Q 
)

Definition at line 4938 of file kstd2.cc.

4939{
4941 assume(idIsInV(F));
4942 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4943 idSkipZeroes(RS); // is this even necessary?
4944 assume(idIsInV(RS));
4945 return(RS);
4946}

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