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:3231
#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:122
#define TEST_OPT_PROT
Definition options.h:104
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 3445 of file kstd1.cc.

3446{
3447 const ring save = currRing;
3449 poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3451 return ret;
3452}
#define Q
Definition sirandom.c:26

◆ kHomModDeg()

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

Definition at line 2422 of file kstd1.cc.

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

3813{
3814#ifdef HAVE_PLURAL
3815 if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3816#endif
3819 )
3820 return kInterRedOld(F,Q);
3821
3822 //return kInterRedOld(F,Q);
3823
3824 BITSET save1;
3826 //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3828 //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3829 //si_opt_1&= ~Sy_bit(OPT_REDSB);
3830 //extern char * showOption() ;
3831 //Print("%s\n",showOption());
3832
3833 int need_retry;
3834 int counter=3;
3835 ideal res, res1;
3836 int elems;
3837 ideal null=NULL;
3838 if ((Q==NULL) || (!TEST_OPT_REDSB))
3839 {
3840 elems=idElem(F);
3842 }
3843 else
3844 {
3845 ideal FF=idSimpleAdd(F,Q);
3847 idDelete(&FF);
3848 null=idInit(1,1);
3849 if (need_retry)
3851 else
3852 res1=kNF(null,Q,res);
3853 idDelete(&res);
3854 res=res1;
3855 need_retry=1;
3856 }
3857 if (idElem(res)<=1) need_retry=0;
3858 while (need_retry && (counter>0))
3859 {
3860 #ifdef KDEBUG
3861 if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3862 #endif
3864 int new_elems=idElem(res1);
3865 counter -= (new_elems >= elems);
3866 elems = new_elems;
3867 idDelete(&res);
3868 if (idElem(res1)<=1) need_retry=0;
3869 if ((Q!=NULL) && (TEST_OPT_REDSB))
3870 {
3871 if (need_retry)
3873 else
3874 res=kNF(null,Q,res1);
3875 idDelete(&res1);
3876 }
3877 else
3878 res = res1;
3879 if (idElem(res)<=1) need_retry=0;
3880 }
3881 if (null!=NULL) idDelete(&null);
3884 return res;
3885}
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:3552
ideal kInterRedOld(ideal F, const ideal Q)
Definition kstd1.cc:3458
#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:105
#define TEST_OPT_DEBUG
Definition options.h:109
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 3458 of file kstd1.cc.

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

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

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

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

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

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

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

◆ kNFBound() [1/2]

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

Definition at line 3394 of file kstd1.cc.

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

◆ kNFBound() [2/2]

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

Definition at line 3287 of file kstd1.cc.

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

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

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

◆ kStd()

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

Definition at line 2483 of file kstd1.cc.

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

2978{
2980 assume(idIsInV(F));
2982 {
2983 /* error: no local ord yet with shifts */
2984 WerrorS("No local ordering possible for shift algebra");
2985 return(NULL);
2986 }
2987 ideal r;
2988 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2990 kStrategy strat=new skStrategy;
2991
2992 strat->rightGB = rightGB;
2993
2995 strat->syzComp = syzComp;
2996 if (TEST_OPT_SB_1)
2998 strat->newIdeal = newIdeal;
3000 strat->LazyPass=20;
3001 else
3002 strat->LazyPass=2;
3003 strat->LazyDegree = 1;
3004 strat->ak = id_RankFreeModule(F,currRing);
3005 strat->kModW=kModW=NULL;
3006 strat->kHomW=kHomW=NULL;
3007 if (vw != NULL)
3008 {
3009 currRing->pLexOrder=FALSE;
3010 strat->kHomW=kHomW=vw;
3011 strat->pOrigFDeg = currRing->pFDeg;
3012 strat->pOrigLDeg = currRing->pLDeg;
3014 toReset = TRUE;
3015 }
3016 if (h==testHomog)
3017 {
3018 if (strat->ak == 0)
3019 {
3020 h = (tHomog)idHomIdeal(F,Q);
3021 w=NULL;
3022 }
3023 else if (!TEST_OPT_DEGBOUND)
3024 {
3025 if (w!=NULL)
3026 h = (tHomog)idHomModule(F,Q,w);
3027 else
3028 h = (tHomog)idHomIdeal(F,Q);
3029 }
3030 }
3031 currRing->pLexOrder=b;
3032 if (h==isHomog)
3033 {
3034 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3035 {
3036 strat->kModW = kModW = *w;
3037 if (vw == NULL)
3038 {
3039 strat->pOrigFDeg = currRing->pFDeg;
3040 strat->pOrigLDeg = currRing->pLDeg;
3042 toReset = TRUE;
3043 }
3044 }
3045 currRing->pLexOrder = TRUE;
3046 if (hilb==NULL) strat->LazyPass*=2;
3047 }
3048 strat->homog=h;
3049#ifdef KDEBUG
3050 idTest(F);
3051#endif
3052 /* global ordering */
3053 if (w!=NULL)
3054 r=bbaShift(F,Q,*w,hilb,strat);
3055 else
3056 r=bbaShift(F,Q,NULL,hilb,strat);
3057#ifdef KDEBUG
3058 idTest(r);
3059#endif
3060 if (toReset)
3061 {
3062 kModW = NULL;
3064 }
3065 currRing->pLexOrder = b;
3066//Print("%d reductions canceled \n",strat->cel);
3067 delete(strat);
3068 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
3069 assume(idIsInV(r));
3070 return r;
3071}
char rightGB
Definition kutil.h:367
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:4577
#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 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2103// if (TEST_OPT_WEIGHTM)
2104// {
2105// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
2106// if (ecartWeights)
2107// {
2108// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
2109// ecartWeights=NULL;
2110// }
2111// }
2112 if(nCoeff_is_Z(currRing->cf))
2113 finalReduceByMon(strat);
2114 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
2116 idTest(strat->Shdl);
2117 return (strat->Shdl);
2118}
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:3888
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: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:112
#define OPT_REDSB
Definition options.h:76
#define TEST_OPT_MULTBOUND
Definition options.h:115
#define TEST_OPT_FASTHC
Definition options.h:110
BOOLEAN rHasMixedOrdering(const ring r)
Definition ring.h:768

◆ rightgb()

ideal rightgb ( ideal  F,
const ideal  Q 
)

Definition at line 4941 of file kstd2.cc.

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

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