My Project
simpleideals.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT - all basic methods to manipulate ideals
6 */
7 
8 
9 /* includes */
10 
11 
12 
13 #include "misc/auxiliary.h"
14 
15 #include "misc/options.h"
16 #include "misc/intvec.h"
17 
18 #include "matpol.h"
19 
20 #include "monomials/p_polys.h"
21 #include "weight.h"
22 #include "sbuckets.h"
23 #include "clapsing.h"
24 
25 #include "simpleideals.h"
26 
28 
30 /*collects the monomials in makemonoms, must be allocated befor*/
32 /*index of the actual monomial in idpower*/
33 
34 /// initialise an ideal / module
35 ideal idInit(int idsize, int rank)
36 {
37  assume( idsize >= 0 && rank >= 0 );
38 
39  ideal hh = (ideal)omAllocBin(sip_sideal_bin);
40 
41  IDELEMS(hh) = idsize; // ncols
42  hh->nrows = 1; // ideal/module!
43 
44  hh->rank = rank; // ideal: 1, module: >= 0!
45 
46  if (idsize>0)
47  hh->m = (poly *)omAlloc0(idsize*sizeof(poly));
48  else
49  hh->m = NULL;
50 
51  return hh;
52 }
53 
54 #ifdef PDEBUG
55 // this is only for outputting an ideal within the debugger
56 // therefor it accept the otherwise illegal id==NULL
57 void idShow(const ideal id, const ring lmRing, const ring tailRing, const int debugPrint)
58 {
59  assume( debugPrint >= 0 );
60 
61  if( id == NULL )
62  PrintS("(NULL)");
63  else
64  {
65  Print("Module of rank %ld,real rank %ld and %d generators.\n",
66  id->rank,id_RankFreeModule(id, lmRing, tailRing),IDELEMS(id));
67 
68  int j = (id->ncols*id->nrows) - 1;
69  while ((j > 0) && (id->m[j]==NULL)) j--;
70  for (int i = 0; i <= j; i++)
71  {
72  Print("generator %d: ",i); p_wrp(id->m[i], lmRing, tailRing);PrintLn();
73  }
74  }
75 }
76 #endif
77 
78 /// index of generator with leading term in ground ring (if any);
79 /// otherwise -1
80 int id_PosConstant(ideal id, const ring r)
81 {
82  id_Test(id, r);
83  const int N = IDELEMS(id) - 1;
84  const poly * m = id->m + N;
85 
86  for (int k = N; k >= 0; --k, --m)
87  {
88  const poly p = *m;
89  if (p!=NULL)
90  if (p_LmIsConstantComp(p, r) == TRUE)
91  return k;
92  }
93 
94  return -1;
95 }
96 
97 /// initialise the maximal ideal (at 0)
98 ideal id_MaxIdeal (const ring r)
99 {
100  int nvars;
101 #ifdef HAVE_SHIFTBBA
102  if (r->isLPring)
103  {
104  nvars = r->isLPring;
105  }
106  else
107 #endif
108  {
109  nvars = rVar(r);
110  }
111  ideal hh = idInit(nvars, 1);
112  for (int l=nvars-1; l>=0; l--)
113  {
114  hh->m[l] = p_One(r);
115  p_SetExp(hh->m[l],l+1,1,r);
116  p_Setm(hh->m[l],r);
117  }
118  id_Test(hh, r);
119  return hh;
120 }
121 
122 /// deletes an ideal/module/matrix
123 void id_Delete (ideal * h, ring r)
124 {
125  if (*h == NULL)
126  return;
127 
128  id_Test(*h, r);
129 
130  const long elems = (long)(*h)->nrows * (long)(*h)->ncols;
131 
132  if ( elems > 0 )
133  {
134  assume( (*h)->m != NULL );
135 
136  if (r!=NULL)
137  {
138  long j = elems;
139  do
140  {
141  j--;
142  poly pp=((*h)->m[j]);
143  if (pp!=NULL) p_Delete(&pp, r);
144  }
145  while (j>0);
146  }
147 
148  omFreeSize((ADDRESS)((*h)->m),sizeof(poly)*elems);
149  }
150 
152  *h=NULL;
153 }
154 
155 
156 /// Shallowdeletes an ideal/matrix
157 void id_ShallowDelete (ideal *h, ring r)
158 {
159  id_Test(*h, r);
160 
161  if (*h == NULL)
162  return;
163 
164  int j,elems;
165  elems=j=(*h)->nrows*(*h)->ncols;
166  if (j>0)
167  {
168  assume( (*h)->m != NULL );
169  do
170  {
171  p_ShallowDelete(&((*h)->m[--j]), r);
172  }
173  while (j>0);
174  omFreeSize((ADDRESS)((*h)->m),sizeof(poly)*elems);
175  }
177  *h=NULL;
178 }
179 
180 /// gives an ideal/module the minimal possible size
181 void idSkipZeroes (ideal ide)
182 {
183  assume (ide != NULL);
184 
185  int k;
186  int j = -1;
187  int idelems=IDELEMS(ide);
188  BOOLEAN change=FALSE;
189 
190  for (k=0; k<idelems; k++)
191  {
192  if (ide->m[k] != NULL)
193  {
194  j++;
195  if (change)
196  {
197  ide->m[j] = ide->m[k];
198  }
199  }
200  else
201  {
202  change=TRUE;
203  }
204  }
205  if (change)
206  {
207  if (j == -1)
208  j = 0;
209  else
210  {
211  for (k=j+1; k<idelems; k++)
212  ide->m[k] = NULL;
213  }
214  j++;
215  pEnlargeSet(&(ide->m),idelems,j-idelems);
216  IDELEMS(ide) = j;
217  }
218 }
219 
220 /// copies the first k (>= 1) entries of the given ideal/module
221 /// and returns these as a new ideal/module
222 /// (Note that the copied entries may be zero.)
223 ideal id_CopyFirstK (const ideal ide, const int k,const ring r)
224 {
225  id_Test(ide, r);
226 
227  assume( ide != NULL );
228  assume( k <= IDELEMS(ide) );
229 
230  ideal newI = idInit(k, ide->rank);
231 
232  for (int i = 0; i < k; i++)
233  newI->m[i] = p_Copy(ide->m[i],r);
234 
235  return newI;
236 }
237 
238 /// ideal id = (id[i]), result is leadcoeff(id[i]) = 1
239 void id_Norm(ideal id, const ring r)
240 {
241  id_Test(id, r);
242  for (int i=IDELEMS(id)-1; i>=0; i--)
243  {
244  if (id->m[i] != NULL)
245  {
246  p_Norm(id->m[i],r);
247  }
248  }
249 }
250 
251 /// ideal id = (id[i]), c any unit
252 /// if id[i] = c*id[j] then id[j] is deleted for j > i
253 void id_DelMultiples(ideal id, const ring r)
254 {
255  id_Test(id, r);
256 
257  int i, j;
258  int k = IDELEMS(id)-1;
259  for (i=k; i>=0; i--)
260  {
261  if (id->m[i]!=NULL)
262  {
263  for (j=k; j>i; j--)
264  {
265  if (id->m[j]!=NULL)
266  {
267  if (rField_is_Ring(r))
268  {
269  /* if id[j] = c*id[i] then delete id[j].
270  In the below cases of a ground field, we
271  check whether id[i] = c*id[j] and, if so,
272  delete id[j] for historical reasons (so
273  that previous output does not change) */
274  if (p_ComparePolys(id->m[j], id->m[i],r)) p_Delete(&id->m[j],r);
275  }
276  else
277  {
278  if (p_ComparePolys(id->m[i], id->m[j],r)) p_Delete(&id->m[j],r);
279  }
280  }
281  }
282  }
283  }
284 }
285 
286 /// ideal id = (id[i])
287 /// if id[i] = id[j] then id[j] is deleted for j > i
288 void id_DelEquals(ideal id, const ring r)
289 {
290  id_Test(id, r);
291 
292  int i, j;
293  int k = IDELEMS(id)-1;
294  for (i=k; i>=0; i--)
295  {
296  if (id->m[i]!=NULL)
297  {
298  for (j=k; j>i; j--)
299  {
300  if ((id->m[j]!=NULL)
301  && (p_EqualPolys(id->m[i], id->m[j],r)))
302  {
303  p_Delete(&id->m[j],r);
304  }
305  }
306  }
307  }
308 }
309 
310 /// Delete id[j], if Lm(j) == Lm(i) and both LC(j), LC(i) are units and j > i
311 void id_DelLmEquals(ideal id, const ring r)
312 {
313  id_Test(id, r);
314 
315  int i, j;
316  int k = IDELEMS(id)-1;
317  for (i=k; i>=0; i--)
318  {
319  if (id->m[i] != NULL)
320  {
321  for (j=k; j>i; j--)
322  {
323  if ((id->m[j] != NULL)
324  && p_LmEqual(id->m[i], id->m[j],r)
325 #ifdef HAVE_RINGS
326  && n_IsUnit(pGetCoeff(id->m[i]),r->cf) && n_IsUnit(pGetCoeff(id->m[j]),r->cf)
327 #endif
328  )
329  {
330  p_Delete(&id->m[j],r);
331  }
332  }
333  }
334  }
335 }
336 
337 /// delete id[j], if LT(j) == coeff*mon*LT(i)
338 static void id_DelDiv_SEV(ideal id, int k,const ring r)
339 {
340  int kk = k+1;
341  long *sev=(long*)omAlloc0(kk*sizeof(long));
342  while(id->m[k]==NULL) k--;
343  BOOLEAN only_lm=r->cf->has_simple_Alloc;
344  if (only_lm)
345  {
346  for (int i=k; i>=0; i--)
347  {
348  if((id->m[i]!=NULL) && (pNext(id->m[i])!=NULL))
349  {
350  only_lm=FALSE;
351  break;
352  }
353  }
354  }
355  for (int i=k; i>=0; i--)
356  {
357  if(id->m[i]!=NULL)
358  {
359  sev[i]=p_GetShortExpVector(id->m[i],r);
360  }
361  }
362  if (only_lm)
363  {
364  for (int i=0; i<k; i++)
365  {
366  if (id->m[i] != NULL)
367  {
368  poly m_i=id->m[i];
369  long sev_i=sev[i];
370  for (int j=i+1; j<=k; j++)
371  {
372  if (id->m[j]!=NULL)
373  {
374  if (p_LmShortDivisibleBy(m_i, sev_i,id->m[j],~sev[j],r))
375  {
376  p_LmFree(&id->m[j],r);
377  }
378  else if (p_LmShortDivisibleBy(id->m[j],sev[j], m_i,~sev_i,r))
379  {
380  p_LmFree(&id->m[i],r);
381  break;
382  }
383  }
384  }
385  }
386  }
387  }
388  else
389  {
390  for (int i=0; i<k; i++)
391  {
392  if (id->m[i] != NULL)
393  {
394  poly m_i=id->m[i];
395  long sev_i=sev[i];
396  for (int j=i+1; j<=k; j++)
397  {
398  if (id->m[j]!=NULL)
399  {
400  if (p_LmShortDivisibleBy(m_i, sev_i, id->m[j],~sev[j],r))
401  {
402  p_Delete(&id->m[j],r);
403  }
404  else if (p_LmShortDivisibleBy(id->m[j],sev[j], m_i,~sev_i,r))
405  {
406  p_Delete(&id->m[i],r);
407  break;
408  }
409  }
410  }
411  }
412  }
413  }
414  omFreeSize(sev,kk*sizeof(long));
415 }
416 
417 
418 /// delete id[j], if LT(j) == coeff*mon*LT(i) and vice versa, i.e.,
419 /// delete id[i], if LT(i) == coeff*mon*LT(j)
420 void id_DelDiv(ideal id, const ring r)
421 {
422  id_Test(id, r);
423 
424  int i, j;
425  int k = IDELEMS(id)-1;
426 #ifdef HAVE_RINGS
427  if (rField_is_Ring(r))
428  {
429  for (i=k-1; i>=0; i--)
430  {
431  if (id->m[i] != NULL)
432  {
433  for (j=k; j>i; j--)
434  {
435  if (id->m[j]!=NULL)
436  {
437  if (p_DivisibleByRingCase(id->m[i], id->m[j],r))
438  {
439  p_Delete(&id->m[j],r);
440  }
441  else if (p_DivisibleByRingCase(id->m[j], id->m[i],r))
442  {
443  p_Delete(&id->m[i],r);
444  break;
445  }
446  }
447  }
448  }
449  }
450  }
451  else
452 #endif
453  {
454  /* the case of a coefficient field: */
455  if (k>9)
456  {
457  id_DelDiv_SEV(id,k,r);
458  return;
459  }
460  for (i=k-1; i>=0; i--)
461  {
462  if (id->m[i] != NULL)
463  {
464  for (j=k; j>i; j--)
465  {
466  if (id->m[j]!=NULL)
467  {
468  if (p_LmDivisibleBy(id->m[i], id->m[j],r))
469  {
470  p_Delete(&id->m[j],r);
471  }
472  else if (p_LmDivisibleBy(id->m[j], id->m[i],r))
473  {
474  p_Delete(&id->m[i],r);
475  break;
476  }
477  }
478  }
479  }
480  }
481  }
482 }
483 
484 /// test if the ideal has only constant polynomials
485 /// NOTE: zero ideal/module is also constant
486 BOOLEAN id_IsConstant(ideal id, const ring r)
487 {
488  id_Test(id, r);
489 
490  for (int k = IDELEMS(id)-1; k>=0; k--)
491  {
492  if (!p_IsConstantPoly(id->m[k],r))
493  return FALSE;
494  }
495  return TRUE;
496 }
497 
498 /// copy an ideal
499 ideal id_Copy(ideal h1, const ring r)
500 {
501  id_Test(h1, r);
502 
503  ideal h2 = idInit(IDELEMS(h1), h1->rank);
504  for (int i=IDELEMS(h1)-1; i>=0; i--)
505  h2->m[i] = p_Copy(h1->m[i],r);
506  return h2;
507 }
508 
509 #ifdef PDEBUG
510 /// Internal verification for ideals/modules and dense matrices!
511 void id_DBTest(ideal h1, int level, const char *f,const int l, const ring r, const ring tailRing)
512 {
513  if (h1 != NULL)
514  {
515  // assume(IDELEMS(h1) > 0); for ideal/module, does not apply to matrix
516  omCheckAddrSize(h1,sizeof(*h1));
517 
518  assume( h1->ncols >= 0 );
519  assume( h1->nrows >= 0 ); // matrix case!
520 
521  assume( h1->rank >= 0 );
522 
523  const long n = ((long)h1->ncols * (long)h1->nrows);
524 
525  assume( !( n > 0 && h1->m == NULL) );
526 
527  if( h1->m != NULL && n > 0 )
528  omdebugAddrSize(h1->m, n * sizeof(poly));
529 
530  long new_rk = 0; // inlining id_RankFreeModule(h1, r, tailRing);
531 
532  /* to be able to test matrices: */
533  for (long i=n - 1; i >= 0; i--)
534  {
535  _pp_Test(h1->m[i], r, tailRing, level);
536  const long k = p_MaxComp(h1->m[i], r, tailRing);
537  if (k > new_rk) new_rk = k;
538  }
539 
540  // dense matrices only contain polynomials:
541  // h1->nrows == h1->rank > 1 && new_rk == 0!
542  assume( !( h1->nrows == h1->rank && h1->nrows > 1 && new_rk > 0 ) ); //
543 
544  if(new_rk > h1->rank)
545  {
546  dReportError("wrong rank %d (should be %d) in %s:%d\n",
547  h1->rank, new_rk, f,l);
548  omPrintAddrInfo(stderr, h1, " for ideal");
549  h1->rank = new_rk;
550  }
551  }
552  else
553  {
554  Print("error: ideal==NULL in %s:%d\n",f,l);
555  assume( h1 != NULL );
556  }
557 }
558 #endif
559 
560 #ifdef PDEBUG
561 /// Internal verification for ideals/modules and dense matrices!
562 void id_DBLmTest(ideal h1, int level, const char *f,const int l, const ring r)
563 {
564  if (h1 != NULL)
565  {
566  // assume(IDELEMS(h1) > 0); for ideal/module, does not apply to matrix
567  omCheckAddrSize(h1,sizeof(*h1));
568 
569  assume( h1->ncols >= 0 );
570  assume( h1->nrows >= 0 ); // matrix case!
571 
572  assume( h1->rank >= 0 );
573 
574  const long n = ((long)h1->ncols * (long)h1->nrows);
575 
576  assume( !( n > 0 && h1->m == NULL) );
577 
578  if( h1->m != NULL && n > 0 )
579  omdebugAddrSize(h1->m, n * sizeof(poly));
580 
581  long new_rk = 0; // inlining id_RankFreeModule(h1, r, tailRing);
582 
583  /* to be able to test matrices: */
584  for (long i=n - 1; i >= 0; i--)
585  {
586  if (h1->m[i]!=NULL)
587  {
588  _p_LmTest(h1->m[i], r, level);
589  const long k = p_GetComp(h1->m[i], r);
590  if (k > new_rk) new_rk = k;
591  }
592  }
593 
594  // dense matrices only contain polynomials:
595  // h1->nrows == h1->rank > 1 && new_rk == 0!
596  assume( !( h1->nrows == h1->rank && h1->nrows > 1 && new_rk > 0 ) ); //
597 
598  if(new_rk > h1->rank)
599  {
600  dReportError("wrong rank %d (should be %d) in %s:%d\n",
601  h1->rank, new_rk, f,l);
602  omPrintAddrInfo(stderr, h1, " for ideal");
603  h1->rank = new_rk;
604  }
605  }
606  else
607  {
608  Print("error: ideal==NULL in %s:%d\n",f,l);
609  assume( h1 != NULL );
610  }
611 }
612 #endif
613 
614 /// for idSort: compare a and b revlex inclusive module comp.
615 static int p_Comp_RevLex(poly a, poly b,BOOLEAN nolex, const ring R)
616 {
617  if (b==NULL) return 1;
618  if (a==NULL) return -1;
619 
620  if (nolex)
621  {
622  int r=p_LtCmp(a,b,R);
623  return r;
624  #if 0
625  if (r!=0) return r;
626  number h=n_Sub(pGetCoeff(a),pGetCoeff(b),R->cf);
627  r = -1+n_IsZero(h,R->cf)+2*n_GreaterZero(h,R->cf); /* -1: <, 0:==, 1: > */
628  n_Delete(&h, R->cf);
629  return r;
630  #endif
631  }
632  int l=rVar(R);
633  while ((l>0) && (p_GetExp(a,l,R)==p_GetExp(b,l,R))) l--;
634  if (l==0)
635  {
636  if (p_GetComp(a,R)==p_GetComp(b,R))
637  {
638  number h=n_Sub(pGetCoeff(a),pGetCoeff(b),R->cf);
639  int r = -1+n_IsZero(h,R->cf)+2*n_GreaterZero(h,R->cf); /* -1: <, 0:==, 1: > */
640  n_Delete(&h,R->cf);
641  return r;
642  }
643  if (p_GetComp(a,R)>p_GetComp(b,R)) return 1;
644  }
645  else if (p_GetExp(a,l,R)>p_GetExp(b,l,R))
646  return 1;
647  return -1;
648 }
649 
650 // sorts the ideal w.r.t. the actual ringordering
651 // uses lex-ordering when nolex = FALSE
652 intvec *id_Sort(const ideal id, const BOOLEAN nolex, const ring r)
653 {
654  id_Test(id, r);
655 
656  intvec * result = new intvec(IDELEMS(id));
657  int i, j, actpos=0, newpos;
658  int diff, olddiff, lastcomp, newcomp;
659  BOOLEAN notFound;
660 
661  for (i=0;i<IDELEMS(id);i++)
662  {
663  if (id->m[i]!=NULL)
664  {
665  notFound = TRUE;
666  newpos = actpos / 2;
667  diff = (actpos+1) / 2;
668  diff = (diff+1) / 2;
669  lastcomp = p_Comp_RevLex(id->m[i],id->m[(*result)[newpos]],nolex,r);
670  if (lastcomp<0)
671  {
672  newpos -= diff;
673  }
674  else if (lastcomp>0)
675  {
676  newpos += diff;
677  }
678  else
679  {
680  notFound = FALSE;
681  }
682  //while ((newpos>=0) && (newpos<actpos) && (notFound))
683  while (notFound && (newpos>=0) && (newpos<actpos))
684  {
685  newcomp = p_Comp_RevLex(id->m[i],id->m[(*result)[newpos]],nolex,r);
686  olddiff = diff;
687  if (diff>1)
688  {
689  diff = (diff+1) / 2;
690  if ((newcomp==1)
691  && (actpos-newpos>1)
692  && (diff>1)
693  && (newpos+diff>=actpos))
694  {
695  diff = actpos-newpos-1;
696  }
697  else if ((newcomp==-1)
698  && (diff>1)
699  && (newpos<diff))
700  {
701  diff = newpos;
702  }
703  }
704  if (newcomp<0)
705  {
706  if ((olddiff==1) && (lastcomp>0))
707  notFound = FALSE;
708  else
709  newpos -= diff;
710  }
711  else if (newcomp>0)
712  {
713  if ((olddiff==1) && (lastcomp<0))
714  {
715  notFound = FALSE;
716  newpos++;
717  }
718  else
719  {
720  newpos += diff;
721  }
722  }
723  else
724  {
725  notFound = FALSE;
726  }
727  lastcomp = newcomp;
728  if (diff==0) notFound=FALSE; /*hs*/
729  }
730  if (newpos<0) newpos = 0;
731  if (newpos>actpos) newpos = actpos;
732  while ((newpos<actpos) && (p_Comp_RevLex(id->m[i],id->m[(*result)[newpos]],nolex,r)==0))
733  newpos++;
734  for (j=actpos;j>newpos;j--)
735  {
736  (*result)[j] = (*result)[j-1];
737  }
738  (*result)[newpos] = i;
739  actpos++;
740  }
741  }
742  for (j=0;j<actpos;j++) (*result)[j]++;
743  return result;
744 }
745 
746 /// concat the lists h1 and h2 without zeros
747 ideal id_SimpleAdd (ideal h1,ideal h2, const ring R)
748 {
749  id_Test(h1, R);
750  id_Test(h2, R);
751 
752  if ( idIs0(h1) )
753  {
754  ideal res=id_Copy(h2,R);
755  if (res->rank<h1->rank) res->rank=h1->rank;
756  return res;
757  }
758  if ( idIs0(h2) )
759  {
760  ideal res=id_Copy(h1,R);
761  if (res->rank<h2->rank) res->rank=h2->rank;
762  return res;
763  }
764 
765  int j = IDELEMS(h1)-1;
766  while ((j >= 0) && (h1->m[j] == NULL)) j--;
767 
768  int i = IDELEMS(h2)-1;
769  while ((i >= 0) && (h2->m[i] == NULL)) i--;
770 
771  const int r = si_max(h1->rank, h2->rank);
772 
773  ideal result = idInit(i+j+2,r);
774 
775  int l;
776 
777  for (l=j; l>=0; l--)
778  result->m[l] = p_Copy(h1->m[l],R);
779 
780  j = i+j+1;
781  for (l=i; l>=0; l--, j--)
782  result->m[j] = p_Copy(h2->m[l],R);
783 
784  return result;
785 }
786 
787 /// insert h2 into h1 (if h2 is not the zero polynomial)
788 /// return TRUE iff h2 was indeed inserted
789 BOOLEAN idInsertPoly (ideal h1, poly h2)
790 {
791  if (h2==NULL) return FALSE;
792  assume (h1 != NULL);
793 
794  int j = IDELEMS(h1) - 1;
795 
796  while ((j >= 0) && (h1->m[j] == NULL)) j--;
797  j++;
798  if (j==IDELEMS(h1))
799  {
800  pEnlargeSet(&(h1->m),IDELEMS(h1),16);
801  IDELEMS(h1)+=16;
802  }
803  h1->m[j]=h2;
804  return TRUE;
805 }
806 
807 /// insert p into I on position pos
808 BOOLEAN idInsertPolyOnPos (ideal I, poly p,int pos)
809 {
810  if (p==NULL) return FALSE;
811  assume (I != NULL);
812 
813  int j = IDELEMS(I) - 1;
814 
815  while ((j >= 0) && (I->m[j] == NULL)) j--;
816  j++;
817  if (j==IDELEMS(I))
818  {
819  pEnlargeSet(&(I->m),IDELEMS(I),IDELEMS(I)+1);
820  IDELEMS(I)+=1;
821  }
822  for(j = IDELEMS(I)-1;j>pos;j--)
823  I->m[j] = I->m[j-1];
824  I->m[pos]=p;
825  return TRUE;
826 }
827 
828 
829 /*! insert h2 into h1 depending on the two boolean parameters:
830  * - if zeroOk is true, then h2 will also be inserted when it is zero
831  * - if duplicateOk is true, then h2 will also be inserted when it is
832  * already present in h1
833  * return TRUE iff h2 was indeed inserted
834  */
835 BOOLEAN id_InsertPolyWithTests (ideal h1, const int validEntries,
836  const poly h2, const bool zeroOk, const bool duplicateOk, const ring r)
837 {
838  id_Test(h1, r);
839  p_Test(h2, r);
840 
841  if ((!zeroOk) && (h2 == NULL)) return FALSE;
842  if (!duplicateOk)
843  {
844  bool h2FoundInH1 = false;
845  int i = 0;
846  while ((i < validEntries) && (!h2FoundInH1))
847  {
848  h2FoundInH1 = p_EqualPolys(h1->m[i], h2,r);
849  i++;
850  }
851  if (h2FoundInH1) return FALSE;
852  }
853  if (validEntries == IDELEMS(h1))
854  {
855  pEnlargeSet(&(h1->m), IDELEMS(h1), 16);
856  IDELEMS(h1) += 16;
857  }
858  h1->m[validEntries] = h2;
859  return TRUE;
860 }
861 
862 /// h1 + h2
863 ideal id_Add (ideal h1,ideal h2, const ring r)
864 {
865  id_Test(h1, r);
866  id_Test(h2, r);
867 
868  ideal result = id_SimpleAdd(h1,h2,r);
870  return result;
871 }
872 
873 /// h1 * h2
874 /// one h_i must be an ideal (with at least one column)
875 /// the other h_i may be a module (with no columns at all)
876 ideal id_Mult (ideal h1,ideal h2, const ring R)
877 {
878  id_Test(h1, R);
879  id_Test(h2, R);
880 
881  int j = IDELEMS(h1);
882  while ((j > 0) && (h1->m[j-1] == NULL)) j--;
883 
884  int i = IDELEMS(h2);
885  while ((i > 0) && (h2->m[i-1] == NULL)) i--;
886 
887  j *= i;
888  int r = si_max( h2->rank, h1->rank );
889  if (j==0)
890  {
891  if ((IDELEMS(h1)>0) && (IDELEMS(h2)>0)) j=1;
892  return idInit(j, r);
893  }
894  ideal hh = idInit(j, r);
895 
896  int k = 0;
897  for (i=0; i<IDELEMS(h1); i++)
898  {
899  if (h1->m[i] != NULL)
900  {
901  for (j=0; j<IDELEMS(h2); j++)
902  {
903  if (h2->m[j] != NULL)
904  {
905  hh->m[k] = pp_Mult_qq(h1->m[i],h2->m[j],R);
906  k++;
907  }
908  }
909  }
910  }
911 
912  id_Compactify(hh,R);
913  return hh;
914 }
915 
916 /// returns true if h is the zero ideal
917 BOOLEAN idIs0 (ideal h)
918 {
919  assume (h != NULL); // will fail :(
920 // if (h == NULL) return TRUE;
921 
922  for( int i = IDELEMS(h)-1; i >= 0; i-- )
923  if(h->m[i] != NULL)
924  return FALSE;
925 
926  return TRUE;
927 
928 }
929 
930 /// return the maximal component number found in any polynomial in s
931 long id_RankFreeModule (ideal s, ring lmRing, ring tailRing)
932 {
933  long j = 0;
934 
935  if (rRing_has_Comp(tailRing) && rRing_has_Comp(lmRing))
936  {
937  poly *p=s->m;
938  for (unsigned int l=IDELEMS(s); l > 0; --l, ++p)
939  if (*p != NULL)
940  {
941  pp_Test(*p, lmRing, tailRing);
942  const long k = p_MaxComp(*p, lmRing, tailRing);
943  if (k>j) j = k;
944  }
945  }
946 
947  return j; // return -1;
948 }
949 
950 /*2
951 *returns true if id is homogenous with respect to the aktual weights
952 */
953 BOOLEAN id_HomIdeal (ideal id, ideal Q, const ring r)
954 {
955  int i;
956  BOOLEAN b;
957  i = 0;
958  b = TRUE;
959  while ((i < IDELEMS(id)) && b)
960  {
961  b = p_IsHomogeneous(id->m[i],r);
962  i++;
963  }
964  if ((b) && (Q!=NULL) && (IDELEMS(Q)>0))
965  {
966  i=0;
967  while ((i < IDELEMS(Q)) && b)
968  {
969  b = p_IsHomogeneous(Q->m[i],r);
970  i++;
971  }
972  }
973  return b;
974 }
975 
976 BOOLEAN id_HomIdealW (ideal id, ideal Q, const intvec *w, const ring r)
977 {
978  int i;
979  BOOLEAN b;
980  i = 0;
981  b = TRUE;
982  while ((i < IDELEMS(id)) && b)
983  {
984  b = p_IsHomogeneousW(id->m[i],w,r);
985  i++;
986  }
987  if ((b) && (Q!=NULL) && (IDELEMS(Q)>0))
988  {
989  i=0;
990  while ((i < IDELEMS(Q)) && b)
991  {
992  b = p_IsHomogeneousW(Q->m[i],w,r);
993  i++;
994  }
995  }
996  return b;
997 }
998 
999 BOOLEAN id_HomModuleW (ideal id, ideal Q, const intvec *w, const intvec *module_w, const ring r)
1000 {
1001  int i;
1002  BOOLEAN b;
1003  i = 0;
1004  b = TRUE;
1005  while ((i < IDELEMS(id)) && b)
1006  {
1007  b = p_IsHomogeneousW(id->m[i],w,module_w,r);
1008  i++;
1009  }
1010  if ((b) && (Q!=NULL) && (IDELEMS(Q)>0))
1011  {
1012  i=0;
1013  while ((i < IDELEMS(Q)) && b)
1014  {
1015  b = p_IsHomogeneousW(Q->m[i],w,r);
1016  i++;
1017  }
1018  }
1019  return b;
1020 }
1021 
1022 /*2
1023 *initialized a field with r numbers between beg and end for the
1024 *procedure idNextChoise
1025 */
1026 void idInitChoise (int r,int beg,int end,BOOLEAN *endch,int * choise)
1027 {
1028  /*returns the first choise of r numbers between beg and end*/
1029  int i;
1030  for (i=0; i<r; i++)
1031  {
1032  choise[i] = 0;
1033  }
1034  if (r <= end-beg+1)
1035  for (i=0; i<r; i++)
1036  {
1037  choise[i] = beg+i;
1038  }
1039  if (r > end-beg+1)
1040  *endch = TRUE;
1041  else
1042  *endch = FALSE;
1043 }
1044 
1045 /*2
1046 *returns the next choise of r numbers between beg and end
1047 */
1048 void idGetNextChoise (int r,int end,BOOLEAN *endch,int * choise)
1049 {
1050  int i = r-1,j;
1051  while ((i >= 0) && (choise[i] == end))
1052  {
1053  i--;
1054  end--;
1055  }
1056  if (i == -1)
1057  *endch = TRUE;
1058  else
1059  {
1060  choise[i]++;
1061  for (j=i+1; j<r; j++)
1062  {
1063  choise[j] = choise[i]+j-i;
1064  }
1065  *endch = FALSE;
1066  }
1067 }
1068 
1069 /*2
1070 *takes the field choise of d numbers between beg and end, cancels the t-th
1071 *entree and searches for the ordinal number of that d-1 dimensional field
1072 * w.r.t. the algorithm of construction
1073 */
1074 int idGetNumberOfChoise(int t, int d, int begin, int end, int * choise)
1075 {
1076  int * localchoise,i,result=0;
1077  BOOLEAN b=FALSE;
1078 
1079  if (d<=1) return 1;
1080  localchoise=(int*)omAlloc((d-1)*sizeof(int));
1081  idInitChoise(d-1,begin,end,&b,localchoise);
1082  while (!b)
1083  {
1084  result++;
1085  i = 0;
1086  while ((i<t) && (localchoise[i]==choise[i])) i++;
1087  if (i>=t)
1088  {
1089  i = t+1;
1090  while ((i<d) && (localchoise[i-1]==choise[i])) i++;
1091  if (i>=d)
1092  {
1093  omFreeSize((ADDRESS)localchoise,(d-1)*sizeof(int));
1094  return result;
1095  }
1096  }
1097  idGetNextChoise(d-1,end,&b,localchoise);
1098  }
1099  omFreeSize((ADDRESS)localchoise,(d-1)*sizeof(int));
1100  return 0;
1101 }
1102 
1103 /*2
1104 *computes the binomial coefficient
1105 */
1106 int binom (int n,int r)
1107 {
1108  int i;
1109  int64 result;
1110 
1111  if (r==0) return 1;
1112  if (n-r<r) return binom(n,n-r);
1113  result = n-r+1;
1114  for (i=2;i<=r;i++)
1115  {
1116  result *= n-r+i;
1117  result /= i;
1118  }
1119  if (result>MAX_INT_VAL)
1120  {
1121  WarnS("overflow in binomials");
1122  result=0;
1123  }
1124  return (int)result;
1125 }
1126 
1127 
1128 /// the free module of rank i
1129 ideal id_FreeModule (int i, const ring r)
1130 {
1131  assume(i >= 0);
1132  if (r->isLPring)
1133  {
1134  PrintS("In order to address bimodules, the command freeAlgebra should be used.");
1135  }
1136  ideal h = idInit(i, i);
1137 
1138  for (int j=0; j<i; j++)
1139  {
1140  h->m[j] = p_One(r);
1141  p_SetComp(h->m[j],j+1,r);
1142  p_SetmComp(h->m[j],r);
1143  }
1144 
1145  return h;
1146 }
1147 
1148 /*2
1149 *computes recursively all monomials of a certain degree
1150 *in every step the actvar-th entry in the exponential
1151 *vector is incremented and the other variables are
1152 *computed by recursive calls of makemonoms
1153 *if the last variable is reached, the difference to the
1154 *degree is computed directly
1155 *vars is the number variables
1156 *actvar is the actual variable to handle
1157 *deg is the degree of the monomials to compute
1158 *monomdeg is the actual degree of the monomial in consideration
1159 */
1160 static void makemonoms(int vars,int actvar,int deg,int monomdeg, const ring r)
1161 {
1162  poly p;
1163  int i=0;
1164 
1165  if ((idpowerpoint == 0) && (actvar ==1))
1166  {
1167  idpower[idpowerpoint] = p_One(r);
1168  monomdeg = 0;
1169  }
1170  while (i<=deg)
1171  {
1172  if (deg == monomdeg)
1173  {
1175  idpowerpoint++;
1176  return;
1177  }
1178  if (actvar == vars)
1179  {
1180  p_SetExp(idpower[idpowerpoint],actvar,deg-monomdeg,r);
1183  idpowerpoint++;
1184  return;
1185  }
1186  else
1187  {
1188  p = p_Copy(idpower[idpowerpoint],r);
1189  makemonoms(vars,actvar+1,deg,monomdeg,r);
1190  idpower[idpowerpoint] = p;
1191  }
1192  monomdeg++;
1193  p_SetExp(idpower[idpowerpoint],actvar,p_GetExp(idpower[idpowerpoint],actvar,r)+1,r);
1196  i++;
1197  }
1198 }
1199 
1200 #ifdef HAVE_SHIFTBBA
1201 /*2
1202 *computes recursively all letterplace monomials of a certain degree
1203 *vars is the number of original variables (lV)
1204 *deg is the degree of the monomials to compute
1205 *
1206 *NOTE: We use idpowerpoint as the last index of the previous call
1207 */
1208 static void lpmakemonoms(int vars, int deg, const ring r)
1209 {
1210  assume(deg <= r->N/r->isLPring);
1211  if (deg == 0)
1212  {
1213  idpower[0] = p_One(r);
1214  return;
1215  }
1216  else
1217  {
1218  lpmakemonoms(vars, deg - 1, r);
1219  }
1220 
1221  int size = idpowerpoint + 1;
1222  for (int j = 2; j <= vars; j++)
1223  {
1224  for (int i = 0; i < size; i++)
1225  {
1226  idpowerpoint = (j-1)*size + i;
1228  }
1229  }
1230  for (int j = 1; j <= vars; j++)
1231  {
1232  for (int i = 0; i < size; i++)
1233  {
1234  idpowerpoint = (j-1)*size + i;
1235  p_SetExp(idpower[idpowerpoint], ((deg - 1) * r->isLPring) + j, 1, r);
1238  }
1239  }
1240 }
1241 #endif
1242 
1243 /*2
1244 *returns the deg-th power of the maximal ideal of 0
1245 */
1246 ideal id_MaxIdeal(int deg, const ring r)
1247 {
1248  if (deg < 1)
1249  {
1250  ideal I=idInit(1,1);
1251  I->m[0]=p_One(r);
1252  return I;
1253  }
1254  if (deg == 1
1255 #ifdef HAVE_SHIFTBBA
1256  && !r->isLPring
1257 #endif
1258  )
1259  {
1260  return id_MaxIdeal(r);
1261  }
1262 
1263  int vars, i;
1264 #ifdef HAVE_SHIFTBBA
1265  if (r->isLPring)
1266  {
1267  vars = r->isLPring - r->LPncGenCount;
1268  i = 1;
1269  // i = vars^deg
1270  for (int j = 0; j < deg; j++)
1271  {
1272  i *= vars;
1273  }
1274  }
1275  else
1276 #endif
1277  {
1278  vars = rVar(r);
1279  i = binom(vars+deg-1,deg);
1280  }
1281  if (i<=0) return idInit(1,1);
1282  ideal id=idInit(i,1);
1283  idpower = id->m;
1284  idpowerpoint = 0;
1285 #ifdef HAVE_SHIFTBBA
1286  if (r->isLPring)
1287  {
1288  lpmakemonoms(vars, deg, r);
1289  }
1290  else
1291 #endif
1292  {
1293  makemonoms(vars,1,deg,0,r);
1294  }
1295  idpower = NULL;
1296  idpowerpoint = 0;
1297  return id;
1298 }
1299 
1300 static void id_NextPotence(ideal given, ideal result,
1301  int begin, int end, int deg, int restdeg, poly ap, const ring r)
1302 {
1303  poly p;
1304  int i;
1305 
1306  p = p_Power(p_Copy(given->m[begin],r),restdeg,r);
1307  i = result->nrows;
1308  result->m[i] = p_Mult_q(p_Copy(ap,r),p,r);
1309 //PrintS(".");
1310  (result->nrows)++;
1311  if (result->nrows >= IDELEMS(result))
1312  {
1313  pEnlargeSet(&(result->m),IDELEMS(result),16);
1314  IDELEMS(result) += 16;
1315  }
1316  if (begin == end) return;
1317  for (i=restdeg-1;i>0;i--)
1318  {
1319  p = p_Power(p_Copy(given->m[begin],r),i,r);
1320  p = p_Mult_q(p_Copy(ap,r),p,r);
1321  id_NextPotence(given, result, begin+1, end, deg, restdeg-i, p,r);
1322  p_Delete(&p,r);
1323  }
1324  id_NextPotence(given, result, begin+1, end, deg, restdeg, ap,r);
1325 }
1326 
1327 ideal id_Power(ideal given,int exp, const ring r)
1328 {
1329  ideal result,temp;
1330  poly p1;
1331  int i;
1332 
1333  if (idIs0(given)) return idInit(1,1);
1334  temp = id_Copy(given,r);
1335  idSkipZeroes(temp);
1336  i = binom(IDELEMS(temp)+exp-1,exp);
1337  result = idInit(i,1);
1338  result->nrows = 0;
1339 //Print("ideal contains %d elements\n",i);
1340  p1=p_One(r);
1341  id_NextPotence(temp,result,0,IDELEMS(temp)-1,exp,exp,p1,r);
1342  p_Delete(&p1,r);
1343  id_Delete(&temp,r);
1344  result->nrows = 1;
1345  id_DelEquals(result,r);
1347  return result;
1348 }
1349 
1350 /*2
1351 *skips all zeroes and double elements, searches also for units
1352 */
1353 void id_Compactify(ideal id, const ring r)
1354 {
1355  int i;
1356  BOOLEAN b=FALSE;
1357 
1358  i = IDELEMS(id)-1;
1359  while ((! b) && (i>=0))
1360  {
1361  b=p_IsUnit(id->m[i],r);
1362  i--;
1363  }
1364  if (b)
1365  {
1366  for(i=IDELEMS(id)-1;i>=0;i--) p_Delete(&id->m[i],r);
1367  id->m[0]=p_One(r);
1368  }
1369  else
1370  {
1371  id_DelMultiples(id,r);
1372  }
1373  idSkipZeroes(id);
1374 }
1375 
1376 /// returns the ideals of initial terms
1377 ideal id_Head(ideal h,const ring r)
1378 {
1379  ideal m = idInit(IDELEMS(h),h->rank);
1380 
1381  if (r->cf->has_simple_Alloc)
1382  {
1383  for (int i=IDELEMS(h)-1;i>=0; i--)
1384  if (h->m[i]!=NULL)
1385  m->m[i]=p_CopyPowerProduct0(h->m[i],pGetCoeff(h->m[i]),r);
1386  }
1387  else
1388  {
1389  for (int i=IDELEMS(h)-1;i>=0; i--)
1390  if (h->m[i]!=NULL)
1391  m->m[i]=p_Head(h->m[i],r);
1392  }
1393 
1394  return m;
1395 }
1396 
1397 ideal id_Homogen(ideal h, int varnum,const ring r)
1398 {
1399  ideal m = idInit(IDELEMS(h),h->rank);
1400  int i;
1401 
1402  for (i=IDELEMS(h)-1;i>=0; i--)
1403  {
1404  m->m[i]=p_Homogen(h->m[i],varnum,r);
1405  }
1406  return m;
1407 }
1408 
1409 /*------------------type conversions----------------*/
1410 ideal id_Vec2Ideal(poly vec, const ring R)
1411 {
1412  ideal result=idInit(1,1);
1414  p_Vec2Polys(vec, &(result->m), &(IDELEMS(result)),R);
1415  return result;
1416 }
1417 
1418 /// for julia: convert an array of poly to vector
1419 poly id_Array2Vector(poly *m, unsigned n, const ring R)
1420 {
1421  poly h;
1422  int l;
1423  sBucket_pt bucket = sBucketCreate(R);
1424 
1425  for(unsigned j=0;j<n ;j++)
1426  {
1427  h = m[j];
1428  if (h!=NULL)
1429  {
1430  h=p_Copy(h, R);
1431  l=pLength(h);
1432  p_SetCompP(h,j+1, R);
1433  sBucket_Merge_p(bucket, h, l);
1434  }
1435  }
1436  sBucketClearMerge(bucket, &h, &l);
1437  sBucketDestroy(&bucket);
1438  return h;
1439 }
1440 
1441 /// converts mat to module, destroys mat
1442 ideal id_Matrix2Module(matrix mat, const ring R)
1443 {
1444  int mc=MATCOLS(mat);
1445  int mr=MATROWS(mat);
1446  ideal result = idInit(mc,mr);
1447  int i,j,l;
1448  poly h;
1449  sBucket_pt bucket = sBucketCreate(R);
1450 
1451  for(j=0;j<mc /*MATCOLS(mat)*/;j++) /* j is also index in result->m */
1452  {
1453  for (i=0;i<mr /*MATROWS(mat)*/;i++)
1454  {
1455  h = MATELEM0(mat,i,j);
1456  if (h!=NULL)
1457  {
1458  l=pLength(h);
1459  MATELEM0(mat,i,j)=NULL;
1460  p_SetCompP(h,i+1, R);
1461  sBucket_Merge_p(bucket, h, l);
1462  }
1463  }
1464  sBucketClearMerge(bucket, &(result->m[j]), &l);
1465  }
1466  sBucketDestroy(&bucket);
1467 
1468  // obachman: need to clean this up
1469  id_Delete((ideal*) &mat,R);
1470  return result;
1471 }
1472 
1473 /*2
1474 * converts a module into a matrix, destroyes the input
1475 */
1476 matrix id_Module2Matrix(ideal mod, const ring R)
1477 {
1478  matrix result = mpNew(mod->rank,IDELEMS(mod));
1479  long i; long cp;
1480  poly p,h;
1481 
1482  for(i=0;i<IDELEMS(mod);i++)
1483  {
1484  p=pReverse(mod->m[i]);
1485  mod->m[i]=NULL;
1486  while (p!=NULL)
1487  {
1488  h=p;
1489  pIter(p);
1490  pNext(h)=NULL;
1491  cp = si_max(1L,p_GetComp(h, R)); // if used for ideals too
1492  //cp = p_GetComp(h,R);
1493  p_SetComp(h,0,R);
1494  p_SetmComp(h,R);
1495 #ifdef TEST
1496  if (cp>mod->rank)
1497  {
1498  Print("## inv. rank %ld -> %ld\n",mod->rank,cp);
1499  int k,l,o=mod->rank;
1500  mod->rank=cp;
1501  matrix d=mpNew(mod->rank,IDELEMS(mod));
1502  for (l=0; l<o; l++)
1503  {
1504  for (k=0; k<IDELEMS(mod); k++)
1505  {
1506  MATELEM0(d,l,k)=MATELEM0(result,l,k);
1507  MATELEM0(result,l,k)=NULL;
1508  }
1509  }
1510  id_Delete((ideal *)&result,R);
1511  result=d;
1512  }
1513 #endif
1514  MATELEM0(result,cp-1,i) = p_Add_q(MATELEM0(result,cp-1,i),h,R);
1515  }
1516  }
1517  // obachman 10/99: added the following line, otherwise memory leack!
1518  id_Delete(&mod,R);
1519  return result;
1520 }
1521 
1522 matrix id_Module2formatedMatrix(ideal mod,int rows, int cols, const ring R)
1523 {
1524  matrix result = mpNew(rows,cols);
1525  int i,cp,r=id_RankFreeModule(mod,R),c=IDELEMS(mod);
1526  poly p,h;
1527 
1528  if (r>rows) r = rows;
1529  if (c>cols) c = cols;
1530  for(i=0;i<c;i++)
1531  {
1532  p=pReverse(mod->m[i]);
1533  mod->m[i]=NULL;
1534  while (p!=NULL)
1535  {
1536  h=p;
1537  pIter(p);
1538  pNext(h)=NULL;
1539  cp = p_GetComp(h,R);
1540  if (cp<=r)
1541  {
1542  p_SetComp(h,0,R);
1543  p_SetmComp(h,R);
1544  MATELEM0(result,cp-1,i) = p_Add_q(MATELEM0(result,cp-1,i),h,R);
1545  }
1546  else
1547  p_Delete(&h,R);
1548  }
1549  }
1550  id_Delete(&mod,R);
1551  return result;
1552 }
1553 
1554 ideal id_ResizeModule(ideal mod,int rows, int cols, const ring R)
1555 {
1556  // columns?
1557  if (cols!=IDELEMS(mod))
1558  {
1559  for(int i=IDELEMS(mod)-1;i>=cols;i--) p_Delete(&mod->m[i],R);
1560  pEnlargeSet(&(mod->m),IDELEMS(mod),cols-IDELEMS(mod));
1561  IDELEMS(mod)=cols;
1562  }
1563  // rows?
1564  if (rows<mod->rank)
1565  {
1566  for(int i=IDELEMS(mod)-1;i>=0;i--)
1567  {
1568  if (mod->m[i]!=NULL)
1569  {
1570  while((mod->m[i]!=NULL) && (p_GetComp(mod->m[i],R)>rows))
1571  mod->m[i]=p_LmDeleteAndNext(mod->m[i],R);
1572  poly p=mod->m[i];
1573  while(pNext(p)!=NULL)
1574  {
1575  if (p_GetComp(pNext(p),R)>rows)
1577  else
1578  pIter(p);
1579  }
1580  }
1581  }
1582  }
1583  mod->rank=rows;
1584  return mod;
1585 }
1586 
1587 /*2
1588 * substitute the n-th variable by the monomial e in id
1589 * destroy id
1590 */
1591 ideal id_Subst(ideal id, int n, poly e, const ring r)
1592 {
1593  int k=MATROWS((matrix)id)*MATCOLS((matrix)id);
1594  ideal res=(ideal)mpNew(MATROWS((matrix)id),MATCOLS((matrix)id));
1595 
1596  res->rank = id->rank;
1597  for(k--;k>=0;k--)
1598  {
1599  res->m[k]=p_Subst(id->m[k],n,e,r);
1600  id->m[k]=NULL;
1601  }
1602  id_Delete(&id,r);
1603  return res;
1604 }
1605 
1606 BOOLEAN id_HomModule(ideal m, ideal Q, intvec **w, const ring R)
1607 {
1608  if (w!=NULL) *w=NULL;
1609  if ((Q!=NULL) && (!id_HomIdeal(Q,NULL,R))) return FALSE;
1610  if (idIs0(m))
1611  {
1612  if (w!=NULL) (*w)=new intvec(m->rank);
1613  return TRUE;
1614  }
1615 
1616  long cmax=1,order=0,ord,* diff,diffmin=32000;
1617  int *iscom;
1618  int i;
1619  poly p=NULL;
1620  pFDegProc d;
1621  if (R->pLexOrder && (R->order[0]==ringorder_lp))
1622  d=p_Totaldegree;
1623  else
1624  d=R->pFDeg;
1625  int length=IDELEMS(m);
1626  poly* P=m->m;
1627  poly* F=(poly*)omAlloc(length*sizeof(poly));
1628  for (i=length-1;i>=0;i--)
1629  {
1630  p=F[i]=P[i];
1631  cmax=si_max(cmax,p_MaxComp(p,R));
1632  }
1633  cmax++;
1634  diff = (long *)omAlloc0(cmax*sizeof(long));
1635  if (w!=NULL) *w=new intvec(cmax-1);
1636  iscom = (int *)omAlloc0(cmax*sizeof(int));
1637  i=0;
1638  while (i<=length)
1639  {
1640  if (i<length)
1641  {
1642  p=F[i];
1643  while ((p!=NULL) && (iscom[__p_GetComp(p,R)]==0)) pIter(p);
1644  }
1645  if ((p==NULL) && (i<length))
1646  {
1647  i++;
1648  }
1649  else
1650  {
1651  if (p==NULL) /* && (i==length) */
1652  {
1653  i=0;
1654  while ((i<length) && (F[i]==NULL)) i++;
1655  if (i>=length) break;
1656  p = F[i];
1657  }
1658  //if (pLexOrder && (currRing->order[0]==ringorder_lp))
1659  // order=pTotaldegree(p);
1660  //else
1661  // order = p->order;
1662  // order = pFDeg(p,currRing);
1663  order = d(p,R) +diff[__p_GetComp(p,R)];
1664  //order += diff[pGetComp(p)];
1665  p = F[i];
1666 //Print("Actual p=F[%d]: ",i);pWrite(p);
1667  F[i] = NULL;
1668  i=0;
1669  }
1670  while (p!=NULL)
1671  {
1672  if (R->pLexOrder && (R->order[0]==ringorder_lp))
1673  ord=p_Totaldegree(p,R);
1674  else
1675  // ord = p->order;
1676  ord = R->pFDeg(p,R);
1677  if (iscom[__p_GetComp(p,R)]==0)
1678  {
1679  diff[__p_GetComp(p,R)] = order-ord;
1680  iscom[__p_GetComp(p,R)] = 1;
1681 /*
1682 *PrintS("new diff: ");
1683 *for (j=0;j<cmax;j++) Print("%d ",diff[j]);
1684 *PrintLn();
1685 *PrintS("new iscom: ");
1686 *for (j=0;j<cmax;j++) Print("%d ",iscom[j]);
1687 *PrintLn();
1688 *Print("new set %d, order %d, ord %d, diff %d\n",pGetComp(p),order,ord,diff[pGetComp(p)]);
1689 */
1690  }
1691  else
1692  {
1693 /*
1694 *PrintS("new diff: ");
1695 *for (j=0;j<cmax;j++) Print("%d ",diff[j]);
1696 *PrintLn();
1697 *Print("order %d, ord %d, diff %d\n",order,ord,diff[pGetComp(p)]);
1698 */
1699  if (order != (ord+diff[__p_GetComp(p,R)]))
1700  {
1701  omFreeSize((ADDRESS) iscom,cmax*sizeof(int));
1702  omFreeSize((ADDRESS) diff,cmax*sizeof(long));
1703  omFreeSize((ADDRESS) F,length*sizeof(poly));
1704  delete *w;*w=NULL;
1705  return FALSE;
1706  }
1707  }
1708  pIter(p);
1709  }
1710  }
1711  omFreeSize((ADDRESS) iscom,cmax*sizeof(int));
1712  omFreeSize((ADDRESS) F,length*sizeof(poly));
1713  for (i=1;i<cmax;i++) (**w)[i-1]=(int)(diff[i]);
1714  for (i=1;i<cmax;i++)
1715  {
1716  if (diff[i]<diffmin) diffmin=diff[i];
1717  }
1718  if (w!=NULL)
1719  {
1720  for (i=1;i<cmax;i++)
1721  {
1722  (**w)[i-1]=(int)(diff[i]-diffmin);
1723  }
1724  }
1725  omFreeSize((ADDRESS) diff,cmax*sizeof(long));
1726  return TRUE;
1727 }
1728 
1729 ideal id_Jet(const ideal i,int d, const ring R)
1730 {
1731  ideal r=idInit((i->nrows)*(i->ncols),i->rank);
1732  r->nrows = i-> nrows;
1733  r->ncols = i-> ncols;
1734  //r->rank = i-> rank;
1735 
1736  for(long k=((long)(i->nrows))*((long)(i->ncols))-1;k>=0; k--)
1737  r->m[k]=pp_Jet(i->m[k],d,R);
1738 
1739  return r;
1740 }
1741 
1742 ideal id_JetW(const ideal i,int d, intvec * iv, const ring R)
1743 {
1744  ideal r=idInit(IDELEMS(i),i->rank);
1745  if (ecartWeights!=NULL)
1746  {
1747  WerrorS("cannot compute weighted jets now");
1748  }
1749  else
1750  {
1751  int *w=iv2array(iv,R);
1752  int k;
1753  for(k=0; k<IDELEMS(i); k++)
1754  {
1755  r->m[k]=pp_JetW(i->m[k],d,w,R);
1756  }
1757  omFreeSize((ADDRESS)w,(rVar(R)+1)*sizeof(int));
1758  }
1759  return r;
1760 }
1761 
1762 /*3
1763 * searches for the next unit in the components of the module arg and
1764 * returns the first one;
1765 */
1766 int id_ReadOutPivot(ideal arg,int* comp, const ring r)
1767 {
1768  if (idIs0(arg)) return -1;
1769  int i=0,j, generator=-1;
1770  int rk_arg=arg->rank; //idRankFreeModule(arg);
1771  int * componentIsUsed =(int *)omAlloc((rk_arg+1)*sizeof(int));
1772  poly p;
1773 
1774  while ((generator<0) && (i<IDELEMS(arg)))
1775  {
1776  memset(componentIsUsed,0,(rk_arg+1)*sizeof(int));
1777  p = arg->m[i];
1778  while (p!=NULL)
1779  {
1780  j = __p_GetComp(p,r);
1781  if (componentIsUsed[j]==0)
1782  {
1783  if (p_LmIsConstantComp(p,r) &&
1784  (!rField_is_Ring(r) || n_IsUnit(pGetCoeff(p),r->cf)))
1785  {
1786  generator = i;
1787  componentIsUsed[j] = 1;
1788  }
1789  else
1790  {
1791  componentIsUsed[j] = -1;
1792  }
1793  }
1794  else if (componentIsUsed[j]>0)
1795  {
1796  (componentIsUsed[j])++;
1797  }
1798  pIter(p);
1799  }
1800  i++;
1801  }
1802  i = 0;
1803  *comp = -1;
1804  for (j=0;j<=rk_arg;j++)
1805  {
1806  if (componentIsUsed[j]>0)
1807  {
1808  if ((*comp==-1) || (componentIsUsed[j]<i))
1809  {
1810  *comp = j;
1811  i= componentIsUsed[j];
1812  }
1813  }
1814  }
1815  omFree(componentIsUsed);
1816  return generator;
1817 }
1818 
1819 #if 0
1820 static void idDeleteComp(ideal arg,int red_comp)
1821 {
1822  int i,j;
1823  poly p;
1824 
1825  for (i=IDELEMS(arg)-1;i>=0;i--)
1826  {
1827  p = arg->m[i];
1828  while (p!=NULL)
1829  {
1830  j = pGetComp(p);
1831  if (j>red_comp)
1832  {
1833  pSetComp(p,j-1);
1834  pSetm(p);
1835  }
1836  pIter(p);
1837  }
1838  }
1839  (arg->rank)--;
1840 }
1841 #endif
1842 
1843 intvec * id_QHomWeight(ideal id, const ring r)
1844 {
1845  poly head, tail;
1846  int k;
1847  int in=IDELEMS(id)-1, ready=0, all=0,
1848  coldim=rVar(r), rowmax=2*coldim;
1849  if (in<0) return NULL;
1850  intvec *imat=new intvec(rowmax+1,coldim,0);
1851 
1852  do
1853  {
1854  head = id->m[in--];
1855  if (head!=NULL)
1856  {
1857  tail = pNext(head);
1858  while (tail!=NULL)
1859  {
1860  all++;
1861  for (k=1;k<=coldim;k++)
1862  IMATELEM(*imat,all,k) = p_GetExpDiff(head,tail,k,r);
1863  if (all==rowmax)
1864  {
1865  ivTriangIntern(imat, ready, all);
1866  if (ready==coldim)
1867  {
1868  delete imat;
1869  return NULL;
1870  }
1871  }
1872  pIter(tail);
1873  }
1874  }
1875  } while (in>=0);
1876  if (all>ready)
1877  {
1878  ivTriangIntern(imat, ready, all);
1879  if (ready==coldim)
1880  {
1881  delete imat;
1882  return NULL;
1883  }
1884  }
1885  intvec *result = ivSolveKern(imat, ready);
1886  delete imat;
1887  return result;
1888 }
1889 
1890 BOOLEAN id_IsZeroDim(ideal I, const ring r)
1891 {
1892  BOOLEAN *UsedAxis=(BOOLEAN *)omAlloc0(rVar(r)*sizeof(BOOLEAN));
1893  int i,n;
1894  poly po;
1895  BOOLEAN res=TRUE;
1896  for(i=IDELEMS(I)-1;i>=0;i--)
1897  {
1898  po=I->m[i];
1899  if ((po!=NULL) &&((n=p_IsPurePower(po,r))!=0)) UsedAxis[n-1]=TRUE;
1900  }
1901  for(i=rVar(r)-1;i>=0;i--)
1902  {
1903  if(UsedAxis[i]==FALSE) {res=FALSE; break;} // not zero-dim.
1904  }
1905  omFreeSize(UsedAxis,rVar(r)*sizeof(BOOLEAN));
1906  return res;
1907 }
1908 
1909 void id_Normalize(ideal I,const ring r) /* for ideal/matrix */
1910 {
1911  if (rField_has_simple_inverse(r)) return; /* Z/p, GF(p,n), R, long R/C */
1912  int i;
1913  for(i=I->nrows*I->ncols-1;i>=0;i--)
1914  {
1915  p_Normalize(I->m[i],r);
1916  }
1917 }
1918 
1919 int id_MinDegW(ideal M,intvec *w, const ring r)
1920 {
1921  int d=-1;
1922  for(int i=0;i<IDELEMS(M);i++)
1923  {
1924  if (M->m[i]!=NULL)
1925  {
1926  int d0=p_MinDeg(M->m[i],w,r);
1927  if(-1<d0&&((d0<d)||(d==-1)))
1928  d=d0;
1929  }
1930  }
1931  return d;
1932 }
1933 
1934 // #include "kernel/clapsing.h"
1935 
1936 /*2
1937 * transpose a module
1938 */
1939 ideal id_Transp(ideal a, const ring rRing)
1940 {
1941  int r = a->rank, c = IDELEMS(a);
1942  ideal b = idInit(r,c);
1943 
1944  int i;
1945  for (i=c; i>0; i--)
1946  {
1947  poly p=a->m[i-1];
1948  while(p!=NULL)
1949  {
1950  poly h=p_Head(p, rRing);
1951  int co=__p_GetComp(h, rRing)-1;
1952  p_SetComp(h, i, rRing);
1953  p_Setm(h, rRing);
1954  h->next=b->m[co];
1955  b->m[co]=h;
1956  pIter(p);
1957  }
1958  }
1959  for (i=IDELEMS(b)-1; i>=0; i--)
1960  {
1961  poly p=b->m[i];
1962  if(p!=NULL)
1963  {
1964  b->m[i]=p_SortMerge(p,rRing,TRUE);
1965  }
1966  }
1967  return b;
1968 }
1969 
1970 /*2
1971 * The following is needed to compute the image of certain map used in
1972 * the computation of cohomologies via BGG
1973 * let M = { w_1, ..., w_k }, k = size(M) == ncols(M), n = nvars(currRing).
1974 * assuming that nrows(M) <= m*n; the procedure computes:
1975 * transpose(M) * transpose( var(1) I_m | ... | var(n) I_m ) :== transpose(module{f_1, ... f_k}),
1976 * where f_i = \sum_{j=1}^{m} (w_i, v_j) gen(j), (w_i, v_j) is a `scalar` multiplication.
1977 * that is, if w_i = (a^1_1, ... a^1_m) | (a^2_1, ..., a^2_m) | ... | (a^n_1, ..., a^n_m) then
1978 
1979  (a^1_1, ... a^1_m) | (a^2_1, ..., a^2_m) | ... | (a^n_1, ..., a^n_m)
1980 * var_1 ... var_1 | var_2 ... var_2 | ... | var_n ... var(n)
1981 * gen_1 ... gen_m | gen_1 ... gen_m | ... | gen_1 ... gen_m
1982 + =>
1983  f_i =
1984 
1985  a^1_1 * var(1) * gen(1) + ... + a^1_m * var(1) * gen(m) +
1986  a^2_1 * var(2) * gen(1) + ... + a^2_m * var(2) * gen(m) +
1987  ...
1988  a^n_1 * var(n) * gen(1) + ... + a^n_m * var(n) * gen(m);
1989 
1990  NOTE: for every f_i we run only ONCE along w_i saving partial sums into a temporary array of polys of size m
1991 */
1992 ideal id_TensorModuleMult(const int m, const ideal M, const ring rRing)
1993 {
1994 // #ifdef DEBU
1995 // WarnS("tensorModuleMult!!!!");
1996 
1997  assume(m > 0);
1998  assume(M != NULL);
1999 
2000  const int n = rRing->N;
2001 
2002  assume(M->rank <= m * n);
2003 
2004  const int k = IDELEMS(M);
2005 
2006  ideal idTemp = idInit(k,m); // = {f_1, ..., f_k }
2007 
2008  for( int i = 0; i < k; i++ ) // for every w \in M
2009  {
2010  poly pTempSum = NULL;
2011 
2012  poly w = M->m[i];
2013 
2014  while(w != NULL) // for each term of w...
2015  {
2016  poly h = p_Head(w, rRing);
2017 
2018  const int gen = __p_GetComp(h, rRing); // 1 ...
2019 
2020  assume(gen > 0);
2021  assume(gen <= n*m);
2022 
2023  // TODO: write a formula with %, / instead of while!
2024  /*
2025  int c = gen;
2026  int v = 1;
2027  while(c > m)
2028  {
2029  c -= m;
2030  v++;
2031  }
2032  */
2033 
2034  int cc = gen % m;
2035  if( cc == 0) cc = m;
2036  int vv = 1 + (gen - cc) / m;
2037 
2038 // assume( cc == c );
2039 // assume( vv == v );
2040 
2041  // 1<= c <= m
2042  assume( cc > 0 );
2043  assume( cc <= m );
2044 
2045  assume( vv > 0 );
2046  assume( vv <= n );
2047 
2048  assume( (cc + (vv-1)*m) == gen );
2049 
2050  p_IncrExp(h, vv, rRing); // h *= var(j) && // p_AddExp(h, vv, 1, rRing);
2051  p_SetComp(h, cc, rRing);
2052 
2053  p_Setm(h, rRing); // addjust degree after the previous steps!
2054 
2055  pTempSum = p_Add_q(pTempSum, h, rRing); // it is slow since h will be usually put to the back of pTempSum!!!
2056 
2057  pIter(w);
2058  }
2059 
2060  idTemp->m[i] = pTempSum;
2061  }
2062 
2063  // simplify idTemp???
2064 
2065  ideal idResult = id_Transp(idTemp, rRing);
2066 
2067  id_Delete(&idTemp, rRing);
2068 
2069  return(idResult);
2070 }
2071 
2072 ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring r)
2073 {
2074  int cnt=0;int rw=0; int cl=0;
2075  int i,j;
2076  // find max. size of xx[.]:
2077  for(j=rl-1;j>=0;j--)
2078  {
2079  i=IDELEMS(xx[j])*xx[j]->nrows;
2080  if (i>cnt) cnt=i;
2081  if (xx[j]->nrows >rw) rw=xx[j]->nrows; // for lifting matrices
2082  if (xx[j]->ncols >cl) cl=xx[j]->ncols; // for lifting matrices
2083  }
2084  if (rw*cl !=cnt)
2085  {
2086  WerrorS("format mismatch in CRT");
2087  return NULL;
2088  }
2089  ideal result=idInit(cnt,xx[0]->rank);
2090  result->nrows=rw; // for lifting matrices
2091  result->ncols=cl; // for lifting matrices
2092  number *x=(number *)omAlloc(rl*sizeof(number));
2093  poly *p=(poly *)omAlloc(rl*sizeof(poly));
2094  CFArray inv_cache(rl);
2095  EXTERN_VAR int n_SwitchChinRem; //TEST
2096  int save_n_SwitchChinRem=n_SwitchChinRem;
2097  n_SwitchChinRem=1;
2098  for(i=cnt-1;i>=0;i--)
2099  {
2100  for(j=rl-1;j>=0;j--)
2101  {
2102  if(i>=IDELEMS(xx[j])*xx[j]->nrows) // out of range of this ideal
2103  p[j]=NULL;
2104  else
2105  p[j]=xx[j]->m[i];
2106  }
2107  result->m[i]=p_ChineseRemainder(p,x,q,rl,inv_cache,r);
2108  for(j=rl-1;j>=0;j--)
2109  {
2110  if(i<IDELEMS(xx[j])*xx[j]->nrows) xx[j]->m[i]=p[j];
2111  }
2112  }
2113  n_SwitchChinRem=save_n_SwitchChinRem;
2114  omFreeSize(p,rl*sizeof(poly));
2115  omFreeSize(x,rl*sizeof(number));
2116  for(i=rl-1;i>=0;i--) id_Delete(&(xx[i]),r);
2117  omFreeSize(xx,rl*sizeof(ideal));
2118  return result;
2119 }
2120 
2121 void id_Shift(ideal M, int s, const ring r)
2122 {
2123 // id_Test( M, r );
2124 
2125 // assume( s >= 0 ); // negative is also possible // TODO: verify input ideal in such a case!?
2126 
2127  for(int i=IDELEMS(M)-1; i>=0;i--)
2128  p_Shift(&(M->m[i]),s,r);
2129 
2130  M->rank += s;
2131 
2132 // id_Test( M, r );
2133 }
2134 
2135 ideal id_Delete_Pos(const ideal I, const int p, const ring r)
2136 {
2137  if ((p<0)||(p>=IDELEMS(I))) return NULL;
2138  ideal ret=idInit(IDELEMS(I)-1,I->rank);
2139  for(int i=0;i<p;i++) ret->m[i]=p_Copy(I->m[i],r);
2140  for(int i=p+1;i<IDELEMS(I);i++) ret->m[i-1]=p_Copy(I->m[i],r);
2141  return ret;
2142 }
All the auxiliary stuff.
long int64
Definition: auxiliary.h:68
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
void * ADDRESS
Definition: auxiliary.h:119
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
CanonicalForm head(const CanonicalForm &f)
int level(const CanonicalForm &f)
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
cl
Definition: cfModGcd.cc:4100
CanonicalForm b
Definition: cfModGcd.cc:4103
int int ncols
Definition: cf_linsys.cc:32
int nrows
Definition: cf_linsys.cc:32
FILE * f
Definition: checklibs.c:9
Definition: intvec.h:23
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:512
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff 'n' is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2),...
Definition: coeffs.h:491
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:461
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
Definition: coeffs.h:652
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:452
#define Print
Definition: emacs.cc:80
#define WarnS
Definition: emacs.cc:78
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int s
Definition: facAbsFact.cc:51
CanonicalForm res
Definition: facAbsFact.cc:60
const CanonicalForm & w
Definition: facAbsFact.cc:51
fq_nmod_poly_t * vec
Definition: facHensel.cc:108
int j
Definition: facHensel.cc:110
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
void WerrorS(const char *s)
Definition: feFopen.cc:24
#define STATIC_VAR
Definition: globaldefs.h:7
#define EXTERN_VAR
Definition: globaldefs.h:6
#define VAR
Definition: globaldefs.h:5
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
void ivTriangIntern(intvec *imat, int &ready, int &all)
Definition: intvec.cc:404
intvec * ivSolveKern(intvec *imat, int dimtr)
Definition: intvec.cc:442
#define IMATELEM(M, I, J)
Definition: intvec.h:85
STATIC_VAR Poly * h
Definition: janet.cc:971
STATIC_VAR jList * Q
Definition: janet.cc:30
poly p_ChineseRemainder(poly *xx, mpz_ptr *x, mpz_ptr *q, int rl, mpz_ptr *C, const ring R)
VAR int n_SwitchChinRem
Definition: longrat.cc:3094
matrix mpNew(int r, int c)
create a r x c zero-matrix
Definition: matpol.cc:37
#define MATELEM0(mat, i, j)
0-based access to matrix
Definition: matpol.h:31
#define MATROWS(i)
Definition: matpol.h:26
#define MATCOLS(i)
Definition: matpol.h:27
#define assume(x)
Definition: mod2.h:389
int dReportError(const char *fmt,...)
Definition: dError.cc:44
#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 __p_GetComp(p, r)
Definition: monomials.h:63
#define rRing_has_Comp(r)
Definition: monomials.h:266
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
STATIC_VAR gmp_float * diff
Definition: mpr_complex.cc:45
const int MAX_INT_VAL
Definition: mylimits.h:12
Definition: ap.h:40
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
#define omdebugAddrSize(addr, size)
Definition: omAllocDecl.h:315
#define omCheckAddrSize(addr, size)
Definition: omAllocDecl.h:327
#define omFree(addr)
Definition: omAllocDecl.h:261
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
#define omFreeBinAddr(addr)
Definition: omAllocDecl.h:258
#define omGetSpecBin(size)
Definition: omBin.h:11
#define NULL
Definition: omList.c:12
omBin_t * omBin
Definition: omStructs.h:12
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition: p_polys.cc:1226
poly pp_Jet(poly p, int m, const ring R)
Definition: p_polys.cc:4354
BOOLEAN p_ComparePolys(poly p1, poly p2, const ring r)
returns TRUE if p1 is a skalar multiple of p2 assume p1 != NULL and p2 != NULL
Definition: p_polys.cc:4572
BOOLEAN p_DivisibleByRingCase(poly f, poly g, const ring r)
divisibility check over ground ring (which may contain zero divisors); TRUE iff LT(f) divides LT(g),...
Definition: p_polys.cc:1638
poly p_Homogen(poly p, int varnum, const ring r)
Definition: p_polys.cc:3266
poly p_Subst(poly p, int n, poly e, const ring r)
Definition: p_polys.cc:3954
void p_Vec2Polys(poly v, poly **p, int *len, const ring r)
Definition: p_polys.cc:3621
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition: p_polys.cc:4702
poly p_Power(poly p, int i, const ring r)
Definition: p_polys.cc:2193
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3809
void p_Norm(poly p1, const ring r)
Definition: p_polys.cc:3715
int p_MinDeg(poly p, intvec *w, const ring R)
Definition: p_polys.cc:4444
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition: p_polys.cc:4776
BOOLEAN p_IsHomogeneousW(poly p, const intvec *w, const ring r)
Definition: p_polys.cc:3339
poly p_One(const ring r)
Definition: p_polys.cc:1313
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3692
BOOLEAN p_IsHomogeneous(poly p, const ring r)
Definition: p_polys.cc:3315
poly pp_JetW(poly p, int m, int *w, const ring R)
Definition: p_polys.cc:4399
poly p_CopyPowerProduct0(const poly p, number n, const ring r)
like p_Head, but with coefficient n
Definition: p_polys.cc:4917
BOOLEAN p_EqualPolys(poly p1, poly p2, const ring r)
Definition: p_polys.cc:4508
static int pLength(poly a)
Definition: p_polys.h:188
static long p_GetExpDiff(poly p1, poly p2, int i, ring r)
Definition: p_polys.h:633
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:934
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1112
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1721
BOOLEAN _p_LmTest(poly p, ring r, int level)
Definition: pDebug.cc:323
void p_ShallowDelete(poly *p, const ring r)
static void p_SetCompP(poly p, int i, ring r)
Definition: p_polys.h:252
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:486
#define pp_Test(p, lmRing, tailRing)
Definition: p_polys.h:161
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:245
static long p_IncrExp(poly p, int v, ring r)
Definition: p_polys.h:589
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:231
#define p_SetmComp
Definition: p_polys.h:242
static poly p_SortMerge(poly p, const ring r, BOOLEAN revert=FALSE)
Definition: p_polys.h:1227
static poly pReverse(poly p)
Definition: p_polys.h:333
static int p_LtCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1619
static BOOLEAN p_LmIsConstantComp(const poly p, const ring r)
Definition: p_polys.h:1004
static poly p_Head(const poly p, const ring r)
copy the (leading) term of p
Definition: p_polys.h:858
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition: p_polys.h:1908
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:467
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1889
static long p_MaxComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:290
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:899
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1149
static void p_LmFree(poly p, ring)
Definition: p_polys.h:681
static BOOLEAN p_IsUnit(const poly p, const ring r)
Definition: p_polys.h:1989
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:753
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:844
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1505
BOOLEAN _pp_Test(poly p, ring lmRing, ring tailRing, int level)
Definition: pDebug.cc:333
#define p_Test(p, r)
Definition: p_polys.h:159
static BOOLEAN p_IsConstantPoly(const poly p, const ring r)
Definition: p_polys.h:1976
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:373
#define pSetm(p)
Definition: polys.h:271
#define pGetComp(p)
Component.
Definition: polys.h:37
#define pSetComp(p, v)
Definition: polys.h:38
void PrintS(const char *s)
Definition: reporter.cc:284
void PrintLn()
Definition: reporter.cc:310
long(* pFDegProc)(poly p, ring r)
Definition: ring.h:38
@ ringorder_lp
Definition: ring.h:77
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:592
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:548
#define rField_is_Ring(R)
Definition: ring.h:485
void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:237
void sBucket_Merge_p(sBucket_pt bucket, poly p, int length)
Merges p into Spoly: assumes Bpoly and p have no common monoms destroys p!
Definition: sbuckets.cc:148
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:103
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:96
void id_DBLmTest(ideal h1, int level, const char *f, const int l, const ring r)
Internal verification for ideals/modules and dense matrices!
ideal id_Add(ideal h1, ideal h2, const ring r)
h1 + h2
STATIC_VAR int idpowerpoint
Definition: simpleideals.cc:31
ideal id_Vec2Ideal(poly vec, const ring R)
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
int id_PosConstant(ideal id, const ring r)
index of generator with leading term in ground ring (if any); otherwise -1
Definition: simpleideals.cc:80
int binom(int n, int r)
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
void id_DBTest(ideal h1, int level, const char *f, const int l, const ring r, const ring tailRing)
Internal verification for ideals/modules and dense matrices!
poly id_Array2Vector(poly *m, unsigned n, const ring R)
for julia: convert an array of poly to vector
static void id_NextPotence(ideal given, ideal result, int begin, int end, int deg, int restdeg, poly ap, const ring r)
void id_Norm(ideal id, const ring r)
ideal id = (id[i]), result is leadcoeff(id[i]) = 1
BOOLEAN id_HomIdeal(ideal id, ideal Q, const ring r)
STATIC_VAR poly * idpower
Definition: simpleideals.cc:29
intvec * id_QHomWeight(ideal id, const ring r)
static void makemonoms(int vars, int actvar, int deg, int monomdeg, const ring r)
BOOLEAN id_HomModuleW(ideal id, ideal Q, const intvec *w, const intvec *module_w, const ring r)
void idGetNextChoise(int r, int end, BOOLEAN *endch, int *choise)
void id_Normalize(ideal I, const ring r)
normialize all polys in id
ideal id_Transp(ideal a, const ring rRing)
transpose a module
ideal id_FreeModule(int i, const ring r)
the free module of rank i
BOOLEAN id_IsZeroDim(ideal I, const ring r)
ideal id_Homogen(ideal h, int varnum, const ring r)
ideal id_Power(ideal given, int exp, const ring r)
matrix id_Module2Matrix(ideal mod, const ring R)
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
ideal id_Copy(ideal h1, const ring r)
copy an ideal
BOOLEAN id_IsConstant(ideal id, const ring r)
test if the ideal has only constant polynomials NOTE: zero ideal/module is also constant
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
BOOLEAN id_HomIdealW(ideal id, ideal Q, const intvec *w, const ring r)
ideal id_TensorModuleMult(const int m, const ideal M, const ring rRing)
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
BOOLEAN idInsertPolyOnPos(ideal I, poly p, int pos)
insert p into I on position pos
int id_ReadOutPivot(ideal arg, int *comp, const ring r)
ideal id_MaxIdeal(const ring r)
initialise the maximal ideal (at 0)
Definition: simpleideals.cc:98
void id_DelDiv(ideal id, const ring r)
delete id[j], if LT(j) == coeff*mon*LT(i) and vice versa, i.e., delete id[i], if LT(i) == coeff*mon*L...
int id_MinDegW(ideal M, intvec *w, const ring r)
void id_DelMultiples(ideal id, const ring r)
ideal id = (id[i]), c any unit if id[i] = c*id[j] then id[j] is deleted for j > i
void id_ShallowDelete(ideal *h, ring r)
Shallowdeletes an ideal/matrix.
BOOLEAN id_InsertPolyWithTests(ideal h1, const int validEntries, const poly h2, const bool zeroOk, const bool duplicateOk, const ring r)
insert h2 into h1 depending on the two boolean parameters:
ideal id_Mult(ideal h1, ideal h2, const ring R)
h1 * h2 one h_i must be an ideal (with at least one column) the other h_i may be a module (with no co...
ideal id_CopyFirstK(const ideal ide, const int k, const ring r)
copies the first k (>= 1) entries of the given ideal/module and returns these as a new ideal/module (...
matrix id_Module2formatedMatrix(ideal mod, int rows, int cols, const ring R)
void idShow(const ideal id, const ring lmRing, const ring tailRing, const int debugPrint)
Definition: simpleideals.cc:57
ideal id_Matrix2Module(matrix mat, const ring R)
converts mat to module, destroys mat
ideal id_ResizeModule(ideal mod, int rows, int cols, const ring R)
ideal id_Delete_Pos(const ideal I, const int p, const ring r)
static int p_Comp_RevLex(poly a, poly b, BOOLEAN nolex, const ring R)
for idSort: compare a and b revlex inclusive module comp.
void id_DelEquals(ideal id, const ring r)
ideal id = (id[i]) if id[i] = id[j] then id[j] is deleted for j > i
VAR omBin sip_sideal_bin
Definition: simpleideals.cc:27
ideal id_Jet(const ideal i, int d, const ring R)
static void id_DelDiv_SEV(ideal id, int k, const ring r)
delete id[j], if LT(j) == coeff*mon*LT(i)
ideal id_SimpleAdd(ideal h1, ideal h2, const ring R)
concat the lists h1 and h2 without zeros
void id_DelLmEquals(ideal id, const ring r)
Delete id[j], if Lm(j) == Lm(i) and both LC(j), LC(i) are units and j > i.
ideal id_JetW(const ideal i, int d, intvec *iv, const ring R)
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
void id_Shift(ideal M, int s, const ring r)
int idGetNumberOfChoise(int t, int d, int begin, int end, int *choise)
intvec * id_Sort(const ideal id, const BOOLEAN nolex, const ring r)
sorts the ideal w.r.t. the actual ringordering uses lex-ordering when nolex = FALSE
void idInitChoise(int r, int beg, int end, BOOLEAN *endch, int *choise)
ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring r)
static void lpmakemonoms(int vars, int deg, const ring r)
void id_Compactify(ideal id, const ring r)
BOOLEAN id_HomModule(ideal m, ideal Q, intvec **w, const ring R)
ideal id_Subst(ideal id, int n, poly e, const ring r)
#define IDELEMS(i)
Definition: simpleideals.h:23
#define id_Test(A, lR)
Definition: simpleideals.h:87
The following sip_sideal structure has many different uses thoughout Singular. Basic use-cases for it...
Definition: simpleideals.h:18
#define R
Definition: sirandom.c:27
#define M
Definition: sirandom.c:25
int * iv2array(intvec *iv, const ring R)
Definition: weight.cc:200
EXTERN_VAR short * ecartWeights
Definition: weight.h:12
#define omPrintAddrInfo(A, B, C)
Definition: xalloc.h:270