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