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#include "coeffs/bigintmat.h" /* for s_poly_proc_t */
26
27// define if tailrings should be used
28#define HAVE_TAIL_RING
29
30#define setmax 128
31#define setmaxL ((int)((4096-12)/sizeof(LObject)))
32#define setmaxLinc ((int)((4096)/sizeof(LObject)))
33
34#define setmaxT ((int)((4096-12)/sizeof(TObject)))
35#define setmaxTinc ((int)((4096)/sizeof(TObject)))
36
37#define RED_CANONICALIZE 200
38#define REDNF_CANONICALIZE 60
39#define REDTAIL_CANONICALIZE 100
40
41// if you want std computations as in Singular version < 2:
42// This disables RedThrough, tailReductions against T (bba),
43// sets posInT = posInT15 (bba, strat->honey), and enables redFirst with LDeg
44// NOTE: can be achieved with option(oldStd)
45
46#undef NO_KINLINE
47#if !defined(KDEBUG) && !defined(NO_INLINE)
48#define KINLINE inline
49#else
50#define KINLINE
51#define NO_KINLINE 1
52#endif
53
54typedef int* intset;
57
58typedef class sTObject TObject;
59typedef class sLObject LObject;
60typedef TObject * TSet;
61typedef LObject * LSet;
62
65
68
70{
71public:
72 unsigned long sevSig;
73 poly sig; // the signature of the element
74 poly p; // Lm(p) \in currRing Tail(p) \in tailRing
75 poly t_p; // t_p \in tailRing: as monomials Lm(t_p) == Lm(p)
76 poly max_exp; // p_GetMaxExpP(pNext(p))
78 long FDeg; // pFDeg(p)
79 int ecart,
80 length, // as of pLDeg
81 pLength, // either == 0, or == pLength(p)
82 i_r; // index of TObject in R set, or -1 if not in T
83
84#ifdef HAVE_SHIFTBBA
85 int shift;
86#endif
87
88 /*BOOLEAN*/ char is_normalized; // true, if pNorm was called on p, false otherwise
89 // used in incremental sba() with F5C:
90 // we know some of the redundant elements in
91 // strat->T beforehand, so we can just discard
92 // them and do not need to consider them in the
93 // interreduction process
94 /*BOOLEAN*/ char is_redundant;
95 // used in sba's sig-safe reduction:
96 // sometimes we already know that a reducer
97 // is sig-safe, so no need for a real
98 // sig-safeness check
99 /*BOOLEAN*/ char is_sigsafe;
100
101
102#ifdef HAVE_PLURAL
103 /*BOOLEAN*/ char is_special; // true, it is a new special S-poly (e.g. for SCA)
104#endif
105
106 // initialization
107 KINLINE void Init(ring r = currRing);
109 KINLINE sTObject(poly p, ring tailRing = currRing);
110 KINLINE sTObject(poly p, ring c_r, ring tailRing);
112
113 KINLINE void Set(ring r=currRing);
114 KINLINE void Set(poly p_in, ring r=currRing);
115 KINLINE void Set(poly p_in, ring c_r, ring t_r);
116
117 // Frees the polys of T
118 KINLINE void Delete();
119 // Sets polys to NULL
120 KINLINE void Clear();
121 // makes a copy of the poly of T
122 KINLINE void Copy();
123
124 // ring-dependent Lm access: these might result in allocation of monomials
125 KINLINE poly GetLmCurrRing();
126 KINLINE poly GetLmTailRing();
127 KINLINE poly GetLm(ring r);
128 // this returns Lm and ring r (preferably from tailRing), but does not
129 // allocate a new poly
130 KINLINE void GetLm(poly &p, ring &r) const;
131
132#ifdef OLIVER_PRIVAT_LT
133 // routines for calc. with rings
134 KINLINE poly GetLtCurrRing();
135 KINLINE poly GetLtTailRing();
136 KINLINE poly GetLt(ring r);
137 KINLINE void GetLt(poly &p, ring &r) const;
138#endif
139
140 KINLINE BOOLEAN IsNull() const;
141
142 KINLINE int GetpLength();
143
144 // makes sure that T.p exists
145 KINLINE void SetLmCurrRing();
146
147 // Iterations
148 // simply get the next monomial
149 KINLINE poly Next();
151
152 // deg stuff
153 // compute pTotalDegree
154 KINLINE long pTotalDeg() const;
155 // computes pFDeg
156 KINLINE long pFDeg() const;
157 // computes and sets FDeg
158 KINLINE long SetpFDeg();
159 // gets stored FDeg
160 KINLINE long GetpFDeg() const;
161
162 // computes pLDeg
163 KINLINE long pLDeg();
164 // sets length, FDeg, returns LDeg
166
167 // arithmetic
168 KINLINE void Mult_nn(number n);
169 KINLINE void ShallowCopyDelete(ring new_tailRing, omBin new_tailBin,
170 pShallowCopyDeleteProc p_shallow_copy_delete,
171 BOOLEAN set_max = TRUE);
172 // manipulations
173 KINLINE void pNorm();
174 KINLINE void pCleardenom();
175 KINLINE void pContent();
176
177#ifdef KDEBUG
178 void wrp();
179#endif
180};
181
183
184class sLObject : public sTObject
185{
186
187public:
188 unsigned long sev;
189 poly p1,p2; /*- the pair p comes from,
190 lm(pi) in currRing, tail(pi) in tailring -*/
191
192 poly lcm; /*- the lcm of p1,p2 -*/
194 int i_r1, i_r2;
195 unsigned checked; // this is the index of S up to which
196 // the corresponding LObject was already checked in
197 // critical pair creation => when entering the
198 // reduction process it is enough to start a second
199 // rewritten criterion check from checked+1 onwards
201 // NOTE: If prod_crit = TRUE then the corresponding pair is
202 // detected by Buchberger's Product Criterion and can be
203 // deleted
204
205 // initialization
206 KINLINE void Init(ring tailRing = currRing);
208 KINLINE sLObject(poly p, ring tailRing = currRing);
209 KINLINE sLObject(poly p, ring c_r, ring tailRing);
210
211 // Frees the polys of L
212 KINLINE void Delete();
213 KINLINE void Clear();
214
215 // Iterations
218
219 // spoly related things
220 // preparation for reduction if not spoly
221 KINLINE void PrepareRed(BOOLEAN use_bucket);
222 KINLINE void SetLmTail(poly lm, poly new_p, int length,
223 int use_bucket, ring r);
224 KINLINE void Tail_Minus_mm_Mult_qq(poly m, poly qq, int lq, poly spNoether);
225 KINLINE void Tail_Mult_nn(number n);
226 // deletes bucket, makes sure that p and t_p exists
227 KINLINE poly GetP(omBin lmBin = (omBin)NULL);
228 // similar, except that only t_p exists
229 KINLINE poly GetTP();
230
231 // does not delete bucket, just canonicalizes it
232 // returned poly is such that Lm(p) \in currRing, Tail(p) \in tailRing
233 KINLINE void CanonicalizeP();
234
235 // makes a copy of the poly of L
236 KINLINE void Copy();
237
238 KINLINE int GetpLength();
239 KINLINE long pLDeg(BOOLEAN use_last);
240 KINLINE long pLDeg();
241 KINLINE int SetLength(BOOLEAN lengt_pLength = FALSE);
244
245 // returns minimal component of p
246 KINLINE long MinComp();
247 // returns component of p
248 KINLINE long Comp();
249
250 KINLINE void ShallowCopyDelete(ring new_tailRing,
251 pShallowCopyDeleteProc p_shallow_copy_delete);
252
253 // sets sev
255
256 // enable assignment from TObject
258
259 // get T's corresponding to p1, p2: they might return NULL
260 KINLINE TObject* T_1(const skStrategy* strat);
261 KINLINE TObject* T_2(const skStrategy* strat);
262 KINLINE void T_1_2(const skStrategy* strat,
263 TObject* &T_1, TObject* &T_2);
264
265 // simplify coefficients
266 KINLINE void Normalize();
267 KINLINE void HeadNormalize();
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;
331 poly t_kNoether; // same polys in tailring
332 KINLINE poly kNoetherTail();
334 BOOLEAN * pairtest;/*used for enterOnePair*/
335 poly tail;
338 // procedure for ShalloCopy from tailRing to currRing
340 // pointers to Tobjects R[i] is ith Tobject which is generated
342 // S_2_R[i] yields Tobject which corresponds to S[i]
343 int* S_2_R;
347 int nr;
348 int cp,c3;
349 int sl,mu;
351 int tl,tmax;
352 int Ll,Lmax;
353 int Bl,Bmax;
358 int minim;
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 #ifdef HAVE_SHIFTBBA
367 int cv; // in shift bases: counting V criterion
368 /*BOOLEAN*/ char rightGB;
369 #endif
370 /*BOOLEAN*/ char interpt;
371 /*BOOLEAN*/ char homog;
372#ifdef HAVE_PLURAL
373 /*BOOLEAN*/ char z2homog; // Z_2 - homogeneous input allows product criterion in commutative and SCA cases!
374#endif
375 /*BOOLEAN*/ char kAllAxis; // all axis are used -> (re)compute noether
376 /*BOOLEAN*/ char honey,sugarCrit;
377 /*BOOLEAN*/ char Gebauer,noTailReduction;
378 /*BOOLEAN*/ char fromT;
379 /*BOOLEAN*/ char noetherSet;
380 /*BOOLEAN*/ char update;
381 /*BOOLEAN*/ char posInLOldFlag;
382 /*BOOLEAN*/ char use_buckets;
383 // if set, pLDeg(p, l) == (pFDeg(pLast(p), pLength)
384 /*BOOLEAN*/ char LDegLast;
385 // if set, then L.length == L.pLength
386 /*BOOLEAN*/ char length_pLength;
387 // if set, then posInL does not depend on L.length
388 /*BOOLEAN*/ char posInLDependsOnLength;
389 /*FALSE, if posInL == posInL10*/
390#ifdef HAVE_PLURAL
391 // set this flag to 1 to stop the product criteria
392 // use ALLOW_PROD_CRIT(strat) to test
393 /*BOOLEAN*/ char no_prod_crit;
394#define ALLOW_PROD_CRIT(A) (!(A)->no_prod_crit)
395#else
396#define ALLOW_PROD_CRIT(A) (1)
397#endif
399 char news;
400 char newt;/*used for messageSets*/
404
405 skStrategy();
406 ~skStrategy();
407
408 // return TObject corresponding to S[i]: assume that it exists
409 // i.e. no error checking is done
410 KINLINE TObject* S_2_T(int i);
411 // like S_2_T, except that NULL is returned if it can not be found
412 KINLINE TObject* s_2_t(int i);
413};
414
415void deleteHC(poly *p, int *e, int *l, kStrategy strat);
416void deleteHC(LObject* L, kStrategy strat, BOOLEAN fromNext = FALSE);
417void deleteInS (int i,kStrategy strat);
418void cleanT (kStrategy strat);
419static inline LSet initL (int nr=setmaxL)
420{ return (LSet)omAlloc(nr*sizeof(LObject)); }
421void deleteInL(LSet set, int *length, int j,kStrategy strat);
422void enterL (LSet *set,int *length, int *LSetmax, LObject p,int at);
423void enterSBba (LObject &p,int atS,kStrategy strat, int atR = -1);
424void enterSBbaShift (LObject &p,int atS,kStrategy strat, int atR = -1);
425void enterSSba (LObject &p,int atS,kStrategy strat, int atR = -1);
426void initEcartPairBba (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
427void initEcartPairMora (LObject* Lp,poly f,poly g,int ecartF,int ecartG);
428int posInS (const kStrategy strat, const int length, const poly p,
429 const int ecart_p);
430int posInSMonFirst (const kStrategy strat, const int length, const poly p);
431int posInIdealMonFirst (const ideal F, const poly p,int start = 0,int end = -1);
432int posInT0 (const TSet set,const int length,LObject &p);
433int posInT1 (const TSet set,const int length,LObject &p);
434int posInT2 (const TSet set,const int length,LObject &p);
435int posInT11 (const TSet set,const int length,LObject &p);
436int posInTSig (const TSet set,const int length,LObject &p);
437int posInT110 (const TSet set,const int length,LObject &p);
438int posInT13 (const TSet set,const int length,LObject &p);
439int posInT15 (const TSet set,const int length,LObject &p);
440int posInT17 (const TSet set,const int length,LObject &p);
441int posInT17_c (const TSet set,const int length,LObject &p);
442int posInT19 (const TSet set,const int length,LObject &p);
443int posInT_EcartpLength(const TSet set,const int length,LObject &p);
444int posInT_EcartFDegpLength(const TSet set,const int length,LObject &p);
445int posInT_FDegpLength(const TSet set,const int length,LObject &p);
446int posInT_pLength(const TSet set,const int length,LObject &p);
447
448#ifdef HAVE_MORE_POS_IN_T
449int posInT_EcartFDegpLength(const TSet set,const int length,LObject &p);
450int posInT_FDegpLength(const TSet set,const int length,LObject &p);
451int posInT_pLength(const TSet set,const int length,LObject &p);
452#endif
453
454
455void reorderS (int* suc,kStrategy strat);
456int posInLF5C (const LSet set, const int length,
457 LObject* L,const kStrategy strat);
458int posInLSig (const LSet set, const int length,
459 LObject* L,const kStrategy strat);
460int posInLSigRing (const LSet set, const int length,
461 LObject* L,const kStrategy strat);
462int posInSyz (const kStrategy strat, const poly sig);
463int posInL0 (const LSet set, const int length,
464 LObject* L,const kStrategy strat);
465int posInL11 (const LSet set, const int length,
466 LObject* L,const kStrategy strat);
467int posInL11Ring (const LSet set, const int length,
468 LObject* L,const kStrategy strat);
469int posInLF5CRing (const LSet set, int start , const int length,
470 LObject* L,const kStrategy strat);
471int posInL11Ringls (const LSet set, const int length,
472 LObject* L,const kStrategy strat);
473int posInL13 (const LSet set, const int length,
474 LObject* L,const kStrategy strat);
475int posInL15 (const LSet set, const int length,
476 LObject* L,const kStrategy strat);
477int posInL15Ring (const LSet set, const int length,
478 LObject* L,const kStrategy strat);
479int posInL17 (const LSet set, const int length,
480 LObject* L,const kStrategy strat);
481int posInL10 (const LSet set, const int length,
482 LObject* L,const kStrategy strat);
483int posInL10Ring (const LSet set, const int length,
484 LObject* L,const kStrategy strat);
485int posInL110 (const LSet set, const int length,
486 LObject* L,const kStrategy strat);
487KINLINE poly redtailBba (poly p,int end_pos,kStrategy strat,BOOLEAN normalize=FALSE);
488KINLINE poly redtailBbaBound (poly p,int end_pos,kStrategy strat,int bound,BOOLEAN normalize=FALSE);
489KINLINE poly redtailBba_Ring (poly p,int end_pos,kStrategy strat);
490KINLINE poly redtailBba_Z (poly p,int end_pos,kStrategy strat);
491poly redtailBba_NF (poly p, kStrategy strat );
492poly redtailBba_Ring (LObject* L, int end_pos, kStrategy strat );
493poly redtailBba_Z (LObject* L, int end_pos, kStrategy strat );
494void redtailBbaAlsoLC_Z (LObject* L, int end_pos, kStrategy strat );
495poly redtailBba (LObject *L, int end_pos,kStrategy strat,
497poly redtailBbaBound (LObject *L, int end_pos,kStrategy strat,int bound,
499poly redtailSba (LObject *L, int end_pos,kStrategy strat,
501poly redtailBba (TObject *T, int end_pos,kStrategy strat);
502poly redtail (poly p,int end_pos,kStrategy strat);
503poly redtail (LObject *L,int end_pos,kStrategy strat);
504poly redNF (poly h,int & max_ind,int nonorm,kStrategy strat);
505int redNF0 (LObject *P,kStrategy strat);
506poly redNFTail (poly h,const int sl,kStrategy strat);
507int redHoney (LObject* h, kStrategy strat);
509int redLiftstd (LObject* h, kStrategy strat);
510int redRing (LObject* h,kStrategy strat);
511int redRing_Z (LObject* h,kStrategy strat);
512int redRiloc (LObject* h,kStrategy strat);
513void enterExtendedSpoly(poly h,kStrategy strat);
514void enterExtendedSpolySig(poly h,poly hSig,kStrategy strat);
515void superenterpairs (poly h,int k,int ecart,int pos,kStrategy strat, int atR = -1);
516void superenterpairsSig (poly h,poly hSig,int hFrom,int k,int ecart,int pos,kStrategy strat, int atR = -1);
517int redLazy (LObject* h,kStrategy strat);
518int redHomog (LObject* h,kStrategy strat);
519int redSig (LObject* h,kStrategy strat);
520int redSigRing (LObject* h,kStrategy strat);
521//adds hSig to be able to check with F5's criteria when entering pairs!
522void enterpairsSig (poly h, poly hSig, int from, int k, int ec, int pos,kStrategy strat, int atR = -1);
523void enterpairs (poly h, int k, int ec, int pos,kStrategy strat, int atR = -1);
525void pairs ();
527void message (int i,int* reduc,int* olddeg,kStrategy strat,int red_result);
528void messageStat (int hilbcount,kStrategy strat);
529void messageStatSBA (int hilbcount,kStrategy strat);
530#ifdef KDEBUG
531void messageSets (kStrategy strat);
532#else
533#define messageSets(s) do {} while (0)
534#endif
535
537void initEcartBBA (TObject* h);
538void initS (ideal F, ideal Q,kStrategy strat);
539void initSL (ideal F, ideal Q,kStrategy strat);
540void initSLSba (ideal F, ideal Q,kStrategy strat);
541/*************************************************
542 * when initializing a new bunch of principal
543 * syzygies at the beginning of a new iteration
544 * step in a signature-based algorithm we
545 * compute ONLY the leading elements of those
546 * syzygies, NOT the whole syzygy
547 * NOTE: this needs to be adjusted for a more
548 * general approach on signature-based algorithms
549 ***********************************************/
550void initSyzRules (kStrategy strat);
551void updateS(BOOLEAN toT,kStrategy strat);
552void enterSyz (LObject &p,kStrategy strat, int atT);
553void enterT (LObject &p,kStrategy strat, int atT = -1);
554void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat);
555void enterT_strong (LObject &p,kStrategy strat, int atT = -1);
556void cancelunit (LObject* p,BOOLEAN inNF=FALSE);
557void HEckeTest (poly pp,kStrategy strat);
558void initBuchMoraCrit(kStrategy strat);
559void initSbaCrit(kStrategy strat);
560void initHilbCrit(ideal F, ideal Q, bigintmat **hilb,kStrategy strat);
561void initBuchMoraPos(kStrategy strat);
563void initSbaPos(kStrategy strat);
564void initBuchMora (ideal F, ideal Q,kStrategy strat);
565void initSbaBuchMora (ideal F, ideal Q,kStrategy strat);
566void exitBuchMora (kStrategy strat);
567void exitSba (kStrategy strat);
568void updateResult(ideal r,ideal Q,kStrategy strat);
569void completeReduce (kStrategy strat, BOOLEAN withT=FALSE);
571void enterOnePairNormal (int i,poly p,int ecart, int isFromQ,kStrategy strat, int atR);
572void chainCritNormal (poly p,int ecart,kStrategy strat);
573void chainCritOpt_1 (poly,int,kStrategy strat);
574void chainCritSig (poly p,int ecart,kStrategy strat);
577BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat);
578BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat);
579KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
580BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
581BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
582BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start);
583BOOLEAN findMinLMPair(poly sig, unsigned long not_sevSig, kStrategy strat, int start);
584
585/// returns index of p in TSet, or -1 if not found
586int kFindInT(poly p, TSet T, int tlength);
587#ifdef HAVE_SHIFTBBA
588int kFindInTShift(poly p, TSet T, int tlength);
589#endif
590
591/// return -1 if no divisor is found
592/// number of first divisor in T, otherwise
593int kFindDivisibleByInT(const kStrategy strat, const LObject* L, const int start=0);
594int kFindDivisibleByInT_ecart(const kStrategy strat, const LObject* L, const int ecart);
595int kFindDivisibleByInT_Z(const kStrategy strat, const LObject* L, const int start=0);
596int kFindSameLMInT_Z(const kStrategy strat, const LObject* L, const int start=0);
597
598/// tests if T[0] divides the leading monomial of L, returns -1 if not
599int kTestDivisibleByT0_Z(const kStrategy strat, const LObject* L);
600/// return -1 if no divisor is found
601/// number of first divisor in S, otherwise
602int kFindDivisibleByInS(const kStrategy strat, int *max_ind, LObject* L);
603
604int kFindNextDivisibleByInS(const kStrategy strat, int start,int max_ind, LObject* L);
605TObject* kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject* L, TObject *T, long ecart = LONG_MAX);
606
607/***************************************************************
608 *
609 * stuff to be inlined
610 *
611 ***************************************************************/
612
615KINLINE unsigned long* initsevT();
616KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
617KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
618KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin);
619KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing, omBin bin);
620
621KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing);
622KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing);
623KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing);
624KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing);
625
626// if exp bound is not violated, return TRUE and
627// get m1 = LCM(LM(p1), LM(p2))/LM(p1)
628// m2 = LCM(LM(p1), LM(p2))/LM(p2)
629// return FALSE and m1 == NULL, m2 == NULL , otherwise
630KINLINE BOOLEAN k_GetLeadTerms(const poly p1, const poly p2, const ring p_r,
631 poly &m1, poly &m2, const ring m_r);
632KINLINE void k_GetStrongLeadTerms(const poly p1, const poly p2, const ring leadRing,
633 poly &m1, poly &m2, poly &lcm, const ring taiRing);
634#ifdef KDEBUG
635// test strat
636BOOLEAN kTest(kStrategy strat);
637// test strat, and test that S is contained in T
639// test LObject
641 BOOLEAN testp = FALSE, int lpos = -1,
642 TSet T = NULL, int tlength = -1);
643// test TObject
644BOOLEAN kTest_T(TObject* T, kStrategy strat, int tpos = -1, char TN = '?');
645// test set strat->SevS
647#else
648#define kTest(A) (TRUE)
649#define kTest_TS(A) (TRUE)
650#define kTest_T(T,S) (TRUE)
651#define kTest_S(T) (TRUE)
652#define kTest_L(T,R) (TRUE)
653#endif
654
655
656/***************************************************************
657 *
658 * From kstd2.cc
659 *
660 ***************************************************************/
661poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing);
662ideal bba (ideal F, ideal Q,intvec *w,bigintmat *hilb,kStrategy strat);
663ideal sba (ideal F, ideal Q,intvec *w,bigintmat *hilb,kStrategy strat);
664poly kNF2 (ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce);
665ideal kNF2 (ideal F,ideal Q,ideal q, kStrategy strat, int lazyReduce);
666poly kNF2Bound (ideal F, ideal Q, poly q,int bound, kStrategy strat, int lazyReduce);
667ideal kNF2Bound (ideal F,ideal Q,ideal q,int bound, kStrategy strat, int lazyReduce);
668void initBba(kStrategy strat);
669void initSba(ideal F,kStrategy strat);
670void f5c (kStrategy strat, int& olddeg, int& minimcnt, int& hilbeledeg,
671 int& hilbcount, int& srmax, int& lrmax, int& reduc, ideal Q,
672 intvec *w,bigintmat *hilb );
673
674/***************************************************************
675 *
676 * From kspoly.cc
677 *
678 ***************************************************************/
679// Reduces PR with PW
680// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
681// Changes: PR
682// Const: PW
683// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
684// If strat != NULL, tailRing is changed if reduction would violate exp bound
685// of tailRing
686// Returns: 0 everything ok, no tailRing change
687// 1 tailRing has successfully changed (strat != NULL)
688// 2 no reduction performed, tailRing needs to be changed first
689// (strat == NULL)
690// -1 tailRing change could not be performed due to exceeding exp
691// bound of currRing
692// reduce should be set inside "kNF" (only relevant for rings)
693int ksReducePoly(LObject* PR,
694 TObject* PW,
695 poly spNoether = NULL,
696 number *coef = NULL,
697 poly *mon =NULL,
698 kStrategy strat = NULL,
700
701/* like ksReducePoly, but if the reducer has only 1 term we still
702 * compute a possible coefficient multiplier for PR. this comes from
703 * a special situation in redRing_Z and it is used only there. */
705 TObject* PW,
706 poly spNoether = NULL,
707 number *coef = NULL,
708 kStrategy strat = NULL);
709
710int ksReducePolyLC(LObject* PR,
711 TObject* PW,
712 poly spNoether = NULL,
713 number *coef = NULL,
714 kStrategy strat = NULL);
715
716
718 TObject* PW,
719 poly spNoether = NULL,
720 number *coef = NULL,
721 kStrategy strat = NULL);
722
724 TObject* PW,
725 int bound,
726 poly spNoether = NULL,
727 number *coef = NULL,
728 kStrategy strat = NULL);
729
730// Reduces PR with PW
731// Assumes PR != NULL, PW != NULL, Lm(PW) divides Lm(PR)
732// Changes: PR
733// Const: PW
734// If coef != NULL, then *coef is a/gcd(a,b), where a = LC(PR), b = LC(PW)
735// If strat != NULL, tailRing is changed if reduction would violate exp bound
736// of tailRing
737// Returns: 0 everything ok, no tailRing change
738// 1 tailRing has successfully changed (strat != NULL)
739// 2 no reduction performed, tailRing needs to be changed first
740// (strat == NULL)
741// 3 no reduction performed, not sig-safe!!!
742// -1 tailRing change could not be performed due to exceeding exp
743// bound of currRing
745 TObject* PW,
746 long idx,
747 poly spNoether = NULL,
748 number *coef = NULL,
749 kStrategy strat = NULL);
750
752 TObject* PW,
753 long idx,
754 poly spNoether = NULL,
755 number *coef = NULL,
756 kStrategy strat = NULL);
757
758// Reduces PR at Current->next with PW
759// Assumes PR != NULL, Current contained in PR
760// Current->next != NULL, LM(PW) divides LM(Current->next)
761// Changes: PR
762// Const: PW
763// Return: see ksReducePoly
765 TObject* PW,
766 poly Current,
767 poly spNoether = NULL);
768
770
771// Creates S-Poly of Pair
772// Const: Pair->p1, Pair->p2
773// Changes: Pair->p == S-Poly of p1, p2
774// Assume: Pair->p1 != NULL && Pair->p2
775void ksCreateSpoly(LObject* Pair, poly spNoether = NULL,
776 int use_buckets=0, ring tailRing=currRing,
777 poly m1 = NULL, poly m2 = NULL, TObject** R = NULL);
778
779/*2
780* creates the leading term of the S-polynomial of p1 and p2
781* do not destroy p1 and p2
782* remarks:
783* 1. the coefficient is 0 (nNew)
784* 2. pNext is undefined
785*/
786poly ksCreateShortSpoly(poly p1, poly p2, ring tailRing);
787
788
789// old stuff
790KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether = NULL);
791KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether = NULL);
792KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether = NULL, ring r = currRing);
793KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r = currRing);
794
795/***************************************************************
796 *
797 * Routines related for ring changes during std computations
798 *
799 ***************************************************************/
800// return TRUE and set m1, m2 to k_GetLcmTerms,
801// if spoly creation of strat->P does not violate
802// exponent bound of strat->tailRing
803// FALSE, otherwise
804BOOLEAN kCheckSpolyCreation(LObject* L, kStrategy strat, poly &m1, poly &m2);
805// return TRUE if gcdpoly creation of R[atR] and S[atS] does not violate
806// exponent bound of strat->tailRing
807// FALSE, otherwise
808BOOLEAN kCheckStrongCreation(int atR, poly m1, int atS, poly m2, kStrategy strat);
809poly preIntegerCheck(ideal F, ideal Q);
810void postReduceByMon(LObject* h, kStrategy strat);
812void finalReduceByMon(kStrategy strat);
813// change strat->tailRing and adjust all data in strat, L, and T:
814// new tailRing has larger exponent bound
815// do nothing and return FALSE if exponent bound increase would result in
816// larger exponent bound that that of currRing
818 LObject* L = NULL, TObject* T = NULL,
819 // take this as new_expbound: if 0
820 // new expbound is 2*expbound of tailRing
821 unsigned long new_expbound = 0);
822// initiate a change of the tailRing of strat -- should be called
823// right before main loop in bba
825
826/// Output some debug info about a given strategy
827void kDebugPrint(kStrategy strat);
828
829// getting sb order for sba computations
830ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1);
831
832KINLINE void clearS (poly p, unsigned long p_sev, int* at, int* k,
833 kStrategy strat);
834
836
837/* shiftgb stuff */
839
840#ifdef HAVE_SHIFTBBA
841static inline int kFindInL1(const poly p, const kStrategy strat)
842{
843 for(int i=strat->Ll;i>=0;i--)
844 {
845 if (p==strat->L[i].p1) return i;
846 }
847 return -1;
848}
849
850void enterTShift(LObject p, kStrategy strat, int atT = -1);
851
852BOOLEAN enterOnePairShift (poly q, poly p, int ecart, int isFromQ, kStrategy strat, int atR, int ecartq, int qisFromQ, int shiftcount, int ifromS);
853
854void enterpairsShift (poly h,int k,int ecart,int pos,kStrategy strat, int atR);
855
856void superenterpairsShift (poly h,int k,int ecart,int pos,kStrategy strat, int atR);
857
858poly redtailBbaShift (LObject* L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize);
859
860int redFirstShift (LObject* h,kStrategy strat); // ok
861
862ideal bbaShift(ideal F, ideal Q,intvec *w,bigintmat *hilb,kStrategy strat);
863#endif
864
865// test syz strategy: // will be removed soon
866EXTERN_VAR int (*test_PosInT)(const TSet T,const int tl,LObject &h);
867EXTERN_VAR int (*test_PosInL)(const LSet set, const int length,
868 LObject* L,const kStrategy strat);
869
870static inline void kDeleteLcm(LObject *P)
871{
872 if (P->lcm!=NULL)
873 {
875 pLmDelete(P->lcm);
876 else
877 pLmFree(P->lcm);
878 P->lcm=NULL;
879 }
880}
881
882void initenterpairs (poly h,int k,int ecart,int isFromQ,kStrategy strat, int atR = -1);
883#endif
int sgn(const Rational &a)
Definition GMPrat.cc:430
long int64
Definition auxiliary.h:68
int BOOLEAN
Definition auxiliary.h:88
#define TRUE
Definition auxiliary.h:101
#define FALSE
Definition auxiliary.h:97
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:4086
g
Definition cfModGcd.cc:4098
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
FILE * f
Definition checklibs.c:9
Matrices of numbers.
Definition bigintmat.h:51
KINLINE long SetDegStuffReturnLDeg()
Definition kInline.h:847
KINLINE void Tail_Mult_nn(number n)
Definition kInline.h:652
int i_r1
Definition kutil.h:194
KINLINE void Copy()
Definition kInline.h:800
KINLINE void Delete()
Definition kInline.h:585
KINLINE void LmDeleteAndIter()
Definition kInline.h:688
KINLINE TObject * T_2(const skStrategy *strat)
Definition kInline.h:918
KINLINE void PrepareRed(BOOLEAN use_bucket)
Definition kInline.h:616
unsigned checked
Definition kutil.h:195
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:634
KINLINE void T_1_2(const skStrategy *strat, TObject *&T_1, TObject *&T_2)
Definition kInline.h:929
KINLINE void Normalize()
Definition kInline.h:347
unsigned long sev
Definition kutil.h:188
KINLINE void Init(ring tailRing=currRing)
Definition kInline.h:592
KINLINE long MinComp()
Definition kInline.h:878
kBucket_pt bucket
Definition kutil.h:193
poly p2
Definition kutil.h:189
BOOLEAN prod_crit
Definition kutil.h:200
KINLINE TObject * T_1(const skStrategy *strat)
Definition kInline.h:908
KINLINE int GetpLength()
Definition kInline.h:861
KINLINE int SetLength(BOOLEAN lengt_pLength=FALSE)
Definition kInline.h:868
poly lcm
Definition kutil.h:192
KINLINE void Clear()
Definition kInline.h:578
KINLINE void Tail_Minus_mm_Mult_qq(poly m, poly qq, int lq, poly spNoether)
Definition kInline.h:666
KINLINE void ShallowCopyDelete(ring new_tailRing, pShallowCopyDeleteProc p_shallow_copy_delete)
Definition kInline.h:777
KINLINE poly GetTP()
Definition kInline.h:734
KINLINE long pLDeg()
Definition kInline.h:816
KINLINE sLObject & operator=(const sTObject &)
Definition kInline.h:902
KINLINE void SetShortExpVector()
Definition kInline.h:788
KINLINE void HeadNormalize()
Definition kInline.h:367
KINLINE poly GetP(omBin lmBin=(omBin) NULL)
Definition kInline.h:750
KINLINE sLObject(ring tailRing=currRing)
Definition kInline.h:600
poly p1
Definition kutil.h:189
KINLINE long Comp()
Definition kInline.h:893
KINLINE poly LmExtractAndIter()
Definition kInline.h:708
int i_r2
Definition kutil.h:194
KINLINE poly GetLm(ring r)
Definition kInline.h:262
KINLINE poly GetLmCurrRing()
Definition kInline.h:242
char is_redundant
Definition kutil.h:94
poly sig
Definition kutil.h:73
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:80
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:79
KINLINE long GetpFDeg() const
Definition kInline.h:437
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:381
char is_special
Definition kutil.h:103
KINLINE void SetLmCurrRing()
Definition kInline.h:299
poly max_exp
Definition kutil.h:76
char is_normalized
Definition kutil.h:88
KINLINE long pLDeg()
Definition kInline.h:442
char is_sigsafe
Definition kutil.h:99
KINLINE void LmDeleteAndIter()
Definition kInline.h:313
int pLength
Definition kutil.h:81
KINLINE long pFDeg() const
Definition kInline.h:422
int i_r
Definition kutil.h:82
poly p
Definition kutil.h:74
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:75
ring tailRing
Definition kutil.h:77
KINLINE int GetpLength()
Definition kInline.h:293
KINLINE void pNorm()
Definition kInline.h:558
KINLINE void Clear()
Definition kInline.h:213
long FDeg
Definition kutil.h:78
KINLINE poly Next()
Definition kInline.h:305
void wrp()
Definition kutil.cc:764
int shift
Definition kutil.h:85
KINLINE void pContent()
Definition kInline.h:536
KINLINE long pTotalDeg() const
Definition kInline.h:427
KINLINE long SetpFDeg()
Definition kInline.h:432
unsigned long sevSig
Definition kutil.h:72
KINLINE void Copy()
Definition kInline.h:224
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:336
bool sigdrop
Definition kutil.h:359
poly t_kNoether
Definition kutil.h:331
int syzComp
Definition kutil.h:355
int * S_2_R
Definition kutil.h:343
ring tailRing
Definition kutil.h:344
void(* chainCrit)(poly p, int ecart, kStrategy strat)
Definition kutil.h:292
ideal D
Definition kutil.h:305
char noTailReduction
Definition kutil.h:377
int currIdx
Definition kutil.h:318
int nrsyzcrit
Definition kutil.h:360
intset lenS
Definition kutil.h:320
int nrrewcrit
Definition kutil.h:361
char posInLOldFlag
Definition kutil.h:381
pFDegProc pOrigFDeg_TailRing
Definition kutil.h:299
int Ll
Definition kutil.h:352
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:399
omBin lmBin
Definition kutil.h:345
int syzmax
Definition kutil.h:350
int Bl
Definition kutil.h:353
intset ecartS
Definition kutil.h:310
int syzidxmax
Definition kutil.h:350
char honey
Definition kutil.h:376
char rightGB
Definition kutil.h:368
polyset S
Definition kutil.h:307
int minim
Definition kutil.h:358
poly kNoether
Definition kutil.h:330
BOOLEAN * NotUsedAxis
Definition kutil.h:333
LSet B
Definition kutil.h:329
BOOLEAN * pairtest
Definition kutil.h:334
int cp
Definition kutil.h:348
int ak
Definition kutil.h:354
TObject ** R
Definition kutil.h:341
BOOLEAN(* rewCrit3)(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.h:296
int lastAxis
Definition kutil.h:356
ideal M
Definition kutil.h:306
int tl
Definition kutil.h:351
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:347
intvec * kHomW
Definition kutil.h:337
int max_lower_index
Definition kutil.h:319
poly tail
Definition kutil.h:335
char sugarCrit
Definition kutil.h:376
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:364
intset syzIdx
Definition kutil.h:314
ideal Shdl
Definition kutil.h:304
int syzl
Definition kutil.h:350
unsigned sbaOrder
Definition kutil.h:317
pFDegProc pOrigFDeg
Definition kutil.h:297
int blockredmax
Definition kutil.h:365
int tmax
Definition kutil.h:351
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:384
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
char kAllAxis
Definition kutil.h:375
int cv
Definition kutil.h:367
char noetherSet
Definition kutil.h:379
pShallowCopyDeleteProc p_shallow_copy_delete
Definition kutil.h:339
char Gebauer
Definition kutil.h:377
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:400
char use_buckets
Definition kutil.h:382
int mu
Definition kutil.h:349
char interpt
Definition kutil.h:370
char redTailChange
Definition kutil.h:398
int newIdeal
Definition kutil.h:357
char fromT
Definition kutil.h:378
char completeReduce_retry
Definition kutil.h:402
void(* initEcart)(TObject *L)
Definition kutil.h:281
omBin tailBin
Definition kutil.h:346
LObject P
Definition kutil.h:303
KINLINE TObject * S_2_T(int i)
Definition kInline.h:38
char noClearS
Definition kutil.h:401
int Lmax
Definition kutil.h:352
char z2homog
Definition kutil.h:373
int LazyPass
Definition kutil.h:354
char no_prod_crit
Definition kutil.h:393
char overflow
Definition kutil.h:403
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:386
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:349
int sbaEnterS
Definition kutil.h:362
int LazyDegree
Definition kutil.h:354
char posInLDependsOnLength
Definition kutil.h:388
unsigned long * sevS
Definition kutil.h:323
char homog
Definition kutil.h:371
pLDegProc pOrigLDeg
Definition kutil.h:298
intset fromS
Definition kutil.h:311
char update
Definition kutil.h:380
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:353
int c3
Definition kutil.h:348
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:15
VAR int(* test_PosInL)(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kstd2.cc:83
VAR int(* test_PosInT)(const TSet T, const int tl, LObject &h)
Definition kstd2.cc:82
VAR int strat_nr
Definition kstdfac.cc:21
poly redtail(LObject *L, int end_pos, kStrategy strat)
Definition kutil.cc:6840
VAR int HCord
Definition kutil.cc:239
VAR denominator_list DENOMINATOR_LIST
Definition kutil.cc:79
int posInLF5C(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:5794
KINLINE void ksOldSpolyTail(poly p1, poly q, poly q2, poly spNoether, ring r=currRing)
Definition kInline.h:1201
void initSbaPos(kStrategy strat)
Definition kutil.cc:9864
void message(int i, int *reduc, int *olddeg, kStrategy strat, int red_result)
Definition kutil.cc:7467
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:477
void initenterpairs(poly h, int k, int ecart, int isFromQ, kStrategy strat, int atR=-1)
Definition kutil.cc:3816
int posInSyz(const kStrategy strat, const poly sig)
Definition kutil.cc:5765
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:590
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:724
int posInT17(const TSet set, const int length, LObject &p)
Definition kutil.cc:5285
int posInL13(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:6149
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9751
void initEcartPairBba(LObject *Lp, poly f, poly g, int ecartF, int ecartG)
Definition kutil.cc:1315
denominator_list_s * denominator_list
Definition kutil.h:64
wlen_type * wlen_set
Definition kutil.h:56
poly kFindZeroPoly(poly input_p, ring leadRing, ring tailRing)
Definition kstd2.cc:613
int redFirstShift(LObject *h, kStrategy strat)
Definition kstd2.cc:4974
BOOLEAN arriRewCriterionPre(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.cc:6650
void enterSyz(LObject &p, kStrategy strat, int atT)
Definition kutil.cc:9343
int posInL15(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:6184
int redNF0(LObject *P, kStrategy strat)
int posInT11(const TSet set, const int length, LObject &p)
Definition kutil.cc:4960
int posInLSigRing(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:5701
int ksReducePolySigRing(LObject *PR, TObject *PW, long idx, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition kspoly.cc:943
int posInTSig(const TSet set, const int length, LObject &p)
int posInT1(const TSet set, const int length, LObject &p)
Definition kutil.cc:4903
int ksReducePolySig(LObject *PR, TObject *PW, long idx, poly spNoether=NULL, number *coef=NULL, kStrategy strat=NULL)
Definition kspoly.cc:737
void enterT_strong(LObject &p, kStrategy strat, int atT=-1)
Definition kutil.cc:9242
BOOLEAN kTest(kStrategy strat)
Definition kutil.cc:1011
void chainCritSig(poly p, int ecart, kStrategy strat)
Definition kutil.cc:3468
int posInT_EcartpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:5153
BOOLEAN kTest_TS(kStrategy strat)
Definition kutil.cc:1074
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:468
int kFindInT(poly p, TSet T, int tlength)
returns index of p in TSet, or -1 if not found
Definition kutil.cc:710
BOOLEAN kCheckStrongCreation(int atR, poly m1, int atS, poly m2, kStrategy strat)
Definition kutil.cc:10519
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether=NULL, number *coef=NULL, poly *mon=NULL, kStrategy strat=NULL, BOOLEAN redtail=FALSE)
Definition kspoly.cc:187
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:923
TObject * TSet
Definition kutil.h:60
void enterL(LSet *set, int *length, int *LSetmax, LObject p, int at)
Definition kutil.cc:1276
int posInL17(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:6259
#define setmaxL
Definition kutil.h:31
void enterT(LObject &p, kStrategy strat, int atT=-1)
Definition kutil.cc:9143
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:12983
int posInT2(const TSet set, const int length, LObject &p)
Definition kutil.cc:4932
int posInL15Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:6219
void superenterpairsSig(poly h, poly hSig, int hFrom, int k, int ecart, int pos, kStrategy strat, int atR=-1)
Definition kutil.cc:4477
int posInT_pLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11471
void completeReduce(kStrategy strat, BOOLEAN withT=FALSE)
Definition kutil.cc:10287
void initHilbCrit(ideal F, ideal Q, bigintmat **hilb, kStrategy strat)
Definition kutil.cc:9417
void enterOnePairNormal(int i, poly p, int ecart, int isFromQ, kStrategy strat, int atR)
Definition kutil.cc:1946
static int kFindInL1(const poly p, const kStrategy strat)
Definition kutil.h:841
int posInT13(const TSet set, const int length, LObject &p)
Definition kutil.cc:5124
void redtailBbaAlsoLC_Z(LObject *L, int end_pos, kStrategy strat)
Definition kutil.cc:7144
poly kNF2(ideal F, ideal Q, poly q, kStrategy strat, int lazyReduce)
Definition kstd2.cc:3944
BOOLEAN syzCriterionInc(poly sig, unsigned long not_sevSig, kStrategy strat)
Definition kutil.cc:6517
void deleteHC(poly *p, int *e, int *l, kStrategy strat)
Definition kutil.cc:351
int kFindDivisibleByInT_ecart(const kStrategy strat, const LObject *L, const int ecart)
Definition kstd2.cc:420
int posInSMonFirst(const kStrategy strat, const int length, const poly p)
Definition kutil.cc:4771
KINLINE BOOLEAN arriRewDummy(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kInline.h:1255
void initBuchMoraPos(kStrategy strat)
Definition kutil.cc:9580
void initS(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7590
int posInIdealMonFirst(const ideal F, const poly p, int start=0, int end=-1)
Definition kutil.cc:4848
KINLINE poly redtailBbaBound(poly p, int end_pos, kStrategy strat, int bound, BOOLEAN normalize=FALSE)
Definition kInline.h:1215
int redHoney(LObject *h, kStrategy strat)
Definition kstd2.cc:2114
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:10540
KINLINE poly k_LmShallowCopyDelete_currRing_2_tailRing(poly p, ring tailRing, omBin bin)
Definition kInline.h:974
BOOLEAN kStratChangeTailRing(kStrategy strat, LObject *L=NULL, TObject *T=NULL, unsigned long new_expbound=0)
Definition kutil.cc:10961
int64 wlen_type
Definition kutil.h:55
int posInLSig(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:5676
KINLINE poly k_LmInit_tailRing_2_currRing(poly p, ring tailRing, omBin bin)
Definition kInline.h:965
int posInL11(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:5806
void chainCritOpt_1(poly, int, kStrategy strat)
Definition kutil.cc:3452
ideal sba(ideal F, ideal Q, intvec *w, bigintmat *hilb, kStrategy strat)
Definition kstd2.cc:2982
int kFindNextDivisibleByInS(const kStrategy strat, int start, int max_ind, LObject *L)
Definition kstd2.cc:571
static LSet initL(int nr=setmaxL)
Definition kutil.h:419
KINLINE TSet initT()
Definition kInline.h:84
void cancelunit(LObject *p, BOOLEAN inNF=FALSE)
Definition kutil.cc:365
int posInL11Ringls(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:5916
KINLINE poly k_LmShallowCopyDelete_tailRing_2_currRing(poly p, ring tailRing, omBin bin)
Definition kInline.h:981
KINLINE poly redtailBba_Ring(poly p, int end_pos, kStrategy strat)
Definition kInline.h:1221
int kFindDivisibleByInT_Z(const kStrategy strat, const LObject *L, const int start=0)
Definition kstd2.cc:213
LObject * LSet
Definition kutil.h:61
int redHomog(LObject *h, kStrategy strat)
Definition kstd2.cc:1154
int posInT17_c(const TSet set, const int length, LObject &p)
Definition kutil.cc:5391
poly redtailBbaShift(LObject *L, int pos, kStrategy strat, BOOLEAN withT, BOOLEAN normalize)
Definition kutil.cc:13006
denominator_list next
Definition kutil.h:66
int posInT_EcartFDegpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11380
int posInT15(const TSet set, const int length, LObject &p)
Definition kutil.cc:5191
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:10704
BOOLEAN syzCriterion(poly sig, unsigned long not_sevSig, kStrategy strat)
Definition kutil.cc:6482
void HEckeTest(poly pp, kStrategy strat)
Definition kutil.cc:493
int redLazy(LObject *h, kStrategy strat)
Definition kstd2.cc:1909
void enterExtendedSpolySig(poly h, poly hSig, kStrategy strat)
Definition kutil.cc:4323
void enterpairsSig(poly h, poly hSig, int from, int k, int ec, int pos, kStrategy strat, int atR=-1)
Definition kutil.cc:4520
void enterpairsShift(poly h, int k, int ecart, int pos, kStrategy strat, int atR)
Definition kutil.cc:12953
KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin bin)
Definition kInline.h:956
void initBba(kStrategy strat)
Definition kstd1.cc:1681
void exitBuchMora(kStrategy strat)
Definition kutil.cc:9838
void messageStatSBA(int hilbcount, kStrategy strat)
Definition kutil.cc:7521
int redRiloc(LObject *h, kStrategy strat)
Definition kstd1.cc:385
void initEcartNormal(TObject *h)
Definition kutil.cc:1300
static void kDeleteLcm(LObject *P)
Definition kutil.h:870
int posInS(const kStrategy strat, const int length, const poly p, const int ecart_p)
Definition kutil.cc:4670
void updateS(BOOLEAN toT, kStrategy strat)
Definition kutil.cc:8559
int posInL0(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:5618
int redSigRing(LObject *h, kStrategy strat)
Definition kstd2.cc:1540
int * intset
Definition kutil.h:54
void initSLSba(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7783
TObject * kFindDivisibleByInS_T(kStrategy strat, int end_pos, LObject *L, TObject *T, long ecart=LONG_MAX)
Definition kutil.cc:6701
void enterSBbaShift(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kutil.cc:8894
void initSba(ideal F, kStrategy strat)
Definition kstd1.cc:1741
int ksReducePolyTail(LObject *PR, TObject *PW, poly Current, poly spNoether=NULL)
Definition kspoly.cc:1350
void initSyzRules(kStrategy strat)
Definition kutil.cc:7935
void initSbaBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9966
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition kutil.cc:10481
void cleanT(kStrategy strat)
Definition kutil.cc:557
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:1057
int posInT110(const TSet set, const int length, LObject &p)
Definition kutil.cc:5036
BOOLEAN kTest_S(kStrategy strat)
Definition kutil.cc:1056
KINLINE TObject ** initR()
Definition kInline.h:95
void replaceInLAndSAndT(LObject &p, int tj, kStrategy strat)
Definition kutil.cc:9052
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition kstd2.cc:2315
ideal bbaShift(ideal F, ideal Q, intvec *w, bigintmat *hilb, kStrategy strat)
Definition kstd2.cc:4594
void reorderS(int *suc, kStrategy strat)
Definition kutil.cc:4617
KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether=NULL)
Definition kInline.h:1171
void enterExtendedSpoly(poly h, kStrategy strat)
Definition kutil.cc:4239
void enterpairs(poly h, int k, int ec, int pos, kStrategy strat, int atR=-1)
Definition kutil.cc:4494
void superenterpairs(poly h, int k, int ecart, int pos, kStrategy strat, int atR=-1)
Definition kutil.cc:4464
int redSig(LObject *h, kStrategy strat)
Definition kstd2.cc:1373
KINLINE poly redtailBba_Z(poly p, int end_pos, kStrategy strat)
Definition kInline.h:1226
KINLINE poly ksOldSpolyRedNew(poly p1, poly p2, poly spNoether=NULL)
Definition kInline.h:1181
int posInL10(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kstd1.cc:1360
KINLINE poly redtailBba(poly p, int end_pos, kStrategy strat, BOOLEAN normalize=FALSE)
Definition kInline.h:1209
void updateResult(ideal r, ideal Q, kStrategy strat)
Definition kutil.cc:10081
int posInT0(const TSet set, const int length, LObject &p)
Definition kutil.cc:4892
#define KINLINE
Definition kutil.h:50
int posInT19(const TSet set, const int length, LObject &p)
Definition kutil.cc:5517
poly redtailBba_NF(poly p, kStrategy strat)
Definition kutil.cc:7354
void exitSba(kStrategy strat)
Definition kutil.cc:10041
ring sbaRing(kStrategy strat, const ring r=currRing, BOOLEAN complete=TRUE, int sgn=1)
Definition kutil.cc:11086
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:12169
void enterSSba(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kutil.cc:8917
void kDebugPrint(kStrategy strat)
Output some debug info about a given strategy.
Definition kutil.cc:11505
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition kutil.cc:1215
KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether=NULL, ring r=currRing)
Definition kInline.h:1191
void kStratInitChangeTailRing(kStrategy strat)
Definition kutil.cc:11058
BOOLEAN arriRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.cc:6625
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9435
void initBuchMoraPosRing(kStrategy strat)
Definition kutil.cc:9665
poly kNF2Bound(ideal F, ideal Q, poly q, int bound, kStrategy strat, int lazyReduce)
Definition kstd2.cc:4032
int kFindInTShift(poly p, TSet T, int tlength)
Definition kutil.cc:735
void postReduceByMonSig(LObject *h, kStrategy strat)
Definition kutil.cc:10780
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:1203
int posInL11Ring(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:5848
void enterSBba(LObject &p, int atS, kStrategy strat, int atR=-1)
Definition kutil.cc:8794
void messageSets(kStrategy strat)
Definition kutil.cc:7540
int redRing(LObject *h, kStrategy strat)
Definition kstd2.cc:992
void deleteInS(int i, kStrategy strat)
Definition kutil.cc:1139
int posInT_FDegpLength(const TSet set, const int length, LObject &p)
Definition kutil.cc:11434
BOOLEAN sbaCheckGcdPair(LObject *h, kStrategy strat)
Definition kutil.cc:1695
int posInL110(const LSet set, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:6062
poly redtail(poly p, int end_pos, kStrategy strat)
Definition kutil.cc:6910
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:1322
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:3211
void initEcartBBA(TObject *h)
Definition kutil.cc:1308
class sTObject TObject
Definition kutil.h:58
ideal bba(ideal F, ideal Q, intvec *w, bigintmat *hilb, kStrategy strat)
Definition kstd2.cc:2622
KINLINE void clearS(poly p, unsigned long p_sev, int *at, int *k, kStrategy strat)
Definition kInline.h:1232
int posInLF5CRing(const LSet set, int start, const int length, LObject *L, const kStrategy strat)
Definition kutil.cc:5882
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:1446
void messageStat(int hilbcount, kStrategy strat)
Definition kutil.cc:7508
int redHoneyM(LObject *h, kStrategy strat)
void f5c(kStrategy strat, int &olddeg, int &minimcnt, int &hilbeledeg, int &hilbcount, int &srmax, int &lrmax, int &reduc, ideal Q, intvec *w, bigintmat *hilb)
Definition kstd2.cc:4282
void initSL(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7683
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:1015
void finalReduceByMon(kStrategy strat)
used for GB over ZZ: final reduction by constant elements background: any known constant element of i...
Definition kutil.cc:10869
BOOLEAN kTest_T(TObject *T, kStrategy strat, int tpos=-1, char TN='?')
Definition kutil.cc:796
void initSbaCrit(kStrategy strat)
Definition kutil.cc:9498
BOOLEAN newHEdge(kStrategy strat)
Definition kutil.cc:10409
BOOLEAN homogTest(polyset F, int Fmax)
class sLObject LObject
Definition kutil.h:59
poly redtailSba(LObject *L, int end_pos, kStrategy strat, BOOLEAN withT=FALSE, BOOLEAN normalize=FALSE)
Definition kstd2.cc:1789
BOOLEAN faugereRewCriterion(poly sig, unsigned long not_sevSig, poly lm, kStrategy strat, int start)
Definition kutil.cc:6566
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)
#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:77
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
Definition polys.h:71
poly * polyset
Definition polys.h:260
long(* pFDegProc)(poly p, ring r)
Definition ring.h:39
long(* pLDegProc)(poly p, int *length, ring r)
Definition ring.h:38
kBucket * kBucket_pt
Definition ring.h:26
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:45
#define rField_is_Ring(R)
Definition ring.h:491
#define R
Definition sirandom.c:27
#define Q
Definition sirandom.c:26
skStrategy * kStrategy
Definition structs.h:54
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027