ppinitialReduction.cc
Go to the documentation of this file.
2 #include <Singular/ipid.h>
3 
4 #include "singularWishlist.h"
5 #include "ppinitialReduction.h"
6 
7 #include <map>
8 #include <set>
9 #include <exception>
10 
11 
12 #ifndef NDEBUG
13 bool isOrderingLocalInT(const ring r)
14 {
15  poly one = p_One(r);
16  poly t = p_One(r);
17  p_SetExp(t,1,1,r);
18  p_Setm(t,r);
19  int s = p_LmCmp(one,t,r);
20  p_Delete(&one,r);
21  p_Delete(&t,r);
22  return (s==1);
23 }
24 #endif
25 
26 void divideByCommonGcd(poly &g, const ring r)
27 {
28  number commonGcd = n_Copy(p_GetCoeff(g,r),r->cf);
29  for (poly gCache=pNext(g); gCache; pIter(gCache))
30  {
31  number commonGcdCache = n_Gcd(commonGcd,p_GetCoeff(gCache,r),r->cf);
32  n_Delete(&commonGcd,r->cf);
33  commonGcd = commonGcdCache;
34  if (n_IsOne(commonGcd,r->cf))
35  {
36  n_Delete(&commonGcd,r->cf);
37  return;
38  }
39  }
40  for (poly gCache=g; gCache; pIter(gCache))
41  {
42  number oldCoeff = p_GetCoeff(gCache,r);
43  number newCoeff = n_Div(oldCoeff,commonGcd,r->cf);
44  p_SetCoeff(gCache,newCoeff,r);
45  }
46  p_Test(g,r);
47  n_Delete(&commonGcd,r->cf);
48  return;
49 }
50 
51 /***
52  * changes a polynomial g with the help p-t such that
53  * 1) each term of g has a distinct monomial in x
54  * 2) no term of g has a coefficient divisible by p
55  * in particular, this means that all g_\alpha can be obtained
56  * by reading the coefficients and that g is initially reduced
57  * with respect to p-t
58  **/
59 void pReduce(poly &g, const number p, const ring r)
60 {
61  if (g==NULL)
62  return;
63  p_Test(g,r);
64 
65  poly toBeChecked = pNext(g);
66  pNext(g) = NULL; poly gEnd = g;
67  poly gCache;
68 
69  number coeff, pPower; int power; poly subst;
70  while(toBeChecked)
71  {
72  for (gCache = g; gCache; pIter(gCache))
73  if (p_LeadmonomDivisibleBy(gCache,toBeChecked,r)) break;
74  if (gCache)
75  {
76  n_Power(p,p_GetExp(toBeChecked,1,r)-p_GetExp(gCache,1,r),&pPower,r->cf);
77  coeff = n_Mult(p_GetCoeff(toBeChecked,r),pPower,r->cf);
78  p_SetCoeff(gCache,n_Add(p_GetCoeff(gCache,r),coeff,r->cf),r);
79  n_Delete(&pPower,r->cf); n_Delete(&coeff,r->cf);
80  toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
81  }
82  else
83  {
84  if (n_DivBy(p_GetCoeff(toBeChecked,r),p,r->cf))
85  {
86  power=1;
87  coeff=n_Div(p_GetCoeff(toBeChecked,r),p,r->cf);
88  while (n_DivBy(coeff,p,r->cf))
89  {
90  power++;
91  number coeff0 = n_Div(coeff,p,r->cf);
92  n_Delete(&coeff,r->cf);
93  coeff = coeff0;
94  coeff0 = NULL;
95  if (power<1)
96  {
97  WerrorS("pReduce: overflow in exponent");
98  throw 0;
99  }
100  }
101  subst=p_LmInit(toBeChecked,r);
102  p_AddExp(subst,1,power,r);
103  p_SetCoeff(subst,coeff,r);
104  p_Setm(subst,r); p_Test(subst,r);
105  toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
106  toBeChecked=p_Add_q(toBeChecked,subst,r);
107  p_Test(toBeChecked,r);
108  }
109  else
110  {
111  pNext(gEnd)=toBeChecked;
112  pIter(gEnd); pIter(toBeChecked);
113  pNext(gEnd)=NULL;
114  p_Test(g,r);
115  }
116  }
117  }
118  p_Test(g,r);
119  divideByCommonGcd(g,r);
120  return;
121 }
122 
123 bool p_xLeadmonomDivisibleBy(const poly g, const poly f, const ring r)
124 {
125  poly gx = p_Head(g,r);
126  poly fx = p_Head(f,r);
127  p_SetExp(gx,1,0,r);
128  p_SetExp(fx,1,0,r);
129  p_Setm(gx,r);
130  p_Setm(fx,r);
131  bool b = p_LeadmonomDivisibleBy(gx,fx,r);
132  p_Delete(&gx,r);
133  p_Delete(&fx,r);
134  return b;
135 }
136 
137 void pReduceInhomogeneous(poly &g, const number p, const ring r)
138 {
139  if (g==NULL)
140  return;
141  p_Test(g,r);
142 
143  poly toBeChecked = pNext(g);
144  pNext(g) = NULL; poly gEnd = g;
145  poly gCache;
146 
147  number coeff, pPower; int power; poly subst;
148  while(toBeChecked)
149  {
150  for (gCache = g; gCache; pIter(gCache))
151  if (p_xLeadmonomDivisibleBy(gCache,toBeChecked,r)) break;
152  if (gCache)
153  {
154  n_Power(p,p_GetExp(toBeChecked,1,r)-p_GetExp(gCache,1,r),&pPower,r->cf);
155  coeff = n_Mult(p_GetCoeff(toBeChecked,r),pPower,r->cf);
156  p_SetCoeff(gCache,n_Add(p_GetCoeff(gCache,r),coeff,r->cf),r);
157  n_Delete(&pPower,r->cf); n_Delete(&coeff,r->cf);
158  toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
159  }
160  else
161  {
162  if (n_DivBy(p_GetCoeff(toBeChecked,r),p,r->cf))
163  {
164  power=1;
165  coeff=n_Div(p_GetCoeff(toBeChecked,r),p,r->cf);
166  while (n_DivBy(coeff,p,r->cf))
167  {
168  power++;
169  number coeff0 = n_Div(coeff,p,r->cf);
170  n_Delete(&coeff,r->cf);
171  coeff = coeff0;
172  coeff0 = NULL;
173  if (power<1)
174  {
175  WerrorS("pReduce: overflow in exponent");
176  throw 0;
177  }
178  }
179  subst=p_LmInit(toBeChecked,r);
180  p_AddExp(subst,1,power,r);
181  p_SetCoeff(subst,coeff,r);
182  p_Setm(subst,r); p_Test(subst,r);
183  toBeChecked=p_LmDeleteAndNext(toBeChecked,r);
184  toBeChecked=p_Add_q(toBeChecked,subst,r);
185  p_Test(toBeChecked,r);
186  }
187  else
188  {
189  pNext(gEnd)=toBeChecked;
190  pIter(gEnd); pIter(toBeChecked);
191  pNext(gEnd)=NULL;
192  p_Test(g,r);
193  }
194  }
195  }
196  p_Test(g,r);
197  divideByCommonGcd(g,r);
198  return;
199 }
200 
201 void ptNormalize(poly* gStar, const number p, const ring r)
202 {
203  poly g = *gStar;
204  if (g==NULL || n_DivBy(p_GetCoeff(g,r),p,r->cf))
205  return;
206  p_Test(g,r);
207 
208  // create p-t
209  poly pt = p_Init(r);
210  p_SetCoeff(pt,n_Copy(p,r->cf),r);
211 
212  pNext(pt) = p_Init(r);
213  p_SetExp(pNext(pt),1,1,r);
214  p_Setm(pNext(pt),r);
215  p_SetCoeff(pNext(pt),n_Init(-1,r->cf),r);
216 
217  // make g monic with the help of p-t
218  number a,b;
219  number gcd = n_ExtGcd(p_GetCoeff(g,r),p,&a,&b,r->cf);
220  assume(n_IsUnit(gcd,r->cf));
221  // now a*leadcoef(g)+b*p = gcd with gcd being a unit
222  // so a*g+b*(p-t)*leadmonom(g) should have a unit as leading coefficient
223  // but first check whether b is 0,
224  // since p_Mult_nn doesn't allow 0 as number input
225  if (n_IsZero(b,r->cf))
226  {
227  n_Delete(&a,r->cf);
228  n_Delete(&b,r->cf);
229  n_Delete(&gcd,r->cf);
230  p_Delete(&pt,r);
231  return;
232  }
233  poly m = p_Head(g,r);
234  p_SetCoeff(m,n_Init(1,r->cf),r);
235  g = p_Add_q(p_Mult_nn(g,a,r),p_Mult_nn(p_Mult_mm(pt,m,r),b,r),r);
236  n_Delete(&a,r->cf);
237  n_Delete(&b,r->cf);
238  n_Delete(&gcd,r->cf);
239  p_Delete(&m,r);
240 
241  p_Test(g,r);
242  return;
243 }
244 
245 void ptNormalize(ideal I, const number p, const ring r)
246 {
247  for (int i=0; i<IDELEMS(I); i++)
248  ptNormalize(&(I->m[i]),p,r);
249  return;
250 }
251 
252 #ifndef NDEBUG
254 {
255  leftv u = args;
256  if ((u != NULL) && (u->Typ() == IDEAL_CMD))
257  {
258  leftv v = u->next;
259  if ((v!=NULL) && (v->Typ()==NUMBER_CMD))
260  {
261  omUpdateInfo();
262  Print("usedBytesBefore=%ld\n",om_Info.UsedBytes);
263  ideal I = (ideal) u->CopyD();
264  number p = (number) v->CopyD();
265  ptNormalize(I,p,currRing);
266  n_Delete(&p,currRing->cf);
267  res->rtyp = IDEAL_CMD;
268  res->data = (char*) I;
269  return FALSE;
270  }
271  }
272  return TRUE;
273 }
274 #endif //NDEBUG
275 
276 void pReduce(ideal &I, const number p, const ring r)
277 {
278  int k = IDELEMS(I);
279  for (int i=0; i<k; i++)
280  {
281  if (I->m[i]!=NULL)
282  {
283  number c = p_GetCoeff(I->m[i],r);
284  if (!n_DivBy(p,c,r->cf))
285  pReduce(I->m[i],p,r);
286  }
287  }
288 }
289 
290 
291 /**
292  * reduces h initially with respect to g,
293  * returns false if h was initially reduced in the first place,
294  * returns true if reductions have taken place.
295  * assumes that h and g are in pReduced form and homogeneous in x of the same degree
296  */
297 bool ppreduceInitially(poly* hStar, const poly g, const ring r)
298 {
299  poly h = *hStar;
300  if (h==NULL || g==NULL)
301  return false;
302  p_Test(h,r);
303  p_Test(g,r);
304  poly hCache;
305  for (hCache=h; hCache; pIter(hCache))
306  if (p_LeadmonomDivisibleBy(g,hCache,r)) break;
307  if (hCache)
308  {
309  number gAlpha = p_GetCoeff(g,r);
310  poly hAlphaT = p_Init(r);
311  p_SetCoeff(hAlphaT,n_Copy(p_GetCoeff(hCache,r),r->cf),r);
312  p_SetExp(hAlphaT,1,p_GetExp(hCache,1,r)-p_GetExp(g,1,r),r);
313  for (int i=2; i<=r->N; i++)
314  p_SetExp(hAlphaT,i,0,r);
315  p_Setm(hAlphaT,r); p_Test(hAlphaT,r);
316  poly q1 = p_Mult_nn(h,gAlpha,r); p_Test(q1,r);
317  poly q2 = p_Mult_q(p_Copy(g,r),hAlphaT,r); p_Test(q2,r);
318  q2 = p_Neg(q2,r); p_Test(q2,r);
319  h = p_Add_q(q1,q2,r);
320  p_Test(h,r);
321  p_Test(g,r);
322  *hStar = h;
323  return true;
324  }
325  p_Test(h,r);
326  p_Test(g,r);
327  return false;
328 }
329 
330 
331 /***
332  * reduces I initially with respect to itself and with respect to p-t.
333  * also sorts the generators of I with respect to the leading monomials in descending order.
334  * assumes that I is generated by elements which are homogeneous in x of the same degree.
335  **/
336 bool ppreduceInitially(ideal I, const number p, const ring r)
337 {
338  idSkipZeroes(I);
339  int m=IDELEMS(I),n=m; poly cache;
340  do
341  {
342  int j=0;
343  for (int i=1; i<n; i++)
344  {
345  if (p_LmCmp(I->m[i-1],I->m[i],r)<0) /*p_LmCmp(p,q): requires: p,q!=NULL*/
346  {
347  cache=I->m[i-1];
348  I->m[i-1]=I->m[i];
349  I->m[i]=cache;
350  j = i;
351  }
352  }
353  n=j;
354  } while(n);
355  for (int i=0; i<m; i++)
356  pReduce(I->m[i],p,r);
357 
358  /***
359  * the first pass. removing terms with the same monomials in x as lt(g_i) out of g_j for i<j
360  **/
361  for (int i=0; i<m-1; i++)
362  for (int j=i+1; j<m; j++)
363  if (ppreduceInitially(&I->m[j], I->m[i], r))
364  pReduce(I->m[j],p,r);
365 
366  /***
367  * the second pass. removing terms divisible by lt(g_j) out of g_i for i<j
368  **/
369  for (int i=0; i<m-1; i++)
370  for (int j=i+1; j<m; j++)
371  if (ppreduceInitially(&I->m[i], I->m[j],r))
372  pReduce(I->m[i],p,r);
373 
374  /***
375  * removes the elements of I which have been reduced to 0 in the previous two passes
376  **/
377  idSkipZeroes(I);
378  return false;
379 }
380 
381 
382 /***
383  * inserts g into I and reduces I with respect to itself and p-t
384  * returns the position in I in which g was inserted
385  * assumes that I was already sorted and initially reduced in the first place
386  **/
387 int ppreduceInitially(ideal I, const number p, const poly g, const ring r)
388 {
389  id_Test(I,r);
390  p_Test(g,r);
391  idInsertPoly(I,g);
392  idSkipZeroes(I);
393  int n=IDELEMS(I);
394  int j;
395  for (j=n-1; j>0; j--)
396  {
397  if (p_LmCmp(I->m[j], I->m[j-1],r)>0) /*p_LmCmp(p,q) requires: p,q!=NULL */
398  {
399  poly cache = I->m[j];
400  I->m[j] = I->m[j-1];
401  I->m[j-1] = cache;
402  }
403  else
404  break;
405  }
406 
407  /***
408  * the first pass. removing terms with the same monomials in x as lt(g_i) out of g_j for i<j
409  * removing terms with the same monomials in x as lt(g_j) out of g_k for j<k
410  **/
411  for (int i=0; i<j; i++)
412  if (ppreduceInitially(&I->m[j], I->m[i], r))
413  pReduce(I->m[j],p,r);
414  for (int k=j+1; k<n; k++)
415  if (ppreduceInitially(&I->m[k], I->m[j], r))
416  {
417  pReduce(I->m[k],p,r);
418  for (int l=j+1; l<k; l++)
419  if (ppreduceInitially(&I->m[k], I->m[l], r))
420  pReduce(I->m[k],p,r);
421  }
422 
423  /***
424  * the second pass. removing terms divisible by lt(g_j) and lt(g_k) out of g_i for i<j<k
425  * removing terms divisible by lt(g_k) out of g_j for j<k
426  **/
427  for (int i=0; i<j; i++)
428  for (int k=j; k<n; k++)
429  if (ppreduceInitially(&I->m[i], I->m[k], r))
430  pReduce(I->m[i],p,r);
431  for (int k=j; k<n-1; k++)
432  for (int l=k+1; l<n; l++)
433  if (ppreduceInitially(&I->m[k], I->m[l], r))
434  pReduce(I->m[k],p,r);
435 
436  /***
437  * removes the elements of I which have been reduced to 0 in the previous two passes
438  **/
439  idSkipZeroes(I);
440  id_Test(I,r);
441  return j;
442 }
443 
444 
445 static poly ppNext(poly p, int l)
446 {
447  poly q = p;
448  for (int i=0; i<l; i++)
449  {
450  if (q==NULL)
451  break;
452  pIter(q);
453  }
454  return q;
455 }
456 
457 
458 static void sortMarks(const ideal H, const ring r, std::vector<mark> &T)
459 {
460  std::pair<int,int> pointerToTerm;
461  int k=T.size();
462  do
463  {
464  int j=0;
465  for (int i=1; i<k-1; i++)
466  {
467  int generatorA = T[i-1].first;
468  int termA = T[i-1].second;
469  int generatorB = T[i].first;
470  int termB = T[i].second;
471  if (p_LmCmp(ppNext(H->m[generatorA],termA),ppNext(H->m[generatorB],termB),r)<0)
472  {
473  mark cache=T[i-1];
474  T[i-1]=T[i];
475  T[i]=cache;
476  j = i;
477  }
478  }
479  k=j;
480  } while(k);
481  return;
482 }
483 
484 
485 static poly getTerm(const ideal H, const mark ab)
486 {
487  int a = ab.first;
488  int b = ab.second;
489  return ppNext(H->m[a],b);
490 }
491 
492 
493 static void adjustMarks(std::vector<mark> &T, const int newEntry)
494 {
495  for (unsigned i=0; i<T.size(); i++)
496  {
497  if (T[i].first>=newEntry)
498  T[i].first = T[i].first+1;
499  }
500  return;
501 }
502 
503 
504 static void cleanupMarks(const ideal H, std::vector<mark> &T)
505 {
506  for (unsigned i=0; i<T.size();)
507  {
508  if (getTerm(H,T[i])==NULL)
509  T.erase(T.begin()+i);
510  else
511  i++;
512  }
513  return;
514 }
515 
516 
517 /***
518  * reduces H initially with respect to itself, with respect to p-t,
519  * and with respect to G.
520  * assumes that the generators of H are homogeneous in x of the same degree,
521  * assumes that the generators of G are homogeneous in x of lesser degree.
522  **/
523 bool ppreduceInitially(ideal &H, const number p, const ideal G, const ring r)
524 {
525  /***
526  * Step 1: reduce H initially with respect to itself and with respect to p-t
527  **/
528  if (ppreduceInitially(H,p,r)) return true;
529 
530  /***
531  * Step 2: initialize an ideal I in which the reductions will take place-
532  * along the reduction it will be enlarged with elements that will be discarded at the end
533  * initialize a working list T which keeps track.
534  * the working list T is a vector of pairs of integer.
535  * if T contains a pair (i,j) then that means that in the i-th element of H
536  * term j and subsequent terms need to be checked for reduction.
537  * T is sorted by the ordering on the temrs the pairs correspond to.
538  **/
539  int m=IDELEMS(H);
540  ideal I = idInit(m);
541  std::vector<mark> T;
542  for (int i=0; i<m; i++)
543  {
544  if(H->m[i]!=NULL)
545  {
546  I->m[i]=H->m[i];
547  if (pNext(I->m[i])!=NULL)
548  T.push_back(std::pair<int,int>(i,1));
549  }
550  }
551 
552  /***
553  * Step 3: as long as the working list is not empty, successively reduce terms in it
554  * by adding suitable elements to I and reducing it initially with respect to itself
555  **/
556  int k=IDELEMS(G);
557  while (T.size()>0)
558  {
559  sortMarks(I,r,T);
560  int i=0;
561  for (; i<k; i++)
562  {
563  if(G->m[i]!=NULL)
564  {
565  if (p_LeadmonomDivisibleBy(G->m[i],getTerm(I,T[0]),r)) break;
566  }
567  }
568  if (i<k)
569  {
570  poly g = p_One(r); poly h0 = getTerm(I,T[0]);
571  assume(h0!=NULL);
572  for (int j=2; j<=r->N; j++)
573  p_SetExp(g,j,p_GetExp(h0,j,r)-p_GetExp(G->m[i],j,r),r);
574  p_Setm(g,r);
575  g = p_Mult_q(g,p_Copy(G->m[i],r),r);
576  int newEntry = ppreduceInitially(I,p,g,r);
577  adjustMarks(T,newEntry);
578  }
579  else
580  T[0].second = T[0].second+1;
581  cleanupMarks(I,T);
582  }
583 
584  /***
585  * Step 4: cleanup, delete all polynomials in I which have been added in Step 3
586  **/
587  k=IDELEMS(I);
588  for (int i=0; i<k; i++)
589  {
590  if(I->m[i]!=NULL)
591  {
592  for (int j=0; j<m; j++)
593  {
594  if ((H->m[j]!=NULL)
595  && (p_LeadmonomDivisibleBy(H->m[j],I->m[i],r)))
596  {
597  I->m[i]=NULL;
598  break;
599  }
600  }
601  }
602  }
603  id_Delete(&I,r);
604  return false;
605 }
606 
607 
608 /**
609  * reduces I initially with respect to itself.
610  * assumes that the generators of I are homogeneous in x and that p-t is in I.
611  */
612 bool ppreduceInitially(ideal I, const ring r, const number p)
613 {
614  assume(!n_IsUnit(p,r->cf));
615 
616  /***
617  * Step 1: split up I into components of same degree in x
618  * the lowest component should only contain p-t
619  **/
620  std::map<long,ideal> H; int n = IDELEMS(I);
621  for (int i=0; i<n; i++)
622  {
623  if(I->m[i]!=NULL)
624  {
625  I->m[i] = p_Cleardenom(I->m[i],r);
626  long d = 0;
627  for (int j=2; j<=r->N; j++)
628  d += p_GetExp(I->m[i],j,r);
629  std::map<long,ideal>::iterator it = H.find(d);
630  if (it != H.end())
631  idInsertPoly(it->second,I->m[i]);
632  else
633  {
634  std::pair<long,ideal> Hd(d,idInit(1));
635  Hd.second->m[0] = I->m[i];
636  H.insert(Hd);
637  }
638  }
639  }
640 
641  std::map<long,ideal>::iterator it=H.begin();
642  ideal Hi = it->second;
643  idShallowDelete(&Hi);
644  it++;
645  Hi = it->second;
646 
647  /***
648  * Step 2: reduce each component initially with respect to itself
649  * and all lower components
650  **/
651  if (ppreduceInitially(Hi,p,r)) return true;
652  idSkipZeroes(Hi);
653  id_Test(Hi,r);
654  id_Test(I,r);
655 
656  ideal G = idInit(n); int m=0;
657  ideal GG = (ideal) omAllocBin(sip_sideal_bin);
658  GG->nrows = 1; GG->rank = 1; GG->m=NULL;
659 
660  for (it++; it!=H.end(); it++)
661  {
662  int l=IDELEMS(Hi); int k=l; poly cache;
663  /**
664  * sorts Hi according to degree in t in descending order
665  * (lowest first, highest last)
666  */
667  do
668  {
669  int j=0;
670  for (int i=1; i<k; i++)
671  {
672  if (p_GetExp(Hi->m[i-1],1,r)<p_GetExp(Hi->m[i],1,r))
673  {
674  cache=Hi->m[i-1];
675  Hi->m[i-1]=Hi->m[i];
676  Hi->m[i]=cache;
677  j = i;
678  }
679  }
680  k=j;
681  } while(k);
682  int kG=n-m, kH=0;
683  for (int i=n-m-l; i<n; i++)
684  {
685  if (kG==n)
686  {
687  memcpy(&(G->m[i]),&(Hi->m[kH]),(n-i)*sizeof(poly));
688  break;
689  }
690  if (kH==l)
691  break;
692  if (p_GetExp(G->m[kG],1,r)>p_GetExp(Hi->m[kH],1,r))
693  G->m[i] = G->m[kG++];
694  else
695  G->m[i] = Hi->m[kH++];
696  }
697  m += l; IDELEMS(GG) = m; GG->m = &G->m[n-m];
698  id_Test(it->second,r);
699  id_Test(GG,r);
700  if (ppreduceInitially(it->second,p,GG,r)) return true;
701  id_Test(it->second,r);
702  id_Test(GG,r);
703  idShallowDelete(&Hi); Hi = it->second;
704  }
705  idShallowDelete(&Hi);
706 
707  ptNormalize(I,p,r);
709  idShallowDelete(&G);
710  return false;
711 }
712 
713 
714 // BOOLEAN ppreduceInitially(leftv res, leftv args)
715 // {
716 // leftv u = args;
717 // if ((u != NULL) && (u->Typ() == IDEAL_CMD))
718 // {
719 // ideal I = (ideal) u->CopyD();
720 // (void) ppreduceInitially(I,currRing);
721 // res->rtyp = IDEAL_CMD;
722 // res->data = (char*) I;
723 // return FALSE;
724 // }
725 // return TRUE;
726 // }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of &#39;a&#39; and &#39;b&#39; in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ...
Definition: coeffs.h:690
const CanonicalForm int s
Definition: facAbsFact.cc:55
Class used for (list of) interpreter objects.
Definition: subexpr.h:82
static FORCE_INLINE BOOLEAN n_IsUnit(number n, const coeffs r)
TRUE iff n has a multiplicative inverse in the given coeff field/ring r.
Definition: coeffs.h:519
const poly a
Definition: syzextra.cc:212
#define Print
Definition: emacs.cc:83
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:720
static poly ppNext(poly p, int l)
std::pair< int, int > mark
#define FALSE
Definition: auxiliary.h:94
bool isOrderingLocalInT(const ring r)
return P p
Definition: myNF.cc:203
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the one element.
Definition: coeffs.h:472
omBin sip_sideal_bin
Definition: simpleideals.cc:30
static void sortMarks(const ideal H, const ring r, std::vector< mark > &T)
bool ppreduceInitially(poly *hStar, const poly g, const ring r)
reduces h initially with respect to g, returns false if h was initially reduced in the first place...
static poly p_Mult_mm(poly p, poly m, const ring r)
Definition: p_polys.h:968
#define id_Test(A, lR)
Definition: simpleideals.h:80
static poly getTerm(const ideal H, const mark ab)
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition: coeffs.h:542
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
#define TRUE
Definition: auxiliary.h:98
void * ADDRESS
Definition: auxiliary.h:115
g
Definition: cfModGcd.cc:4031
void WerrorS(const char *s)
Definition: feFopen.cc:24
int k
Definition: cfEzgcd.cc:93
static void cleanupMarks(const ideal H, std::vector< mark > &T)
static TreeM * G
Definition: janet.cc:38
int Typ()
Definition: subexpr.cc:995
static number p_SetCoeff(poly p, number n, ring r)
Definition: p_polys.h:407
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:804
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
const CanonicalForm & GG
Definition: cfModGcd.cc:4017
void * data
Definition: subexpr.h:88
#define pIter(p)
Definition: monomials.h:44
poly res
Definition: myNF.cc:322
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:640
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:10
static poly p_Head(poly p, const ring r)
Definition: p_polys.h:812
const ring r
Definition: syzextra.cc:208
bool p_xLeadmonomDivisibleBy(const poly g, const poly f, const ring r)
poly p_One(const ring r)
Definition: p_polys.cc:1314
static long p_GetExp(const poly p, const unsigned long iBitmask, const int VarOffset)
get a single variable exponent : the integer VarOffset encodes:
Definition: p_polys.h:464
int j
Definition: myNF.cc:70
omInfo_t om_Info
Definition: omStats.c:13
#define assume(x)
Definition: mod2.h:394
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of &#39;a&#39; and &#39;b&#39;, i.e., a+b
Definition: coeffs.h:660
void pReduce(poly &g, const number p, const ring r)
static FORCE_INLINE BOOLEAN n_DivBy(number a, number b, const coeffs r)
test whether &#39;a&#39; is divisible &#39;b&#39;; for r encoding a field: TRUE iff &#39;b&#39; does not represent zero in Z:...
Definition: coeffs.h:787
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted ...
static int p_LmCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1467
int m
Definition: cfEzgcd.cc:119
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:123
static poly p_Mult_nn(poly p, number n, const ring r)
Definition: p_polys.h:895
CanonicalForm H
Definition: facAbsFact.cc:64
#define IDELEMS(i)
Definition: simpleideals.h:24
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:468
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define p_Test(p, r)
Definition: p_polys.h:160
void ptNormalize(poly *gStar, const number p, const ring r)
leftv next
Definition: subexpr.h:86
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:843
static FORCE_INLINE number n_ExtGcd(number a, number b, number *s, number *t, const coeffs r)
beware that ExtGCD is only relevant for a few chosen coeff. domains and may perform something unexpec...
Definition: coeffs.h:697
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:38
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
static unsigned long p_SetExp(poly p, const unsigned long e, const unsigned long iBitmask, const int VarOffset)
set a single variable exponent : VarOffset encodes the position in p->exp
Definition: p_polys.h:483
static FORCE_INLINE void n_Power(number a, int b, number *res, const coeffs r)
fill res with the power a^b
Definition: coeffs.h:636
#define NULL
Definition: omList.c:10
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of &#39;n&#39;
Definition: coeffs.h:455
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:619
static void idShallowDelete(ideal *h)
id_ShallowDelete deletes the monomials of the polynomials stored inside of it
int gcd(int a, int b)
Definition: walkSupport.cc:839
void omUpdateInfo()
Definition: omStats.c:24
void divideByCommonGcd(poly &g, const ring r)
static void adjustMarks(std::vector< mark > &T, const int newEntry)
int rtyp
Definition: subexpr.h:91
#define pNext(p)
Definition: monomials.h:43
static poly p_LmInit(poly p, const ring r)
Definition: p_polys.h:1258
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:228
static long p_AddExp(poly p, int v, long ee, ring r)
Definition: p_polys.h:601
#define p_GetCoeff(p, r)
Definition: monomials.h:57
#define pPower(p, q)
Definition: polys.h:187
static poly p_Neg(poly p, const ring r)
Definition: p_polys.h:1013
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
static jList * T
Definition: janet.cc:37
polyrec * poly
Definition: hilb.h:10
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:877
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
static Poly * h
Definition: janet.cc:978
int BOOLEAN
Definition: auxiliary.h:85
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1243
const poly b
Definition: syzextra.cc:213
poly p_Cleardenom(poly p, const ring r)
Definition: p_polys.cc:2755
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1020
void * CopyD(int t)
Definition: subexpr.cc:707
static BOOLEAN p_LeadmonomDivisibleBy(poly a, poly b, const ring r)
p_LmDivisibleBy checks also the divisibility of coefficients
idhdl h0
Definition: libparse.cc:1141
int l
Definition: cfEzgcd.cc:94
void pReduceInhomogeneous(poly &g, const number p, const ring r)