My Project
Loading...
Searching...
No Matches
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
270
272#ifdef HAVE_OMALLOC
273 : public omallocClass
274#endif
275{
276public:
278 int (*red)(LObject * L,kStrategy strat);
279 int (*red2)(LObject * L,kStrategy strat);
280 void (*initEcart)(TObject * L);
281 int (*posInT)(const TSet T,const int tl,LObject &h);
282 int (*posInLSba)(const LSet set, const int length,
283 LObject* L,const kStrategy strat);
284 int (*posInL)(const LSet set, const int length,
285 LObject* L,const kStrategy strat);
286 void (*enterS)(LObject &h, int pos,kStrategy strat, int atR/* =-1*/ );
287 void (*initEcartPair)(LObject * h, poly f, poly g, int ecartF, int ecartG);
288 int (*posInLOld)(const LSet Ls,const int Ll,
289 LObject* Lo,const kStrategy strat);
290 void (*enterOnePair) (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR /*= -1*/);
291 void (*chainCrit) (poly p,int ecart,kStrategy strat);
292 BOOLEAN (*syzCrit) (poly sig, unsigned long not_sevSig, kStrategy strat);
293 BOOLEAN (*rewCrit1) (poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start /*= 0*/);
294 BOOLEAN (*rewCrit2) (poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start /*= 0*/);
295 BOOLEAN (*rewCrit3) (poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start /*= 0*/);
301
303 ideal Shdl;
304 ideal D; /*V(S) is in D(D)*/
305 ideal M; /*set of minimal generators*/
310 intset fromS; // from which S[i] S[j] comes from
311 // this is important for signature-based
312 // algorithms
313 intset syzIdx;// index in the syz array at which the first
314 // syzygy of component i comes up
315 // important for signature-based algorithms
316 unsigned sbaOrder;
320 wlen_set lenSw; /* for tgb.ccc */
322 unsigned long* sevS;
323 unsigned long* sevSyz;
324 unsigned long* sevSig;
325 unsigned long* sevT;
330 poly t_kNoether; // same polys in tailring
331 KINLINE poly kNoetherTail();
333 BOOLEAN * pairtest;/*used for enterOnePair*/
334 poly tail;
337 // procedure for ShalloCopy from tailRing to currRing
339 // pointers to Tobjects R[i] is ith Tobject which is generated
341 // S_2_R[i] yields Tobject which corresponds to S[i]
342 int* S_2_R;
346 int nr;
347 int cp,c3;
348 int sl,mu;
350 int tl,tmax;
351 int Ll,Lmax;
352 int Bl,Bmax;
354 unsigned syzComp;
357 int minim;
358 #ifdef HAVE_RINGS
359 bool sigdrop; //This is used to check sigdrop in sba over Z
360 int nrsyzcrit; // counts how many pairs are deleted by SyzCrit
361 int nrrewcrit; // counts how many pairs are deleted by FaugereRewCrit
362 int sbaEnterS; // sba over Z strategy: if sigdrop element has _*gen(sbaEnterS+1), then
363 // add directly sbaEnterS elements into S
364 int blockred; // counter for blocked reductions in redSig
366 #endif
367 #ifdef HAVE_SHIFTBBA
368 int cv; // in shift bases: counting V criterion
369 /*BOOLEAN*/ char rightGB;
370 #endif
371 /*BOOLEAN*/ char interpt;
372 /*BOOLEAN*/ char homog;
373#ifdef HAVE_PLURAL
374 /*BOOLEAN*/ char z2homog; // Z_2 - homogeneous input allows product criterion in commutative and SCA cases!
375#endif
376 /*BOOLEAN*/ char kAllAxis; // all axis are used -> (re)compute noether
377 /*BOOLEAN*/ char honey,sugarCrit;
378 /*BOOLEAN*/ char Gebauer,noTailReduction;
379 /*BOOLEAN*/ char fromT;
380 /*BOOLEAN*/ char noetherSet;
381 /*BOOLEAN*/ char update;
382 /*BOOLEAN*/ char posInLOldFlag;
383 /*BOOLEAN*/ char use_buckets;
384 // if set, pLDeg(p, l) == (pFDeg(pLast(p), pLength)
385 /*BOOLEAN*/ char LDegLast;
386 // if set, then L.length == L.pLength
387 /*BOOLEAN*/ char length_pLength;
388 // if set, then posInL does not depend on L.length
389 /*BOOLEAN*/ char posInLDependsOnLength;
390 /*FALSE, if posInL == posInL10*/
391#ifdef HAVE_PLURAL
392 // set this flag to 1 to stop the product criteria
393 // use ALLOW_PROD_CRIT(strat) to test
394 /*BOOLEAN*/ char no_prod_crit;
395#define ALLOW_PROD_CRIT(A) (!(A)->no_prod_crit)
396#else
397#define ALLOW_PROD_CRIT(A) (1)
398#endif
400 char news;
401 char newt;/*used for messageSets*/
405
406 skStrategy();
407 ~skStrategy();
408
409 // return TObject corresponding to S[i]: assume that it exists
410 // i.e. no error checking is done
411 KINLINE TObject* S_2_T(int i);
412 // like S_2_T, except that NULL is returned if it can not be found
413 KINLINE TObject* s_2_t(int i);
414};
415
416void deleteHC(poly *p, int *e, int *l, kStrategy strat);
417void deleteHC(LObject* L, kStrategy strat, BOOLEAN fromNext = FALSE);
418void deleteInS (int i,kStrategy strat);
419void cleanT (kStrategy strat);
420static inline LSet initL (int nr=setmaxL)
421{ return (LSet)omAlloc(nr*sizeof(LObject)); }
422void deleteInL(LSet set, int *length, int j,kStrategy strat);
423void enterL (LSet *set,int *length, int *LSetmax, LObject p,int at);
424void enterSBba (LObject &p,int atS,kStrategy strat, int atR = -1);
425void enterSBbaShift (LObject &p,int atS,kStrategy strat, int atR = -1);
426void enterSSba (LObject &p,int atS,kStrategy strat, int atR = -1);
427void initEcartPairBba (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
428void initEcartPairMora (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
429int posInS (const kStrategy strat, const int length, const poly p,
430 const int ecart_p);
431int posInSMonFirst (const kStrategy strat, const int length, const poly p);
432int posInIdealMonFirst (const ideal F, const poly p,int start = 0,int end = -1);
433int posInT0 (const TSet set,const int length,LObject &p);
434int posInT1 (const TSet set,const int length,LObject &p);
435int posInT2 (const TSet set,const int length,LObject &p);
436int posInT11 (const TSet set,const int length,LObject &p);
437int posInTSig (const TSet set,const int length,LObject &p);
438int posInT110 (const TSet set,const int length,LObject &p);
439int posInT13 (const TSet set,const int length,LObject &p);
440int posInT15 (const TSet set,const int length,LObject &p);
441int posInT17 (const TSet set,const int length,LObject &p);
442int posInT17_c (const TSet set,const int length,LObject &p);
443int posInT19 (const TSet set,const int length,LObject &p);
444int posInT_EcartpLength(const TSet set,const int length,LObject &p);
445int posInT_EcartFDegpLength(const TSet set,const int length,LObject &p);
446int posInT_FDegpLength(const TSet set,const int length,LObject &p);
447int posInT_pLength(const TSet set,const int length,LObject &p);
448
449#ifdef HAVE_MORE_POS_IN_T
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#endif
454
455
456void reorderS (int* suc,kStrategy strat);
457int posInLF5C (const LSet set, const int length,
458 LObject* L,const kStrategy strat);
459int posInLSig (const LSet set, const int length,
460 LObject* L,const kStrategy strat);
461int posInLSigRing (const LSet set, const int length,
462 LObject* L,const kStrategy strat);
463int posInSyz (const kStrategy strat, const poly sig);
464int posInL0 (const LSet set, const int length,
465 LObject* L,const kStrategy strat);
466int posInL11 (const LSet set, const int length,
467 LObject* L,const kStrategy strat);
468int posInL11Ring (const LSet set, const int length,
469 LObject* L,const kStrategy strat);
470int posInLF5CRing (const LSet set, int start , const int length,
471 LObject* L,const kStrategy strat);
472int posInL11Ringls (const LSet set, const int length,
473 LObject* L,const kStrategy strat);
474int posInL13 (const LSet set, const int length,
475 LObject* L,const kStrategy strat);
476int posInL15 (const LSet set, const int length,
477 LObject* L,const kStrategy strat);
478int posInL15Ring (const LSet set, const int length,
479 LObject* L,const kStrategy strat);
480int posInL17 (const LSet set, const int length,
481 LObject* L,const kStrategy strat);
482int posInL10 (const LSet set, const int length,
483 LObject* L,const kStrategy strat);
484int posInL10Ring (const LSet set, const int length,
485 LObject* L,const kStrategy strat);
486int posInL110 (const LSet set, const int length,
487 LObject* L,const kStrategy strat);
488KINLINE poly redtailBba (poly p,int end_pos,kStrategy strat,BOOLEAN normalize=FALSE);
489KINLINE poly redtailBbaBound (poly p,int end_pos,kStrategy strat,int bound,BOOLEAN normalize=FALSE);
490#ifdef HAVE_RINGS
491KINLINE poly redtailBba_Ring (poly p,int end_pos,kStrategy strat);
492KINLINE poly redtailBba_Z (poly p,int end_pos,kStrategy strat);
493poly redtailBba_NF (poly p, kStrategy strat );
494poly redtailBba_Ring (LObject* L, int end_pos, kStrategy strat );
495poly redtailBba_Z (LObject* L, int end_pos, kStrategy strat );
496void redtailBbaAlsoLC_Z (LObject* L, int end_pos, kStrategy strat );
497#endif
498poly redtailBba (LObject *L, int end_pos,kStrategy strat,
500poly redtailBbaBound (LObject *L, int end_pos,kStrategy strat,int bound,
502poly redtailSba (LObject *L, int end_pos,kStrategy strat,
504poly redtailBba (TObject *T, int end_pos,kStrategy strat);
505poly redtail (poly p,int end_pos,kStrategy strat);
506poly redtail (LObject *L,int end_pos,kStrategy strat);
507poly redNF (poly h,int & max_ind,int nonorm,kStrategy strat);
508int redNF0 (LObject *P,kStrategy strat);
509poly redNFTail (poly h,const int sl,kStrategy strat);
510int redHoney (LObject* h, kStrategy strat);
512int redLiftstd (LObject* h, kStrategy strat);
513#ifdef HAVE_RINGS
514int redRing (LObject* h,kStrategy strat);
515int redRing_Z (LObject* h,kStrategy strat);
516int redRiloc (LObject* h,kStrategy strat);
517void enterExtendedSpoly(poly h,kStrategy strat);
518void enterExtendedSpolySig(poly h,poly hSig,kStrategy strat);
519void superenterpairs (poly h,int k,int ecart,int pos,kStrategy strat, int atR = -1);
520void superenterpairsSig (poly h,poly hSig,int hFrom,int k,int ecart,int pos,kStrategy strat, int atR = -1);
521#endif
522int redLazy (LObject* h,kStrategy strat);
523int redHomog (LObject* h,kStrategy strat);
524int redSig (LObject* h,kStrategy strat);
525int redSigRing (LObject* h,kStrategy strat);
526//adds hSig to be able to check with F5's criteria when entering pairs!
527void enterpairsSig (poly h, poly hSig, int from, int k, int ec, int pos,kStrategy strat, int atR = -1);
528void enterpairs (poly h, int k, int ec, int pos,kStrategy strat, int atR = -1);
530void pairs ();
532void message (int i,int* reduc,int* olddeg,kStrategy strat,int red_result);
533void messageStat (int hilbcount,kStrategy strat);
534void messageStatSBA (int hilbcount,kStrategy strat);
535#ifdef KDEBUG
536void messageSets (kStrategy strat);
537#else
538#define messageSets(s) do {} while (0)
539#endif
540
542void initEcartBBA (TObject* h);
543void initS (ideal F, ideal Q,kStrategy strat);
544void initSL (ideal F, ideal Q,kStrategy strat);
545void initSLSba (ideal F, ideal Q,kStrategy strat);
546/*************************************************
547 * when initializing a new bunch of principal
548 * syzygies at the beginning of a new iteration
549 * step in a signature-based algorithm we
550 * compute ONLY the leading elements of those
551 * syzygies, NOT the whole syzygy
552 * NOTE: this needs to be adjusted for a more
553 * general approach on signature-based algorithms
554 ***********************************************/
555void initSyzRules (kStrategy strat);
556void updateS(BOOLEAN toT,kStrategy strat);
557void enterSyz (LObject &p,kStrategy strat, int atT);
558void enterT (LObject &p,kStrategy strat, int atT = -1);
559void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat);
560#ifdef HAVE_RINGS
561void enterT_strong (LObject &p,kStrategy strat, int atT = -1);
562#endif
563void cancelunit (LObject* p,BOOLEAN inNF=FALSE);
564void HEckeTest (poly pp,kStrategy strat);
565void initBuchMoraCrit(kStrategy strat);
566void initSbaCrit(kStrategy strat);
567void initHilbCrit(ideal F, ideal Q, intvec **hilb,kStrategy strat);
568void initBuchMoraPos(kStrategy strat);
570void initSbaPos(kStrategy strat);
571void initBuchMora (ideal F, ideal Q,kStrategy strat);
572void initSbaBuchMora (ideal F, ideal Q,kStrategy strat);
573void exitBuchMora (kStrategy strat);
574void exitSba (kStrategy strat);
575void updateResult(ideal r,ideal Q,kStrategy strat);
576void completeReduce (kStrategy strat, BOOLEAN withT=FALSE);
578void enterOnePairNormal (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR);
579void chainCritNormal (poly p,int ecart,kStrategy strat);
580void chainCritOpt_1 (poly,int,kStrategy strat);
581void chainCritSig (poly p,int ecart,kStrategy strat);
584BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat);
585BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat);
586KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
587BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
588BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
589BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
590BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
591
592/// returns index of p in TSet, or -1 if not found
593int kFindInT(poly p, TSet T, int tlength);
594#ifdef HAVE_SHIFTBBA
595int kFindInTShift(poly p, TSet T, int tlength);
596#endif
597
598/// return -1 if no divisor is found
599/// number of first divisor in T, otherwise
600int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start=0);
601int kFindDivisibleByInT_Z(const kStrategy strat, const LObject* L, const int start=0);
602int kFindSameLMInT_Z(const kStrategy strat, const LObject* L, const int start=0);
603
604/// tests if T[0] divides the leading monomial of L, returns -1 if not
605int kTestDivisibleByT0_Z(const kStrategy strat, const LObject* L);
606/// return -1 if no divisor is found
607/// number of first divisor in S, otherwise
608int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject* L);
609
610int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L);
611TObject* kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject* L, TObject *T, long ecart = LONG_MAX);
612
613/***************************************************************
614 *
615 * stuff to be inlined
616 *
617 ***************************************************************/
618
621KINLINE unsigned long* initsevT();
622KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
623KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
624KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
625KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
626
627KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing);
628KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing);
629KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing);
630KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing);
631
632// if exp bound is not violated, return TRUE and
633// get m1 = LCM(LM(p1), LM(p2))/LM(p1)
634// m2 = LCM(LM(p1), LM(p2))/LM(p2)
635// return FALSE and m1 == NULL, m2 == NULL , otherwise
636KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r,
637 poly &m1, poly &m2, const ring m_r);
638#ifdef HAVE_RINGS
639KINLINE void k_GetStrongLeadTerms(const poly p1, const poly p2, const ring leadRing,
640 poly &m1, poly &m2, poly &lcm, const ring taiRing);
641#endif
642#ifdef KDEBUG
643// test strat
644BOOLEAN kTest(kStrategy strat);
645// test strat, and test that S is contained in T
647// test LObject
649 BOOLEAN testp = FALSE, int lpos = -1,
650 TSet T = NULL, int tlength = -1);
651// test TObject
652BOOLEAN kTest_T(TObject* T, kStrategy strat, int tpos = -1, char TN = '?');
653// test set strat->SevS
655#else
656#define kTest(A) (TRUE)
657#define kTest_TS(A) (TRUE)
658#define kTest_T(T,S) (TRUE)
659#define kTest_S(T) (TRUE)
660#define kTest_L(T,R) (TRUE)
661#endif
662
663
664/***************************************************************
665 *
666 * From kstd2.cc
667 *
668 ***************************************************************/
669poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing);
670ideal bba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
671ideal sba (ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
672poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
673ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
674poly kNF2Bound (ideal F, ideal Q, poly q,int bound, kStrategy strat, int lazyReduce);
675ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound, kStrategy strat, int lazyReduce);
676void initBba(kStrategy strat);
677void initSba(ideal F,kStrategy strat);
678void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
679 int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
680 intvec *w,intvec *hilb );
681
682/***************************************************************
683 *
684 * From kspoly.cc
685 *
686 ***************************************************************/
687// Reduces PR with PW
688// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
689// Changes: PR
690// Const: PW
691// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
692// If strat != NULL, tailRing is changed if reduction would violate exp bound
693// of tailRing
694// Returns: 0 everything ok, no tailRing change
695// 1 tailRing has successfully changed (strat != NULL)
696// 2 no reduction performed, tailRing needs to be changed first
697// (strat == NULL)
698// -1 tailRing change could not be performed due to exceeding exp
699// bound of currRing
700// reduce should be set inside "kNF" (only relevant for rings)
701int ksReducePoly(LObject* PR,
702 TObject* PW,
703 poly spNoether = NULL,
704 number *coef = NULL,
705 poly *mon =NULL,
706 kStrategy strat = NULL,
708
709/* like ksReducePoly, but if the reducer has only 1 term we still
710 * compute a possible coefficient multiplier for PR. this comes from
711 * a special situation in redRing_Z and it is used only there. */
713 TObject* PW,
714 poly spNoether = NULL,
715 number *coef = NULL,
716 kStrategy strat = NULL);
717
718int ksReducePolyLC(LObject* PR,
719 TObject* PW,
720 poly spNoether = NULL,
721 number *coef = NULL,
722 kStrategy strat = NULL);
723
724
726 TObject* PW,
727 poly spNoether = NULL,
728 number *coef = NULL,
729 kStrategy strat = NULL);
730
732 TObject* PW,
733 int bound,
734 poly spNoether = NULL,
735 number *coef = NULL,
736 kStrategy strat = NULL);
737
738// Reduces PR with PW
739// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
740// Changes: PR
741// Const: PW
742// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
743// If strat != NULL, tailRing is changed if reduction would violate exp bound
744// of tailRing
745// Returns: 0 everything ok, no tailRing change
746// 1 tailRing has successfully changed (strat != NULL)
747// 2 no reduction performed, tailRing needs to be changed first
748// (strat == NULL)
749// 3 no reduction performed, not sig-safe!!!
750// -1 tailRing change could not be performed due to exceeding exp
751// bound of currRing
753 TObject* PW,
754 long idx,
755 poly spNoether = NULL,
756 number *coef = NULL,
757 kStrategy strat = NULL);
758
760 TObject* PW,
761 long idx,
762 poly spNoether = NULL,
763 number *coef = NULL,
764 kStrategy strat = NULL);
765
766// Reduces PR at Current->next with PW
767// Assumes PR != NULL, Current contained in PR
768// Current->next != NULL, LM(PW) divides LM(Current->next)
769// Changes: PR
770// Const: PW
771// Return: see ksReducePoly
773 TObject* PW,
774 poly Current,
775 poly spNoether = NULL);
776
778
779// Creates S-Poly of Pair
780// Const: Pair->p1, Pair->p2
781// Changes: Pair->p == S-Poly of p1, p2
782// Assume: Pair->p1 != NULL && Pair->p2
783void ksCreateSpoly(LObject* Pair, poly spNoether = NULL,
784 int use_buckets=0, ring tailRing=currRing,
785 poly m1 = NULL, poly m2 = NULL, TObject** R = NULL);
786
787/*2
788* creates the leading term of the S-polynomial of p1 and p2
789* do not destroy p1 and p2
790* remarks:
791* 1. the coefficient is 0 (nNew)
792* 2. pNext is undefined
793*/
794poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing);
795
796
797// old stuff
798KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether = NULL);
799KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether = NULL);
800KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether = NULL, ring r = currRing);
801KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r = currRing);
802
803/***************************************************************
804 *
805 * Routines related for ring changes during std computations
806 *
807 ***************************************************************/
808// return TRUE and set m1, m2 to k_GetLcmTerms,
809// if spoly creation of strat->P does not violate
810// exponent bound of strat->tailRing
811// FALSE, otherwise
812BOOLEAN kCheckSpolyCreation(LObject* L, kStrategy strat, poly &m1, poly &m2);
813#ifdef HAVE_RINGS
814// return TRUE if gcdpoly creation of R[atR] and S[atS] does not violate
815// exponent bound of strat->tailRing
816// FALSE, otherwise
817BOOLEAN kCheckStrongCreation(int atR, poly m1, int atS, poly m2, kStrategy strat);
818poly preIntegerCheck(ideal F, ideal Q);
819void postReduceByMon(LObject* h, kStrategy strat);
821void finalReduceByMon(kStrategy strat);
822#endif
823// change strat->tailRing and adjust all data in strat, L, and T:
824// new tailRing has larger exponent bound
825// do nothing and return FALSE if exponent bound increase would result in
826// larger exponent bound that that of currRing
828 LObject* L = NULL, TObject* T = NULL,
829 // take this as new_expbound: if 0
830 // new expbound is 2*expbound of tailRing
831 unsigned long new_expbound = 0);
832// initiate a change of the tailRing of strat -- should be called
833// right before main loop in bba
835
836/// Output some debug info about a given strategy
837void kDebugPrint(kStrategy strat);
838
839// getting sb order for sba computations
840ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1);
841
842KINLINE void clearS (poly p, unsigned long p_sev, int* at, int* k,
843 kStrategy strat);
844
846
847/* shiftgb stuff */
849
850#ifdef HAVE_SHIFTBBA
851static inline int kFindInL1(const poly p, const kStrategy strat)
852{
853 for(int i=strat->Ll;i>=0;i--)
854 {
855 if (p==strat->L[i].p1) return i;
856 }
857 return -1;
858}
859
860void enterTShift(LObject p, kStrategy strat, int atT = -1);
861
862BOOLEAN enterOnePairShift (poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS);
863
864void enterpairsShift (poly h,int k,int ecart,int pos,kStrategy strat, int atR);
865
866void superenterpairsShift (poly h,int k,int ecart,int pos,kStrategy strat, int atR);
867
868poly redtailBbaShift (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize);
869
870int redFirstShift (LObject* h,kStrategy strat); // ok
871
872ideal bbaShift(ideal F, ideal Q,intvec *w,intvec *hilb,kStrategy strat);
873#endif
874
875// test syz strategy: // will be removed soon
876EXTERN_VAR int (*test_PosInT)(const TSet T,const int tl,LObject &h);
877EXTERN_VAR int (*test_PosInL)(const LSet set, const int length,
878 LObject* L,const kStrategy strat);
879
880static inline void kDeleteLcm(LObject *P)
881{
882 if (P->lcm!=NULL)
883 {
884 #ifdef HAVE_RINGS
886 pLmDelete(P->lcm);
887 else
888 #endif
889 pLmFree(P->lcm);
890 P->lcm=NULL;
891 }
892}
893
894void initenterpairs (poly h,int k,int ecart,int isFromQ,kStrategy strat, int atR = -1);
895#endif
int sgn(const Rational &a)
Definition: GMPrat.cc:430
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 FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
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:4078
g
Definition: cfModGcd.cc:4090
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
FILE * f
Definition: checklibs.c:9
Definition: intvec.h:23
KINLINE long SetDegStuffReturnLDeg()
Definition: kInline.h:849
KINLINE void Tail_Mult_nn(number n)
Definition: kInline.h:654
int i_r1
Definition: kutil.h:193
KINLINE void Copy()
Definition: kInline.h:802
KINLINE void Delete()
Definition: kInline.h:587
KINLINE void LmDeleteAndIter()
Definition: kInline.h:690
KINLINE TObject * T_2(const skStrategy *strat)
Definition: kInline.h:921
KINLINE void PrepareRed(BOOLEAN use_bucket)
Definition: kInline.h:618
unsigned checked
Definition: kutil.h:194
KINLINE void CanonicalizeP()
Definition: kInline.h:361
KINLINE void SetLmTail(poly lm, poly new_p, int length, int use_bucket, ring r)
Definition: kInline.h:636
KINLINE void T_1_2(const skStrategy *strat, TObject *&T_1, TObject *&T_2)
Definition: kInline.h:932
KINLINE void Normalize()
Definition: kInline.h:347
unsigned long sev
Definition: kutil.h:187
KINLINE void Init(ring tailRing=currRing)
Definition: kInline.h:594
KINLINE long MinComp()
Definition: kInline.h:880
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:911
KINLINE int GetpLength()
Definition: kInline.h:863
KINLINE int SetLength(BOOLEAN lengt_pLength=FALSE)
Definition: kInline.h:870
poly lcm
Definition: kutil.h:191
KINLINE void Clear()
Definition: kInline.h:580
KINLINE void Tail_Minus_mm_Mult_qq(poly m, poly qq, int lq, poly spNoether)
Definition: kInline.h:668
KINLINE void ShallowCopyDelete(ring new_tailRing, pShallowCopyDeleteProc p_shallow_copy_delete)
Definition: kInline.h:779
KINLINE poly GetTP()
Definition: kInline.h:736
KINLINE long pLDeg()
Definition: kInline.h:818
KINLINE sLObject & operator=(const sTObject &)
Definition: kInline.h:904
KINLINE void SetShortExpVector()
Definition: kInline.h:790
KINLINE void HeadNormalize()
Definition: kInline.h:367
KINLINE poly GetP(omBin lmBin=(omBin) NULL)
Definition: kInline.h:752
poly p1
Definition: kutil.h:188
KINLINE long Comp()
Definition: kInline.h:895
KINLINE poly LmExtractAndIter()
Definition: kInline.h:710
int i_r2
Definition: kutil.h:193
Definition: kutil.h:69
KINLINE poly GetLm(ring r)
Definition: kInline.h:262
KINLINE poly GetLmCurrRing()
Definition: kInline.h:242
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:334
int length
Definition: kutil.h:79
KINLINE long SetDegStuffReturnLDeg()
Definition: kInline.h:446
KINLINE poly GetLmTailRing()
Definition: kInline.h:249
KINLINE void pCleardenom()
Definition: kInline.h:458
int ecart
Definition: kutil.h:78
KINLINE long GetpFDeg() const
Definition: kInline.h:437
KINLINE void ShallowCopyDelete(ring new_tailRing, omBin new_tailBin, pShallowCopyDeleteProc p_shallow_copy_delete, BOOLEAN set_max=TRUE)
Definition: kInline.h:381
char is_special
Definition: kutil.h:102
KINLINE void SetLmCurrRing()
Definition: kInline.h:299
poly max_exp
Definition: kutil.h:75
char is_normalized
Definition: kutil.h:87
KINLINE long pLDeg()
Definition: kInline.h:442
char is_sigsafe
Definition: kutil.h:98
KINLINE void LmDeleteAndIter()
Definition: kInline.h:313
int pLength
Definition: kutil.h:80
KINLINE long pFDeg() const
Definition: kInline.h:422
int i_r
Definition: kutil.h:81
poly p
Definition: kutil.h:73
KINLINE BOOLEAN IsNull() const
Definition: kInline.h:288
KINLINE void Set(ring r=currRing)
Definition: kInline.h:106
KINLINE void Delete()
Definition: kInline.h:199
poly t_p
Definition: kutil.h:74
ring tailRing
Definition: kutil.h:76
KINLINE int GetpLength()
Definition: kInline.h:293
KINLINE void pNorm()
Definition: kInline.h:560
KINLINE void Clear()
Definition: kInline.h:213
long FDeg
Definition: kutil.h:77
KINLINE poly Next()
Definition: kInline.h:305
void wrp()
Definition: kutil.cc:773
int shift
Definition: kutil.h:84
KINLINE void pContent()
Definition: kInline.h:538
KINLINE long pTotalDeg() const
Definition: kInline.h:427
KINLINE long SetpFDeg()
Definition: kInline.h:432
unsigned long sevSig
Definition: kutil.h:71
KINLINE void Copy()
Definition: kInline.h:224
KINLINE poly kNoetherTail()
Definition: kInline.h:66
unsigned long * sevSyz
Definition: kutil.h:323
kStrategy next
Definition: kutil.h:277
intvec * kModW
Definition: kutil.h:335
bool sigdrop
Definition: kutil.h:359
poly t_kNoether
Definition: kutil.h:330
int * S_2_R
Definition: kutil.h:342
ring tailRing
Definition: kutil.h:343
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition: kutil.h:291
ideal D
Definition: kutil.h:304
char noTailReduction
Definition: kutil.h:378
int currIdx
Definition: kutil.h:317
~skStrategy()
Definition: kutil.cc:11384
skStrategy()
Definition: kutil.cc:11364
int nrsyzcrit
Definition: kutil.h:360
intset lenS
Definition: kutil.h:319
int nrrewcrit
Definition: kutil.h:361
char posInLOldFlag
Definition: kutil.h:382
pFDegProc pOrigFDeg_TailRing
Definition: kutil.h:298
int Ll
Definition: kutil.h:351
TSet T
Definition: kutil.h:326
BOOLEAN(* rewCrit1)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:293
char news
Definition: kutil.h:400
omBin lmBin
Definition: kutil.h:344
int syzmax
Definition: kutil.h:349
int Bl
Definition: kutil.h:352
intset ecartS
Definition: kutil.h:309
int syzidxmax
Definition: kutil.h:349
char honey
Definition: kutil.h:377
unsigned syzComp
Definition: kutil.h:354
char rightGB
Definition: kutil.h:369
polyset S
Definition: kutil.h:306
int minim
Definition: kutil.h:357
poly kNoether
Definition: kutil.h:329
BOOLEAN * NotUsedAxis
Definition: kutil.h:332
LSet B
Definition: kutil.h:328
BOOLEAN * pairtest
Definition: kutil.h:333
int cp
Definition: kutil.h:347
int ak
Definition: kutil.h:353
TObject ** R
Definition: kutil.h:340
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:295
int lastAxis
Definition: kutil.h:355
ideal M
Definition: kutil.h:305
int tl
Definition: kutil.h:350
int(* red2)(LObject *L, kStrategy strat)
Definition: kutil.h:279
unsigned long * sevT
Definition: kutil.h:325
unsigned long * sevSig
Definition: kutil.h:324
int nr
Definition: kutil.h:346
intvec * kHomW
Definition: kutil.h:336
int max_lower_index
Definition: kutil.h:318
poly tail
Definition: kutil.h:334
char sugarCrit
Definition: kutil.h:377
int(* posInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:284
KINLINE TObject * s_2_t(int i)
Definition: kInline.h:47
int blockred
Definition: kutil.h:364
intset syzIdx
Definition: kutil.h:313
ideal Shdl
Definition: kutil.h:303
int syzl
Definition: kutil.h:349
unsigned sbaOrder
Definition: kutil.h:316
pFDegProc pOrigFDeg
Definition: kutil.h:296
int blockredmax
Definition: kutil.h:365
int tmax
Definition: kutil.h:350
int(* posInLOld)(const LSet Ls, const int Ll, LObject *Lo, const kStrategy strat)
Definition: kutil.h:288
polyset sig
Definition: kutil.h:308
polyset syz
Definition: kutil.h:307
char LDegLast
Definition: kutil.h:385
void(* initEcartPair)(LObject *h, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.h:287
BOOLEAN(* syzCrit)(poly sig, unsigned long not_sevSig, kStrategy strat)
Definition: kutil.h:292
wlen_set lenSw
Definition: kutil.h:320
char kAllAxis
Definition: kutil.h:376
int cv
Definition: kutil.h:368
char noetherSet
Definition: kutil.h:380
pShallowCopyDeleteProc p_shallow_copy_delete
Definition: kutil.h:338
char Gebauer
Definition: kutil.h:378
intset fromQ
Definition: kutil.h:321
void(* enterS)(LObject &h, int pos, kStrategy strat, int atR)
Definition: kutil.h:286
char newt
Definition: kutil.h:401
char use_buckets
Definition: kutil.h:383
int mu
Definition: kutil.h:348
char interpt
Definition: kutil.h:371
char redTailChange
Definition: kutil.h:399
int newIdeal
Definition: kutil.h:356
char fromT
Definition: kutil.h:379
char completeReduce_retry
Definition: kutil.h:403
void(* initEcart)(TObject *L)
Definition: kutil.h:280
omBin tailBin
Definition: kutil.h:345
LObject P
Definition: kutil.h:302
KINLINE TObject * S_2_T(int i)
Definition: kInline.h:38
char noClearS
Definition: kutil.h:402
int Lmax
Definition: kutil.h:351
char z2homog
Definition: kutil.h:374
int LazyPass
Definition: kutil.h:353
char no_prod_crit
Definition: kutil.h:394
char overflow
Definition: kutil.h:404
void(* enterOnePair)(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.h:290
LSet L
Definition: kutil.h:327
char length_pLength
Definition: kutil.h:387
int(* posInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:281
int(* red)(LObject *L, kStrategy strat)
Definition: kutil.h:278
BOOLEAN(* rewCrit2)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.h:294
int sl
Definition: kutil.h:348
int sbaEnterS
Definition: kutil.h:362
int LazyDegree
Definition: kutil.h:353
char posInLDependsOnLength
Definition: kutil.h:389
unsigned long * sevS
Definition: kutil.h:322
char homog
Definition: kutil.h:372
pLDegProc pOrigLDeg
Definition: kutil.h:297
intset fromS
Definition: kutil.h:310
char update
Definition: kutil.h:381
s_poly_proc_t s_poly
Definition: kutil.h:300
int(* posInLSba)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:282
pLDegProc pOrigLDeg_TailRing
Definition: kutil.h:299
int Bmax
Definition: kutil.h:352
int c3
Definition: kutil.h:347
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
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:5821
KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r=currRing)
Definition: kInline.h:1206
void initSbaPos(kStrategy strat)
Definition: kutil.cc:9911
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition: kutil.cc:7512
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)
int ksReducePolyLC(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:481
void initenterpairs(poly h, int k, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition: kutil.cc:3822
int posInSyz(const kStrategy strat, const poly sig)
Definition: kutil.cc:5792
int redLiftstd(LObject *h, kStrategy strat)
Definition: kLiftstd.cc:167
int ksReducePolyBound(LObject *PR, TObject *PW, int bound, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:595
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:321
int redRing_Z(LObject *h, kStrategy strat)
Definition: kstd2.cc:683
int posInT17(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5306
int posInL13(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6182
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:9800
void initEcartPairBba(LObject *Lp, poly f, poly g, int ecartF, int ecartG)
Definition: kutil.cc:1319
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:569
int redFirstShift(LObject *h, kStrategy strat)
Definition: kstd2.cc:4988
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.cc:6689
void enterSyz(LObject &p, kStrategy strat, int atT)
Definition: kutil.cc:9380
int posInL15(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6217
int redNF0(LObject *P, kStrategy strat)
int posInT11(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4975
int posInLSigRing(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5728
int ksReducePolySigRing(LObject *PR, TObject *PW, long idx, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:948
int posInTSig(const TSet set, const int length, LObject &p)
int posInT1(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4918
EXTERN_VAR int(* test_PosInT)(const TSet T, const int tl, LObject &h)
Definition: kutil.h:876
int ksReducePolySig(LObject *PR, TObject *PW, long idx, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition: kspoly.cc:742
void enterT_strong(LObject &p, kStrategy strat, int atT=-1)
Definition: kutil.cc:9278
BOOLEAN kTest(kStrategy strat)
Definition: kutil.cc:1012
void chainCritSig(poly p, int ecart, kStrategy strat)
Definition: kutil.cc:3474
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5172
BOOLEAN kTest_TS(kStrategy strat)
Definition: kutil.cc:1073
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:421
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:10573
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, poly *mon=NULL, kStrategy strat=NULL, BOOLEAN redtail=FALSE)
Definition: kspoly.cc:189
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:146
BOOLEAN kTest_L(LObject *L, kStrategy strat, BOOLEAN testp=FALSE, int lpos=-1, TSet T=NULL, int tlength=-1)
Definition: kutil.cc:926
TObject * TSet
Definition: kutil.h:59
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition: kutil.cc:1280
int posInL17(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6294
#define setmaxL
Definition: kutil.h:30
void enterT(LObject &p, kStrategy strat, int atT=-1)
Definition: kutil.cc:9178
int kFindSameLMInT_Z(const kStrategy strat, const LObject *L, const int start=0)
void enterTShift(LObject p, kStrategy strat, int atT=-1)
Definition: kutil.cc:13058
int posInT2(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4947
int posInL15Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6253
void superenterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4491
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11526
void completeReduce(kStrategy strat, BOOLEAN withT=FALSE)
Definition: kutil.cc:10340
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.cc:1952
static int kFindInL1(const poly p, const kStrategy strat)
Definition: kutil.h:851
int posInT13(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5143
void redtailBbaAlsoLC_Z(LObject *L, int end_pos, kStrategy strat)
Definition: kutil.cc:7188
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:3967
BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat)
Definition: kutil.cc:6556
void deleteHC(poly *p, int *e, int *l, kStrategy strat)
Definition: kutil.cc:359
int posInSMonFirst(const kStrategy strat, const int length, const poly p)
Definition: kutil.cc:4786
KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kInline.h:1264
ideal sba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:3001
EXTERN_VAR denominator_list DENOMINATOR_LIST
Definition: kutil.h:66
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9627
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7635
int posInIdealMonFirst(const ideal F, const poly p, int start=0, int end=-1)
Definition: kutil.cc:4863
KINLINE poly redtailBbaBound(poly p, int end_pos, kStrategy strat, int bound, BOOLEAN normalize=FALSE)
Definition: kInline.h:1220
int redHoney(LObject *h, kStrategy strat)
Definition: kstd2.cc:2088
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:10596
KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:977
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L=NULL, TObject *T=NULL, unsigned long new_expbound=0)
Definition: kutil.cc:11021
int64 wlen_type
Definition: kutil.h:54
int posInLSig(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5703
KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:968
int posInL11(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5833
void chainCritOpt_1(poly, int, kStrategy strat)
Definition: kutil.cc:3458
int kFindNextDivisibleByInS(const kStrategy strat, int start, int max_ind, LObject *L)
Definition: kstd2.cc:524
static LSet initL(int nr=setmaxL)
Definition: kutil.h:420
KINLINE TSet initT()
Definition: kInline.h:84
void cancelunit(LObject *p, BOOLEAN inNF=FALSE)
Definition: kutil.cc:373
EXTERN_VAR int(* test_PosInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.h:877
int posInL11Ringls(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5946
KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:984
KINLINE poly redtailBba_Ring(poly p, int end_pos, kStrategy strat)
Definition: kInline.h:1227
int kFindDivisibleByInT_Z(const kStrategy strat, const LObject *L, const int start=0)
Definition: kstd2.cc:213
LObject * LSet
Definition: kutil.h:60
int redHomog(LObject *h, kStrategy strat)
Definition: kstd2.cc:1121
int posInT17_c(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5414
poly redtailBbaShift(LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
Definition: kutil.cc:13081
denominator_list next
Definition: kutil.h:65
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11435
int posInT15(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5210
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:10763
BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat)
Definition: kutil.cc:6521
EXTERN_VAR int HCord
Definition: kutil.h:269
void HEckeTest(poly pp, kStrategy strat)
Definition: kutil.cc:501
ideal bba(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:2642
int redLazy(LObject *h, kStrategy strat)
Definition: kstd2.cc:1881
void enterExtendedSpolySig(poly h, poly hSig, kStrategy strat)
Definition: kutil.cc:4333
void enterpairsSig(poly h, poly hSig, int from, int k, int ec, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4535
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition: kutil.cc:13028
KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin)
Definition: kInline.h:959
void initBba(kStrategy strat)
Definition: kstd1.cc:1689
void exitBuchMora(kStrategy strat)
Definition: kutil.cc:9885
void messageStatSBA(int hilbcount, kStrategy strat)
Definition: kutil.cc:7566
int redRiloc(LObject *h, kStrategy strat)
Definition: kstd1.cc:387
void initEcartNormal(TObject *h)
Definition: kutil.cc:1304
static void kDeleteLcm(LObject *P)
Definition: kutil.h:880
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition: kutil.cc:4685
void updateS(BOOLEAN toT, kStrategy strat)
Definition: kutil.cc:8594
int posInL0(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5643
int redSigRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:1511
int * intset
Definition: kutil.h:53
void initSLSba(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7826
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart=LONG_MAX)
Definition: kutil.cc:6740
void enterSBbaShift(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kutil.cc:8929
void initSba(ideal F, kStrategy strat)
Definition: kstd1.cc:1747
int ksReducePolyTail(LObject *PR, TObject *PW, poly Current, poly spNoether=NULL)
Definition: kspoly.cc:1357
void initSyzRules(kStrategy strat)
Definition: kutil.cc:7976
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10013
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10534
void cleanT(kStrategy strat)
Definition: kutil.cc:565
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:1061
int posInT110(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5053
BOOLEAN kTest_S(kStrategy strat)
Definition: kutil.cc:1055
KINLINE TObject ** initR()
Definition: kInline.h:95
void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat)
Definition: kutil.cc:9087
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition: kstd2.cc:2325
void reorderS(int *suc, kStrategy strat)
Definition: kutil.cc:4632
KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether=NULL)
Definition: kInline.h:1176
void enterExtendedSpoly(poly h, kStrategy strat)
Definition: kutil.cc:4249
void enterpairs(poly h, int k, int ec, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4509
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR=-1)
Definition: kutil.cc:4478
int redSig(LObject *h, kStrategy strat)
Definition: kstd2.cc:1343
KINLINE poly redtailBba_Z(poly p, int end_pos, kStrategy strat)
Definition: kInline.h:1232
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether=NULL)
Definition: kInline.h:1186
int posInL10(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kstd1.cc:1365
KINLINE poly redtailBba(poly p, int end_pos, kStrategy strat, BOOLEAN normalize=FALSE)
Definition: kInline.h:1214
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition: kutil.cc:10128
int posInT0(const TSet set, const int length, LObject &p)
Definition: kutil.cc:4907
#define KINLINE
Definition: kutil.h:49
int posInT19(const TSet set, const int length, LObject &p)
Definition: kutil.cc:5542
poly redtailBba_NF(poly p, kStrategy strat)
Definition: kutil.cc:7398
void exitSba(kStrategy strat)
Definition: kutil.cc:10088
ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1)
Definition: kutil.cc:11142
BOOLEAN enterOnePairShift(poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS)
Definition: kutil.cc:12234
void enterSSba(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kutil.cc:8952
void kDebugPrint(kStrategy strat)
Output some debug info about a given strategy.
Definition: kutil.cc:11560
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:4296
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1215
void initHilbCrit(ideal F, ideal Q, intvec **hilb, kStrategy strat)
Definition: kutil.cc:9458
KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether=NULL, ring r=currRing)
Definition: kInline.h:1196
void kStratInitChangeTailRing(kStrategy strat)
Definition: kutil.cc:11114
BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.cc:6664
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9476
void initBuchMoraPosRing(kStrategy strat)
Definition: kutil.cc:9713
poly kNF2Bound(ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
Definition: kstd2.cc:4049
int kFindInTShift(poly p, TSet T, int tlength)
Definition: kutil.cc:743
void postReduceByMonSig(LObject *h, kStrategy strat)
Definition: kutil.cc:10839
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:1208
int posInL11Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5876
void enterSBba(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition: kutil.cc:8829
void messageSets(kStrategy strat)
Definition: kutil.cc:7585
int redRing(LObject *h, kStrategy strat)
Definition: kstd2.cc:954
void deleteInS(int i, kStrategy strat)
Definition: kutil.cc:1139
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition: kutil.cc:11489
BOOLEAN sbaCheckGcdPair(LObject *h, kStrategy strat)
Definition: kutil.cc:1700
int posInL110(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:6093
poly redtail(poly p, int end_pos, kStrategy strat)
Definition: kutil.cc:6953
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:1326
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:3217
void initEcartBBA(TObject *h)
Definition: kutil.cc:1312
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:1239
ideal bbaShift(ideal F, ideal Q, intvec *w, intvec *hilb, kStrategy strat)
Definition: kstd2.cc:4608
int posInLF5CRing(const LSet set, int start, const int length, LObject *L, const kStrategy strat)
Definition: kutil.cc:5910
int ksReducePolyZ(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
poly redNFTail(poly h, const int sl, kStrategy strat)
poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing)
Definition: kspoly.cc:1453
void messageStat(int hilbcount, kStrategy strat)
Definition: kutil.cc:7553
int redHoneyM(LObject *h, kStrategy strat)
void initSL(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7729
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:1018
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition: kutil.cc:10928
BOOLEAN kTest_T(TObject *T, kStrategy strat, int tpos=-1, char TN='?')
Definition: kutil.cc:801
void initSbaCrit(kStrategy strat)
Definition: kutil.cc:9541
BOOLEAN newHEdge(kStrategy strat)
Definition: kutil.cc:10462
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:1761
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition: kutil.cc:6605
KINLINE unsigned long * initsevT()
Definition: kInline.h:100
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
Definition: lq.h:40
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define NULL
Definition: omList.c:12
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
Compatibility 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
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 rField_is_Ring(R)
Definition: ring.h:485
#define R
Definition: sirandom.c:27
#define Q
Definition: sirandom.c:26
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027