My Project  UNKNOWN_GIT_VERSION
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 ideal id_ResizeModule(ideal mod,int rows, int cols, const ring R)
1280 {
1281  // columns?
1282  if (cols!=IDELEMS(mod))
1283  {
1284  for(int i=IDELEMS(mod)-1;i>=cols;i--) p_Delete(&mod->m[i],R);
1285  pEnlargeSet(&(mod->m),IDELEMS(mod),cols-IDELEMS(mod));
1286  IDELEMS(mod)=cols;
1287  }
1288  // rows?
1289  if (rows<mod->rank)
1290  {
1291  for(int i=IDELEMS(mod)-1;i>=0;i--)
1292  {
1293  if (mod->m[i]!=NULL)
1294  {
1295  while((mod->m[i]!=NULL) && (p_GetComp(mod->m[i],R)>rows))
1296  mod->m[i]=p_LmDeleteAndNext(mod->m[i],R);
1297  poly p=mod->m[i];
1298  while(pNext(p)!=NULL)
1299  {
1300  if (p_GetComp(pNext(p),R)>rows)
1302  else
1303  pIter(p);
1304  }
1305  }
1306  }
1307  }
1308  mod->rank=rows;
1309  return mod;
1310 }
1311 
1312 /*2
1313 * substitute the n-th variable by the monomial e in id
1314 * destroy id
1315 */
1316 ideal id_Subst(ideal id, int n, poly e, const ring r)
1317 {
1318  int k=MATROWS((matrix)id)*MATCOLS((matrix)id);
1319  ideal res=(ideal)mpNew(MATROWS((matrix)id),MATCOLS((matrix)id));
1320 
1321  res->rank = id->rank;
1322  for(k--;k>=0;k--)
1323  {
1324  res->m[k]=p_Subst(id->m[k],n,e,r);
1325  id->m[k]=NULL;
1326  }
1327  id_Delete(&id,r);
1328  return res;
1329 }
1330 
1331 BOOLEAN id_HomModule(ideal m, ideal Q, intvec **w, const ring R)
1332 {
1333  if (w!=NULL) *w=NULL;
1334  if ((Q!=NULL) && (!id_HomIdeal(Q,NULL,R))) return FALSE;
1335  if (idIs0(m))
1336  {
1337  if (w!=NULL) (*w)=new intvec(m->rank);
1338  return TRUE;
1339  }
1340 
1341  long cmax=1,order=0,ord,* diff,diffmin=32000;
1342  int *iscom;
1343  int i;
1344  poly p=NULL;
1345  pFDegProc d;
1346  if (R->pLexOrder && (R->order[0]==ringorder_lp))
1347  d=p_Totaldegree;
1348  else
1349  d=R->pFDeg;
1350  int length=IDELEMS(m);
1351  poly* P=m->m;
1352  poly* F=(poly*)omAlloc(length*sizeof(poly));
1353  for (i=length-1;i>=0;i--)
1354  {
1355  p=F[i]=P[i];
1356  cmax=si_max(cmax,p_MaxComp(p,R));
1357  }
1358  cmax++;
1359  diff = (long *)omAlloc0(cmax*sizeof(long));
1360  if (w!=NULL) *w=new intvec(cmax-1);
1361  iscom = (int *)omAlloc0(cmax*sizeof(int));
1362  i=0;
1363  while (i<=length)
1364  {
1365  if (i<length)
1366  {
1367  p=F[i];
1368  while ((p!=NULL) && (iscom[__p_GetComp(p,R)]==0)) pIter(p);
1369  }
1370  if ((p==NULL) && (i<length))
1371  {
1372  i++;
1373  }
1374  else
1375  {
1376  if (p==NULL) /* && (i==length) */
1377  {
1378  i=0;
1379  while ((i<length) && (F[i]==NULL)) i++;
1380  if (i>=length) break;
1381  p = F[i];
1382  }
1383  //if (pLexOrder && (currRing->order[0]==ringorder_lp))
1384  // order=pTotaldegree(p);
1385  //else
1386  // order = p->order;
1387  // order = pFDeg(p,currRing);
1388  order = d(p,R) +diff[__p_GetComp(p,R)];
1389  //order += diff[pGetComp(p)];
1390  p = F[i];
1391 //Print("Actual p=F[%d]: ",i);pWrite(p);
1392  F[i] = NULL;
1393  i=0;
1394  }
1395  while (p!=NULL)
1396  {
1397  if (R->pLexOrder && (R->order[0]==ringorder_lp))
1398  ord=p_Totaldegree(p,R);
1399  else
1400  // ord = p->order;
1401  ord = R->pFDeg(p,R);
1402  if (iscom[__p_GetComp(p,R)]==0)
1403  {
1404  diff[__p_GetComp(p,R)] = order-ord;
1405  iscom[__p_GetComp(p,R)] = 1;
1406 /*
1407 *PrintS("new diff: ");
1408 *for (j=0;j<cmax;j++) Print("%d ",diff[j]);
1409 *PrintLn();
1410 *PrintS("new iscom: ");
1411 *for (j=0;j<cmax;j++) Print("%d ",iscom[j]);
1412 *PrintLn();
1413 *Print("new set %d, order %d, ord %d, diff %d\n",pGetComp(p),order,ord,diff[pGetComp(p)]);
1414 */
1415  }
1416  else
1417  {
1418 /*
1419 *PrintS("new diff: ");
1420 *for (j=0;j<cmax;j++) Print("%d ",diff[j]);
1421 *PrintLn();
1422 *Print("order %d, ord %d, diff %d\n",order,ord,diff[pGetComp(p)]);
1423 */
1424  if (order != (ord+diff[__p_GetComp(p,R)]))
1425  {
1426  omFreeSize((ADDRESS) iscom,cmax*sizeof(int));
1427  omFreeSize((ADDRESS) diff,cmax*sizeof(long));
1428  omFreeSize((ADDRESS) F,length*sizeof(poly));
1429  delete *w;*w=NULL;
1430  return FALSE;
1431  }
1432  }
1433  pIter(p);
1434  }
1435  }
1436  omFreeSize((ADDRESS) iscom,cmax*sizeof(int));
1437  omFreeSize((ADDRESS) F,length*sizeof(poly));
1438  for (i=1;i<cmax;i++) (**w)[i-1]=(int)(diff[i]);
1439  for (i=1;i<cmax;i++)
1440  {
1441  if (diff[i]<diffmin) diffmin=diff[i];
1442  }
1443  if (w!=NULL)
1444  {
1445  for (i=1;i<cmax;i++)
1446  {
1447  (**w)[i-1]=(int)(diff[i]-diffmin);
1448  }
1449  }
1450  omFreeSize((ADDRESS) diff,cmax*sizeof(long));
1451  return TRUE;
1452 }
1453 
1454 ideal id_Jet(const ideal i,int d, const ring R)
1455 {
1456  ideal r=idInit((i->nrows)*(i->ncols),i->rank);
1457  r->nrows = i-> nrows;
1458  r->ncols = i-> ncols;
1459  //r->rank = i-> rank;
1460 
1461  for(int k=(i->nrows)*(i->ncols)-1;k>=0; k--)
1462  r->m[k]=pp_Jet(i->m[k],d,R);
1463 
1464  return r;
1465 }
1466 
1467 ideal id_JetW(const ideal i,int d, intvec * iv, const ring R)
1468 {
1469  ideal r=idInit(IDELEMS(i),i->rank);
1470  if (ecartWeights!=NULL)
1471  {
1472  WerrorS("cannot compute weighted jets now");
1473  }
1474  else
1475  {
1476  short *w=iv2array(iv,R);
1477  int k;
1478  for(k=0; k<IDELEMS(i); k++)
1479  {
1480  r->m[k]=pp_JetW(i->m[k],d,w,R);
1481  }
1482  omFreeSize((ADDRESS)w,(rVar(R)+1)*sizeof(short));
1483  }
1484  return r;
1485 }
1486 
1487 /*3
1488 * searches for the next unit in the components of the module arg and
1489 * returns the first one;
1490 */
1491 int id_ReadOutPivot(ideal arg,int* comp, const ring r)
1492 {
1493  if (idIs0(arg)) return -1;
1494  int i=0,j, generator=-1;
1495  int rk_arg=arg->rank; //idRankFreeModule(arg);
1496  int * componentIsUsed =(int *)omAlloc((rk_arg+1)*sizeof(int));
1497  poly p;
1498 
1499  while ((generator<0) && (i<IDELEMS(arg)))
1500  {
1501  memset(componentIsUsed,0,(rk_arg+1)*sizeof(int));
1502  p = arg->m[i];
1503  while (p!=NULL)
1504  {
1505  j = __p_GetComp(p,r);
1506  if (componentIsUsed[j]==0)
1507  {
1508  if (p_LmIsConstantComp(p,r) &&
1509  (!rField_is_Ring(r) || n_IsUnit(pGetCoeff(p),r->cf)))
1510  {
1511  generator = i;
1512  componentIsUsed[j] = 1;
1513  }
1514  else
1515  {
1516  componentIsUsed[j] = -1;
1517  }
1518  }
1519  else if (componentIsUsed[j]>0)
1520  {
1521  (componentIsUsed[j])++;
1522  }
1523  pIter(p);
1524  }
1525  i++;
1526  }
1527  i = 0;
1528  *comp = -1;
1529  for (j=0;j<=rk_arg;j++)
1530  {
1531  if (componentIsUsed[j]>0)
1532  {
1533  if ((*comp==-1) || (componentIsUsed[j]<i))
1534  {
1535  *comp = j;
1536  i= componentIsUsed[j];
1537  }
1538  }
1539  }
1540  omFree(componentIsUsed);
1541  return generator;
1542 }
1543 
1544 #if 0
1545 static void idDeleteComp(ideal arg,int red_comp)
1546 {
1547  int i,j;
1548  poly p;
1549 
1550  for (i=IDELEMS(arg)-1;i>=0;i--)
1551  {
1552  p = arg->m[i];
1553  while (p!=NULL)
1554  {
1555  j = pGetComp(p);
1556  if (j>red_comp)
1557  {
1558  pSetComp(p,j-1);
1559  pSetm(p);
1560  }
1561  pIter(p);
1562  }
1563  }
1564  (arg->rank)--;
1565 }
1566 #endif
1567 
1568 intvec * id_QHomWeight(ideal id, const ring r)
1569 {
1570  poly head, tail;
1571  int k;
1572  int in=IDELEMS(id)-1, ready=0, all=0,
1573  coldim=rVar(r), rowmax=2*coldim;
1574  if (in<0) return NULL;
1575  intvec *imat=new intvec(rowmax+1,coldim,0);
1576 
1577  do
1578  {
1579  head = id->m[in--];
1580  if (head!=NULL)
1581  {
1582  tail = pNext(head);
1583  while (tail!=NULL)
1584  {
1585  all++;
1586  for (k=1;k<=coldim;k++)
1587  IMATELEM(*imat,all,k) = p_GetExpDiff(head,tail,k,r);
1588  if (all==rowmax)
1589  {
1590  ivTriangIntern(imat, ready, all);
1591  if (ready==coldim)
1592  {
1593  delete imat;
1594  return NULL;
1595  }
1596  }
1597  pIter(tail);
1598  }
1599  }
1600  } while (in>=0);
1601  if (all>ready)
1602  {
1603  ivTriangIntern(imat, ready, all);
1604  if (ready==coldim)
1605  {
1606  delete imat;
1607  return NULL;
1608  }
1609  }
1610  intvec *result = ivSolveKern(imat, ready);
1611  delete imat;
1612  return result;
1613 }
1614 
1615 BOOLEAN id_IsZeroDim(ideal I, const ring r)
1616 {
1617  BOOLEAN *UsedAxis=(BOOLEAN *)omAlloc0(rVar(r)*sizeof(BOOLEAN));
1618  int i,n;
1619  poly po;
1620  BOOLEAN res=TRUE;
1621  for(i=IDELEMS(I)-1;i>=0;i--)
1622  {
1623  po=I->m[i];
1624  if ((po!=NULL) &&((n=p_IsPurePower(po,r))!=0)) UsedAxis[n-1]=TRUE;
1625  }
1626  for(i=rVar(r)-1;i>=0;i--)
1627  {
1628  if(UsedAxis[i]==FALSE) {res=FALSE; break;} // not zero-dim.
1629  }
1630  omFreeSize(UsedAxis,rVar(r)*sizeof(BOOLEAN));
1631  return res;
1632 }
1633 
1634 void id_Normalize(ideal I,const ring r) /* for ideal/matrix */
1635 {
1636  if (rField_has_simple_inverse(r)) return; /* Z/p, GF(p,n), R, long R/C */
1637  int i;
1638  for(i=I->nrows*I->ncols-1;i>=0;i--)
1639  {
1640  p_Normalize(I->m[i],r);
1641  }
1642 }
1643 
1644 int id_MinDegW(ideal M,intvec *w, const ring r)
1645 {
1646  int d=-1;
1647  for(int i=0;i<IDELEMS(M);i++)
1648  {
1649  if (M->m[i]!=NULL)
1650  {
1651  int d0=p_MinDeg(M->m[i],w,r);
1652  if(-1<d0&&((d0<d)||(d==-1)))
1653  d=d0;
1654  }
1655  }
1656  return d;
1657 }
1658 
1659 // #include "kernel/clapsing.h"
1660 
1661 /*2
1662 * transpose a module
1663 */
1664 ideal id_Transp(ideal a, const ring rRing)
1665 {
1666  int r = a->rank, c = IDELEMS(a);
1667  ideal b = idInit(r,c);
1668 
1669  int i;
1670  for (i=c; i>0; i--)
1671  {
1672  poly p=a->m[i-1];
1673  while(p!=NULL)
1674  {
1675  poly h=p_Head(p, rRing);
1676  int co=__p_GetComp(h, rRing)-1;
1677  p_SetComp(h, i, rRing);
1678  p_Setm(h, rRing);
1679  h->next=b->m[co];
1680  b->m[co]=h;
1681  pIter(p);
1682  }
1683  }
1684  for (i=IDELEMS(b)-1; i>=0; i--)
1685  {
1686  poly p=b->m[i];
1687  if(p!=NULL)
1688  {
1689  b->m[i]=p_SortMerge(p,rRing,TRUE);
1690  }
1691  }
1692  return b;
1693 }
1694 
1695 /*2
1696 * The following is needed to compute the image of certain map used in
1697 * the computation of cohomologies via BGG
1698 * let M = { w_1, ..., w_k }, k = size(M) == ncols(M), n = nvars(currRing).
1699 * assuming that nrows(M) <= m*n; the procedure computes:
1700 * transpose(M) * transpose( var(1) I_m | ... | var(n) I_m ) :== transpose(module{f_1, ... f_k}),
1701 * where f_i = \sum_{j=1}^{m} (w_i, v_j) gen(j), (w_i, v_j) is a `scalar` multiplication.
1702 * that is, if w_i = (a^1_1, ... a^1_m) | (a^2_1, ..., a^2_m) | ... | (a^n_1, ..., a^n_m) then
1703 
1704  (a^1_1, ... a^1_m) | (a^2_1, ..., a^2_m) | ... | (a^n_1, ..., a^n_m)
1705 * var_1 ... var_1 | var_2 ... var_2 | ... | var_n ... var(n)
1706 * gen_1 ... gen_m | gen_1 ... gen_m | ... | gen_1 ... gen_m
1707 + =>
1708  f_i =
1709 
1710  a^1_1 * var(1) * gen(1) + ... + a^1_m * var(1) * gen(m) +
1711  a^2_1 * var(2) * gen(1) + ... + a^2_m * var(2) * gen(m) +
1712  ...
1713  a^n_1 * var(n) * gen(1) + ... + a^n_m * var(n) * gen(m);
1714 
1715  NOTE: for every f_i we run only ONCE along w_i saving partial sums into a temporary array of polys of size m
1716 */
1717 ideal id_TensorModuleMult(const int m, const ideal M, const ring rRing)
1718 {
1719 // #ifdef DEBU
1720 // WarnS("tensorModuleMult!!!!");
1721 
1722  assume(m > 0);
1723  assume(M != NULL);
1724 
1725  const int n = rRing->N;
1726 
1727  assume(M->rank <= m * n);
1728 
1729  const int k = IDELEMS(M);
1730 
1731  ideal idTemp = idInit(k,m); // = {f_1, ..., f_k }
1732 
1733  for( int i = 0; i < k; i++ ) // for every w \in M
1734  {
1735  poly pTempSum = NULL;
1736 
1737  poly w = M->m[i];
1738 
1739  while(w != NULL) // for each term of w...
1740  {
1741  poly h = p_Head(w, rRing);
1742 
1743  const int gen = __p_GetComp(h, rRing); // 1 ...
1744 
1745  assume(gen > 0);
1746  assume(gen <= n*m);
1747 
1748  // TODO: write a formula with %, / instead of while!
1749  /*
1750  int c = gen;
1751  int v = 1;
1752  while(c > m)
1753  {
1754  c -= m;
1755  v++;
1756  }
1757  */
1758 
1759  int cc = gen % m;
1760  if( cc == 0) cc = m;
1761  int vv = 1 + (gen - cc) / m;
1762 
1763 // assume( cc == c );
1764 // assume( vv == v );
1765 
1766  // 1<= c <= m
1767  assume( cc > 0 );
1768  assume( cc <= m );
1769 
1770  assume( vv > 0 );
1771  assume( vv <= n );
1772 
1773  assume( (cc + (vv-1)*m) == gen );
1774 
1775  p_IncrExp(h, vv, rRing); // h *= var(j) && // p_AddExp(h, vv, 1, rRing);
1776  p_SetComp(h, cc, rRing);
1777 
1778  p_Setm(h, rRing); // addjust degree after the previous steps!
1779 
1780  pTempSum = p_Add_q(pTempSum, h, rRing); // it is slow since h will be usually put to the back of pTempSum!!!
1781 
1782  pIter(w);
1783  }
1784 
1785  idTemp->m[i] = pTempSum;
1786  }
1787 
1788  // simplify idTemp???
1789 
1790  ideal idResult = id_Transp(idTemp, rRing);
1791 
1792  id_Delete(&idTemp, rRing);
1793 
1794  return(idResult);
1795 }
1796 
1797 ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring r)
1798 {
1799  int cnt=0;int rw=0; int cl=0;
1800  int i,j;
1801  // find max. size of xx[.]:
1802  for(j=rl-1;j>=0;j--)
1803  {
1804  i=IDELEMS(xx[j])*xx[j]->nrows;
1805  if (i>cnt) cnt=i;
1806  if (xx[j]->nrows >rw) rw=xx[j]->nrows; // for lifting matrices
1807  if (xx[j]->ncols >cl) cl=xx[j]->ncols; // for lifting matrices
1808  }
1809  if (rw*cl !=cnt)
1810  {
1811  WerrorS("format mismatch in CRT");
1812  return NULL;
1813  }
1814  ideal result=idInit(cnt,xx[0]->rank);
1815  result->nrows=rw; // for lifting matrices
1816  result->ncols=cl; // for lifting matrices
1817  number *x=(number *)omAlloc(rl*sizeof(number));
1818  poly *p=(poly *)omAlloc(rl*sizeof(poly));
1819  CFArray inv_cache(rl);
1820  extern int n_SwitchChinRem; //TEST
1821  int save_n_SwitchChinRem=n_SwitchChinRem;
1822  n_SwitchChinRem=1;
1823  for(i=cnt-1;i>=0;i--)
1824  {
1825  for(j=rl-1;j>=0;j--)
1826  {
1827  if(i>=IDELEMS(xx[j])*xx[j]->nrows) // out of range of this ideal
1828  p[j]=NULL;
1829  else
1830  p[j]=xx[j]->m[i];
1831  }
1832  result->m[i]=p_ChineseRemainder(p,x,q,rl,inv_cache,r);
1833  for(j=rl-1;j>=0;j--)
1834  {
1835  if(i<IDELEMS(xx[j])*xx[j]->nrows) xx[j]->m[i]=p[j];
1836  }
1837  }
1838  n_SwitchChinRem=save_n_SwitchChinRem;
1839  omFreeSize(p,rl*sizeof(poly));
1840  omFreeSize(x,rl*sizeof(number));
1841  for(i=rl-1;i>=0;i--) id_Delete(&(xx[i]),r);
1842  omFreeSize(xx,rl*sizeof(ideal));
1843  return result;
1844 }
1845 
1846 void id_Shift(ideal M, int s, const ring r)
1847 {
1848 // id_Test( M, r );
1849 
1850 // assume( s >= 0 ); // negative is also possible // TODO: verify input ideal in such a case!?
1851 
1852  for(int i=IDELEMS(M)-1; i>=0;i--)
1853  p_Shift(&(M->m[i]),s,r);
1854 
1855  M->rank += s;
1856 
1857 // id_Test( M, r );
1858 }
1859 
1860 ideal id_Delete_Pos(const ideal I, const int p, const ring r)
1861 {
1862  if ((p<0)||(p>=IDELEMS(I))) return NULL;
1863  ideal ret=idInit(IDELEMS(I)-1,I->rank);
1864  for(int i=0;i<p;i++) ret->m[i]=p_Copy(I->m[i],r);
1865  for(int i=p+1;i<IDELEMS(I);i++) ret->m[i-1]=p_Copy(I->m[i],r);
1866  return ret;
1867 }
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:248
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:515
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:494
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:464
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:669
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
#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:263
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:2938
matrix mpNew(int r, int c)
create a r x c zero-matrix
Definition: matpol.cc:37
#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:65
#define pIter(p)
Definition: monomials.h:38
#define pNext(p)
Definition: monomials.h:37
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:45
#define __p_GetComp(p, r)
Definition: monomials.h:64
#define rRing_has_Comp(r)
Definition: monomials.h:267
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:4256
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:4474
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:3865
void p_Vec2Polys(poly v, poly **p, int *len, const ring r)
Definition: p_polys.cc:3573
poly pp_JetW(poly p, int m, short *w, const ring R)
Definition: p_polys.cc:4301
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition: p_polys.cc:4604
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:3723
void p_Norm(poly p1, const ring r)
Definition: p_polys.cc:3670
int p_MinDeg(poly p, intvec *w, const ring R)
Definition: p_polys.cc:4346
poly p_One(const ring r)
Definition: p_polys.cc:1305
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3647
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:4410
static long p_GetExpDiff(poly p1, poly p2, int i, ring r)
Definition: p_polys.h:636
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:893
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1051
static poly p_Head(poly p, const ring r)
Definition: p_polys.h:826
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1649
void p_ShallowDelete(poly *p, const ring r)
static void p_SetCompP(poly p, int i, ring r)
Definition: p_polys.h:255
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:489
#define pp_Test(p, lmRing, tailRing)
Definition: p_polys.h:166
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:248
static long p_IncrExp(poly p, int v, ring r)
Definition: p_polys.h:592
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:234
#define p_SetmComp
Definition: p_polys.h:245
static poly p_SortMerge(poly p, const ring r, BOOLEAN revert=FALSE)
Definition: p_polys.h:1166
static poly pReverse(poly p)
Definition: p_polys.h:336
static int p_LtCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1539
static BOOLEAN p_LmIsConstantComp(const poly p, const ring r)
Definition: p_polys.h:963
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:470
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1830
static long p_MaxComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:293
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:858
static unsigned pLength(poly a)
Definition: p_polys.h:193
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1088
static BOOLEAN p_IsUnit(const poly p, const ring r)
Definition: p_polys.h:1956
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition: p_polys.h:726
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:813
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1444
BOOLEAN _pp_Test(poly p, ring lmRing, ring tailRing, int level)
Definition: pDebug.cc:333
#define p_Test(p, r)
Definition: p_polys.h:164
static BOOLEAN p_IsConstantPoly(const poly p, const ring r)
Definition: p_polys.h:1943
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:235
#define pSetm(p)
Definition: polys.h:265
#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:475
long(* pFDegProc)(poly p, ring r)
Definition: ring.h:39
@ ringorder_lp
Definition: ring.h:78
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:582
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:539
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:150
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:105
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:98
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_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
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