My Project
kutil.h
Go to the documentation of this file.
1#ifndef KUTIL_H
2#define KUTIL_H
3/****************************************
4* Computer Algebra System SINGULAR *
5****************************************/
6/*
7* ABSTRACT: kernel: utils for kStd
8*/
9
10
11#include <string.h>
12
13#include "omalloc/omalloc.h"
14#ifdef HAVE_OMALLOC
16#endif
17
18#include "misc/mylimits.h"
19
20#include "kernel/polys.h"
22
23#include "kernel/structs.h"
24#include "kernel/GBEngine/kstd1.h" /* for s_poly_proc_t */
25
26// define if tailrings should be used
27#define HAVE_TAIL_RING
28
29#define setmax 128
30#define setmaxL ((4096-12)/sizeof(LObject))
31#define setmaxLinc ((4096)/sizeof(LObject))
32
33#define setmaxT ((4096-12)/sizeof(TObject))
34#define setmaxTinc ((4096)/sizeof(TObject))
35
36#define RED_CANONICALIZE 200
37#define REDNF_CANONICALIZE 60
38#define REDTAIL_CANONICALIZE 100
39
40// if you want std computations as in Singular version < 2:
41// This disables RedThrough, tailReductions against T (bba),
42// sets posInT = posInT15 (bba, strat->honey), and enables redFirst with LDeg
43// NOTE: can be achieved with option(oldStd)
44
45#undef NO_KINLINE
46#if !defined(KDEBUG) && !defined(NO_INLINE)
47#define KINLINE inline
48#else
49#define KINLINE
50#define NO_KINLINE 1
51#endif
52
53typedef int* intset;
56
57typedef class sTObject TObject;
58typedef class sLObject LObject;
59typedef TObject * TSet;
60typedef LObject * LSet;
61
64
67
69{
70public:
71 unsigned long sevSig;
72 poly sig; // the signature of the element
73 poly p; // Lm(p) \in currRing Tail(p) \in tailRing
74 poly t_p; // t_p \in tailRing: as monomials Lm(t_p) == Lm(p)
75 poly max_exp; // p_GetMaxExpP(pNext(p))
77 long FDeg; // pFDeg(p)
78 int ecart,
79 length, // as of pLDeg
80 pLength, // either == 0, or == pLength(p)
81 i_r; // index of TObject in R set, or -1 if not in T
82
83#ifdef HAVE_SHIFTBBA
84 int shift;
85#endif
86
87 /*BOOLEAN*/ char is_normalized; // true, if pNorm was called on p, false otherwise
88 // used in incremental sba() with F5C:
89 // we know some of the redundant elements in
90 // strat->T beforehand, so we can just discard
91 // them and do not need to consider them in the
92 // interreduction process
93 /*BOOLEAN*/ char is_redundant;
94 // used in sba's sig-safe reduction:
95 // sometimes we already know that a reducer
96 // is sig-safe, so no need for a real
97 // sig-safeness check
98 /*BOOLEAN*/ char is_sigsafe;
99
100
101#ifdef HAVE_PLURAL
102 /*BOOLEAN*/ char is_special; // true, it is a new special S-poly (e.g. for SCA)
103#endif
104
105 // initialization
106 KINLINE void Init(ring r = currRing);
108 KINLINE sTObject(poly p, ring tailRing = currRing);
109 KINLINE sTObject(poly p, ring c_r, ring tailRing);
111
112 KINLINE void Set(ring r=currRing);
113 KINLINE void Set(poly p_in, ring r=currRing);
114 KINLINE void Set(poly p_in, ring c_r, ring t_r);
115
116 // Frees the polys of T
117 KINLINE void Delete();
118 // Sets polys to NULL
119 KINLINE void Clear();
120 // makes a copy of the poly of T
121 KINLINE void Copy();
122
123 // ring-dependent Lm access: these might result in allocation of monomials
124 KINLINE poly GetLmCurrRing();
125 KINLINE poly GetLmTailRing();
126 KINLINE poly GetLm(ring r);
127 // this returns Lm and ring r (preferably from tailRing), but does not
128 // allocate a new poly
129 KINLINE void GetLm(poly &p, ring &r) const;
130
131#ifdef OLIVER_PRIVAT_LT
132 // routines for calc. with rings
133 KINLINE poly GetLtCurrRing();
134 KINLINE poly GetLtTailRing();
135 KINLINE poly GetLt(ring r);
136 KINLINE void GetLt(poly &p, ring &r) const;
137#endif
138
139 KINLINE BOOLEAN IsNull() const;
140
141 KINLINE int GetpLength();
142
143 // makes sure that T.p exists
144 KINLINE void SetLmCurrRing();
145
146 // Iterations
147 // simply get the next monomial
148 KINLINE poly Next();
150
151 // deg stuff
152 // compute pTotalDegree
153 KINLINE long pTotalDeg() const;
154 // computes pFDeg
155 KINLINE long pFDeg() const;
156 // computes and sets FDeg
157 KINLINE long SetpFDeg();
158 // gets stored FDeg
159 KINLINE long GetpFDeg() const;
160
161 // computes pLDeg
162 KINLINE long pLDeg();
163 // sets length, FDeg, returns LDeg
165
166 // arithmetic
167 KINLINE void Mult_nn(number n);
168 KINLINE void ShallowCopyDelete(ring new_tailRing, omBin new_tailBin,
169 pShallowCopyDeleteProc p_shallow_copy_delete,
170 BOOLEAN set_max = TRUE);
171 // manipulations
172 KINLINE void pNorm();
173 KINLINE void pCleardenom();
174 KINLINE void pContent();
175
176#ifdef KDEBUG
177 void wrp();
178#endif
179};
180
182
183class sLObject : public sTObject
184{
185
186public:
187 unsigned long sev;
188 poly p1,p2; /*- the pair p comes from,
189 lm(pi) in currRing, tail(pi) in tailring -*/
190
191 poly lcm; /*- the lcm of p1,p2 -*/
193 int i_r1, i_r2;
194 unsigned checked; // this is the index of S up to which
195 // the corresponding LObject was already checked in
196 // critical pair creation => when entering the
197 // reduction process it is enough to start a second
198 // rewritten criterion check from checked+1 onwards
200 // NOTE: If prod_crit = TRUE then the corresponding pair is
201 // detected by Buchberger's Product Criterion and can be
202 // deleted
203
204 // initialization
205 KINLINE void Init(ring tailRing = currRing);
207 KINLINE sLObject(poly p, ring tailRing = currRing);
208 KINLINE sLObject(poly p, ring c_r, ring tailRing);
209
210 // Frees the polys of L
211 KINLINE void Delete();
212 KINLINE void Clear();
213
214 // Iterations
217
218 // spoly related things
219 // preparation for reduction if not spoly
220 KINLINE void PrepareRed(BOOLEAN use_bucket);
221 KINLINE void SetLmTail(poly lm, poly new_p, int length,
222 int use_bucket, ring r);
223 KINLINE void Tail_Minus_mm_Mult_qq(poly m, poly qq, int lq, poly spNoether);
224 KINLINE void Tail_Mult_nn(number n);
225 // deletes bucket, makes sure that p and t_p exists
226 KINLINE poly GetP(omBin lmBin = (omBin)NULL);
227 // similar, except that only t_p exists
228 KINLINE poly GetTP();
229
230 // does not delete bucket, just canonicalizes it
231 // returned poly is such that Lm(p) \in currRing, Tail(p) \in tailRing
232 KINLINE void CanonicalizeP();
233
234 // makes a copy of the poly of L
235 KINLINE void Copy();
236
237 KINLINE int GetpLength();
238 KINLINE long pLDeg(BOOLEAN use_last);
239 KINLINE long pLDeg();
240 KINLINE int SetLength(BOOLEAN lengt_pLength = FALSE);
243
244 // returns minimal component of p
245 KINLINE long MinComp();
246 // returns component of p
247 KINLINE long Comp();
248
249 KINLINE void ShallowCopyDelete(ring new_tailRing,
250 pShallowCopyDeleteProc p_shallow_copy_delete);
251
252 // sets sev
254
255 // enable assignment from TObject
257
258 // get T's corresponding to p1, p2: they might return NULL
259 KINLINE TObject* T_1(const skStrategy* strat);
260 KINLINE TObject* T_2(const skStrategy* strat);
261 KINLINE void T_1_2(const skStrategy* strat,
262 TObject* &T_1, TObject* &T_2);
263
264 // simplify coefficients
265 KINLINE void Normalize();
266 KINLINE void HeadNormalize();
267};
268
269
271
273#ifdef HAVE_OMALLOC
274 : public omallocClass
275#endif
276{
277public:
279 int (*red)(LObject * L,kStrategy strat);
280 int (*red2)(LObject * L,kStrategy strat);
281 void (*initEcart)(TObject * L);
282 int (*posInT)(const TSet T,const int tl,LObject &h);
283 int (*posInLSba)(const LSet set, const int length,
284 LObject* L,const kStrategy strat);
285 int (*posInL)(const LSet set, const int length,
286 LObject* L,const kStrategy strat);
287 void (*enterS)(LObject &h, int pos,kStrategy strat, int atR/* =-1*/ );
288 void (*initEcartPair)(LObject * h, poly f, poly g, int ecartF, int ecartG);
289 int (*posInLOld)(const LSet Ls,const int Ll,
290 LObject* Lo,const kStrategy strat);
291 void (*enterOnePair) (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR /*= -1*/);
292 void (*chainCrit) (poly p,int ecart,kStrategy strat);
293 BOOLEAN (*syzCrit) (poly sig, unsigned long not_sevSig, kStrategy strat);
294 BOOLEAN (*rewCrit1) (poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start /*= 0*/);
295 BOOLEAN (*rewCrit2) (poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start /*= 0*/);
296 BOOLEAN (*rewCrit3) (poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start /*= 0*/);
302
304 ideal Shdl;
305 ideal D; /*V(S) is in D(D)*/
306 ideal M; /*set of minimal generators*/
311 intset fromS; // from which S[i] S[j] comes from
312 // this is important for signature-based
313 // algorithms
314 intset syzIdx;// index in the syz array at which the first
315 // syzygy of component i comes up
316 // important for signature-based algorithms
317 unsigned sbaOrder;
321 wlen_set lenSw; /* for tgb.ccc */
323 unsigned long* sevS;
324 unsigned long* sevSyz;
325 unsigned long* sevSig;
326 unsigned long* sevT;
330 poly kHEdge;
332 poly t_kHEdge; // same polys in tailring
333 KINLINE poly kNoetherTail();
336 BOOLEAN * pairtest;/*used for enterOnePair*/
337 poly tail;
340 // procedure for ShalloCopy from tailRing to currRing
342 // pointers to Tobjects R[i] is ith Tobject which is generated
344 // S_2_R[i] yields Tobject which corresponds to S[i]
345 int* S_2_R;
349 int nr;
350 int cp,c3;
351 int sl,mu;
353 int tl,tmax;
354 int Ll,Lmax;
355 int Bl,Bmax;
358 int HCord;
361 int minim;
362 #ifdef HAVE_RINGS
363 bool sigdrop; //This is used to check sigdrop in sba over Z
364 int nrsyzcrit; // counts how many pairs are deleted by SyzCrit
365 int nrrewcrit; // counts how many pairs are deleted by FaugereRewCrit
366 int sbaEnterS; // sba over Z strategy: if sigdrop element has _*gen(sbaEnterS+1), then
367 // add directly sbaEnterS elements into S
368 int blockred; // counter for blocked reductions in redSig
370 #endif
371 #ifdef HAVE_SHIFTBBA
372 int cv; // in shift bases: counting V criterion
373 /*BOOLEAN*/ char rightGB;
374 #endif
375 /*BOOLEAN*/ char interpt;
376 /*BOOLEAN*/ char homog;
377#ifdef HAVE_PLURAL
378 /*BOOLEAN*/ char z2homog; // Z_2 - homogeneous input allows product criterion in commutative and SCA cases!
379#endif
380 /*BOOLEAN*/ char kHEdgeFound;
381 /*BOOLEAN*/ char honey,sugarCrit;
382 /*BOOLEAN*/ char Gebauer,noTailReduction;
383 /*BOOLEAN*/ char fromT;
384 /*BOOLEAN*/ char noetherSet;
385 /*BOOLEAN*/ char update;
386 /*BOOLEAN*/ char posInLOldFlag;
387 /*BOOLEAN*/ char use_buckets;
388 // if set, pLDeg(p, l) == (pFDeg(pLast(p), pLength)
389 /*BOOLEAN*/ char LDegLast;
390 // if set, then L.length == L.pLength
391 /*BOOLEAN*/ char length_pLength;
392 // if set, then posInL does not depend on L.length
393 /*BOOLEAN*/ char posInLDependsOnLength;
394 /*FALSE, if posInL == posInL10*/
395#ifdef HAVE_PLURAL
396 // set this flag to 1 to stop the product criteria
397 // use ALLOW_PROD_CRIT(strat) to test
398 /*BOOLEAN*/ char no_prod_crit;
399#define ALLOW_PROD_CRIT(A) (!(A)->no_prod_crit)
400#else
401#define ALLOW_PROD_CRIT(A) (1)
402#endif
404 char news;
405 char newt;/*used for messageSets*/
409
410 skStrategy();
411 ~skStrategy();
412
413 // return TObject corresponding to S[i]: assume that it exists
414 // i.e. no error checking is done
415 KINLINE TObject* S_2_T(int i);
416 // like S_2_T, except that NULL is returned if it can not be found
417 KINLINE TObject* s_2_t(int i);
418};
419
420void deleteHC(poly *p, int *e, int *l, kStrategy strat);
421void deleteHC(LObject* L, kStrategy strat, BOOLEAN fromNext = FALSE);
422void deleteInS (int i,kStrategy strat);
423void deleteInSSba (int i,kStrategy strat);
424void cleanT (kStrategy strat);
425static inline LSet initL (int nr=setmaxL)
426{ return (LSet)omAlloc(nr*sizeof(LObject)); }
427void deleteInL(LSet set, int *length, int j,kStrategy strat);
428void enterL (LSet *set,int *length, int *LSetmax, LObject p,int at);
429void enterSBba (LObject &p,int atS,kStrategy strat, int atR = -1);
430void enterSBbaShift (LObject &p,int atS,kStrategy strat, int atR = -1);
431void enterSSba (LObject &p,int atS,kStrategy strat, int atR = -1);
432void initEcartPairBba (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
433void initEcartPairMora (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
434int posInS (const kStrategy strat, const int length, const poly p,
435 const int ecart_p);
436int posInSMonFirst (const kStrategy strat, const int length, const poly p);
437int posInIdealMonFirst (const ideal F, const poly p,int start = 0,int end = -1);
438int posInT0 (const TSet set,const int length,LObject &p);
439int posInT1 (const TSet set,const int length,LObject &p);
440int posInT2 (const TSet set,const int length,LObject &p);
441int posInT11 (const TSet set,const int length,LObject &p);
442int posInTSig (const TSet set,const int length,LObject &p);
443int posInT110 (const TSet set,const int length,LObject &p);
444int posInT13 (const TSet set,const int length,LObject &p);
445int posInT15 (const TSet set,const int length,LObject &p);
446int posInT17 (const TSet set,const int length,LObject &p);
447int posInT17_c (const TSet set,const int length,LObject &p);
448int posInT19 (const TSet set,const int length,LObject &p);
449int posInT_EcartpLength(const TSet set,const int length,LObject &p);
450int posInT_EcartFDegpLength(const TSet set,const int length,LObject &p);
451int posInT_FDegpLength(const TSet set,const int length,LObject &p);
452int posInT_pLength(const TSet set,const int length,LObject &p);
453
454#ifdef HAVE_MORE_POS_IN_T
455int posInT_EcartFDegpLength(const TSet set,const int length,LObject &p);
456int posInT_FDegpLength(const TSet set,const int length,LObject &p);
457int posInT_pLength(const TSet set,const int length,LObject &p);
458#endif
459
460
461void reorderS (int* suc,kStrategy strat);
462int posInLF5C (const LSet set, const int length,
463 LObject* L,const kStrategy strat);
464int posInLSig (const LSet set, const int length,
465 LObject* L,const kStrategy strat);
466int posInLSigRing (const LSet set, const int length,
467 LObject* L,const kStrategy strat);
468int posInLRing (const LSet set, const int length,
469 LObject* L,const kStrategy strat);
470int posInSyz (const kStrategy strat, const poly sig);
471int posInL0 (const LSet set, const int length,
472 LObject* L,const kStrategy strat);
473int posInL11 (const LSet set, const int length,
474 LObject* L,const kStrategy strat);
475int posInL11Ring (const LSet set, const int length,
476 LObject* L,const kStrategy strat);
477int posInLF5CRing (const LSet set, int start , const int length,
478 LObject* L,const kStrategy strat);
479int posInL11Ringls (const LSet set, const int length,
480 LObject* L,const kStrategy strat);
481int posInL13 (const LSet set, const int length,
482 LObject* L,const kStrategy strat);
483int posInL15 (const LSet set, const int length,
484 LObject* L,const kStrategy strat);
485int posInL15Ring (const LSet set, const int length,
486 LObject* L,const kStrategy strat);
487int posInL17 (const LSet set, const int length,
488 LObject* L,const kStrategy strat);
489int posInL10 (const LSet set, const int length,
490 LObject* L,const kStrategy strat);
491int posInL10Ring (const LSet set, const int length,
492 LObject* L,const kStrategy strat);
493int posInL110 (const LSet set, const int length,
494 LObject* L,const kStrategy strat);
495KINLINE poly redtailBba (poly p,int end_pos,kStrategy strat,BOOLEAN normalize=FALSE);
496KINLINE poly redtailBbaBound (poly p,int end_pos,kStrategy strat,int bound,BOOLEAN normalize=FALSE);
497#ifdef HAVE_RINGS
498KINLINE poly redtailBba_Ring (poly p,int end_pos,kStrategy strat);
499KINLINE poly redtailBba_Z (poly p,int end_pos,kStrategy strat);
500poly redtailBba_Ring (LObject* L, int end_pos, kStrategy strat );
501poly redtailBba_Z (LObject* L, int end_pos, kStrategy strat );
502void redtailBbaAlsoLC_Z (LObject* L, int end_pos, kStrategy strat );
503#endif
504poly redtailBba (LObject *L, int end_pos,kStrategy strat,
506poly redtailBbaBound (LObject *L, int end_pos,kStrategy strat,int bound,
508poly redtailSba (LObject *L, int end_pos,kStrategy strat,
510poly redtailBba (TObject *T, int end_pos,kStrategy strat);
511poly redtail (poly p,int end_pos,kStrategy strat);
512poly redtail (LObject *L,int end_pos,kStrategy strat);
513poly redNF (poly h,int & max_ind,int nonorm,kStrategy strat);
514int redNF0 (LObject *P,kStrategy strat);
515poly redNFTail (poly h,const int sl,kStrategy strat);
516int redHoney (LObject* h, kStrategy strat);
517int redLiftstd (LObject* h, kStrategy strat);
518#ifdef HAVE_RINGS
519int redRing (LObject* h,kStrategy strat);
520int redRing_Z (LObject* h,kStrategy strat);
521int redRiloc (LObject* h,kStrategy strat);
522void enterExtendedSpoly(poly h,kStrategy strat);
523void enterExtendedSpolySig(poly h,poly hSig,kStrategy strat);
524void superenterpairs (poly h,int k,int ecart,int pos,kStrategy strat, int atR = -1);
525void superenterpairsSig (poly h,poly hSig,int hFrom,int k,int ecart,int pos,kStrategy strat, int atR = -1);
526#endif
527int redLazy (LObject* h,kStrategy strat);
528int redHomog (LObject* h,kStrategy strat);
529int redSig (LObject* h,kStrategy strat);
530int redSigRing (LObject* h,kStrategy strat);
531//adds hSig to be able to check with F5's criteria when entering pairs!
532void enterpairsSig (poly h, poly hSig, int from, int k, int ec, int pos,kStrategy strat, int atR = -1);
533void enterpairs (poly h, int k, int ec, int pos,kStrategy strat, int atR = -1);
535void pairs ();
537void message (int i,int* reduc,int* olddeg,kStrategy strat,int red_result);
538void messageStat (int hilbcount,kStrategy strat);
539void messageStatSBA (int hilbcount,kStrategy strat);
540#ifdef KDEBUG
541void messageSets (kStrategy strat);
542#else
543#define messageSets(s) do {} while (0)
544#endif
545
547void initEcartBBA (TObject* h);
548void initS (ideal F, ideal Q,kStrategy strat);
549void initSL (ideal F, ideal Q,kStrategy strat);
550void initSLSba (ideal F, ideal Q,kStrategy strat);
551/*************************************************
552 * when initializing a new bunch of principal
553 * syzygies at the beginning of a new iteration
554 * step in a signature-based algorithm we
555 * compute ONLY the leading elements of those
556 * syzygies, NOT the whole syzygy
557 * NOTE: this needs to be adjusted for a more
558 * general approach on signature-based algorithms
559 ***********************************************/
560void initSyzRules (kStrategy strat);
561void updateS(BOOLEAN toT,kStrategy strat);
562void enterSyz (LObject &p,kStrategy strat, int atT);
563void enterT (LObject &p,kStrategy strat, int atT = -1);
564void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat);
565#ifdef HAVE_RINGS
566void enterT_strong (LObject &p,kStrategy strat, int atT = -1);
567#endif
568void cancelunit (LObject* p,BOOLEAN inNF=FALSE);
569void HEckeTest (poly pp,kStrategy strat);
570void initBuchMoraCrit(kStrategy strat);
571void initSbaCrit(kStrategy strat);
572void initHilbCrit(ideal F, ideal Q, intvec **hilb,kStrategy strat);
573void initBuchMoraPos(kStrategy strat);
575void initSbaPos(kStrategy strat);
576void initBuchMora (ideal F, ideal Q,kStrategy strat);
577void initSbaBuchMora (ideal F, ideal Q,kStrategy strat);
578void exitBuchMora (kStrategy strat);
579void exitSba (kStrategy strat);
580void updateResult(ideal r,ideal Q,kStrategy strat);
581void completeReduce (kStrategy strat, BOOLEAN withT=FALSE);
583void enterOnePairNormal (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR);
584void chainCritNormal (poly p,int ecart,kStrategy strat);
585void chainCritOpt_1 (poly,int,kStrategy strat);
586void chainCritSig (poly p,int ecart,kStrategy strat);
589BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat);
590BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat);
591KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
592BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
593BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
594BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
595BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
596
597/// returns index of p in TSet, or -1 if not found
598int kFindInT(poly p, TSet T, int tlength);
599#ifdef HAVE_SHIFTBBA
600int kFindInTShift(poly p, TSet T, int tlength);
601#endif
602
603/// return -1 if no divisor is found
604/// number of first divisor in T, otherwise
605int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start=0);
606int kFindDivisibleByInT_Z(const kStrategy strat, const LObject* L, const int start=0);
607int kFindSameLMInT_Z(const kStrategy strat, const LObject* L, const int start=0);
608
609/// tests if T[0] divides the leading monomial of L, returns -1 if not
610int kTestDivisibleByT0_Z(const kStrategy strat, const LObject* L);
611/// return -1 if no divisor is found
612/// number of first divisor in S, otherwise
613int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject* L);
614
615int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L);
616TObject* kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject* L, TObject *T, long ecart = LONG_MAX);
617
618/***************************************************************
619 *
620 * stuff to be inlined
621 *
622 ***************************************************************/
623
626KINLINE unsigned long* initsevT();
627KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
628KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
629KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
630KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
631
632KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing);
633KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing);
634KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing);
635KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing);
636
637// if exp bound is not violated, return TRUE and
638// get m1 = LCM(LM(p1), LM(p2))/LM(p1)
639// m2 = LCM(LM(p1), LM(p2))/LM(p2)
640// return FALSE and m1 == NULL, m2 == NULL , otherwise
641KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r,
642 poly &m1, poly &m2, const ring m_r);
643#ifdef HAVE_RINGS
644KINLINE void k_GetStrongLeadTerms(const poly p1, const poly p2, const ring leadRing,
645 poly &m1, poly &m2, poly &lcm, const ring taiRing);
646#endif
647#ifdef KDEBUG
648// test strat
649BOOLEAN kTest(kStrategy strat);
650// test strat, and test that S is contained in T
652// test LObject
653BOOLEAN kTest_L(LObject* L, ring tailRing,
654 BOOLEAN testp = FALSE, int lpos = -1,
655 TSet T = NULL, int tlength = -1);
656// test TObject
657BOOLEAN kTest_T(TObject* T, ring tailRing = NULL, int tpos = -1, char TN = '?');
658// test set strat->SevS
660#else
661#define kTest(A) (TRUE)
662#define kTest_TS(A) (TRUE)
663#define kTest_T(T) (TRUE)
664#define kTest_S(T) (TRUE)
665#define kTest_L(T,R) (TRUE)
666#endif
667
668
669/***************************************************************
670 *
671 * From kstd2.cc
672 *
673 ***************************************************************/
674poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing);
675ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
676ideal sba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
677poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
678ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
679poly kNF2Bound (ideal F, ideal Q, poly q,int bound, kStrategy strat, int lazyReduce);
680ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound, kStrategy strat, int lazyReduce);
681void initBba(kStrategy strat);
682void initSba(ideal F,kStrategy strat);
683void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
684 int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
685 intvec *w,intvec *hilb );
686
687/***************************************************************
688 *
689 * From kspoly.cc
690 *
691 ***************************************************************/
692// Reduces PR with PW
693// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
694// Changes: PR
695// Const: PW
696// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
697// If strat != NULL, tailRing is changed if reduction would violate exp bound
698// of tailRing
699// Returns: 0 everything ok, no tailRing change
700// 1 tailRing has successfully changed (strat != NULL)
701// 2 no reduction performed, tailRing needs to be changed first
702// (strat == NULL)
703// -1 tailRing change could not be performed due to exceeding exp
704// bound of currRing
705int ksReducePoly(LObject* PR,
706 TObject* PW,
707 poly spNoether = NULL,
708 number *coef = NULL,
709 poly *mon =NULL,
710 kStrategy strat = NULL);
711
712/* like ksReducePoly, but if the reducer has only 1 term we still
713 * compute a possible coefficient multiplier for PR. this comes from
714 * a special situation in redRing_Z and it is used only there. */
715int ksReducePolyZ(LObject* PR,
716 TObject* PW,
717 poly spNoether = NULL,
718 number *coef = NULL,
719 kStrategy strat = NULL);
720
721int ksReducePolyLC(LObject* PR,
722 TObject* PW,
723 poly spNoether = NULL,
724 number *coef = NULL,
725 kStrategy strat = NULL);
726
727
729 TObject* PW,
730 poly spNoether = NULL,
731 number *coef = NULL,
732 kStrategy strat = NULL);
733
735 TObject* PW,
736 int bound,
737 poly spNoether = NULL,
738 number *coef = NULL,
739 kStrategy strat = NULL);
740
741// Reduces PR with PW
742// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
743// Changes: PR
744// Const: PW
745// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
746// If strat != NULL, tailRing is changed if reduction would violate exp bound
747// of tailRing
748// Returns: 0 everything ok, no tailRing change
749// 1 tailRing has successfully changed (strat != NULL)
750// 2 no reduction performed, tailRing needs to be changed first
751// (strat == NULL)
752// 3 no reduction performed, not sig-safe!!!
753// -1 tailRing change could not be performed due to exceeding exp
754// bound of currRing
756 TObject* PW,
757 long idx,
758 poly spNoether = NULL,
759 number *coef = NULL,
760 kStrategy strat = NULL);
761
763 TObject* PW,
764 long idx,
765 poly spNoether = NULL,
766 number *coef = NULL,
767 kStrategy strat = NULL);
768
769// Reduces PR at Current->next with PW
770// Assumes PR != NULL, Current contained in PR
771// Current->next != NULL, LM(PW) devides LM(Current->next)
772// Changes: PR
773// Const: PW
774// Return: see ksReducePoly
776 TObject* PW,
777 poly Current,
778 poly spNoether = NULL);
779
781
782// Creates S-Poly of Pair
783// Const: Pair->p1, Pair->p2
784// Changes: Pair->p == S-Poly of p1, p2
785// Assume: Pair->p1 != NULL && Pair->p2
786void ksCreateSpoly(LObject* Pair, poly spNoether = NULL,
787 int use_buckets=0, ring tailRing=currRing,
788 poly m1 = NULL, poly m2 = NULL, TObject** R = NULL);
789
790/*2
791* creates the leading term of the S-polynomial of p1 and p2
792* do not destroy p1 and p2
793* remarks:
794* 1. the coefficient is 0 (nNew)
795* 2. pNext is undefined
796*/
797poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing);
798
799
800// old stuff
801KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether = NULL);
802KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether = NULL);
803KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether = NULL, ring r = currRing);
804KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r = currRing);
805
806/***************************************************************
807 *
808 * Routines related for ring changes during std computations
809 *
810 ***************************************************************/
811// return TRUE and set m1, m2 to k_GetLcmTerms,
812// if spoly creation of strat->P does not violate
813// exponent bound of strat->tailRing
814// FALSE, otherwise
815BOOLEAN kCheckSpolyCreation(LObject* L, kStrategy strat, poly &m1, poly &m2);
816#ifdef HAVE_RINGS
817// return TRUE if gcdpoly creation of R[atR] and S[atS] does not violate
818// exponent bound of strat->tailRing
819// FALSE, otherwise
820BOOLEAN kCheckStrongCreation(int atR, poly m1, int atS, poly m2, kStrategy strat);
821poly preIntegerCheck(ideal F, ideal Q);
822void postReduceByMon(LObject* h, kStrategy strat);
824void finalReduceByMon(kStrategy strat);
825#endif
826// change strat->tailRing and adjust all data in strat, L, and T:
827// new tailRing has larger exponent bound
828// do nothing and return FALSE if exponent bound increase would result in
829// larger exponent bound that that of currRing
831 LObject* L = NULL, TObject* T = NULL,
832 // take this as new_expbound: if 0
833 // new expbound is 2*expbound of tailRing
834 unsigned long new_expbound = 0);
835// initiate a change of the tailRing of strat -- should be called
836// right before main loop in bba
838
839/// Output some debug info about a given strategy
840void kDebugPrint(kStrategy strat);
841
842// getting sb order for sba computations
843ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1);
844
845KINLINE void clearS (poly p, unsigned long p_sev, int* at, int* k,
846 kStrategy strat);
847
849
850/* shiftgb stuff */
852
853poly pMove2CurrTail(poly p, kStrategy strat);
854
855poly pMoveCurrTail2poly(poly p, kStrategy strat);
856
857poly pCopyL2p(LObject h, kStrategy strat);
858
859void enterTShift(LObject p, kStrategy strat, int atT = -1);
860
861void enterOnePairShift (poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS);
862
863void enterpairsShift (poly h,int k,int ecart,int pos,kStrategy strat, int atR);
864
865void superenterpairsShift (poly h,int k,int ecart,int pos,kStrategy strat, int atR);
866
867poly redtailBbaShift (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize);
868
869int redFirstShift (LObject* h,kStrategy strat); // ok
870
871ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
872// test syz strategy: // will be removed soon
873EXTERN_VAR int (*test_PosInT)(const TSet T,const int tl,LObject &h);
874EXTERN_VAR int (*test_PosInL)(const LSet set, const int length,
875 LObject* L,const kStrategy strat);
876
877static inline void kDeleteLcm(LObject *P)
878{
879 if (P->lcm!=NULL)
880 {
881 #ifdef HAVE_RINGS
883 pLmDelete(P->lcm);
884 else
885 #endif
886 pLmFree(P->lcm);
887 P->lcm=NULL;
888 }
889}
890
891void initenterpairs (poly h,int k,int ecart,int isFromQ,kStrategy strat, int atR = -1);
892#endif
int sgn(const Rational &a)
Definition: GMPrat.cc:430
#define NULL
Definition: auxiliary.h:104
long int64
Definition: auxiliary.h:68
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
CanonicalForm lcm(const CanonicalForm &, const CanonicalForm &)
CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:763
CanonicalForm normalize(const CanonicalForm &F)
normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leadi...
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4080
f
Definition: cfModGcd.cc:4083
g
Definition: cfModGcd.cc:4092
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
Definition: intvec.h:23
KINLINE long SetDegStuffReturnLDeg()
Definition: kInline.h:817
KINLINE void Tail_Mult_nn(number n)
Definition: kInline.h:622
int i_r1
Definition: kutil.h:193
KINLINE void Copy()
Definition: kInline.h:770
KINLINE void Delete()
Definition: kInline.h:555
KINLINE void LmDeleteAndIter()
Definition: kInline.h:658
KINLINE TObject * T_2(const skStrategy *strat)
Definition: kInline.h:889
KINLINE void PrepareRed(BOOLEAN use_bucket)
Definition: kInline.h:586
unsigned checked
Definition: kutil.h:194
KINLINE void CanonicalizeP()
Definition: kInline.h:372
KINLINE void SetLmTail(poly lm, poly new_p, int length, int use_bucket, ring r)
Definition: kInline.h:604
KINLINE void T_1_2(const skStrategy *strat, TObject *&T_1, TObject *&T_2)
Definition: kInline.h:900
KINLINE void Normalize()
Definition: kInline.h:358
unsigned long sev
Definition: kutil.h:187
KINLINE void Init(ring tailRing=currRing)
Definition: kInline.h:562
KINLINE long MinComp()
Definition: kInline.h:848
kBucket_pt bucket
Definition: kutil.h:192
poly p2
Definition: kutil.h:188
BOOLEAN prod_crit
Definition: kutil.h:199
KINLINE TObject * T_1(const skStrategy *strat)
Definition: kInline.h:879
KINLINE int GetpLength()
Definition: kInline.h:831
KINLINE int SetLength(BOOLEAN lengt_pLength=FALSE)
Definition: kInline.h:838
poly lcm
Definition: kutil.h:191
KINLINE void Clear()
Definition: kInline.h:549
KINLINE void Tail_Minus_mm_Mult_qq(poly m, poly qq, int lq, poly spNoether)
Definition: kInline.h:636
KINLINE void ShallowCopyDelete(ring new_tailRing, pShallowCopyDeleteProc p_shallow_copy_delete)
Definition: kInline.h:747
KINLINE poly GetTP()
Definition: kInline.h:704
KINLINE long pLDeg()
Definition: kInline.h:786
KINLINE sLObject & operator=(const sTObject &)
Definition: kInline.h:872
KINLINE void SetShortExpVector()
Definition: kInline.h:758
KINLINE void HeadNormalize()
Definition: kInline.h:378
KINLINE poly GetP(omBin lmBin=(omBin) NULL)
Definition: kInline.h:720
KINLINE sLObject(ring tailRing=currRing)
Definition: kInline.h:570
poly p1
Definition: kutil.h:188
KINLINE long Comp()
Definition: kInline.h:863
KINLINE poly LmExtractAndIter()
Definition: kInline.h:678
int i_r2
Definition: kutil.h:193
Definition: kutil.h:69
KINLINE poly GetLm(ring r)
Definition: kInline.h:273
KINLINE poly GetLmCurrRing()
Definition: kInline.h:253
char is_redundant
Definition: kutil.h:93
poly sig
Definition: kutil.h:72
KINLINE void Init(ring r=currRing)
Definition: kInline.h:110
KINLINE void Mult_nn(number n)
Definition: kInline.h:345
int length
Definition: kutil.h:79
KINLINE long SetDegStuffReturnLDeg()
Definition: kInline.h:457
KINLINE poly GetLmTailRing()
Definition: kInline.h:260
KINLINE void pCleardenom()
Definition: kInline.h:469
int ecart
Definition: kutil.h:78
KINLINE long GetpFDeg() const
Definition: kInline.h:448
KINLINE sTObject(ring tailRing=currRing)
Definition: kInline.h:116
KINLINE void ShallowCopyDelete(ring new_tailRing, omBin new_tailBin, pShallowCopyDeleteProc p_shallow_copy_delete, BOOLEAN set_max=TRUE)
Definition: kInline.h:392
char is_special
Definition: kutil.h:102
KINLINE void SetLmCurrRing()
Definition: kInline.h:310
poly max_exp
Definition: kutil.h:75
char is_normalized
Definition: kutil.h:87
KINLINE long pLDeg()
Definition: kInline.h:453
char is_sigsafe
Definition: kutil.h:98
KINLINE void LmDeleteAndIter()
Definition: kInline.h:324
int pLength
Definition: kutil.h:80
KINLINE long pFDeg() const
Definition: kInline.h:433
int i_r
Definition: kutil.h:81
poly p
Definition: kutil.h:73
KINLINE BOOLEAN IsNull() const
Definition: kInline.h:299
KINLINE void Set(ring r=currRing)
Definition: kInline.h:106
KINLINE void Delete()
Definition: kInline.h:210
poly t_p
Definition: kutil.h:74
ring tailRing
Definition: kutil.h:76
KINLINE int GetpLength()
Definition: kInline.h:304
KINLINE void pNorm()
Definition: kInline.h:529
KINLINE void Clear()
Definition: kInline.h:224
long FDeg
Definition: kutil.h:77
KINLINE poly Next()
Definition: kInline.h:316
void wrp()
Definition: kutil.cc:773
int shift
Definition: kutil.h:84
KINLINE void pContent()
Definition: kInline.h:507
KINLINE long pTotalDeg() const
Definition: kInline.h:438
KINLINE long SetpFDeg()
Definition: kInline.h:443
unsigned long sevSig
Definition: kutil.h:71
KINLINE void Copy()
Definition: kInline.h:235
KINLINE poly kNoetherTail()
Definition: kInline.h:66
unsigned long * sevSyz
Definition: kutil.h:324
kStrategy next
Definition: kutil.h:278
intvec * kModW
Definition: kutil.h:338
bool sigdrop
Definition: kutil.h:363
poly t_kNoether
Definition: kutil.h:334
int syzComp
Definition: kutil.h:357
int * S_2_R
Definition: kutil.h:345
ring tailRing
Definition: kutil.h:346
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:292
ideal D
Definition: kutil.h:305
char noTailReduction
Definition: kutil.h:382
int currIdx
Definition: kutil.h:318
~skStrategy()
Definition: kutil.cc:11575
skStrategy()
Definition: kutil.cc:11555
int nrsyzcrit
Definition: kutil.h:364
intset lenS
Definition: kutil.h:320
int nrrewcrit
Definition: kutil.h:365
char posInLOldFlag
Definition: kutil.h:386
pFDegProc pOrigFDeg_TailRing
Definition: kutil.h:299
int Ll
Definition: kutil.h:354
TSet T
Definition: kutil.h:327
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:294
char news
Definition: kutil.h:404
omBin lmBin
Definition: kutil.h:347
int syzmax
Definition: kutil.h:352
int Bl
Definition: kutil.h:355
intset ecartS
Definition: kutil.h:310
int syzidxmax
Definition: kutil.h:352
char honey
Definition: kutil.h:381
char rightGB
Definition: kutil.h:373
polyset S
Definition: kutil.h:307
int minim
Definition: kutil.h:361
poly kNoether
Definition: kutil.h:331
BOOLEAN * NotUsedAxis
Definition: kutil.h:335
LSet B
Definition: kutil.h:329
BOOLEAN * pairtest
Definition: kutil.h:336
int cp
Definition: kutil.h:350
int ak
Definition: kutil.h:356
TObject ** R
Definition: kutil.h:343
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:296
poly kHEdge
Definition: kutil.h:330
int lastAxis
Definition: kutil.h:359
ideal M
Definition: kutil.h:306
poly t_kHEdge
Definition: kutil.h:332
int tl
Definition: kutil.h:353
int(* red2)(LObject *L, kStrategy strat)
Definition: kutil.h:280
unsigned long * sevT
Definition: kutil.h:326
unsigned long * sevSig
Definition: kutil.h:325
int nr
Definition: kutil.h:349
intvec * kHomW
Definition: kutil.h:339
int max_lower_index
Definition: kutil.h:319
poly tail
Definition: kutil.h:337
char sugarCrit
Definition: kutil.h:381
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:285
KINLINE TObject * s_2_t(int i)
Definition: kInline.h:47
int blockred
Definition: kutil.h:368
intset syzIdx
Definition: kutil.h:314
ideal Shdl
Definition: kutil.h:304
int syzl
Definition: kutil.h:352
unsigned sbaOrder
Definition: kutil.h:317
pFDegProc pOrigFDeg
Definition: kutil.h:297
int blockredmax
Definition: kutil.h:369
int tmax
Definition: kutil.h:353
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:289
polyset sig
Definition: kutil.h:309
polyset syz
Definition: kutil.h:308
char LDegLast
Definition: kutil.h:389
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:288
BOOLEAN(* syzCrit)(poly sig, unsigned long not_sevSig, kStrategy strat)
Definition: kutil.h:293
wlen_set lenSw
Definition: kutil.h:321
int cv
Definition: kutil.h:372
char noetherSet
Definition: kutil.h:384
pShallowCopyDeleteProc p_shallow_copy_delete
Definition: kutil.h:341
char Gebauer
Definition: kutil.h:382
intset fromQ
Definition: kutil.h:322
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:287
char newt
Definition: kutil.h:405
char use_buckets
Definition: kutil.h:387
int mu
Definition: kutil.h:351
char interpt
Definition: kutil.h:375
char redTailChange
Definition: kutil.h:403
int newIdeal
Definition: kutil.h:360
char fromT
Definition: kutil.h:383
char completeReduce_retry
Definition: kutil.h:407
void(* initEcart)(TObject *L)
Definition: kutil.h:281
omBin tailBin
Definition: kutil.h:348
LObject P
Definition: kutil.h:303
KINLINE TObject * S_2_T(int i)
Definition: kInline.h:38
char noClearS
Definition: kutil.h:406
int Lmax
Definition: kutil.h:354
char z2homog
Definition: kutil.h:378
int LazyPass
Definition: kutil.h:356
char no_prod_crit
Definition: kutil.h:398
char overflow
Definition: kutil.h:408
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.h:291
LSet L
Definition: kutil.h:328
char length_pLength
Definition: kutil.h:391
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:282
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:279
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:295
int sl
Definition: kutil.h:351
int sbaEnterS
Definition: kutil.h:366
int LazyDegree
Definition: kutil.h:356
char kHEdgeFound
Definition: kutil.h:380
char posInLDependsOnLength
Definition: kutil.h:393
unsigned long * sevS
Definition: kutil.h:323
int HCord
Definition: kutil.h:358
char homog
Definition: kutil.h:376
pLDegProc pOrigLDeg
Definition: kutil.h:298
intset fromS
Definition: kutil.h:311
char update
Definition: kutil.h:385
s_poly_proc_t s_poly
Definition: kutil.h:301
int(* posInLSba)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:283
pLDegProc pOrigLDeg_TailRing
Definition: kutil.h:300
int Bmax
Definition: kutil.h:355
int c3
Definition: kutil.h:350
const CanonicalForm & w
Definition: facAbsFact.cc:51
CFArray copy(const CFList &list)
write elements of list into an array
int j
Definition: facHensel.cc:110
#define EXTERN_VAR
Definition: globaldefs.h:6
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
STATIC_VAR jList * T
Definition: janet.cc:30
STATIC_VAR Poly * h
Definition: janet.cc:971
STATIC_VAR jList * Q
Definition: janet.cc:30
BOOLEAN(* s_poly_proc_t)(kStrategy strat)
Definition: kstd1.h:14
int posInLF5C(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5974
int posInLRing(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5873
KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r=currRing)
Definition: kInline.h:1172
void initSbaPos(kStrategy strat)
Definition: kutil.cc:10105
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:7706
BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start)
int ksReducePolyGCD(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:316
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:452
void initenterpairs(poly h, int k, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition: kutil.cc:3840
int posInSyz(const kStrategy strat, const poly sig)
Definition: kutil.cc:5946
int redLiftstd(LObject *h, kStrategy strat)
Definition: kLiftstd.cc:152
int ksReducePolyBound(LObject *PR, TObject *PW, int bound, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:563
int kFindDivisibleByInT(const kStrategy strat, const LObject *L, const int start=0)
return -1 if no divisor is found number of first divisor in T, otherwise
Definition: kstd2.cc:288
int redRing_Z(LObject *h, kStrategy strat)
Definition: kstd2.cc:667
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5394
int posInL13(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6372
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:9995
void initEcartPairBba(LObject *Lp, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.cc:1340
poly pMove2CurrTail(poly p, kStrategy strat)
Definition: kutil.cc:11891
denominator_list_s * denominator_list
Definition: kutil.h:63
wlen_type * wlen_set
Definition: kutil.h:55
poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
Definition: kstd2.cc:553
int redFirstShift(LObject *h, kStrategy strat)
Definition: kstd2.cc:4724
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.cc:6876
void enterSyz(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9574
int posInL15(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6407
int redNF0(LObject *P, kStrategy strat)
int posInT11(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4990
int posInLSigRing(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5810
int ksReducePolySigRing(LObject *PR, TObject *PW, long idx, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:910
int posInTSig(const TSet set, const int length, LObject &p)
int posInT1(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4934
EXTERN_VAR int(* test_PosInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:873
int ksReducePolySig(LObject *PR, TObject *PW, long idx, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:707
void enterT_strong(LObject &p, kStrategy strat, int atT=-1)
Definition: kutil.cc:9472
BOOLEAN kTest(kStrategy strat)
Definition: kutil.cc:1010
void chainCritSig(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3492
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5261
poly pMoveCurrTail2poly(poly p, kStrategy strat)
Definition: kutil.cc:11905
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:1071
int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject *L)
return -1 if no divisor is found number of first divisor in S, otherwise
Definition: kstd2.cc:398
int kFindInT(poly p, TSet T, int tlength)
returns index of p in TSet, or -1 if not found
Definition: kutil.cc:718
BOOLEAN kCheckStrongCreation(int atR, poly m1, int atS, poly m2, kStrategy strat)
Definition: kutil.cc:10757
int kTestDivisibleByT0_Z(const kStrategy strat, const LObject *L)
tests if T[0] divides the leading monomial of L, returns -1 if not
Definition: kstd2.cc:140
TObject * TSet
Definition: kutil.h:59
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition: kutil.cc:1301
int posInL17(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6483
#define setmaxL
Definition: kutil.h:30
void enterT(LObject &p, kStrategy strat, int atT=-1)
Definition: kutil.cc:9372
int kFindSameLMInT_Z(const kStrategy strat, const LObject *L, const int start=0)
Definition: kstd2.cc:84
void enterTShift(LObject p, kStrategy strat, int atT=-1)
Definition: kutil.cc:13339
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4962
int posInL15Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6442
void superenterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4507
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11719
void completeReduce(kStrategy strat, BOOLEAN withT=FALSE)
Definition: kutil.cc:10532
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.cc:1975
int posInT13(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5232
void redtailBbaAlsoLC_Z(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:7374
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3701
BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat)
Definition: kutil.cc:6743
void deleteHC(poly *p, int *e, int *l, kStrategy strat)
Definition: kutil.cc:329
poly pCopyL2p(LObject h, kStrategy strat)
Definition: kutil.cc:11922
int posInSMonFirst(const kStrategy strat, const int length, const poly p)
Definition: kutil.cc:4802
KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kInline.h:1230
ideal sba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2734
EXTERN_VAR denominator_list DENOMINATOR_LIST
Definition: kutil.h:66
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9822
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7829
int posInIdealMonFirst(const ideal F, const poly p, int start=0, int end=-1)
Definition: kutil.cc:4879
KINLINE poly redtailBbaBound(poly p, int end_pos, kStrategy strat, int bound, BOOLEAN normalize=FALSE)
Definition: kInline.h:1186
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:1892
EXTERN_VAR int strat_nr
Definition: kutil.h:181
poly preIntegerCheck(ideal F, ideal Q)
used for GB over ZZ: look for constant and monomial elements in the ideal background: any known const...
Definition: kutil.cc:10780
KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:945
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L=NULL, TObject *T=NULL, unsigned long new_expbound=0)
Definition: kutil.cc:11205
int64 wlen_type
Definition: kutil.h:54
int posInLSig(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5786
KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:936
int posInL11(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5986
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3476
int kFindNextDivisibleByInS(const kStrategy strat, int start, int max_ind, LObject *L)
Definition: kstd2.cc:467
static LSet initL(int nr=setmaxL)
Definition: kutil.h:425
KINLINE TSet initT()
Definition: kInline.h:84
void cancelunit(LObject *p, BOOLEAN inNF=FALSE)
Definition: kutil.cc:343
EXTERN_VAR int(* test_PosInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:874
int posInL11Ringls(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6098
KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:952
KINLINE poly redtailBba_Ring(poly p, int end_pos, kStrategy strat)
Definition: kInline.h:1193
int kFindDivisibleByInT_Z(const kStrategy strat, const LObject *L, const int start=0)
Definition: kstd2.cc:207
LObject * LSet
Definition: kutil.h:60
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:929
int posInT17_c(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5501
poly redtailBbaShift(LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
Definition: kutil.cc:13362
denominator_list next
Definition: kutil.h:65
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11628
int posInT15(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5299
void kFreeStrat(kStrategy strat)
void pairs()
void postReduceByMon(LObject *h, kStrategy strat)
used for GB over ZZ: intermediate reduction by monomial elements background: any known constant eleme...
Definition: kutil.cc:10947
BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat)
Definition: kutil.cc:6708
EXTERN_VAR int HCord
Definition: kutil.h:270
void HEckeTest(poly pp, kStrategy strat)
Definition: kutil.cc:475
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2374
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1687
void enterExtendedSpolySig(poly h, poly hSig, kStrategy strat)
Definition: kutil.cc:4350
void enterpairsSig(poly h, poly hSig, int from, int k, int ec, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4551
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:13309
KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:927
void initBba(kStrategy strat)
Definition: kstd1.cc:1670
void enterOnePairShift(poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS)
Definition: kutil.cc:12535
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:10079
void messageStatSBA(int hilbcount, kStrategy strat)
Definition: kutil.cc:7760
int redRiloc(LObject *h, kStrategy strat)
Definition: kstd1.cc:385
void initEcartNormal(TObject *h)
Definition: kutil.cc:1325
static void kDeleteLcm(LObject *P)
Definition: kutil.h:877
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:4701
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:8788
int posInL0(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5728
int redSigRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:1317
int * intset
Definition: kutil.h:53
void initSLSba(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:8020
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart=LONG_MAX)
Definition: kutil.cc:6927
void enterSBbaShift(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kutil.cc:9123
void initSba(ideal F, kStrategy strat)
Definition: kstd1.cc:1728
int ksReducePolyTail(LObject *PR, TObject *PW, poly Current, poly spNoether=NULL)
Definition: kspoly.cc:1315
BOOLEAN kTest_L(LObject *L, ring tailRing, BOOLEAN testp=FALSE, int lpos=-1, TSet T=NULL, int tlength=-1)
Definition: kutil.cc:925
void initSyzRules(kStrategy strat)
Definition: kutil.cc:8170
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10207
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10718
void cleanT(kStrategy strat)
Definition: kutil.cc:545
KINLINE void k_GetStrongLeadTerms(const poly p1, const poly p2, const ring leadRing, poly &m1, poly &m2, poly &lcm, const ring taiRing)
Definition: kInline.h:1029
int posInT110(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5143
BOOLEAN kTest_S(kStrategy strat)
Definition: kutil.cc:1053
KINLINE TObject ** initR()
Definition: kInline.h:95
void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat)
Definition: kutil.cc:9281
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition: kstd2.cc:2126
void reorderS(int *suc, kStrategy strat)
Definition: kutil.cc:4648
KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether=NULL)
Definition: kInline.h:1142
void enterExtendedSpoly(poly h, kStrategy strat)
Definition: kutil.cc:4267
void enterpairs(poly h, int k, int ec, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4525
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4494
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:1149
KINLINE poly redtailBba_Z(poly p, int end_pos, kStrategy strat)
Definition: kInline.h:1198
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether=NULL)
Definition: kInline.h:1152
int posInL10(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kstd1.cc:1342
KINLINE poly redtailBba(poly p, int end_pos, kStrategy strat, BOOLEAN normalize=FALSE)
Definition: kInline.h:1180
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10320
int posInT0(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4923
#define KINLINE
Definition: kutil.h:49
int posInT19(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5628
void exitSba(kStrategy strat)
Definition: kutil.cc:10280
ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1)
Definition: kutil.cc:11333
void enterSSba(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kutil.cc:9146
void kDebugPrint(kStrategy strat)
Output some debug info about a given strategy.
Definition: kutil.cc:11753
void f5c(kStrategy strat, int &olddeg, int &minimcnt, int &hilbeledeg, int &hilbcount, int &srmax, int &lrmax, int &reduc, ideal Q, intvec *w, intvec *hilb)
Definition: kstd2.cc:4032
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1244
void initHilbCrit(ideal F, ideal Q, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9652
KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether=NULL, ring r=currRing)
Definition: kInline.h:1162
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11305
BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.cc:6851
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9670
void deleteInSSba(int i, kStrategy strat)
Definition: kutil.cc:1189
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9908
poly kNF2Bound(ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3783
int kFindInTShift(poly p, TSet T, int tlength)
Definition: kutil.cc:743
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, poly *mon=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:185
void postReduceByMonSig(LObject *h, kStrategy strat)
Definition: kutil.cc:11023
void ksCreateSpoly(LObject *Pair, poly spNoether=NULL, int use_buckets=0, ring tailRing=currRing, poly m1=NULL, poly m2=NULL, TObject **R=NULL)
Definition: kspoly.cc:1167
int posInL11Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6028
void enterSBba(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kutil.cc:9023
void messageSets(kStrategy strat)
Definition: kutil.cc:7779
int redRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:822
void deleteInS(int i, kStrategy strat)
Definition: kutil.cc:1137
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11682
BOOLEAN kTest_T(TObject *T, ring tailRing=NULL, int tpos=-1, char TN='?')
Definition: kutil.cc:801
BOOLEAN sbaCheckGcdPair(LObject *h, kStrategy strat)
Definition: kutil.cc:1722
int posInL110(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6284
poly redtail(poly p, int end_pos, kStrategy strat)
Definition: kutil.cc:7139
int posInL10Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
void initEcartPairMora(LObject *Lp, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.cc:1347
void superenterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
void entersets(LObject h)
void chainCritNormal(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3240
void initEcartBBA(TObject *h)
Definition: kutil.cc:1333
class sTObject TObject
Definition: kutil.h:57
KINLINE void clearS(poly p, unsigned long p_sev, int *at, int *k, kStrategy strat)
Definition: kInline.h:1205
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:4345
int posInLF5CRing(const LSet set, int start, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6062
int ksReducePolyZ(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:44
poly redNFTail(poly h, const int sl, kStrategy strat)
poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing)
Definition: kspoly.cc:1415
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7747
void initSL(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7923
KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r, poly &m1, poly &m2, const ring m_r)
Definition: kInline.h:986
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition: kutil.cc:11112
void initSbaCrit(kStrategy strat)
Definition: kutil.cc:9735
BOOLEAN newHEdge(kStrategy strat)
Definition: kutil.cc:10654
BOOLEAN homogTest(polyset F, int Fmax)
class sLObject LObject
Definition: kutil.h:58
poly redtailSba(LObject *L, int end_pos, kStrategy strat, BOOLEAN withT=FALSE, BOOLEAN normalize=FALSE)
Definition: kstd2.cc:1567
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.cc:6792
KINLINE unsigned long * initsevT()
Definition: kInline.h:100
Definition: lq.h:40
#define omAlloc(size)
Definition: omAllocDecl.h:210
omBin_t * omBin
Definition: omStructs.h:12
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
Compatiblity layer for legacy polynomial operations (over currRing)
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76
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
poly * polyset
Definition: polys.h:259
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:486
long(* pFDegProc)(poly p, ring r)
Definition: ring.h:38
long(* pLDegProc)(poly p, int *length, ring r)
Definition: ring.h:37
poly(* pShallowCopyDeleteProc)(poly s_p, ring source_r, ring dest_r, omBin dest_bin)
returns a poly from dest_r which is a ShallowCopy of s_p from source_r assumes that source_r->N == de...
Definition: ring.h:44
#define R
Definition: sirandom.c:27