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 else { k=A->rank;}
362 /* NF(A 0 E,quot E 0)
363 * A,quot: 1..k, 0,E: k+1..k+IDELEMS(quot),
364 * E,0: k+IDELEMS(quot)..k+IDELEMS(quot)+IDELEMS(A) */
365 /* new ring */
369 /* move ideals to new ring */
371 ideal s_A;
372 if (orig_ring != syz_ring)
373 {
376 }
377 else
378 {
381 }
382 /* quot[i] -> quot[i]+e(k+i+1) */
383 for(int i=0;i<IDELEMS(s_quot);i++)
384 {
385 poly p=p_One(syz_ring);
388 if (lsmod==1) p_Shift(&(s_quot->m[i]),1,syz_ring);
389 s_quot->m[i]=p_Add_q(s_quot->m[i],p,syz_ring);
390 }
391 s_quot->rank=k+IDELEMS(quot)+1;
392 /* A[i] -> A[i]*e(1) */
393 if (lsmod==1)
394 {
395 for(int i=0;i<IDELEMS(s_A);i++)
396 {
397 p_Shift(&s_A->m[i],1,syz_ring);
398 }
399 }
400 if (unit!=NULL)
401 {
402 int u_k=k+IDELEMS(quot)+2;
403 for(int i=0;i<IDELEMS(s_A);i++)
404 {
405 poly p=p_One(syz_ring);
408 s_A->m[i]=p_Add_q(s_A->m[i],p,syz_ring);
409 }
410 s_A->rank=k+IDELEMS(quot)+IDELEMS(A)+1;
411 }
412 /* normalform */
413 #if 0
414 PrintS("to reduce:\n");
415 {
416 void ipPrint_MA0(matrix m, const char *name);
418 ipPrint_MA0(m, "A");
420 }
421 PrintS("with:\n");
422 {
423 void ipPrint_MA0(matrix m, const char *name);
425 ipPrint_MA0(m, "B");
427 }
428 #endif
430 #if 0
431 PrintS("result NF:\n");
432 {
433 void ipPrint_MA0(matrix m, const char *name);
435 ipPrint_MA0(m, "A");
437 }
438 #endif
439 /* clean s_quot,s_A */
442 /* interpret rest: remainder */
444 for(int i=0;i<IDELEMS(rest);i++)
445 {
446 poly p=rest->m[i];
447 poly d=NULL;
448 while(p!=NULL)
449 {
450 poly q=p; pIter(p);
451 pNext(q)=NULL;
452 if (p_GetComp(q,syz_ring)<=k)
453 {
454 result->m[i]=p_Add_q(result->m[i],q,syz_ring);
455 }
456 else
457 {
458 d=p_Add_q(d,q,syz_ring);
459 }
460 }
461 p_Shift(&d,-k,syz_ring);
462 rest->m[i]=d;
463 }
464 rest->rank-=k;
465 #if 0
466 PrintS("rest:\n");
467 {
468 void ipPrint_MA0(matrix m, const char *name);
470 ipPrint_MA0(m, "_");
472 }
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 int uk=IDELEMS(quot);
484 for(int i=0;i<IDELEMS(rest);i++)
485 {
486 poly d=NULL;
487 poly p=rest->m[i];
488 while(p!=NULL)
489 {
490 poly q=p; pIter(p);
491 pNext(q)=NULL;
492 if (p_GetComp(q,syz_ring)<=uk)
493 {
494 factor->m[i]=p_Add_q(factor->m[i],q,syz_ring);
495 }
496 else
497 {
498 d=p_Add_q(d,q,syz_ring);
499 }
500 }
501 p_Shift(&d,-uk-1,syz_ring);
502 rest->m[i]=d;
503 factor->m[i]=p_Neg(factor->m[i],syz_ring);
504 }
505 if (unit!=NULL)
506 {
507 #if 0
508 PrintS("unit:\n");
509 {
510 void ipPrint_MA0(matrix m, const char *name);
512 ipPrint_MA0(m, "_");
514 }
515 #endif
517 for(int i=0;i<IDELEMS(rest);i++)
518 {
519 poly p=rest->m[i];
520 rest->m[i]=NULL;
521 (*unit)->m[i]=p;
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:3227
#define p_GetComp(p, r)
Definition monomials.h:64
#define pIter(p)
Definition monomials.h:37
#define pNext(p)
Definition monomials.h:36
#define NULL
Definition omList.c:12
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition p_polys.cc:4756
poly p_One(const ring r)
Definition p_polys.cc:1316
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 1819 of file kstd1.cc.

1820{
1821 int i,j;
1822
1823 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1824 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1825 strat->enterS = enterSMora;
1826 strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1827 strat->posInLOld = strat->posInL;
1828 strat->posInLOldFlag = TRUE;
1829 strat->initEcart = initEcartNormal;
1830 strat->kAllAxis = (currRing->ppNoether) != NULL; //!!
1831 if ( currRing->ppNoether != NULL )
1832 {
1833 strat->kNoether = pCopy((currRing->ppNoether));
1834 strat->red = redFirst; /*take the first possible in T*/
1835 if (TEST_OPT_PROT)
1836 {
1837 Print("H(%ld)",p_FDeg(currRing->ppNoether,currRing)+1);
1838 mflush();
1839 }
1840 }
1841 else if (strat->homog)
1842 strat->red = redFirst; /*take the first possible in T*/
1843 else
1844 strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1845 if (currRing->ppNoether != NULL)
1846 {
1847 HCord = currRing->pFDeg((currRing->ppNoether),currRing)+1;
1848 }
1849 else
1850 {
1851 HCord = 32000;/*- very large -*/
1852 }
1853
1855 {
1856 if (rField_is_Z(currRing))
1857 strat->red = redRiloc_Z;
1858 else
1859 strat->red = redRiloc;
1860 }
1861
1862 /*reads the ecartWeights used for Graebes method from the
1863 *intvec ecart and set ecartWeights
1864 */
1865 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1866 {
1867 //interred machen Aenderung
1868 strat->pOrigFDeg=currRing->pFDeg;
1869 strat->pOrigLDeg=currRing->pLDeg;
1870 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1871 /*uses automatic computation of the ecartWeights to set them*/
1873
1875 if (TEST_OPT_PROT)
1876 {
1877 for(i=1; i<=(currRing->N); i++)
1878 Print(" %d",ecartWeights[i]);
1879 PrintLn();
1880 mflush();
1881 }
1882 }
1883 kOptimizeLDeg(currRing->pLDeg, strat);
1884}
int BOOLEAN
Definition auxiliary.h:87
char posInLOldFlag
Definition kutil.h:382
poly kNoether
Definition kutil.h:329
BOOLEAN * NotUsedAxis
Definition kutil.h:332
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.h:284
pFDegProc pOrigFDeg
Definition kutil.h:296
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition kutil.h:288
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition kutil.h:287
char kAllAxis
Definition kutil.h:376
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition kutil.h:286
void(* initEcart)(TObject *L)
Definition kutil.h:280
int(* red)(LObject *L, kStrategy strat)
Definition kutil.h:278
char homog
Definition kutil.h:372
pLDegProc pOrigLDeg
Definition kutil.h:297
#define Print
Definition emacs.cc:80
int j
Definition facHensel.cc:110
int redFirst(LObject *h, kStrategy strat)
Definition kstd1.cc:797
int redEcart(LObject *h, kStrategy strat)
Definition kstd1.cc:169
static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
Definition kstd1.cc:100
int redRiloc(LObject *h, kStrategy strat)
Definition kstd1.cc:387
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1628
int redRiloc_Z(LObject *h, kStrategy strat)
Definition kstd1.cc:568
VAR int HCord
Definition kutil.cc:246
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition kutil.cc:1326
void initEcartNormal(TObject *h)
Definition kutil.cc:1304
#define omAlloc(size)
#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:3659
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 3441 of file kstd1.cc.

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

◆ kHomModDeg()

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

Definition at line 2428 of file kstd1.cc.

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

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

3455{
3456 int j;
3457 kStrategy strat = new skStrategy;
3458
3459 ideal tempF = F;
3460 ideal tempQ = Q;
3461
3462#ifdef HAVE_PLURAL
3463 if(rIsSCA(currRing))
3464 {
3465 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3466 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3468
3469 // this should be done on the upper level!!! :
3470 // tempQ = SCAQuotient(currRing);
3471
3472 if(Q == currRing->qideal)
3474 }
3475#endif
3476
3477// if (TEST_OPT_PROT)
3478// {
3479// writeTime("start InterRed:");
3480// mflush();
3481// }
3482 //strat->syzComp = 0;
3483 strat->kAllAxis = (currRing->ppNoether) != NULL;
3484 strat->kNoether=pCopy((currRing->ppNoether));
3486 initBuchMoraCrit(strat);
3487 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3488 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3489 strat->enterS = enterSBba;
3490 strat->posInT = posInT17;
3491 strat->initEcart = initEcartNormal;
3492 strat->sl = -1;
3493 strat->tl = -1;
3494 strat->tmax = setmaxT;
3495 strat->T = initT();
3496 strat->R = initR();
3497 strat->sevT = initsevT();
3499 initS(tempF, tempQ, strat);
3500 if (TEST_OPT_REDSB)
3501 strat->noTailReduction=FALSE;
3502 updateS(TRUE,strat);
3504 completeReduce(strat);
3505 //else if (TEST_OPT_PROT) PrintLn();
3506 cleanT(strat);
3507 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
3508 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3509 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3510 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3511 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3512 omfree(strat->sevT);
3513 omfree(strat->S_2_R);
3514 omfree(strat->R);
3515
3516 if (strat->fromQ)
3517 {
3518 for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3519 {
3520 if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3521 }
3522 omFree((ADDRESS)strat->fromQ);
3523 strat->fromQ=NULL;
3524 }
3525// if (TEST_OPT_PROT)
3526// {
3527// writeTime("end Interred:");
3528// mflush();
3529// }
3530 ideal shdl=strat->Shdl;
3532 if (strat->fromQ)
3533 {
3534 omfree(strat->fromQ);
3535 strat->fromQ=NULL;
3537 idDelete(&shdl);
3538 shdl=res;
3539 }
3540 delete(strat);
3541#ifdef HAVE_PLURAL
3542 if( tempF != F )
3544#endif
3545 return shdl;
3546}
#define FALSE
Definition auxiliary.h:96
int * S_2_R
Definition kutil.h:342
char noTailReduction
Definition kutil.h:378
TSet T
Definition kutil.h:326
intset ecartS
Definition kutil.h:309
char honey
Definition kutil.h:377
int ak
Definition kutil.h:353
TObject ** R
Definition kutil.h:340
int tl
Definition kutil.h:350
unsigned long * sevT
Definition kutil.h:325
ideal Shdl
Definition kutil.h:303
int tmax
Definition kutil.h:350
intset fromQ
Definition kutil.h:321
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition kutil.h:281
int sl
Definition kutil.h:348
unsigned long * sevS
Definition kutil.h:322
KINLINE TSet initT()
Definition kInline.h:84
KINLINE TObject ** initR()
Definition kInline.h:95
KINLINE unsigned long * initsevT()
Definition kInline.h:100
ideal kInterRed(ideal F, const ideal Q)
Definition kstd1.cc:3808
int posInT17(const TSet set, const int length, LObject &p)
Definition kutil.cc:5306
void initS(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7635
void updateS(BOOLEAN toT, kStrategy strat)
Definition kutil.cc:8611
void cleanT(kStrategy strat)
Definition kutil.cc:565
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9493
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition kutil.cc:10357
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8846
#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 3077 of file kstd1.cc.

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

2419{
2420 long o=p_WDegree(p, r);
2421 long i=__p_GetComp(p, r);
2422 if (i==0) return o;
2423 //assume((i>0) && (i<=kModW->length()));
2424 if (i<=kModW->length())
2425 return o+(*kModW)[i-1];
2426 return o;
2427}
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
long p_WDegree(poly p, const ring r)
Definition p_polys.cc:717

◆ kNF() [1/2]

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

Definition at line 3325 of file kstd1.cc.

3326{
3327 ideal res;
3328 if (TEST_OPT_PROT)
3329 {
3330 Print("(S:%d)",IDELEMS(p));mflush();
3331 }
3332 if (idIs0(p))
3333 return idInit(IDELEMS(p),si_max(p->rank,F->rank));
3334
3335 ideal pp = p;
3336#ifdef HAVE_PLURAL
3337 if(rIsSCA(currRing))
3338 {
3339 const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
3340 const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
3342
3343 if(Q == currRing->qideal)
3345 }
3346#endif
3347
3348 if ((Q!=NULL)&&(idIs0(Q))) Q=NULL;
3349
3350 if ((idIs0(F))&&(Q==NULL))
3351 {
3352#ifdef HAVE_PLURAL
3353 if(p != pp)
3354 return pp;
3355#endif
3356 return idCopy(p); /*F+Q=0*/
3357 }
3358
3359 kStrategy strat=new skStrategy;
3360 strat->syzComp = syzComp;
3362 if (strat->ak>0) // only for module case, see Tst/Short/bug_reduce.tst
3363 {
3364 strat->ak = si_max(strat->ak,(int)F->rank);
3365 }
3366
3368 {
3369#ifdef HAVE_SHIFTBBA
3370 if (currRing->isLPring)
3371 {
3372 WerrorS("No local ordering possible for shift algebra");
3373 return(NULL);
3374 }
3375#endif
3376 res=kNF1(F,Q,pp,strat,lazyReduce);
3377 }
3378 else
3379 res=kNF2(F,Q,pp,strat,lazyReduce);
3380 delete(strat);
3381
3382#ifdef HAVE_PLURAL
3383 if(pp != p)
3385#endif
3386
3387 return res;
3388}
static int si_max(const int a, const int b)
Definition auxiliary.h:124
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition cf_gcd.cc:676
void WerrorS(const char *s)
Definition feFopen.cc:24
poly kNF1(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd1.cc:2126
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd2.cc:3950

◆ kNF() [2/2]

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

Definition at line 3227 of file kstd1.cc.

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

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

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

◆ kNFBound() [1/2]

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

Definition at line 3390 of file kstd1.cc.

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

◆ kNFBound() [2/2]

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

Definition at line 3283 of file kstd1.cc.

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

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

2678{
2679 if(idIs0(F))
2680 return idInit(1,F->rank);
2682 {
2683 ideal r;
2684 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2686 kStrategy strat=new skStrategy;
2687 strat->sbaOrder = sbaOrder;
2688 if (arri!=0)
2689 {
2690 strat->rewCrit1 = arriRewDummy;
2691 strat->rewCrit2 = arriRewCriterion;
2693 }
2694 else
2695 {
2699 }
2700
2702 strat->syzComp = syzComp;
2703 if (TEST_OPT_SB_1)
2704 //if(!rField_is_Ring(currRing)) // always true here
2705 strat->newIdeal = newIdeal;
2707 strat->LazyPass=20;
2708 else
2709 strat->LazyPass=2;
2710 strat->LazyDegree = 1;
2714 strat->ak = id_RankFreeModule(F,currRing);
2715 strat->kModW=kModW=NULL;
2716 strat->kHomW=kHomW=NULL;
2717 if (vw != NULL)
2718 {
2719 currRing->pLexOrder=FALSE;
2720 strat->kHomW=kHomW=vw;
2721 strat->pOrigFDeg = currRing->pFDeg;
2722 strat->pOrigLDeg = currRing->pLDeg;
2724 toReset = TRUE;
2725 }
2726 if (h==testHomog)
2727 {
2728 if (strat->ak == 0)
2729 {
2730 h = (tHomog)idHomIdeal(F,Q);
2731 w=NULL;
2732 }
2733 else if (!TEST_OPT_DEGBOUND)
2734 {
2735 if (w!=NULL)
2736 h = (tHomog)idHomModule(F,Q,w);
2737 else
2738 h = (tHomog)idHomIdeal(F,Q);
2739 }
2740 }
2741 currRing->pLexOrder=b;
2742 if (h==isHomog)
2743 {
2744 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2745 {
2746 strat->kModW = kModW = *w;
2747 if (vw == NULL)
2748 {
2749 strat->pOrigFDeg = currRing->pFDeg;
2750 strat->pOrigLDeg = currRing->pLDeg;
2752 toReset = TRUE;
2753 }
2754 }
2755 currRing->pLexOrder = TRUE;
2756 if (hilb==NULL) strat->LazyPass*=2;
2757 }
2758 strat->homog=h;
2759 #ifdef KDEBUG
2760 idTest(F);
2761 if(Q != NULL)
2762 idTest(Q);
2763 #endif
2764 #ifdef HAVE_PLURAL
2766 {
2767 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2768 strat->no_prod_crit = ! bIsSCA;
2769 if (w!=NULL)
2770 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2771 else
2772 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2773 }
2774 else
2775 #endif
2776 {
2778 {
2779 if (w!=NULL)
2780 r=mora(F,Q,*w,hilb,strat);
2781 else
2782 r=mora(F,Q,NULL,hilb,strat);
2783 }
2784 else
2785 {
2786 strat->sigdrop = FALSE;
2787 if (w!=NULL)
2788 r=sba(F,Q,*w,hilb,strat);
2789 else
2790 r=sba(F,Q,NULL,hilb,strat);
2791 }
2792 }
2793 #ifdef KDEBUG
2794 idTest(r);
2795 #endif
2796 if (toReset)
2797 {
2798 kModW = NULL;
2800 }
2801 currRing->pLexOrder = b;
2802 //Print("%d reductions canceled \n",strat->cel);
2803 //delete(strat);
2804 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2805 return r;
2806 }
2807 else
2808 {
2809 //--------------------------RING CASE-------------------------
2810 assume(sbaOrder == 1);
2811 assume(arri == 0);
2812 ideal r;
2813 r = idCopy(F);
2814 int sbaEnterS = -1;
2815 bool sigdrop = TRUE;
2816 //This is how we set the SBA algorithm;
2817 int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2818 while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2819 && (blockred <= blockedreductions))
2820 {
2821 loops++;
2822 if(loops == 1)
2823 sigdrop = FALSE;
2824 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2826 kStrategy strat=new skStrategy;
2827 strat->sbaEnterS = sbaEnterS;
2828 strat->sigdrop = sigdrop;
2829 #if 0
2830 strat->blockred = blockred;
2831 #else
2832 strat->blockred = 0;
2833 #endif
2835 //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2836 //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2837 strat->sbaOrder = sbaOrder;
2838 if (arri!=0)
2839 {
2840 strat->rewCrit1 = arriRewDummy;
2841 strat->rewCrit2 = arriRewCriterion;
2843 }
2844 else
2845 {
2849 }
2850
2852 strat->syzComp = syzComp;
2853 if (TEST_OPT_SB_1)
2855 strat->newIdeal = newIdeal;
2857 strat->LazyPass=20;
2858 else
2859 strat->LazyPass=2;
2860 strat->LazyDegree = 1;
2864 strat->ak = id_RankFreeModule(F,currRing);
2865 strat->kModW=kModW=NULL;
2866 strat->kHomW=kHomW=NULL;
2867 if (vw != NULL)
2868 {
2869 currRing->pLexOrder=FALSE;
2870 strat->kHomW=kHomW=vw;
2871 strat->pOrigFDeg = currRing->pFDeg;
2872 strat->pOrigLDeg = currRing->pLDeg;
2874 toReset = TRUE;
2875 }
2876 if (h==testHomog)
2877 {
2878 if (strat->ak == 0)
2879 {
2880 h = (tHomog)idHomIdeal(F,Q);
2881 w=NULL;
2882 }
2883 else if (!TEST_OPT_DEGBOUND)
2884 {
2885 if (w!=NULL)
2886 h = (tHomog)idHomModule(F,Q,w);
2887 else
2888 h = (tHomog)idHomIdeal(F,Q);
2889 }
2890 }
2891 currRing->pLexOrder=b;
2892 if (h==isHomog)
2893 {
2894 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2895 {
2896 strat->kModW = kModW = *w;
2897 if (vw == NULL)
2898 {
2899 strat->pOrigFDeg = currRing->pFDeg;
2900 strat->pOrigLDeg = currRing->pLDeg;
2902 toReset = TRUE;
2903 }
2904 }
2905 currRing->pLexOrder = TRUE;
2906 if (hilb==NULL) strat->LazyPass*=2;
2907 }
2908 strat->homog=h;
2909 #ifdef KDEBUG
2910 idTest(F);
2911 if(Q != NULL)
2912 idTest(Q);
2913 #endif
2914 #ifdef HAVE_PLURAL
2916 {
2917 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2918 strat->no_prod_crit = ! bIsSCA;
2919 if (w!=NULL)
2920 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2921 else
2922 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2923 }
2924 else
2925 #endif
2926 {
2928 {
2929 if (w!=NULL)
2930 r=mora(F,Q,*w,hilb,strat);
2931 else
2932 r=mora(F,Q,NULL,hilb,strat);
2933 }
2934 else
2935 {
2936 if (w!=NULL)
2937 r=sba(r,Q,*w,hilb,strat);
2938 else
2939 {
2940 r=sba(r,Q,NULL,hilb,strat);
2941 }
2942 }
2943 }
2944 #ifdef KDEBUG
2945 idTest(r);
2946 #endif
2947 if (toReset)
2948 {
2949 kModW = NULL;
2951 }
2952 currRing->pLexOrder = b;
2953 //Print("%d reductions canceled \n",strat->cel);
2954 sigdrop = strat->sigdrop;
2955 sbaEnterS = strat->sbaEnterS;
2956 blockred = strat->blockred;
2957 delete(strat);
2958 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2959 }
2960 // Go to std
2961 if(sigdrop || blockred > blockedreductions)
2962 {
2963 r = kStd(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2964 }
2965 return r;
2966 }
2967}
bool sigdrop
Definition kutil.h:359
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition kutil.h:291
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:293
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:295
intvec * kHomW
Definition kutil.h:336
int blockred
Definition kutil.h:364
unsigned sbaOrder
Definition kutil.h:316
int blockredmax
Definition kutil.h:365
int newIdeal
Definition kutil.h:356
char z2homog
Definition kutil.h:374
char no_prod_crit
Definition kutil.h:394
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition kutil.h:290
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:294
int sbaEnterS
Definition kutil.h:362
#define idTest(id)
Definition ideals.h:47
KINLINE BOOLEAN arriRewDummy(poly, unsigned long, poly, kStrategy, int)
Definition kInline.h:1263
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:2428
ideal mora(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd1.cc:1888
VAR intvec * kHomW
Definition kstd1.cc:2416
ideal sba(ideal F0, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition kstd2.cc:2984
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition kutil.cc:6689
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition kutil.cc:6664
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition kutil.cc:1952
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition kutil.cc:6605
void chainCritOpt_1(poly, int, kStrategy strat)
Definition kutil.cc:3458
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition kutil.cc:3217
#define TEST_OPT_SB_1
Definition options.h:119

◆ kStd()

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

Definition at line 2475 of file kstd1.cc.

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

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

◆ kVerify()

BOOLEAN kVerify ( ideal  F,
ideal  Q 
)

◆ mora()

ideal mora ( ideal  F,
ideal  Q,
intvec w,
intvec hilb,
kStrategy  strat 
)

Definition at line 1888 of file kstd1.cc.

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

◆ rightgb()

ideal rightgb ( ideal  F,
const ideal  Q 
)

Definition at line 4959 of file kstd2.cc.

4960{
4962 assume(idIsInV(F));
4963 ideal RS = kStdShift(F, Q, testHomog, NULL, NULL, 0, 0, NULL, TRUE);
4964 idSkipZeroes(RS); // is this even necessary?
4965 assume(idIsInV(RS));
4966 return(RS);
4967}

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