My Project
Functions
kLiftstd.cc File Reference
#include "kernel/mod2.h"
#include "kernel/GBEngine/kutil.h"
#include "misc/options.h"
#include "kernel/polys.h"
#include "kernel/ideals.h"
#include "kernel/GBEngine/kstd1.h"
#include "kernel/GBEngine/khstd.h"
#include "polys/kbuckets.h"
#include "polys/prCopy.h"
#include "polys/weight.h"
#include "misc/intvec.h"
#include "polys/nc/nc.h"

Go to the source code of this file.

Functions

static poly kSplitAt (int k, TObject *h, kStrategy strat)
 
static poly kSplitAt (int k, LObject *h, kStrategy strat)
 
static void kAppend (poly t, TObject *h)
 
static poly lazyComp (number *A, poly *M, poly *T, int index, poly s, int *l, const ring tailR)
 
int redLiftstd (LObject *h, kStrategy strat)
 

Function Documentation

◆ kAppend()

static void kAppend ( poly  t,
TObject h 
)
static

Definition at line 107 of file kLiftstd.cc.

108{
109 poly p;
110 if (h->t_p!=NULL)
111 p=h->t_p;
112 else
113 p=h->p;
114 while(p->next!=NULL) pIter(p);
115 p->next=t;
116 if ((h->p!=NULL)&&(h->t_p!=NULL)) pNext(h->p)=pNext(h->t_p);
117}
#define NULL
Definition: auxiliary.h:104
int p
Definition: cfModGcd.cc:4080
STATIC_VAR Poly * h
Definition: janet.cc:971
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36

◆ kSplitAt() [1/2]

static poly kSplitAt ( int  k,
LObject h,
kStrategy  strat 
)
static

Definition at line 58 of file kLiftstd.cc.

59{
60 poly p,pr,t=NULL;
61 int l;
62 if (h->bucket!=NULL)
63 {
64 kBucketClear(h->bucket,&p,&l);
65 pr=p;
66 }
67 else
68 {
69 if (h->t_p==NULL)
70 {
71 if (currRing!=strat->tailRing)
72 {
74 p=h->t_p;
75 }
76 else
77 p=h->p;
78 }
79 else
80 p=h->t_p;
81 }
82 const ring tailRing=strat->tailRing;
83 if(p==NULL) return NULL;
84 if (p_GetComp(p,tailRing)>k)
85 {
86 return p;
87 }
88 if (p->next==NULL)
89 {
90 goto finish;
91 }
92 while(p_GetComp(p->next,tailRing)<=k)
93 {
94 pIter(p);
95 if (p->next==NULL) break;
96 }
97 t=p->next;
98 p->next=NULL;
99finish:
100 if (h->bucket!=NULL)
101 {
102 l=pLength(pr);
103 kBucketInit(h->bucket,pr,l);
104 }
105 return t;
106}
int l
Definition: cfEzgcd.cc:100
int k
Definition: cfEzgcd.cc:99
ring tailRing
Definition: kutil.h:346
KINLINE poly k_LmInit_currRing_2_tailRing(poly p, ring tailRing, omBin tailBin)
Definition: kInline.h:927
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:521
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:493
#define p_GetComp(p, r)
Definition: monomials.h:64
static unsigned pLength(poly a)
Definition: p_polys.h:191
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13

◆ kSplitAt() [2/2]

static poly kSplitAt ( int  k,
TObject h,
kStrategy  strat 
)
static

Definition at line 27 of file kLiftstd.cc.

28{
29 poly p;
30 if (h->t_p==NULL)
31 {
32 if (currRing!=strat->tailRing)
33 {
35 p=h->t_p;
36 }
37 else
38 p=h->p;
39 }
40 else
41 p=h->t_p;
42 if (p->next==NULL) return NULL;
43 const ring tailRing=strat->tailRing;
44 while(p_GetComp(p->next,tailRing)<=k)
45 {
46 pIter(p);
47 if ((p==NULL)||(p->next==NULL))
48 {
49 h->pLength=0; // force re-computation
50 return NULL;
51 }
52 }
53 poly t=p->next;
54 p->next=NULL;
55 h->pLength=0; // force re-computation
56 return t;
57}

◆ lazyComp()

static poly lazyComp ( number *  A,
poly *  M,
poly *  T,
int  index,
poly  s,
int *  l,
const ring  tailR 
)
static

Definition at line 118 of file kLiftstd.cc.

119{
120 if ((TEST_OPT_PROT) && (index>0)) { Print("<%d>",index+1); mflush(); }
123 int cnt=RED_CANONICALIZE;
124 for(int i=0;i<index;i++)
125 {
127 n_Delete(&A[i],tailR->cf);
128 poly tt=T[i];
129 if (tt!=NULL)
130 {
131 cnt--;
132 int dummy=pLength(tt);
133 kBucket_Minus_m_Mult_p(b,M[i],tt,&dummy);
134 }
135 p_Delete(&M[i],tailR);
136 if (UNLIKELY(cnt==0))
137 {
140 }
141 }
142 poly p;
143 kBucketClear(b,&p,l);
145 return p;
146}
int i
Definition: cfEzgcd.cc:132
CanonicalForm b
Definition: cfModGcd.cc:4105
#define UNLIKELY(expression)
Definition: cf_factory.cc:25
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
#define Print
Definition: emacs.cc:80
const CanonicalForm int s
Definition: facAbsFact.cc:51
STATIC_VAR jList * T
Definition: janet.cc:30
void kBucket_Minus_m_Mult_p(kBucket_pt bucket, poly m, poly p, int *l, poly spNoether)
Bpoly == Bpoly - m*p; where m is a monom Does not destroy p and m assume (*l <= 0 || pLength(p) == *l...
Definition: kbuckets.cc:722
void kBucket_Mult_n(kBucket_pt bucket, number n)
Multiply Bucket by number ,i.e. Bpoly == n*Bpoly.
Definition: kbuckets.cc:598
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:216
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:209
int kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
#define RED_CANONICALIZE
Definition: kutil.h:36
#define TEST_OPT_PROT
Definition: options.h:103
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:861
#define mflush()
Definition: reporter.h:58
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25

◆ redLiftstd()

int redLiftstd ( LObject h,
kStrategy  strat 
)

Definition at line 152 of file kLiftstd.cc.

153{
154 if (strat->tl<0) return 1;
155 assume(h->FDeg == h->pFDeg());
157 poly h_p;
158 int i,j,pass,ei, ii, h_d,ci;
159 unsigned long not_sev;
160 long reddeg,d;
161 number A[500];
162 poly C[500];
163 poly T[500];
164 memset(T,0,sizeof(T));
165 memset(C,0,sizeof(T));
166 const ring tailRing=strat->tailRing;
167
168 pass = j = 0;
169 d = reddeg = h->GetpFDeg() + h->ecart;
170 h->SetShortExpVector();
171 int li;
172 h_p = h->GetLmTailRing();
173 not_sev = ~ h->sev;
174
175 // split h into mina part (h) and tail (h_tail)
176 poly h_tail=kSplitAt(strat->syzComp,h,strat);
177 // fix h-pLength
178 h->pLength=0;
179 // remove content
180 //number cont;
181 //p_Content_n(h_p,cont,strat->tailRing);
182 //if (!n_IsOne(cont,strat->tailRing))
183 // h_tail=p_Div_nn(h_tail,cont,tailRing);
184
185 h->PrepareRed(strat->use_buckets);
186 loop
187 {
188 j=kFindDivisibleByInT(strat, h);
189 if (j < 0)
190 {
191 // lazy computation:
192 int l;
193 poly p=lazyComp(A,C,T,pass,h_tail,&l,strat->tailRing);
194 kBucket_Add_q(h->bucket,p,&l);
195 return 1;
196 }
197
198 ei = strat->T[j].ecart;
199 li = strat->T[j].pLength;
200 ci = nSize(pGetCoeff(strat->T[j].p));
201 ii = j;
202 /*
203 * the polynomial to reduce with (up to the moment) is;
204 * pi with ecart ei (T[ii])
205 */
206 i = j;
207 if (TEST_OPT_LENGTH)
208 {
209 if (li<=0) li=strat->T[j].GetpLength();
210 if (li>1)
211 loop
212 {
213 /*- possible with respect to ecart, minimal nSize -*/
214 i++;
215 if (i > strat->tl)
216 break;
217 //if (ei < h->ecart)
218 // break;
219 if ((((strat->T[i].ecart < ei) && (ei> h->ecart))
220 || ((strat->T[i].ecart <= h->ecart)
221 && (strat->T[i].pLength <= li)
222 && (nSize(pGetCoeff(strat->T[i].p)) <ci)))
223 &&
224 p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
225 h_p, not_sev, tailRing))
226 {
227 /*
228 * the polynomial to reduce with is now;
229 */
230 ei = strat->T[i].ecart;
231 li = strat->T[i].pLength;
232 if (li<=0) li=strat->T[i].GetpLength();
233 ii = i;
234 if (li==1) break;
235 }
236 }
237 }
238
239 /*
240 * end of search: have to reduce with pi
241 */
242#ifdef KDEBUG
243 if (TEST_OPT_DEBUG)
244 {
245 PrintS("red:");
246 h->wrp();
247 Print("\nwith T[%d]:",ii);
248 strat->T[ii].wrp();
249 }
250#endif
251 assume(strat->fromT == FALSE);
252
253 //strat->T[ii].pCleardenom();
254 // split T[ii]:
255 // remember pLength of strat->T[ii]
256 int l_orig=strat->T[ii].pLength;
257 // split strat->T[ii]
258 poly T_tail=kSplitAt(strat->syzComp,&strat->T[ii],strat);
259 h->pLength=0; // force re-computation of length
260 ksReducePoly(h,&(strat->T[ii]),NULL,&A[pass],&C[pass], strat);
261 // restore T[ii]:
262 kAppend(T_tail,&strat->T[ii]);
263 strat->T[ii].pLength=l_orig;
264 // store T_tail
265 T[pass]=T_tail;
266 // delayed computation: A[pass]*tail-M[pass]*T[pass]
267#ifdef KDEBUG
268 if (TEST_OPT_DEBUG)
269 {
270 PrintS("\nto:");
271 h->wrp();
272 PrintLn();
273 }
274#endif
275 if(h->IsNull())
276 {
277 // clean up A,C,h_tail:
278 for(int i=0;i<=pass;i++)
279 {
280 n_Delete(&A[i],tailRing->cf);
281 p_Delete(&C[i],tailRing);
282 }
283 p_Delete(&h_tail,tailRing);
284 kDeleteLcm(h);
285 h->Clear();
286 return 0;
287 }
288 h->SetShortExpVector();
289 not_sev = ~ h->sev;
290 h_d = h->SetpFDeg();
291 /* compute the ecart */
292 if (ei <= h->ecart)
293 h->ecart = d-h_d;
294 else
295 h->ecart = d-h_d+ei-h->ecart;
296
297 /*
298 * try to reduce the s-polynomial h
299 *test first whether h should go to the lazyset L
300 *-if the degree jumps
301 *-if the number of pre-defined reductions jumps
302 */
303 pass++;
304 d = h_d + h->ecart;
305 if (pass%RED_CANONICALIZE==0) kBucketCanonicalize(h->bucket);
306 }
307}
#define FALSE
Definition: auxiliary.h:96
int syzComp
Definition: kutil.h:357
TSet T
Definition: kutil.h:327
int tl
Definition: kutil.h:353
unsigned long * sevT
Definition: kutil.h:326
char use_buckets
Definition: kutil.h:387
char fromT
Definition: kutil.h:383
int j
Definition: facHensel.cc:110
static poly lazyComp(number *A, poly *M, poly *T, int index, poly s, int *l, const ring tailR)
Definition: kLiftstd.cc:118
static void kAppend(poly t, TObject *h)
Definition: kLiftstd.cc:107
static poly kSplitAt(int k, TObject *h, kStrategy strat)
Definition: kLiftstd.cc:27
void kBucket_Add_q(kBucket_pt bucket, poly q, int *l)
Add to Bucket a poly ,i.e. Bpoly == q+Bpoly.
Definition: kbuckets.cc:660
int ksReducePoly(LObject *PR, TObject *PW, poly spNoether, number *coef, poly *mon, kStrategy strat)
Definition: kspoly.cc:185
int kFindDivisibleByInT(const kStrategy strat, const LObject *L, const int start)
return -1 if no divisor is found number of first divisor in T, otherwise
Definition: kstd2.cc:288
static void kDeleteLcm(LObject *P)
Definition: kutil.h:877
#define assume(x)
Definition: mod2.h:387
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:44
#define nSize(n)
Definition: numbers.h:39
#define TEST_OPT_IDLIFT
Definition: options.h:129
#define TEST_OPT_LENGTH
Definition: options.h:131
#define TEST_OPT_DEBUG
Definition: options.h:108
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1897
void PrintS(const char *s)
Definition: reporter.cc:284
void PrintLn()
Definition: reporter.cc:310
#define loop
Definition: structs.h:80