My Project
kLiftstd.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT - Kernel: alg. of Buchberger
6 */
7 
8 #include "kernel/mod2.h"
9 
10 // define if no buckets should be used
11 // #define NO_BUCKETS
12 
13 #include "kernel/GBEngine/kutil.h"
14 #include "misc/options.h"
15 #include "kernel/polys.h"
16 #include "kernel/ideals.h"
17 #include "kernel/GBEngine/kstd1.h"
18 #include "kernel/GBEngine/khstd.h"
19 #include "polys/kbuckets.h"
20 #include "polys/prCopy.h"
21 #include "polys/weight.h"
22 #include "misc/intvec.h"
23 #ifdef HAVE_PLURAL
24 #include "polys/nc/nc.h"
25 #endif
26 
27 static poly kSplitAt(int k,poly p, const ring r)
28 {
29  if((p==NULL) || (p->next==NULL)) return NULL;
30  while(p_GetComp(p->next,r)<=k)
31  {
32  pIter(p);
33  if (p->next==NULL) return NULL;
34  }
35  poly t=p->next;
36  p->next=NULL;
37  return t;
38 }
39 static poly kSplitAt(int k,TObject* h,int *l,kStrategy strat)
40 {
41  poly p;
42  if (h->t_p==NULL) h->GetLmTailRing();
43  p=h->t_p;
44  if ((p==NULL) ||(p->next==NULL)) return NULL;
45  int ll=1;
46  const ring tailRing=strat->tailRing;
47  while(p_GetComp(p->next,tailRing)<=k)
48  {
49  pIter(p);
50  *l=ll;
51  if ((p==NULL)||(p->next==NULL)) return NULL;
52  ll++;
53  }
54  poly t=p->next;
55  p->next=NULL;
56  *l=ll;
57  return t;
58 }
59 static poly kSplitAt(int k,LObject* h,kStrategy strat)
60 {
61  poly p,pr;
62  int l;
63  if (h->bucket!=NULL)
64  {
65  kBucketClear(h->bucket,&p,&l);
66  pr=p;
67  }
68  else
69  {
70  if (h->t_p!=NULL) h->GetLmTailRing();
71  p=h->t_p;
72  }
73  const ring tailRing=strat->tailRing;
74  if (p_GetComp(p,tailRing)>k)
75  {
76  return p;
77  }
78  if (p->next==NULL) return NULL;
79  while(p_GetComp(p->next,tailRing)<=k) pIter(p);
80  poly t=p->next;
81  p->next=NULL;
82  if (h->bucket!=NULL)
83  {
84  l=pLength(pr);
85  kBucketInit(h->bucket,pr,l);
86  }
87  return t;
88 }
89 static poly kTailAt(int k,TObject* h,kStrategy strat)
90 {
91  poly p;
92  if (h->t_p!=NULL)
93  p=h->t_p;
94  else
95  p=h->p;
96  assume(p_GetComp(p,strat->tailRing)<=k);
97  if (p->next==NULL) return NULL;
98  const ring tailRing=strat->tailRing;
99  while(p_GetComp(p->next,tailRing)<=k) pIter(p);
100  poly t=p->next;
101  return t;
102 }
103 static void kAppend(poly t,TObject* h)
104 {
105  poly p;
106  if (h->t_p!=NULL)
107  p=h->t_p;
108  else
109  p=h->p;
110  while(p->next!=NULL) pIter(p);
111  p->next=t;
112  if ((h->p!=NULL)&&(h->t_p!=NULL)) pNext(h->p)=pNext(h->t_p);
113 }
114 static void kAppend(poly t,LObject* h)
115 {
116  if (h->bucket!=NULL)
117  {
118  int l=-1;
119  kBucket_Add_q(h->bucket,t,&l);
120  }
121  else
122  {
123  poly p;
124  if (h->t_p!=NULL)
125  p=h->t_p;
126  else
127  p=h->p;
128  while(p->next!=NULL) pIter(p);
129  p->next=t;
130  if ((h->p!=NULL)&&(h->t_p!=NULL)) pNext(h->p)=pNext(h->t_p);
131  }
132 }
133 
134 static poly lazyComp(number* A, poly* M,poly* T,int index,poly s,int *l,const ring tailR)
135 {
136  if ((TEST_OPT_PROT) && (index>0)) { Print("<%d>",index+1); mflush(); }
137  kBucket_pt b=kBucketCreate(tailR);
138  kBucketInit(b,s,pLength(s));
139  for(int i=0;i<index;i++)
140  {
141  kBucket_Mult_n(b,A[i]);
142  n_Delete(&A[i],tailR->cf);
143  poly tt=T[i];
144  if (tt!=NULL)
145  {
146  int dummy=pLength(tt);
147  kBucket_Minus_m_Mult_p(b,M[i],tt,&dummy);
148  }
149  p_Delete(&M[i],tailR);
150  }
151  poly p;
152  kBucketClear(b,&p,l);
153  kBucketDestroy(&b);
154  return p;
155 }
156 /*2
157 * reduction procedure for the sugar-strategy (honey)
158 * reduces h with elements from T choosing first possible
159 * element in T with respect to the given ecart
160 */
162 {
163  if (strat->tl<0) return 1;
164  assume(h->FDeg == h->pFDeg());
165  poly h_p;
166  int i,j,at,pass,ei, ii, h_d,ci;
167  unsigned long not_sev;
168  long reddeg,d;
169  number A[500];
170  poly C[500];
171  poly T[500];
172  memset(T,0,sizeof(T));
173  memset(C,0,sizeof(T));
174  const ring tailRing=strat->tailRing;
175 
176  pass = j = 0;
177  d = reddeg = h->GetpFDeg() + h->ecart;
178  h->SetShortExpVector();
179  int li;
180  h_p = h->GetLmTailRing();
181  not_sev = ~ h->sev;
182 
183  // split h into mina part (h) and tail (h_tail)
184  poly h_tail=kSplitAt(strat->syzComp,h,strat);
185  // fix h-pLength
186  h->pLength=0;
187  // remove content
188  //number cont;
189  //p_Content_n(h_p,cont,strat->tailRing);
190  //if (!n_IsOne(cont,strat->tailRing))
191  // h_tail=p_Div_nn(h_tail,cont,tailRing);
192 
193  h->PrepareRed(strat->use_buckets);
194  loop
195  {
196  j=kFindDivisibleByInT(strat, h);
197  if (j < 0)
198  {
199  // lazy computation:
200  int l;
201  poly p=lazyComp(A,C,T,pass,h_tail,&l,strat->tailRing);
202  kBucket_Add_q(h->bucket,p,&l);
203  return 1;
204  }
205 
206  ei = strat->T[j].ecart;
207  li = strat->T[j].pLength;
208  ci = nSize(pGetCoeff(strat->T[j].p));
209  if (li<=0) li=strat->T[j].GetpLength();
210  ii = j;
211  /*
212  * the polynomial to reduce with (up to the moment) is;
213  * pi with ecart ei (T[ii])
214  */
215  i = j;
216  if (TEST_OPT_LENGTH)
217  loop
218  {
219  /*- possible with respect to ecart, minimal nSize -*/
220  i++;
221  if (i > strat->tl)
222  break;
223  //if (ei < h->ecart)
224  // break;
225  if (li==1)
226  break;
227  if ((((strat->T[i].ecart < ei) && (ei> h->ecart))
228  || ((strat->T[i].ecart <= h->ecart)
229  && (strat->T[i].pLength <= li)
230  && (nSize(pGetCoeff(strat->T[i].p)) <ci)))
231  &&
232  p_LmShortDivisibleBy(strat->T[i].GetLmTailRing(), strat->sevT[i],
233  h_p, not_sev, tailRing))
234  {
235  /*
236  * the polynomial to reduce with is now;
237  */
238  ei = strat->T[i].ecart;
239  li = strat->T[i].pLength;
240  if (li<=0) li=strat->T[i].GetpLength();
241  ii = i;
242  }
243  }
244 
245  /*
246  * end of search: have to reduce with pi
247  */
248 #ifdef KDEBUG
249  if (TEST_OPT_DEBUG)
250  {
251  PrintS("red:");
252  h->wrp();
253  Print("\nwith T[%d]:",ii);
254  strat->T[ii].wrp();
255  }
256 #endif
257  assume(strat->fromT == FALSE);
258 
259  //strat->T[ii].pCleardenom();
260  // split T[ii]:
261  // remember pLength of strat->T[ii]
262  int l_orig=strat->T[ii].pLength;
263  // split strat->T[ii]
264  poly T_tail=kSplitAt(strat->syzComp,&strat->T[ii],&strat->T[ii].pLength,strat);
265  ksReducePoly(h,&(strat->T[ii]),NULL,&A[pass],&C[pass], strat);
266  // restore T[ii]:
267  kAppend(T_tail,&strat->T[ii]);
268  strat->T[ii].pLength=l_orig;
269  // store T_tail
270  T[pass]=T_tail;
271  // delayed computation: A[pass]*tail-M[pass]*T[pass]
272 #ifdef KDEBUG
273  if (TEST_OPT_DEBUG)
274  {
275  PrintS("\nto:");
276  h->wrp();
277  PrintLn();
278  }
279 #endif
280  if(h->IsNull())
281  {
282  // clean up A,C,h_tail:
283  for(int i=0;i<=pass;i++)
284  {
285  n_Delete(&A[i],tailRing->cf);
286  p_Delete(&C[i],tailRing);
287  }
288  p_Delete(&h_tail,tailRing);
289  kDeleteLcm(h);
290  h->Clear();
291  return 0;
292  }
293  h->SetShortExpVector();
294  not_sev = ~ h->sev;
295  h_d = h->SetpFDeg();
296  /* compute the ecart */
297  if (ei <= h->ecart)
298  h->ecart = d-h_d;
299  else
300  h->ecart = d-h_d+ei-h->ecart;
301 
302  /*
303  * try to reduce the s-polynomial h
304  *test first whether h should go to the lazyset L
305  *-if the degree jumps
306  *-if the number of pre-defined reductions jumps
307  */
308  pass++;
309  d = h_d + h->ecart;
310  if (pass%64==0) kBucketCanonicalize(h->bucket);
311  }
312 }
#define FALSE
Definition: auxiliary.h:96
int l
Definition: cfEzgcd.cc:100
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4080
CanonicalForm b
Definition: cfModGcd.cc:4105
int syzComp
Definition: kutil.h:353
ring tailRing
Definition: kutil.h:342
TSet T
Definition: kutil.h:323
int tl
Definition: kutil.h:349
unsigned long * sevT
Definition: kutil.h:322
char use_buckets
Definition: kutil.h:383
char fromT
Definition: kutil.h:379
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
int j
Definition: facHensel.cc:110
STATIC_VAR jList * T
Definition: janet.cc:30
STATIC_VAR Poly * h
Definition: janet.cc:971
int redLiftstd(LObject *h, kStrategy strat)
Definition: kLiftstd.cc:161
static poly lazyComp(number *A, poly *M, poly *T, int index, poly s, int *l, const ring tailR)
Definition: kLiftstd.cc:134
static void kAppend(poly t, TObject *h)
Definition: kLiftstd.cc:103
static poly kSplitAt(int k, poly p, const ring r)
Definition: kLiftstd.cc:27
static poly kTailAt(int k, TObject *h, kStrategy strat)
Definition: kLiftstd.cc:89
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:521
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
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:493
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:209
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 kBucketCanonicalize(kBucket_pt bucket)
Canonicalizes Bpoly, i.e. converts polys of buckets into one poly in one bucket: Returns number of bu...
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
class sTObject TObject
Definition: kutil.h:53
class sLObject LObject
Definition: kutil.h:54
#define assume(x)
Definition: mod2.h:387
#define p_GetComp(p, r)
Definition: monomials.h:64
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
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 NULL
Definition: omList.c:12
#define TEST_OPT_LENGTH
Definition: options.h:129
#define TEST_OPT_PROT
Definition: options.h:102
#define TEST_OPT_DEBUG
Definition: options.h:107
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
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
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:861
static unsigned pLength(poly a)
Definition: p_polys.h:191
Compatiblity layer for legacy polynomial operations (over currRing)
void PrintS(const char *s)
Definition: reporter.cc:284
void PrintLn()
Definition: reporter.cc:310
#define mflush()
Definition: reporter.h:58
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25
#define loop
Definition: structs.h:80