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