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:3224
#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:4462
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:452
void rSetSyzComp(int k, const ring r)
Definition ring.cc:5170
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 ( currRing->ppNoether != NULL )
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(currRing->ppNoether,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 (currRing->ppNoether != NULL)
1842 {
1843 HCord = currRing->pFDeg((currRing->ppNoether),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 3438 of file kstd1.cc.

3439{
3440 const ring save = currRing;
3442 poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3444 return ret;
3445}
#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 3805 of file kstd1.cc.

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

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

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

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

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

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

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

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

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

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