My Project
Loading...
Searching...
No Matches
kstd1.h File Reference

Go to the source code of this file.

Macros

#define KSTD_NF_LAZY   1
 
#define KSTD_NF_ECART   2
 
#define KSTD_NF_NONORM   4
 
#define KSTD_NF_CANCELUNIT   8
 
#define KSTD_NF_NOLF   4096
 

Typedefs

typedef BOOLEAN(* s_poly_proc_t) (kStrategy strat)
 

Functions

ideal mora (ideal F, ideal Q, intvec *w, bigintmat *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, bigintmat *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)
 generic interface to GB/SB computations
 
ideal kStd2 (ideal F, ideal Q, tHomog h, intvec **mw, bigintmat *hilb=NULL, int syzComp=0, int newIdeal=0, intvec *vw=NULL, s_poly_proc_t sp=NULL)
 generic interface to GB/SB computations, large hilbert vectors
 
ideal kStd_internal (ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb=NULL, int syzComp=0, int newIdeal=0, intvec *vw=NULL, s_poly_proc_t sp=NULL)
 pure GB/SB computations
 
ideal kStdShift (ideal F, ideal Q, tHomog h, intvec **mw, bigintmat *hilb=NULL, int syzComp=0, int newIdeal=0, intvec *vw=NULL, BOOLEAN rightGB=FALSE)
 
ideal kTryHilbstd (ideal F, ideal Q)
 
ideal kTryHilbstd_par (ideal F, ideal Q, tHomog h, intvec **mw)
 
poly kTryHC (ideal F, ideal Q)
 
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)
 
ideal kInterRedBba (ideal F, ideal Q, int &need_retry)
 
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_std2 (ideal F, ideal Q, tHomog h, intvec **w, ideal &M, bigintmat *hilb, int syzComp=0, int reduced=0)
 
ideal kMin_std (ideal F, ideal Q, tHomog h, intvec **w, ideal &M, intvec *hilb, 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_CANCELUNIT

#define KSTD_NF_CANCELUNIT   8

Definition at line 24 of file kstd1.h.

◆ KSTD_NF_ECART

#define KSTD_NF_ECART   2

Definition at line 20 of file kstd1.h.

◆ KSTD_NF_LAZY

#define KSTD_NF_LAZY   1

Definition at line 18 of file kstd1.h.

◆ KSTD_NF_NOLF

#define KSTD_NF_NOLF   4096

Definition at line 26 of file kstd1.h.

◆ KSTD_NF_NONORM

#define KSTD_NF_NONORM   4

Definition at line 22 of file kstd1.h.

Typedef Documentation

◆ s_poly_proc_t

typedef BOOLEAN(* s_poly_proc_t) (kStrategy strat)

Definition at line 15 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 {
352 factor=idInit(1,IDELEMS(quot));
353 setUnit(A->rank,unit);
354 return idCopy(A);
355 }
356 /* ideal or module? */
357 ring orig_ring=currRing;
358 int k=id_RankFreeModule(quot,orig_ring);
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 */
365 ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
366 rSetSyzComp(1,syz_ring);
367 rChangeCurrRing(syz_ring);
368 /* move ideals to new ring */
369 ideal s_quot;
370 ideal s_A;
371 if (orig_ring != syz_ring)
372 {
373 s_quot=idrCopyR_NoSort(quot,orig_ring,syz_ring);
374 s_A=idrCopyR_NoSort(A,orig_ring,syz_ring);
375 }
376 else
377 {
378 s_quot=id_Copy(quot,syz_ring);
379 s_A=id_Copy(A,syz_ring);
380 }
381 /* quot[i] -> quot[i]+e(k+i+1) */
382 for(int i=0;i<IDELEMS(s_quot);i++)
383 {
384 p_Shift(&s_quot->m[i],lsmod,syz_ring);
385 poly p=p_One(syz_ring);
386 p_SetComp(p,k+i+2,syz_ring);
387 p_Setm(p,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);
405 p_SetComp(p,u_k+i,syz_ring);
406 p_Setm(p,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");
418 id_Delete((ideal *) &m,currRing);
419 }
420 PrintS("with:\n");
421 {
422 void ipPrint_MA0(matrix m, const char *name);
424 ipPrint_MA0(m, "B");
425 id_Delete((ideal *) &m,currRing);
426 }
427 #endif
428 ideal rest=kNF(s_quot,syz_ring->qideal,s_A,0,lazyReduce);
429 #if 0
430 PrintS("result NF:\n");
431 {
432 void ipPrint_MA0(matrix m, const char *name);
434 ipPrint_MA0(m, "A");
435 id_Delete((ideal *) &m,currRing);
436 }
437 #endif
438 /* clean s_quot,s_A */
439 id_Delete(&s_quot,syz_ring);
440 id_Delete(&s_A,syz_ring);
441 /* interpret rest: remainder */
442 ideal result=idInit(IDELEMS(rest),A->rank);
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;
461 p_Shift(&result->m[i],-lsmod,syz_ring);
462 }
463 #if 0
464 PrintS("rest:\n");
465 {
466 void ipPrint_MA0(matrix m, const char *name);
468 ipPrint_MA0(m, "_");
469 id_Delete((ideal *) &m,currRing);
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, "_");
478 id_Delete((ideal *) &m,currRing);
479 }
480 #endif
481 /* interpret rest: factors */
482 factor=idInit(IDELEMS(rest),IDELEMS(quot));
483 if (unit==NULL)
484 {
485 for(int i=0;i<IDELEMS(rest);i++)
486 {
487 poly p=rest->m[i];
488 p_Shift(&p,-k-lsmod,syz_ring);
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 {
496 *unit=idInit(IDELEMS(A),IDELEMS(A));
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 }
524 id_Delete(&rest,syz_ring);
525 if (orig_ring != syz_ring)
526 {
527 rChangeCurrRing(orig_ring);
528 result=idrMoveR_NoSort(result, syz_ring, orig_ring);
529 factor=idrMoveR(factor, syz_ring, orig_ring);
530 if (unit!=NULL)
531 {
532 *unit=idrMoveR(*unit, syz_ring, orig_ring);
533 }
534 rDelete(syz_ring);
535 }
536 return result;
537}
#define TRUE
Definition auxiliary.h:101
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
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
ip_smatrix * matrix
Definition matpol.h:43
#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:4815
poly p_One(const ring r)
Definition p_polys.cc:1314
static poly p_Neg(poly p, const ring r)
Definition p_polys.h:1109
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:938
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition p_polys.h:249
static void p_Setm(poly p, const ring r)
Definition p_polys.h:235
void rChangeCurrRing(ring r)
Definition polys.cc:16
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:4522
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:454
void rSetSyzComp(int k, const ring r)
Definition ring.cc:5230
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
int name
New type name for int.

◆ initMora()

void initMora ( ideal F,
kStrategy strat )

Definition at line 1811 of file kstd1.cc.

1812{
1813 int i,j;
1814
1815 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
1816 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
1817 strat->enterS = enterSMora;
1818 strat->initEcartPair = initEcartPairMora; /*- ecart approximation -*/
1819 strat->posInLOld = strat->posInL;
1820 strat->posInLOldFlag = TRUE;
1821 strat->initEcart = initEcartNormal;
1822 if (strat->homog)
1823 strat->red = redFirst; /*take the first possible in T*/
1824 else
1825 strat->red = redEcart;/*take the first possible in under ecart-restriction*/
1826 if ( currRing->ppNoether!=NULL )
1827 {
1828 strat->kNoether = pCopy((currRing->ppNoether));
1829 if (TEST_OPT_PROT)
1830 {
1831 Print("H(%ld)",p_FDeg(strat->kNoether,currRing)+1);
1832 mflush();
1833 }
1834 }
1835 if (strat->kNoether!=NULL)
1836 {
1837 HCord = currRing->pFDeg((strat->kNoether),currRing)+1;
1838 }
1839 else
1840 {
1841 HCord = INT_MAX-3;/*- very large -*/
1842 }
1843
1845 {
1846 if (rField_is_Z(currRing))
1847 strat->red = redRiloc_Z;
1848 else
1849 strat->red = redRiloc;
1850 }
1851
1852 /*reads the ecartWeights used for Graebes method from the
1853 *intvec ecart and set ecartWeights
1854 */
1855 if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
1856 {
1857 //interred machen Aenderung
1858 strat->pOrigFDeg=currRing->pFDeg;
1859 strat->pOrigLDeg=currRing->pLDeg;
1860 ecartWeights=(short *)omAlloc(((currRing->N)+1)*sizeof(short));
1861 /*uses automatic computation of the ecartWeights to set them*/
1863
1865 if (TEST_OPT_PROT)
1866 {
1867 for(i=1; i<=(currRing->N); i++)
1868 Print(" %d",ecartWeights[i]);
1869 PrintLn();
1870 mflush();
1871 }
1872 }
1873 kOptimizeLDeg(currRing->pLDeg, strat);
1874}
int BOOLEAN
Definition auxiliary.h:88
char posInLOldFlag
Definition kutil.h:381
poly kNoether
Definition kutil.h:330
BOOLEAN * NotUsedAxis
Definition kutil.h:333
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.h:285
pFDegProc pOrigFDeg
Definition kutil.h:297
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition kutil.h:289
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition kutil.h:288
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition kutil.h:287
void(* initEcart)(TObject *L)
Definition kutil.h:281
int(* red)(LObject *L, kStrategy strat)
Definition kutil.h:279
char homog
Definition kutil.h:371
pLDegProc pOrigLDeg
Definition kutil.h:298
#define Print
Definition emacs.cc:80
int j
Definition facHensel.cc:110
int redFirst(LObject *h, kStrategy strat)
Definition kstd1.cc:794
int redEcart(LObject *h, kStrategy strat)
Definition kstd1.cc:168
static void kOptimizeLDeg(pLDegProc ldeg, kStrategy strat)
Definition kstd1.cc:100
int redRiloc(LObject *h, kStrategy strat)
Definition kstd1.cc:385
void enterSMora(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1620
int redRiloc_Z(LObject *h, kStrategy strat)
Definition kstd1.cc:566
VAR int HCord
Definition kutil.cc:239
void initEcartPairMora(LObject *Lp, poly, poly, int ecartF, int ecartG)
Definition kutil.cc:1322
void initEcartNormal(TObject *h)
Definition kutil.cc:1300
#define omAlloc(size)
#define TEST_OPT_WEIGHTM
Definition options.h:123
#define TEST_OPT_PROT
Definition options.h:105
void pSetDegProcs(ring r, pFDegProc new_FDeg, pLDegProc new_lDeg)
Definition p_polys.cc:3717
static long p_FDeg(const poly p, const ring r)
Definition p_polys.h:382
#define pCopy(p)
return a copy of the poly
Definition polys.h:186
void PrintLn()
Definition reporter.cc:310
#define mflush()
Definition reporter.h:58
static BOOLEAN rField_is_Z(const ring r)
Definition ring.h:515
#define rField_is_Ring(R)
Definition ring.h:491
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;
3441 if( currRing != _currRing ) rChangeCurrRing(_currRing);
3442 poly ret = kNF(F, Q, p, syzComp, lazyReduce);
3443 if( currRing != save ) rChangeCurrRing(save);
3444 return ret;
3445}
#define Q
Definition sirandom.c:26

◆ kHomModDeg()

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

Definition at line 2417 of file kstd1.cc.

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

◆ kInterRed()

ideal kInterRed ( ideal F,
const ideal Q = NULL )

Definition at line 3797 of file kstd1.cc.

3798{
3799#ifdef HAVE_PLURAL
3800 if(rIsPluralRing(currRing)) return kInterRedOld(F,Q);
3801#endif
3804 )
3805 return kInterRedOld(F,Q);
3806
3807 //return kInterRedOld(F,Q);
3808
3809 BITSET save1;
3810 SI_SAVE_OPT1(save1);
3811 //si_opt_1|=Sy_bit(OPT_NOT_SUGAR);
3813 //si_opt_1&= ~Sy_bit(OPT_REDTAIL);
3814 //si_opt_1&= ~Sy_bit(OPT_REDSB);
3815 //extern char * showOption() ;
3816 //Print("%s\n",showOption());
3817
3818 int need_retry;
3819 int counter=3;
3820 ideal res, res1;
3821 int elems=0;
3822 ideal null=NULL;
3823 if ((Q==NULL) || (!TEST_OPT_REDSB))
3824 {
3825 elems=idElem(F);
3826 res=kInterRedBba(F,Q,need_retry);
3827 }
3828 else
3829 {
3830 ideal FF=idSimpleAdd(F,Q);
3831 res=kInterRedBba(FF,NULL,need_retry);
3832 idDelete(&FF);
3833 null=idInit(1,1);
3834 if (need_retry)
3835 res1=kNF(null,Q,res,0,KSTD_NF_LAZY | KSTD_NF_NONORM);
3836 else
3837 res1=kNF(null,Q,res);
3838 idDelete(&res);
3839 res=res1;
3840 need_retry=1;
3841 }
3842 if (idElem(res)<=1) need_retry=0;
3843 while (need_retry && (counter>0))
3844 {
3845 #ifdef KDEBUG
3846 if (TEST_OPT_DEBUG) { Print("retry counter %d\n",counter); }
3847 #endif
3848 res1=kInterRedBba(res,Q,need_retry);
3849 int new_elems=idElem(res1);
3850 counter -= (new_elems >= elems);
3851 elems = new_elems;
3852 idDelete(&res);
3853 if (idElem(res1)<=1) need_retry=0;
3854 if ((Q!=NULL) && (TEST_OPT_REDSB))
3855 {
3856 if (need_retry)
3857 res=kNF(null,Q,res1,0,KSTD_NF_LAZY | KSTD_NF_NONORM);
3858 else
3859 res=kNF(null,Q,res1);
3860 idDelete(&res1);
3861 }
3862 else
3863 res = res1;
3864 if (idElem(res)<=1) need_retry=0;
3865 }
3866 if (null!=NULL) idDelete(&null);
3867 SI_RESTORE_OPT1(save1);
3869 return res;
3870}
#define BITSET
Definition auxiliary.h:85
CanonicalForm res
Definition facAbsFact.cc:60
#define idDelete(H)
delete an ideal
Definition ideals.h:29
#define idSimpleAdd(A, B)
Definition ideals.h:42
ideal kInterRedBba(ideal F, ideal Q, int &need_retry)
Definition kstd1.cc:3546
ideal kInterRedOld(ideal F, const ideal Q)
Definition kstd1.cc:3451
#define KSTD_NF_LAZY
Definition kstd1.h:18
#define KSTD_NF_NONORM
Definition kstd1.h:22
VAR unsigned si_opt_1
Definition options.c:5
#define SI_SAVE_OPT1(A)
Definition options.h:21
#define SI_RESTORE_OPT1(A)
Definition options.h:24
#define OPT_REDTHROUGH
Definition options.h:83
#define Sy_bit(x)
Definition options.h:31
#define TEST_OPT_REDSB
Definition options.h:106
#define TEST_OPT_DEBUG
Definition options.h:110
static BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition ring.h:769
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition ring.h:406
static BOOLEAN rField_is_numeric(const ring r)
Definition ring.h:521
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

◆ kInterRedBba()

ideal kInterRedBba ( ideal F,
ideal Q,
int & need_retry )

Definition at line 3546 of file kstd1.cc.

3547{
3548 need_retry=0;
3549 int red_result = 1;
3550 int olddeg,reduc;
3551 BOOLEAN withT = FALSE;
3552 // BOOLEAN toReset=FALSE;
3553 kStrategy strat=new skStrategy;
3554 tHomog h;
3555
3557 strat->LazyPass=20;
3558 else
3559 strat->LazyPass=2;
3560 strat->LazyDegree = 1;
3561 strat->ak = id_RankFreeModule(F,currRing);
3562 strat->syzComp = strat->ak;
3563 strat->kModW=kModW=NULL;
3564 strat->kHomW=kHomW=NULL;
3565 if (strat->ak == 0)
3566 {
3567 h = (tHomog)idHomIdeal(F,Q);
3568 }
3569 else if (!TEST_OPT_DEGBOUND)
3570 {
3571 h = (tHomog)idHomIdeal(F,Q);
3572 }
3573 else
3574 h = isNotHomog;
3575 if (h==isHomog)
3576 {
3577 strat->LazyPass*=2;
3578 }
3579 strat->homog=h;
3580#ifdef KDEBUG
3581 idTest(F);
3582#endif
3583
3584 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
3586 initBuchMoraPosRing(strat);
3587 else
3588 initBuchMoraPos(strat);
3589 initBba(strat);
3590 /*set enterS, spSpolyShort, reduce, red, initEcart, initEcartPair*/
3591 strat->posInL=posInL0; /* ord according pComp */
3592
3593 /*Shdl=*/initBuchMora(F, Q, strat);
3594 reduc = olddeg = 0;
3595
3596#ifndef NO_BUCKETS
3598 strat->use_buckets = 1;
3599#endif
3600
3601 // redtailBBa against T for inhomogeneous input
3602 if (!TEST_OPT_OLDSTD)
3603 withT = ! strat->homog;
3604
3605 // strat->posInT = posInT_pLength;
3606 kTest_TS(strat);
3607
3608#ifdef HAVE_TAIL_RING
3610#endif
3611
3612 /* compute------------------------------------------------------- */
3613 while (strat->Ll >= 0)
3614 {
3615 #ifdef KDEBUG
3616 if (TEST_OPT_DEBUG) messageSets(strat);
3617 #endif
3618 if (strat->Ll== 0) strat->interpt=TRUE;
3619 /* picks the last element from the lazyset L */
3620 strat->P = strat->L[strat->Ll];
3621 strat->Ll--;
3622
3623 if (strat->P.p1 == NULL)
3624 {
3625 // for input polys, prepare reduction
3626 strat->P.PrepareRed(strat->use_buckets);
3627 }
3628
3629 if (strat->P.p == NULL && strat->P.t_p == NULL)
3630 {
3631 red_result = 0;
3632 }
3633 else
3634 {
3635 if (TEST_OPT_PROT)
3636 message(strat->P.pFDeg(),
3637 &olddeg,&reduc,strat, red_result);
3638
3639 /* reduction of the element chosen from L */
3640 red_result = strat->red(&strat->P,strat);
3641 }
3642
3643 // reduction to non-zero new poly
3644 if (red_result == 1)
3645 {
3646 /* statistic */
3647 if (TEST_OPT_PROT) PrintS("s");
3648
3649 // get the polynomial (canonicalize bucket, make sure P.p is set)
3650 strat->P.GetP(strat->lmBin);
3651
3652 int pos=posInS(strat,strat->sl,strat->P.p,strat->P.ecart);
3653
3654 // reduce the tail and normalize poly
3655 // in the ring case we cannot expect LC(f) = 1,
3656 // therefore we call pCleardenom instead of pNorm
3658 {
3659 strat->P.pCleardenom();
3660 }
3661 else
3662 {
3663 strat->P.pNorm();
3664 }
3665
3666#ifdef KDEBUG
3667 if (TEST_OPT_DEBUG){PrintS("new s:");strat->P.wrp();PrintLn();}
3668#endif
3669
3670 // enter into S, L, and T
3671 if ((!TEST_OPT_IDLIFT) || (pGetComp(strat->P.p) <= strat->syzComp))
3672 {
3673 enterT(strat->P, strat);
3674 // posInS only depends on the leading term
3675 strat->enterS(strat->P, pos, strat, strat->tl);
3676
3677 if (pos<strat->sl)
3678 {
3679 need_retry++;
3680 // move all "larger" elements fromS to L
3681 // remove them from T
3682 int ii=pos+1;
3683 for(;ii<=strat->sl;ii++)
3684 {
3685 LObject h;
3686 h.Clear();
3687 h.tailRing=strat->tailRing;
3688 h.p=strat->S[ii]; strat->S[ii]=NULL;
3689 strat->initEcart(&h);
3690 h.sev=strat->sevS[ii];
3691 int jj=strat->tl;
3692 while (jj>=0)
3693 {
3694 if (strat->T[jj].p==h.p)
3695 {
3696 strat->T[jj].p=NULL;
3697 if (jj<strat->tl)
3698 {
3699 memmove(&(strat->T[jj]),&(strat->T[jj+1]),
3700 (strat->tl-jj)*sizeof(strat->T[jj]));
3701 memmove(&(strat->sevT[jj]),&(strat->sevT[jj+1]),
3702 (strat->tl-jj)*sizeof(strat->sevT[jj]));
3703 }
3704 strat->tl--;
3705 break;
3706 }
3707 jj--;
3708 }
3709 int lpos=strat->posInL(strat->L,strat->Ll,&h,strat);
3710 enterL(&strat->L,&strat->Ll,&strat->Lmax,h,lpos);
3711 #ifdef KDEBUG
3712 if (TEST_OPT_DEBUG)
3713 {
3714 Print("move S[%d] -> L[%d]: ",ii,pos);
3715 p_wrp(h.p,currRing, strat->tailRing);
3716 PrintLn();
3717 }
3718 #endif
3719 }
3720 if (strat->fromQ!=NULL)
3721 {
3722 for(ii=pos+1;ii<=strat->sl;ii++) strat->fromQ[ii]=0;
3723 }
3724 strat->sl=pos;
3725 }
3726 }
3727 else
3728 {
3729 // clean P
3730 }
3731 kDeleteLcm(&strat->P);
3732 }
3733
3734#ifdef KDEBUG
3735 if (TEST_OPT_DEBUG)
3736 {
3737 messageSets(strat);
3738 }
3739 strat->P.Clear();
3740#endif
3741 //kTest_TS(strat);: i_r out of sync in kInterRedBba, but not used!
3742 }
3743#ifdef KDEBUG
3744 //if (TEST_OPT_DEBUG) messageSets(strat);
3745#endif
3746 /* complete reduction of the standard basis--------- */
3747
3748 if((need_retry<=0) && (TEST_OPT_REDSB))
3749 {
3750 completeReduce(strat);
3751 if (strat->completeReduce_retry)
3752 {
3753 // completeReduce needed larger exponents, retry
3754 // hopefully: kStratChangeTailRing already provided a larger tailRing
3755 // (otherwise: it will fail again)
3757 completeReduce(strat);
3758 if (strat->completeReduce_retry)
3759 {
3760#ifdef HAVE_TAIL_RING
3761 if(currRing->bitmask>strat->tailRing->bitmask)
3762 {
3763 // retry without T
3765 cleanT(strat);strat->tailRing=currRing;
3766 int i;
3767 for(i=strat->sl;i>=0;i--) strat->S_2_R[i]=-1;
3768 completeReduce(strat);
3769 }
3770 if (strat->completeReduce_retry)
3771#endif
3772 Werror("exponent bound is %ld",currRing->bitmask);
3773 }
3774 }
3775 }
3776 else if (TEST_OPT_PROT) PrintLn();
3777
3778
3779 /* release temp data-------------------------------- */
3780 exitBuchMora(strat);
3781// if (TEST_OPT_WEIGHTM)
3782// {
3783// pRestoreDegProcs(currRing,strat->pOrigFDeg, strat->pOrigLDeg);
3784// if (ecartWeights)
3785// {
3786// omFreeSize((ADDRESS)ecartWeights,((currRing->N)+1)*sizeof(short));
3787// ecartWeights=NULL;
3788// }
3789// }
3790 //if (TEST_OPT_PROT) messageStat(0/*hilbcount*/,strat);
3791 if (Q!=NULL) updateResult(strat->Shdl,Q,strat);
3792 ideal res=strat->Shdl;
3793 strat->Shdl=NULL;
3794 delete strat;
3795 return res;
3796}
#define FALSE
Definition auxiliary.h:97
intvec * kModW
Definition kutil.h:336
int syzComp
Definition kutil.h:355
int * S_2_R
Definition kutil.h:343
ring tailRing
Definition kutil.h:344
int Ll
Definition kutil.h:352
TSet T
Definition kutil.h:327
omBin lmBin
Definition kutil.h:345
polyset S
Definition kutil.h:307
int ak
Definition kutil.h:354
int tl
Definition kutil.h:351
unsigned long * sevT
Definition kutil.h:326
intvec * kHomW
Definition kutil.h:337
ideal Shdl
Definition kutil.h:304
intset fromQ
Definition kutil.h:322
char use_buckets
Definition kutil.h:382
char interpt
Definition kutil.h:370
char completeReduce_retry
Definition kutil.h:402
LObject P
Definition kutil.h:303
int Lmax
Definition kutil.h:352
int LazyPass
Definition kutil.h:354
LSet L
Definition kutil.h:328
int sl
Definition kutil.h:349
int LazyDegree
Definition kutil.h:354
unsigned long * sevS
Definition kutil.h:323
#define idTest(id)
Definition ideals.h:47
static BOOLEAN idHomIdeal(ideal id, ideal Q=NULL)
Definition ideals.h:91
STATIC_VAR Poly * h
Definition janet.cc:971
void initBba(kStrategy strat)
Definition kstd1.cc:1681
VAR intvec * kHomW
Definition kstd1.cc:2405
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition kutil.cc:7467
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9751
void enterT(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9143
BOOLEAN kTest_TS(kStrategy strat)
Definition kutil.cc:1074
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition kutil.cc:1276
void initBuchMoraPos(kStrategy strat)
Definition kutil.cc:9580
int posInL0(const LSet set, const int length, LObject *p, const kStrategy)
Definition kutil.cc:5618
void exitBuchMora(kStrategy strat)
Definition kutil.cc:9838
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition kutil.cc:4670
void cleanT(kStrategy strat)
Definition kutil.cc:557
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition kutil.cc:10081
void kStratInitChangeTailRing(kStrategy strat)
Definition kutil.cc:11058
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9435
void completeReduce(kStrategy strat, BOOLEAN withT)
Definition kutil.cc:10287
void initBuchMoraPosRing(kStrategy strat)
Definition kutil.cc:9665
void messageSets(kStrategy strat)
Definition kutil.cc:7540
static void kDeleteLcm(LObject *P)
Definition kutil.h:870
class sLObject LObject
Definition kutil.h:59
#define TEST_OPT_IDLIFT
Definition options.h:131
#define TEST_OPT_INTSTRATEGY
Definition options.h:112
#define TEST_OPT_OLDSTD
Definition options.h:125
#define TEST_OPT_DEGBOUND
Definition options.h:115
#define TEST_OPT_NOT_BUCKETS
Definition options.h:107
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition polys0.cc:373
#define pGetComp(p)
Component.
Definition polys.h:38
void Werror(const char *fmt,...)
Definition reporter.cc:189
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition ring.h:554
tHomog
Definition structs.h:31
@ isHomog
Definition structs.h:33
@ isNotHomog
Definition structs.h:32
skStrategy * kStrategy
Definition structs.h:54

◆ 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);
3464 tempF = id_KillSquares(F, m_iFirstAltVar, m_iLastAltVar, currRing);
3465
3466 // this should be done on the upper level!!! :
3467 // tempQ = SCAQuotient(currRing);
3468
3469 if(Q == currRing->qideal)
3470 tempQ = SCAQuotient(currRing);
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));
3482 strat->ak = 0;
3483 if (id_IsModule(tempF,currRing)) strat->ak = id_RankFreeModule(tempF,currRing);
3484 initBuchMoraCrit(strat);
3485 strat->NotUsedAxis = (BOOLEAN *)omAlloc(((currRing->N)+1)*sizeof(BOOLEAN));
3486 for (j=(currRing->N); j>0; j--) strat->NotUsedAxis[j] = TRUE;
3487 strat->enterS = enterSBba;
3488 strat->posInT = posInT17;
3489 strat->initEcart = initEcartNormal;
3490 strat->sl = -1;
3491 strat->tl = -1;
3492 strat->tmax = setmaxT;
3493 strat->T = initT();
3494 strat->R = initR();
3495 strat->sevT = initsevT();
3497 initS(tempF, tempQ, strat);
3498 if (TEST_OPT_REDSB)
3499 strat->noTailReduction=FALSE;
3500 updateS(TRUE,strat);
3502 completeReduce(strat);
3503 //else if (TEST_OPT_PROT) PrintLn();
3504 cleanT(strat);
3505 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
3506 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
3507 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
3508 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
3509 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
3510 omfree(strat->sevT);
3511 omfree(strat->S_2_R);
3512 omfree(strat->R);
3513
3514 if (strat->fromQ)
3515 {
3516 for (j=IDELEMS(strat->Shdl)-1;j>=0;j--)
3517 {
3518 if(strat->fromQ[j]) pDelete(&strat->Shdl->m[j]);
3519 }
3520 omFree((ADDRESS)strat->fromQ);
3521 strat->fromQ=NULL;
3522 }
3523// if (TEST_OPT_PROT)
3524// {
3525// writeTime("end Interred:");
3526// mflush();
3527// }
3528 ideal shdl=strat->Shdl;
3529 idSkipZeroes(shdl);
3530 if (strat->fromQ)
3531 {
3532 omfree(strat->fromQ);
3533 strat->fromQ=NULL;
3534 ideal res=kInterRed(shdl,NULL);
3535 idDelete(&shdl);
3536 shdl=res;
3537 }
3538 delete(strat);
3539#ifdef HAVE_PLURAL
3540 if( tempF != F )
3541 id_Delete( &tempF, currRing);
3542#endif
3543 return shdl;
3544}
void * ADDRESS
Definition auxiliary.h:120
char noTailReduction
Definition kutil.h:377
intset ecartS
Definition kutil.h:310
char honey
Definition kutil.h:376
TObject ** R
Definition kutil.h:341
int tmax
Definition kutil.h:351
char kAllAxis
Definition kutil.h:375
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition kutil.h:282
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:3797
int posInT17(const TSet set, const int length, LObject &p)
Definition kutil.cc:5285
void initS(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7590
void updateS(BOOLEAN toT, kStrategy strat)
Definition kutil.cc:8559
void enterSBba(LObject &p, int atS, kStrategy strat, int atR)
Definition kutil.cc:8794
#define setmaxT
Definition kutil.h:34
class sTObject TObject
Definition kutil.h:58
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 pDelete(p_ptr)
Definition polys.h:187
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:71
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
BOOLEAN id_IsModule(ideal A, const ring src)

◆ kMin_std()

ideal kMin_std ( ideal F,
ideal Q,
tHomog h,
intvec ** w,
ideal & M,
intvec * hilb,
int syzComp = 0,
int reduced = 0 )

Definition at line 3216 of file kstd1.cc.

3218{
3219 bigintmat *hh=iv2biv(hilb,coeffs_BIGINT);
3220 ideal res=kMin_std2(F,Q,h,w,M,hh,syzComp,reduced);
3221 if (hh!=NULL) delete hh;
3222 return res;
3223}
Matrices of numbers.
Definition bigintmat.h:51
const CanonicalForm & w
Definition facAbsFact.cc:51
bigintmat * iv2biv(intvec *hilb, const coeffs cf)
Definition intvec.cc:851
ideal kMin_std2(ideal F, ideal Q, tHomog h, intvec **w, ideal &M, bigintmat *hilb, int syzComp, int reduced)
Definition kstd1.cc:3064
VAR coeffs coeffs_BIGINT
Definition polys.cc:14
#define M
Definition sirandom.c:25

◆ kMin_std2()

ideal kMin_std2 ( ideal F,
ideal Q,
tHomog h,
intvec ** w,
ideal & M,
bigintmat * hilb,
int syzComp = 0,
int reduced = 0 )

Definition at line 3064 of file kstd1.cc.

3066{
3067 if(idIs0(F))
3068 {
3069 M=idInit(1,F->rank);
3070 return idInit(1,F->rank);
3071 }
3073 {
3074 ideal sb;
3075 sb = kStd2(F, Q, h, w, hilb);
3076 idSkipZeroes(sb);
3077 if(IDELEMS(sb) <= IDELEMS(F))
3078 {
3079 M = idCopy(sb);
3080 idSkipZeroes(M);
3081 return(sb);
3082 }
3083 else
3084 {
3085 M = idCopy(F);
3086 idSkipZeroes(M);
3087 return(sb);
3088 }
3089 }
3090 ideal r=NULL;
3091 int Kstd1_OldDeg = Kstd1_deg,i;
3092 intvec* temp_w=NULL;
3093 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
3094 BOOLEAN delete_w=(w==NULL);
3095 BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
3096 kStrategy strat=new skStrategy;
3097
3099 strat->syzComp = syzComp;
3101 strat->LazyPass=20;
3102 else
3103 strat->LazyPass=2;
3104 strat->LazyDegree = 1;
3105 strat->minim=(reduced % 2)+1;
3106 strat->ak = 0;
3107 if (id_IsModule(F,currRing)) strat->ak = id_RankFreeModule(F,currRing);
3108 if (delete_w)
3109 {
3110 temp_w=new intvec((strat->ak)+1);
3111 w = &temp_w;
3112 }
3113 if (h==testHomog)
3114 {
3115 if (strat->ak == 0)
3116 {
3117 h = (tHomog)idHomIdeal(F,Q);
3118 w=NULL;
3119 }
3120 else
3121 {
3122 h = (tHomog)idHomModule(F,Q,w);
3123 }
3124 }
3125 if (h==isHomog)
3126 {
3127 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
3128 {
3129 kModW = *w;
3130 strat->kModW = *w;
3131 assume(currRing->pFDeg != NULL && currRing->pLDeg != NULL);
3132 strat->pOrigFDeg = currRing->pFDeg;
3133 strat->pOrigLDeg = currRing->pLDeg;
3135
3136 toReset = TRUE;
3137 if (reduced>1)
3138 {
3139 Kstd1_OldDeg=Kstd1_deg;
3140 Kstd1_deg = -1;
3141 for (i=IDELEMS(F)-1;i>=0;i--)
3142 {
3143 if ((F->m[i]!=NULL) && (currRing->pFDeg(F->m[i],currRing)>=Kstd1_deg))
3144 Kstd1_deg = currRing->pFDeg(F->m[i],currRing)+1;
3145 }
3146 }
3147 }
3148 currRing->pLexOrder = TRUE;
3149 strat->LazyPass*=2;
3150 }
3151 strat->homog=h;
3152 ideal SB=NULL;
3154 {
3155 r=idMinBase(F,&SB); // SB and M via minbase
3156 strat->M=r;
3157 r=SB;
3158 }
3159 else
3160 {
3161 if (w!=NULL)
3162 r=bba(F,Q,*w,hilb,strat);
3163 else
3164 r=bba(F,Q,NULL,hilb,strat);
3165 }
3166#ifdef KDEBUG
3167 {
3168 int i;
3169 for (i=IDELEMS(r)-1; i>=0; i--) pTest(r->m[i]);
3170 }
3171#endif
3172 idSkipZeroes(r);
3173 if (toReset)
3174 {
3176 kModW = NULL;
3177 }
3178 currRing->pLexOrder = b;
3179 if ((delete_w)&&(temp_w!=NULL)) delete temp_w;
3180 if ((IDELEMS(r)==1) && (r->m[0]!=NULL) && pIsConstant(r->m[0]) && (strat->ak==0))
3181 {
3182 M=idInit(1,F->rank);
3183 M->m[0]=pOne();
3184 //if (strat->ak!=0) { pSetComp(M->m[0],strat->ak); pSetmComp(M->m[0]); }
3185 if (strat->M!=NULL) idDelete(&strat->M);
3186 }
3187 else if (strat->M==NULL)
3188 {
3189 M=idInit(1,F->rank);
3190 WarnS("no minimal generating set computed");
3191 }
3192 else
3193 {
3194 idSkipZeroes(strat->M);
3195 M=strat->M;
3196 strat->M=NULL;
3197 }
3198 delete(strat);
3199 if (reduced>2)
3200 {
3201 Kstd1_deg=Kstd1_OldDeg;
3202 if (!oldDegBound)
3204 }
3205 else
3206 {
3207 if (IDELEMS(M)>IDELEMS(r))
3208 {
3209 idDelete(&M);
3210 M=idCopy(r);
3211 }
3212 }
3213 return r;
3214}
CanonicalForm b
Definition cfModGcd.cc:4111
int minim
Definition kutil.h:358
ideal M
Definition kutil.h:306
#define WarnS
Definition emacs.cc:78
ideal idMinBase(ideal h1, ideal *SB)
Definition ideals.cc:51
static BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition ideals.h:96
long kModDeg(poly p, const ring r)
Definition kstd1.cc:2407
ideal kStd2(ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
generic interface to GB/SB computations, large hilbert vectors
Definition kstd1.cc:2602
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:70
ideal bba(ideal F, ideal Q, intvec *w, bigintmat *hilb, kStrategy strat)
Definition kstd2.cc:2622
#define assume(x)
Definition mod2.h:389
#define TEST_OPT_RETURN_SB
Definition options.h:114
#define OPT_DEGBOUND
Definition options.h:91
void pRestoreDegProcs(ring r, pFDegProc old_FDeg, pLDegProc old_lDeg)
Definition p_polys.cc:3729
#define pTest(p)
Definition polys.h:415
#define pIsConstant(p)
like above, except that Comp must be 0
Definition polys.h:239
#define pOne()
Definition polys.h:316
@ testHomog
Definition structs.h:34

◆ kModDeg()

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

Definition at line 2407 of file kstd1.cc.

2408{
2409 long o=p_WDegree(p, r);
2410 long i=__p_GetComp(p, r);
2411 if (i==0) return o;
2412 //assume((i>0) && (i<=kModW->length()));
2413 if (i<=kModW->length())
2414 return o+(*kModW)[i-1];
2415 return o;
2416}
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);
3338 pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
3339
3340 if(Q == currRing->qideal)
3342 }
3343#endif
3344
3345 if (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:125
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:2115
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd2.cc:3944

◆ 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);
3236 pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing);
3237
3238 if(Q == currRing->qideal)
3240 }
3241#endif
3242 if(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:903
#define pMaxComp(p)
Definition polys.h:300

◆ kNF1() [1/2]

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

Definition at line 2256 of file kstd1.cc.

2257{
2258 assume(!idIs0(q));
2259 assume(!(idIs0(F)&&(Q==NULL)));
2260
2261// lazy_reduce flags: can be combined by |
2262//#define KSTD_NF_LAZY 1
2263 // do only a reduction of the leading term
2264//#define KSTD_NF_ECART 2
2265 // only local: reduce even with bad ecart
2266 poly p;
2267 int i;
2268 int j;
2269 int o;
2270 LObject h;
2271 ideal res;
2272 BITSET save1;
2273 SI_SAVE_OPT1(save1);
2274
2275 //if (idIs0(q)) return idInit(IDELEMS(q),si_max(q->rank,F->rank));
2276 //if ((idIs0(F))&&(Q==NULL))
2277 // return idCopy(q); /*F=0*/
2278 //strat->ak = si_max(idRankFreeModule(F),idRankFreeModule(q));
2279 /*- creating temp data structures------------------- -*/
2280 strat->kAllAxis = (currRing->ppNoether) != NULL;
2281 strat->kNoether=pCopy((currRing->ppNoether));
2284 && (0<Kstd1_deg)
2285 && ((strat->kNoether==NULL)
2287 {
2288 pLmDelete(&strat->kNoether);
2289 strat->kNoether=pOne();
2290 pSetExp(strat->kNoether,1, Kstd1_deg+1);
2291 pSetm(strat->kNoether);
2292 //strat->kAllAxis=TRUE;
2293 }
2294 initBuchMoraCrit(strat);
2296 initBuchMoraPosRing(strat);
2297 else
2298 initBuchMoraPos(strat);
2299 initMora(F,strat);
2300 strat->enterS = enterSMoraNF;
2301 /*- set T -*/
2302 strat->tl = -1;
2303 strat->tmax = setmaxT;
2304 strat->T = initT();
2305 strat->R = initR();
2306 strat->sevT = initsevT();
2307 /*- set S -*/
2308 strat->sl = -1;
2309 /*- init local data struct.-------------------------- -*/
2310 /*Shdl=*/initS(F,Q,strat);
2311 if ((strat->ak!=0)
2312 && (strat->kNoether!=NULL))
2313 {
2314 if (strat->ak!=1)
2315 {
2316 pSetComp(strat->kNoether,1);
2317 pSetmComp(strat->kNoether);
2318 poly p=pHead(strat->kNoether);
2319 pSetComp(p,strat->ak);
2320 pSetmComp(p);
2321 p=pAdd(strat->kNoether,p);
2322 strat->kNoether=pNext(p);
2324 }
2325 }
2326 if (((lazyReduce & KSTD_NF_LAZY)==0)
2327 && (!rField_is_Ring(currRing)))
2328 {
2329 for (i=strat->sl; i>=0; i--)
2330 pNorm(strat->S[i]);
2331 }
2332 /*- compute------------------------------------------- -*/
2333 res=idInit(IDELEMS(q),strat->ak);
2334 for (i=0; i<IDELEMS(q); i++)
2335 {
2336 if (q->m[i]!=NULL)
2337 {
2338 p = pCopy(q->m[i]);
2339 deleteHC(&p,&o,&j,strat);
2340 if (p!=NULL)
2341 {
2342 /*- puts the elements of S also to T -*/
2343 for (j=0; j<=strat->sl; j++)
2344 {
2345 h.p = strat->S[j];
2346 h.ecart = strat->ecartS[j];
2347 h.pLength = h.length = pLength(h.p);
2348 if (strat->sevS[j] == 0) strat->sevS[j] = pGetShortExpVector(h.p);
2349 else assume(strat->sevS[j] == pGetShortExpVector(h.p));
2350 h.sev = strat->sevS[j];
2351 h.SetpFDeg();
2353 enterT_strong(h,strat);
2354 else
2355 enterT(h,strat);
2356 }
2357 if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
2359 {
2360 p = redMoraNFRing(p,strat, lazyReduce);
2361 }
2362 else
2363 p = redMoraNF(p,strat, lazyReduce);
2364 if ((p!=NULL)&&((lazyReduce & KSTD_NF_LAZY)==0))
2365 {
2366 if (TEST_OPT_PROT) { PrintS("t"); mflush(); }
2367 p = redtail(p,strat->sl,strat);
2368 }
2369 cleanT(strat);
2370 }
2371 res->m[i]=p;
2372 }
2373 //else
2374 // res->m[i]=NULL;
2375 }
2376 /*- release temp data------------------------------- -*/
2377 assume(strat->L==NULL); /*strat->L unused */
2378 assume(strat->B==NULL); /*strat->B unused */
2379 omFreeSize((ADDRESS)strat->T,strat->tmax*sizeof(TObject));
2380 omFreeSize((ADDRESS)strat->ecartS,IDELEMS(strat->Shdl)*sizeof(int));
2381 omFreeSize((ADDRESS)strat->sevS,IDELEMS(strat->Shdl)*sizeof(unsigned long));
2382 omFreeSize((ADDRESS)strat->NotUsedAxis,((currRing->N)+1)*sizeof(BOOLEAN));
2383 omFree(strat->sevT);
2384 omFree(strat->S_2_R);
2385 omFree(strat->R);
2386 omfree((ADDRESS)strat->fromQ);
2387 strat->fromQ=NULL;
2388 if (strat->kNoether!=NULL) pLmFree(&strat->kNoether);
2389// if ((TEST_OPT_WEIGHTM)&&(F!=NULL))
2390// {
2391// pFDeg=strat->pOrigFDeg;
2392// pLDeg=strat->pOrigLDeg;
2393// if (ecartWeights)
2394// {
2395// omFreeSize((ADDRESS *)&ecartWeights,((currRing->N)+1)*sizeof(short));
2396// ecartWeights=NULL;
2397// }
2398// }
2399 idDelete(&strat->Shdl);
2400 SI_RESTORE_OPT1(save1);
2401 if (TEST_OPT_PROT) PrintLn();
2402 return res;
2403}
LSet B
Definition kutil.h:329
void initMora(ideal F, kStrategy strat)
Definition kstd1.cc:1811
void enterSMoraNF(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kstd1.cc:1673
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:6840
void enterT_strong(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9242
void deleteHC(LObject *L, kStrategy strat, BOOLEAN fromNext)
Definition kutil.cc:286
#define OPT_REDTAIL
Definition options.h:92
#define TEST_OPT_STAIRCASEBOUND
Definition options.h:117
static int pLength(poly a)
Definition p_polys.h:190
static void p_LmDelete(poly p, const ring r)
Definition p_polys.h:725
#define pAdd(p, q)
Definition polys.h:204
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition polys.h:68
#define pSetm(p)
Definition polys.h:272
void pNorm(poly p)
Definition polys.h:363
#define pSetComp(p, v)
Definition polys.h:39
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition polys.h:77
#define pGetShortExpVector(a)
returns the "Short Exponent Vector" – used to speed up divisibility tests (see polys-impl....
Definition polys.h:153
#define pSetmComp(p)
TODO:
Definition polys.h:274
#define pSetExp(p, i, v)
Definition polys.h:43
#define pWTotaldegree(p)
Definition polys.h:284

◆ kNF1() [2/2]

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

Definition at line 2115 of file kstd1.cc.

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

◆ kNFBound() [1/2]

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

Definition at line 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);
3403 pp = id_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, currRing, false);
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:4032

◆ 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);
3292 pp = p_KillSquares(pp, m_iFirstAltVar, m_iLastAltVar, 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,
bigintmat * hilb = NULL,
int syzComp = 0,
int newIdeal = 0,
intvec * vw = NULL )

Definition at line 2663 of file kstd1.cc.

2665{
2666 if(idIs0(F))
2667 return idInit(1,F->rank);
2669 {
2670 ideal r;
2671 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2672 BOOLEAN delete_w=(w==NULL);
2673 kStrategy strat=new skStrategy;
2674 strat->sbaOrder = sbaOrder;
2675 if (arri!=0)
2676 {
2677 strat->rewCrit1 = arriRewDummy;
2678 strat->rewCrit2 = arriRewCriterion;
2680 }
2681 else
2682 {
2686 }
2687
2689 strat->syzComp = syzComp;
2690 if (TEST_OPT_SB_1)
2691 //if(!rField_is_Ring(currRing)) // always true here
2692 strat->newIdeal = newIdeal;
2694 strat->LazyPass=20;
2695 else
2696 strat->LazyPass=2;
2697 strat->LazyDegree = 1;
2701 strat->ak = 0;
2702 if (id_IsModule(F,currRing)) strat->ak = id_RankFreeModule(F,currRing);
2703 strat->kModW=kModW=NULL;
2704 strat->kHomW=kHomW=NULL;
2705 if (vw != NULL)
2706 {
2707 currRing->pLexOrder=FALSE;
2708 strat->kHomW=kHomW=vw;
2709 strat->pOrigFDeg = currRing->pFDeg;
2710 strat->pOrigLDeg = currRing->pLDeg;
2712 toReset = TRUE;
2713 }
2714 if (h==testHomog)
2715 {
2716 if (strat->ak == 0)
2717 {
2718 h = (tHomog)idHomIdeal(F,Q);
2719 w=NULL;
2720 }
2721 else if (!TEST_OPT_DEGBOUND)
2722 {
2723 if (w!=NULL)
2724 h = (tHomog)idHomModule(F,Q,w);
2725 else
2726 h = (tHomog)idHomIdeal(F,Q);
2727 }
2728 }
2729 currRing->pLexOrder=b;
2730 if (h==isHomog)
2731 {
2732 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2733 {
2734 strat->kModW = kModW = *w;
2735 if (vw == NULL)
2736 {
2737 strat->pOrigFDeg = currRing->pFDeg;
2738 strat->pOrigLDeg = currRing->pLDeg;
2740 toReset = TRUE;
2741 }
2742 }
2743 currRing->pLexOrder = TRUE;
2744 if (hilb==NULL) strat->LazyPass*=2;
2745 }
2746 strat->homog=h;
2747 #ifdef KDEBUG
2748 idTest(F);
2749 if(Q != NULL)
2750 idTest(Q);
2751 #endif
2752 #ifdef HAVE_PLURAL
2754 {
2755 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2756 strat->no_prod_crit = ! bIsSCA;
2757 if (w!=NULL)
2758 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2759 else
2760 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2761 }
2762 else
2763 #endif
2764 {
2766 {
2767 if (w!=NULL)
2768 r=mora(F,Q,*w,hilb,strat);
2769 else
2770 r=mora(F,Q,NULL,hilb,strat);
2771 }
2772 else
2773 {
2774 strat->sigdrop = FALSE;
2775 if (w!=NULL)
2776 r=sba(F,Q,*w,hilb,strat);
2777 else
2778 r=sba(F,Q,NULL,hilb,strat);
2779 }
2780 }
2781 #ifdef KDEBUG
2782 idTest(r);
2783 #endif
2784 if (toReset)
2785 {
2786 kModW = NULL;
2788 }
2789 currRing->pLexOrder = b;
2790 //Print("%d reductions canceled \n",strat->cel);
2791 //delete(strat);
2792 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2793 return r;
2794 }
2795 else
2796 {
2797 //--------------------------RING CASE-------------------------
2798 assume(sbaOrder == 1);
2799 assume(arri == 0);
2800 ideal r;
2801 r = idCopy(F);
2802 int sbaEnterS = -1;
2803 bool sigdrop = TRUE;
2804 //This is how we set the SBA algorithm;
2805 int totalsbaruns = 1,blockedreductions = 20,blockred = 0,loops = 0;
2806 while(sigdrop && (loops < totalsbaruns || totalsbaruns == -1)
2807 && (blockred <= blockedreductions))
2808 {
2809 loops++;
2810 if(loops == 1)
2811 sigdrop = FALSE;
2812 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2813 BOOLEAN delete_w=(w==NULL);
2814 kStrategy strat=new skStrategy;
2815 strat->sbaEnterS = sbaEnterS;
2816 strat->sigdrop = sigdrop;
2817 #if 0
2818 strat->blockred = blockred;
2819 #else
2820 strat->blockred = 0;
2821 #endif
2822 strat->blockredmax = blockedreductions;
2823 //printf("\nsbaEnterS beginning = %i\n",strat->sbaEnterS);
2824 //printf("\nsigdrop beginning = %i\n",strat->sigdrop);
2825 strat->sbaOrder = sbaOrder;
2826 if (arri!=0)
2827 {
2828 strat->rewCrit1 = arriRewDummy;
2829 strat->rewCrit2 = arriRewCriterion;
2831 }
2832 else
2833 {
2837 }
2838
2840 strat->syzComp = syzComp;
2841 if (TEST_OPT_SB_1)
2843 strat->newIdeal = newIdeal;
2845 strat->LazyPass=20;
2846 else
2847 strat->LazyPass=2;
2848 strat->LazyDegree = 1;
2852 strat->ak = 0;
2853 if (id_IsModule(F,currRing)) strat->ak = id_RankFreeModule(F,currRing);
2854 strat->kModW=kModW=NULL;
2855 strat->kHomW=kHomW=NULL;
2856 if (vw != NULL)
2857 {
2858 currRing->pLexOrder=FALSE;
2859 strat->kHomW=kHomW=vw;
2860 strat->pOrigFDeg = currRing->pFDeg;
2861 strat->pOrigLDeg = currRing->pLDeg;
2863 toReset = TRUE;
2864 }
2865 if (h==testHomog)
2866 {
2867 if (strat->ak == 0)
2868 {
2869 h = (tHomog)idHomIdeal(F,Q);
2870 w=NULL;
2871 }
2872 else if (!TEST_OPT_DEGBOUND)
2873 {
2874 if (w!=NULL)
2875 h = (tHomog)idHomModule(F,Q,w);
2876 else
2877 h = (tHomog)idHomIdeal(F,Q);
2878 }
2879 }
2880 currRing->pLexOrder=b;
2881 if (h==isHomog)
2882 {
2883 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2884 {
2885 strat->kModW = kModW = *w;
2886 if (vw == NULL)
2887 {
2888 strat->pOrigFDeg = currRing->pFDeg;
2889 strat->pOrigLDeg = currRing->pLDeg;
2891 toReset = TRUE;
2892 }
2893 }
2894 currRing->pLexOrder = TRUE;
2895 if (hilb==NULL) strat->LazyPass*=2;
2896 }
2897 strat->homog=h;
2898 #ifdef KDEBUG
2899 idTest(F);
2900 if(Q != NULL)
2901 idTest(Q);
2902 #endif
2903 #ifdef HAVE_PLURAL
2905 {
2906 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2907 strat->no_prod_crit = ! bIsSCA;
2908 if (w!=NULL)
2909 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2910 else
2911 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2912 }
2913 else
2914 #endif
2915 {
2917 {
2918 if (w!=NULL)
2919 r=mora(F,Q,*w,hilb,strat);
2920 else
2921 r=mora(F,Q,NULL,hilb,strat);
2922 }
2923 else
2924 {
2925 if (w!=NULL)
2926 r=sba(r,Q,*w,hilb,strat);
2927 else
2928 {
2929 r=sba(r,Q,NULL,hilb,strat);
2930 }
2931 }
2932 }
2933 #ifdef KDEBUG
2934 idTest(r);
2935 #endif
2936 if (toReset)
2937 {
2938 kModW = NULL;
2940 }
2941 currRing->pLexOrder = b;
2942 //Print("%d reductions canceled \n",strat->cel);
2943 sigdrop = strat->sigdrop;
2944 sbaEnterS = strat->sbaEnterS;
2945 blockred = strat->blockred;
2946 delete(strat);
2947 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2948 }
2949 // Go to std
2950 if(sigdrop || blockred > blockedreductions)
2951 {
2952 r = kStd2(r, Q, h, w, hilb, syzComp, newIdeal, vw);
2953 }
2954 return r;
2955 }
2956}
bool sigdrop
Definition kutil.h:359
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition kutil.h:292
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:294
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:296
int blockred
Definition kutil.h:364
unsigned sbaOrder
Definition kutil.h:317
int blockredmax
Definition kutil.h:365
int newIdeal
Definition kutil.h:357
char z2homog
Definition kutil.h:373
char no_prod_crit
Definition kutil.h:393
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition kutil.h:291
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:295
int sbaEnterS
Definition kutil.h:362
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 bigintmat *hilb, kStrategy strat, const ring r)
Definition nc.h:27
long kHomModDeg(poly p, const ring r)
Definition kstd1.cc:2417
ideal mora(ideal F, ideal Q, intvec *w, bigintmat *hilb, kStrategy strat)
Definition kstd1.cc:1878
ideal sba(ideal F0, ideal Q, intvec *w, bigintmat *hilb, kStrategy strat)
Definition kstd2.cc:2982
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int)
Definition kutil.cc:6650
BOOLEAN arriRewCriterion(poly, unsigned long, poly, kStrategy strat, int start=0)
Definition kutil.cc:6625
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition kutil.cc:1946
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly, kStrategy strat, int start=0)
Definition kutil.cc:6566
void chainCritOpt_1(poly, int, kStrategy strat)
Definition kutil.cc:3452
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition kutil.cc:3211
#define TEST_OPT_SB_1
Definition options.h:121

◆ kStd()

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

generic interface to GB/SB computations

Definition at line 2654 of file kstd1.cc.

2656{
2657 bigintmat *hh=iv2biv(hilb,coeffs_BIGINT);
2658 ideal res=kStd2(F,Q,h,w,hh,syzComp,newIdeal,vw,sp);
2659 if (hh!=NULL) delete hh;
2660 return res;
2661}

◆ kStd2()

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

generic interface to GB/SB computations, large hilbert vectors

rIsLPRing already tested above

Definition at line 2602 of file kstd1.cc.

2604{
2605 if(idIs0(F))
2606 return idInit(1,F->rank);
2607
2608 if(idIs0(Q)) Q=NULL;
2609#ifdef HAVE_SHIFTBBA
2610 if(rIsLPRing(currRing)) return kStdShift(F, Q, h, w, hilb, syzComp, newIdeal, vw, FALSE);
2611#endif
2612
2613 if ((hilb==NULL)
2614 && (vw==NULL)
2615 && (newIdeal==0)
2616 && (sp==NULL)
2617 && (IDELEMS(F)>1)
2618 && (!TEST_OPT_SB_1)
2619 && (currRing->ppNoether==NULL)
2620 && !rIsPluralRing(currRing) /*!rIsLPRing already tested above*/
2621 && (!id_IsModule(F,currRing)))
2622 {
2623 /* test HC precomputation*/
2627 && (!idIsMonomial(F)))
2628 {
2629 currRing->ppNoether=kTryHC(F,Q);
2630 ideal res=kStd_internal(F,Q,h,w,hilb,syzComp,newIdeal,vw,sp);
2631 if (currRing->ppNoether!=NULL) pLmDelete(currRing->ppNoether);
2632 currRing->ppNoether=NULL;
2633 return res;
2634 }
2635 /* test hilbstd */
2638 && (!TEST_OPT_RETURN_SB)
2639 && (currRing->LexOrder
2641 && (!idIsMonomial(F)))
2642 {
2643 ideal result=kTryHilbstd(F,Q);
2644 //ideal result=kTryHilbstd_par(F,Q,h,w);
2645 if (result!=NULL)
2646 {
2647 return result;
2648 }
2649 }
2650 }
2651 return kStd_internal(F,Q,h,w,hilb,syzComp,newIdeal,vw,sp);
2652}
ideal kStd_internal(ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
pure GB/SB computations
Definition kstd1.cc:2430
ideal kStdShift(ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, BOOLEAN rightGB)
Definition kstd1.cc:2959
poly kTryHC(ideal F, ideal Q)
Definition kstdhelper.cc:33
ideal kTryHilbstd(ideal F, ideal Q)
BOOLEAN rHasBlockOrder(const ring r)
Definition ring.cc:1923
BOOLEAN rOrd_is_Ds(const ring r)
Definition ring.cc:2075
BOOLEAN rOrd_is_ds(const ring r)
Definition ring.cc:2065
static BOOLEAN rHasGlobalOrdering(const ring r)
Definition ring.h:768
static BOOLEAN rIsLPRing(const ring r)
Definition ring.h:417
static BOOLEAN rField_is_Q(const ring r)
Definition ring.h:512
BOOLEAN idIsMonomial(ideal h)
returns true if h is generated by monomials

◆ kStd_internal()

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

pure GB/SB computations

Definition at line 2430 of file kstd1.cc.

2432{
2433 assume(!idIs0(F));
2434 assume((Q==NULL)||(!idIs0(Q)));
2435
2436 kStrategy strat=new skStrategy;
2437
2438 ideal r;
2439 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2440 BOOLEAN delete_w=(w==NULL);
2441
2442 strat->s_poly=sp;
2444 strat->syzComp = syzComp;
2445 if (TEST_OPT_SB_1
2447 )
2448 strat->newIdeal = newIdeal;
2450 strat->LazyPass=20;
2451 else
2452 strat->LazyPass=2;
2453 strat->LazyDegree = 1;
2454 strat->ak = 0;
2455 if (id_IsModule(F,currRing)) strat->ak = id_RankFreeModule(F,currRing);
2456 strat->kModW=kModW=NULL;
2457 strat->kHomW=kHomW=NULL;
2458 if (vw != NULL)
2459 {
2460 currRing->pLexOrder=FALSE;
2461 strat->kHomW=kHomW=vw;
2462 strat->pOrigFDeg = currRing->pFDeg;
2463 strat->pOrigLDeg = currRing->pLDeg;
2465 toReset = TRUE;
2466 }
2467 if (h==testHomog)
2468 {
2469 if (strat->ak == 0)
2470 {
2471 h = (tHomog)idHomIdeal(F,Q);
2472 w=NULL;
2473 }
2474 else if (!TEST_OPT_DEGBOUND)
2475 {
2476 if (w!=NULL)
2477 h = (tHomog)idHomModule(F,Q,w);
2478 else
2479 h = (tHomog)idHomIdeal(F,Q);
2480 }
2481 }
2482 currRing->pLexOrder=b;
2483 if (h==isHomog)
2484 {
2485 if (strat->ak > 0 && (w!=NULL) && (*w!=NULL))
2486 {
2487 strat->kModW = kModW = *w;
2488 if (vw == NULL)
2489 {
2490 strat->pOrigFDeg = currRing->pFDeg;
2491 strat->pOrigLDeg = currRing->pLDeg;
2493 toReset = TRUE;
2494 }
2495 }
2496 currRing->pLexOrder = TRUE;
2497 if (hilb==NULL) strat->LazyPass*=2;
2498 }
2499 strat->homog=h;
2500#ifdef KDEBUG
2501 idTest(F);
2502 if (Q!=NULL) idTest(Q);
2503#endif
2504#ifdef HAVE_PLURAL
2506 {
2507 const BOOLEAN bIsSCA = rIsSCA(currRing) && strat->z2homog; // for Z_2 prod-crit
2508 strat->no_prod_crit = ! bIsSCA;
2509 if (w!=NULL)
2510 r = nc_GB(F, Q, *w, hilb, strat, currRing);
2511 else
2512 r = nc_GB(F, Q, NULL, hilb, strat, currRing);
2513 }
2514 else
2515#endif
2516 {
2517 #if PRE_INTEGER_CHECK
2518 //the preinteger check strategy is not for modules
2519 if(nCoeff_is_Z(currRing->cf) && strat->ak <= 0)
2520 {
2521 ideal FCopy = idCopy(F);
2522 poly pFmon = preIntegerCheck(FCopy, Q);
2523 if(pFmon != NULL)
2524 {
2525 idInsertPoly(FCopy, pFmon);
2526 strat->kModW=kModW=NULL;
2527 if (h==testHomog)
2528 {
2529 h = (tHomog)idHomIdeal(FCopy,Q);
2530 w=NULL;
2531 }
2532 currRing->pLexOrder=b;
2533 if (h==isHomog)
2534 {
2535 if ((w!=NULL) && (*w!=NULL))
2536 {
2537 strat->kModW = kModW = *w;
2538 if (vw == NULL)
2539 {
2540 strat->pOrigFDeg = currRing->pFDeg;
2541 strat->pOrigLDeg = currRing->pLDeg;
2543 toReset = TRUE;
2544 }
2545 }
2546 currRing->pLexOrder = TRUE;
2547 if (hilb==NULL) strat->LazyPass*=2;
2548 }
2549 strat->homog=h;
2550 }
2551 omTestMemory(1);
2552 if(w == NULL)
2553 {
2555 r=mora(FCopy,Q,NULL,hilb,strat);
2556 else
2557 r=bba(FCopy,Q,NULL,hilb,strat);
2558 }
2559 else
2560 {
2562 r=mora(FCopy,Q,*w,hilb,strat);
2563 else
2564 r=bba(FCopy,Q,*w,hilb,strat);
2565 }
2566 idDelete(&FCopy);
2567 }
2568 else
2569 #endif
2570 {
2571 if(w==NULL)
2572 {
2574 r=mora(F,Q,NULL,hilb,strat);
2575 else
2576 r=bba(F,Q,NULL,hilb,strat);
2577 }
2578 else
2579 {
2581 r=mora(F,Q,*w,hilb,strat);
2582 else
2583 r=bba(F,Q,*w,hilb,strat);
2584 }
2585 }
2586 }
2587#ifdef KDEBUG
2588 idTest(r);
2589#endif
2590 if (toReset)
2591 {
2592 kModW = NULL;
2594 }
2595 currRing->pLexOrder = b;
2596//Print("%d reductions canceled \n",strat->cel);
2597 delete(strat);
2598 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
2599 return r;
2600}
s_poly_proc_t s_poly
Definition kutil.h:301
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
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:10540
omError_t omTestMemory(int check_level)
Definition omDebug.c:94

◆ kStdShift()

ideal kStdShift ( ideal F,
ideal Q,
tHomog h,
intvec ** mw,
bigintmat * hilb = NULL,
int syzComp = 0,
int newIdeal = 0,
intvec * vw = NULL,
BOOLEAN rightGB = FALSE )

Definition at line 2959 of file kstd1.cc.

2961{
2963 assume(idIsInV(F));
2965 {
2966 /* error: no local ord yet with shifts */
2967 WerrorS("No local ordering possible for shift algebra");
2968 return(NULL);
2969 }
2970 ideal r;
2971 BOOLEAN b=currRing->pLexOrder,toReset=FALSE;
2972 BOOLEAN delete_w=(w==NULL);
2973 kStrategy strat=new skStrategy;
2974
2975 strat->rightGB = rightGB;
2976
2978 strat->syzComp = syzComp;
2979 if (TEST_OPT_SB_1)
2981 strat->newIdeal = newIdeal;
2983 strat->LazyPass=20;
2984 else
2985 strat->LazyPass=2;
2986 strat->LazyDegree = 1;
2987 strat->ak = 0;
2988 if (id_IsModule(F,currRing)) 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
3036 /* global ordering */
3037 if (w!=NULL)
3038 r=bbaShift(F,Q,*w,hilb,strat);
3039 else
3040 r=bbaShift(F,Q,NULL,hilb,strat);
3041#ifdef KDEBUG
3042 idTest(r);
3043#endif
3044 if (toReset)
3045 {
3046 kModW = NULL;
3048 }
3049 currRing->pLexOrder = b;
3050//Print("%d reductions canceled \n",strat->cel);
3051 delete(strat);
3052 if ((delete_w)&&(w!=NULL)&&(*w!=NULL)) delete *w;
3053 assume(idIsInV(r));
3054 return r;
3055}
char rightGB
Definition kutil.h:368
ideal bbaShift(ideal F, ideal Q, intvec *w, bigintmat *hilb, kStrategy strat)
Definition kstd2.cc:4594
#define idIsInV(I)
Definition shiftop.h:49

◆ kTryHC()

poly kTryHC ( ideal F,
ideal Q )

Definition at line 33 of file kstdhelper.cc.

34{
35 if (Q!=NULL)
36 return NULL;
37 int prim=kFindLuckyPrime(F,Q);
38 if (TEST_OPT_PROT) Print("try HC in ring over ZZ/%d\n",prim);
39 // create Zp_ring
40 ring save_ring=currRing;
41 ring Zp_ring=rCopy0(save_ring);
42 nKillChar(Zp_ring->cf);
43 Zp_ring->cf=nInitChar(n_Zp, (void*)(long)prim);
44 rComplete(Zp_ring);
45 // map data
46 rChangeCurrRing(Zp_ring);
47 nMapFunc nMap=n_SetMap(save_ring->cf,Zp_ring->cf);
48 if (nMap==NULL) return NULL;
49 ideal FF=id_PermIdeal(F,1,IDELEMS(F),NULL,save_ring,Zp_ring,nMap,NULL,0,0);
50 ideal QQ=NULL;
51 if (Q!=NULL) QQ=id_PermIdeal(Q,1,IDELEMS(Q),NULL,save_ring,Zp_ring,nMap,NULL,0,0);
52 // call std
53 kStrategy strat=new skStrategy;
54 strat->LazyPass=20;
55 strat->LazyDegree = 1;
56 strat->kModW=kModW=NULL;
57 strat->kHomW=kHomW=NULL;
58 strat->homog = (tHomog)idHomIdeal(F,Q);
59 ideal res=mora(FF,QQ,NULL,NULL,strat);
60 // clean
61 idDelete(&FF);
62 poly HC=NULL;
63 if (strat->kNoether!=NULL) scComputeHC(res,QQ,0,HC);
64 delete strat;
65 if (QQ!=NULL) idDelete(&QQ);
66 idDelete(&res);
67 // map back
68 rChangeCurrRing(save_ring);
69 if (HC!=NULL)
70 {
71 //p_IncrExp(HC,Zp_ring->N,Zp_ring);
72 for (int i=rVar(Zp_ring)-1; i>0; i--)
73 {
74 if (pGetExp(HC, i) > 0) pDecrExp(HC,i);
75 }
76 p_Setm(HC,Zp_ring);
77 if (TEST_OPT_PROT) Print("HC(%ld) found\n",pTotaldegree(HC));
78 pSetCoeff0(HC,nInit(1));
79 }
80 else
81 {
82 if (TEST_OPT_PROT) PrintS("HC not found\n");
83 }
84 rDelete(Zp_ring);
85 return HC;
86}
@ n_Zp
\F{p < 2^31}
Definition coeffs.h:29
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition coeffs.h:701
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition numbers.cc:406
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition coeffs.h:80
void nKillChar(coeffs r)
undo all initialisations
Definition numbers.cc:556
void scComputeHC(ideal S, ideal Q, int ak, poly &hEdge)
Definition hdegree.cc:1074
static int kFindLuckyPrime(ideal F, ideal Q)
Definition kstdhelper.cc:26
#define pSetCoeff0(p, n)
Definition monomials.h:59
#define nInit(i)
Definition numbers.h:24
static long pTotaldegree(poly p)
Definition polys.h:283
#define pGetExp(p, i)
Exponent.
Definition polys.h:42
#define pDecrExp(p, i)
Definition polys.h:45
BOOLEAN rComplete(ring r, int force)
this needs to be called whenever a new ring is created: new fields in ring are created (like VarOffse...
Definition ring.cc:3526
ring rCopy0(const ring r, BOOLEAN copy_qideal, BOOLEAN copy_ordering)
Definition ring.cc:1426
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition ring.h:598
ideal id_PermIdeal(ideal I, int R, int C, const int *perm, const ring src, const ring dst, nMapFunc nMap, const int *par_perm, int P, BOOLEAN use_mult)
mapping ideals/matrices to other rings

◆ kTryHilbstd()

ideal kTryHilbstd ( ideal F,
ideal Q )

Definition at line 270 of file kstdhelper.cc.

271{
272 if(!TEST_V_PURE_GB)
273 {
275 if (h==(tHomog)TRUE) return kTryHilbstd_homog(F,Q);
276 if (h==(tHomog)FALSE) return kTryHilbstd_nonhomog(F,Q);
277 }
278 return NULL;
279}
static ideal kTryHilbstd_nonhomog(ideal F, ideal Q)
static ideal kTryHilbstd_homog(ideal F, ideal Q)
Definition kstdhelper.cc:90
#define TEST_V_PURE_GB
Definition options.h:137
BOOLEAN id_HomIdealDP(ideal id, ideal Q, const ring r)

◆ kTryHilbstd_par()

ideal kTryHilbstd_par ( ideal F,
ideal Q,
tHomog h,
intvec ** mw )

Definition at line 281 of file kstdhelper.cc.

282{
283#if 0
284 if(!TEST_V_PURE_GB)
285 {
286 int cp_std[2];
287 int cp_hstd[2];
288 int err1=pipe(cp_std);// [0] is read , [1] is write
289 int err2=pipe(cp_hstd);
290 if (err1||err2)
291 {
292 Werror("pipe failed with %d\n",errno);
293 si_close(cp_std[0]);
294 si_close(cp_std[1]);
295 si_close(cp_hstd[0]);
296 si_close(cp_hstd[1]);
297 return NULL;
298 }
299 pid_t pid_std=fork();
300 if (pid_std==0) /*child std*/
301 {
303 si_close(cp_std[0]);
304 si_close(cp_hstd[0]);
305 si_close(cp_hstd[1]);
306 ssiInfo d;
307 memset(&d,0,sizeof(d));
308 d.f_write=fdopen(cp_std[1],"w");
309 d.fd_write=cp_std[1];
310 d.r=currRing;
312 ideal res=kStd_internal(F,Q,h,mw);
314 fclose(d.f_write);
315 _exit(0);
316 }
317 pid_t pid_hstd=fork();
318 if (pid_hstd==0) /*child hstd*/
319 {
321 si_close(cp_hstd[0]);
322 si_close(cp_std[0]);
323 si_close(cp_std[1]);
324 ssiInfo d;
325 memset(&d,0,sizeof(d));
326 d.f_write=fdopen(cp_hstd[1],"w");
327 d.fd_write=cp_hstd[1];
328 d.r=currRing;
329
331 ideal res=kTryHilbstd(F,Q);
332 if (res!=NULL)
333 {
335 }
336 fclose(d.f_write);
337 _exit(0);
338 }
339 /*parent*/
340 si_close(cp_std[1]);
341 si_close(cp_hstd[1]);
342 #ifdef HAVE_POLL
343 pollfd pfd[2];
344 pfd[0].fd=cp_std[0];
345 pfd[0].events=POLLIN;
346 pfd[1].fd=cp_hstd[0];
347 pfd[1].events=POLLIN;
348 int s=si_poll(pfd,2,-1); // wait infinite
349 ideal res;
350 ssiInfo d;
351 memset(&d,0,sizeof(d));
352 d.r=currRing;
353 if (s==1) //std
354 {
355 d.f_read=s_open(cp_std[0]);
356 d.fd_read=cp_std[0];
357 res=ssiReadIdeal(&d);
358 si_close(cp_hstd[0]);
359 s_close(d.f_read);
360 si_close(cp_std[0]);
361 kill(pid_hstd,SIGTERM);
362 si_waitpid(pid_std,NULL,0);
363 si_waitpid(pid_hstd,NULL,0);
364 }
365 else if(s==2)
366 {
367 d.f_read=s_open(cp_hstd[0]);
368 d.fd_read=cp_hstd[0];
369 res=ssiReadIdeal(&d);
370 si_close(cp_std[0]);
371 s_close(d.f_read);
372 si_close(cp_hstd[0]);
373 kill(pid_std,SIGTERM);
374 si_waitpid(pid_hstd,NULL,0);
375 si_waitpid(pid_std,NULL,0);
376 }
377 return res;
378 #endif
379 }
380#endif
381 return NULL;
382}
si_hdl_typ si_set_signal(int sig, si_hdl_typ signal_handler)
meta function for binding a signal to an handler
Definition cntrlc.cc:121
void sig_term_hdl_child(int)
Definition cntrlc.cc:86
const CanonicalForm int s
Definition facAbsFact.cc:51
@ IDEAL_CMD
Definition grammar.cc:285
ideal kTryHilbstd(ideal F, ideal Q)
VAR unsigned si_opt_2
Definition options.c:6
#define V_PURE_GB
Definition options.h:71
s_buff s_open(int fd)
Definition s_buff.cc:32
int s_close(s_buff &F)
Definition s_buff.cc:46
int fd_write
Definition s_buff.h:26
s_buff f_read
Definition s_buff.h:22
FILE * f_write
Definition s_buff.h:23
ring r
Definition s_buff.h:24
int fd_read
Definition s_buff.h:26

◆ kVerify()

BOOLEAN kVerify ( ideal F,
ideal Q )

◆ mora()

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

Definition at line 1878 of file kstd1.cc.

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

◆ rightgb()

ideal rightgb ( ideal F,
const ideal Q )

Definition at line 4958 of file kstd2.cc.

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

◆ stdred()

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

Variable Documentation

◆ kHomW

Definition at line 95 of file kstd1.h.

◆ kModW

Definition at line 94 of file kstd1.h.

◆ kOptions

EXTERN_VAR BITSET kOptions

Definition at line 72 of file kstd1.h.

◆ Kstd1_deg

EXTERN_VAR int Kstd1_deg

Definition at line 70 of file kstd1.h.

◆ Kstd1_mu

EXTERN_VAR int Kstd1_mu

Definition at line 70 of file kstd1.h.

◆ validOpts

EXTERN_VAR BITSET validOpts

Definition at line 74 of file kstd1.h.