My Project  debian-1:4.1.1-p2+ds-4build1
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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
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 }
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 }
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 }
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 }
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 }
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 }
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 }
omdebugAddrSize
#define omdebugAddrSize(addr, size)
Definition: omAllocDecl.h:313
id_FreeModule
ideal id_FreeModule(int i, const ring r)
the free module of rank i
Definition: simpleideals.cc:934
nrows
int nrows
Definition: cf_linsys.cc:32
FALSE
#define FALSE
Definition: auxiliary.h:94
id_SimpleAdd
ideal id_SimpleAdd(ideal h1, ideal h2, const ring R)
concat the lists h1 and h2 without zeros
Definition: simpleideals.cc:597
id_HomModule
BOOLEAN id_HomModule(ideal m, ideal Q, intvec **w, const ring R)
Definition: simpleideals.cc:1297
dReportError
int dReportError(const char *fmt,...)
Definition: dError.cc:43
sip_sideal_bin
omBin sip_sideal_bin
Definition: simpleideals.cc:28
id_Homogen
ideal id_Homogen(ideal h, int varnum, const ring r)
Definition: simpleideals.cc:1121
omCheckAddrSize
#define omCheckAddrSize(addr, size)
Definition: omAllocDecl.h:325
sBucketClearMerge
void sBucketClearMerge(sBucket_pt bucket, poly *p, int *length)
Definition: sbuckets.cc:237
idElem
int idElem(const ideal F)
count non-zero elements
Definition: simpleideals.cc:209
omalloc.h
p_Subst
poly p_Subst(poly p, int n, poly e, const ring r)
Definition: p_polys.cc:3848
ncols
int int ncols
Definition: cf_linsys.cc:32
p_GetComp
#define p_GetComp(p, r)
Definition: monomials.h:68
ip_smatrix
Definition: matpol.h:13
p_LmIsConstantComp
static BOOLEAN p_LmIsConstantComp(const poly p, const ring r)
Definition: p_polys.h:947
pGetComp
#define pGetComp(p)
Component.
Definition: polys.h:36
p_GetExp
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:457
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
omFree
#define omFree(addr)
Definition: omAllocDecl.h:259
p_Normalize
void p_Normalize(poly p, const ring r)
Definition: p_polys.cc:3706
p_Comp_RevLex
static int p_Comp_RevLex(poly a, poly b, BOOLEAN nolex, const ring R)
for idSort: compare a and b revlex inclusive module comp.
Definition: simpleideals.cc:465
id_Matrix2Module
ideal id_Matrix2Module(matrix mat, const ring R)
converts mat to module, destroys mat
Definition: simpleideals.cc:1166
k
int k
Definition: cfEzgcd.cc:92
ecartWeights
short * ecartWeights
Definition: weight0.c:27
x
Variable x
Definition: cfModGcd.cc:4023
MATELEM
#define MATELEM(mat, i, j)
Definition: matpol.h:28
diff
static gmp_float * diff
Definition: mpr_complex.cc:45
result
return result
Definition: facAbsBiFact.cc:76
omGetSpecBin
#define omGetSpecBin(size)
Definition: omBin.h:10
idInsertPolyOnPos
BOOLEAN idInsertPolyOnPos(ideal I, poly p, int pos)
insert p into I on position pos
Definition: simpleideals.cc:658
id_Norm
void id_Norm(ideal id, const ring r)
ideal id = (id[i]), result is leadcoeff(id[i]) = 1
Definition: simpleideals.cc:241
id_ChineseRemainder
ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring r)
Definition: simpleideals.cc:1763
pEnlargeSet
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3630
ADDRESS
void * ADDRESS
Definition: auxiliary.h:133
pFDegProc
long(* pFDegProc)(poly p, ring r)
Definition: ring.h:44
p_Head
static poly p_Head(poly p, const ring r)
Definition: p_polys.h:810
id_TensorModuleMult
ideal id_TensorModuleMult(const int m, const ideal M, const ring rRing)
Definition: simpleideals.cc:1683
p_ComparePolys
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:4456
id_PosConstant
int id_PosConstant(ideal id, const ring r)
index of generator with leading term in ground ring (if any); otherwise -1
Definition: simpleideals.cc:81
p_SetCompP
static void p_SetCompP(poly p, int i, ring r)
Definition: p_polys.h:245
weight.h
idIs0
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
Definition: simpleideals.cc:767
id_IsConstant
BOOLEAN id_IsConstant(ideal id, const ring r)
test if the ideal has only constant polynomials NOTE: zero ideal/module is also constant
Definition: simpleideals.cc:390
id_InsertPolyWithTests
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:
Definition: simpleideals.cc:685
id_DelDiv
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...
Definition: simpleideals.cc:341
id_MaxIdeal
ideal id_MaxIdeal(const ring r)
initialise the maximal ideal (at 0)
Definition: simpleideals.cc:99
p_Homogen
poly p_Homogen(poly p, int varnum, const ring r)
Definition: p_polys.cc:3205
simpleideals.h
idInsertPoly
BOOLEAN idInsertPoly(ideal h1, poly h2)
insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
Definition: simpleideals.cc:639
id_QHomWeight
intvec * id_QHomWeight(ideal id, const ring r)
Definition: simpleideals.cc:1534
iv2array
short * iv2array(intvec *iv, const ring R)
Definition: weight.cc:205
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:267
p_ChineseRemainder
poly p_ChineseRemainder(poly *xx, number *x, number *q, int rl, CFArray &inv_cache, const ring R)
Definition: p_polys.cc:85
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
__p_GetComp
#define __p_GetComp(p, r)
Definition: monomials.h:67
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:455
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
p_Test
#define p_Test(p, r)
Definition: p_polys.h:155
p_wrp
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:234
omAllocBin
#define omAllocBin(bin)
Definition: omAllocDecl.h:203
options.h
auxiliary.h
id_Copy
ideal id_Copy(ideal h1, const ring r)
copy an ideal
Definition: simpleideals.cc:403
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
id_Shift
void id_Shift(ideal M, int s, const ring r)
Definition: simpleideals.cc:1812
n_IsZero
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:464
pSetComp
#define pSetComp(p, v)
Definition: polys.h:37
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
id_ShallowDelete
void id_ShallowDelete(ideal *h, ring r)
Shallowdeletes an ideal/matrix.
Definition: simpleideals.cc:147
b
CanonicalForm b
Definition: cfModGcd.cc:4044
p_IsHomogeneous
BOOLEAN p_IsHomogeneous(poly p, const ring r)
Definition: p_polys.cc:3254
ap
Definition: ap.h:35
cl
cl
Definition: cfModGcd.cc:4041
p_SetmComp
#define p_SetmComp
Definition: p_polys.h:235
id_HomIdeal
BOOLEAN id_HomIdeal(ideal id, ideal Q, const ring r)
Definition: simpleideals.cc:805
p_LmEqual
#define p_LmEqual(p1, p2, r)
Definition: p_polys.h:1638
id_DBTest
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!
Definition: simpleideals.cc:415
p_SetExp
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:476
pLength
static unsigned pLength(poly a)
Definition: p_polys.h:183
p_Copy
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:797
p_Power
poly p_Power(poly p, int i, const ring r)
Definition: p_polys.cc:2141
id_Sort
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
Definition: simpleideals.cc:502
rVar
static short rVar(const ring r)
#define rVar(r) (r->N)
Definition: ring.h:582
TRUE
#define TRUE
Definition: auxiliary.h:98
i
int i
Definition: cfEzgcd.cc:125
Array
Definition: ftmpl_array.h:17
id_Delete
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
Definition: simpleideals.cc:113
res
CanonicalForm res
Definition: facAbsFact.cc:64
id_RankFreeModule
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
Definition: simpleideals.cc:781
matpol.h
idShow
void idShow(const ideal id, const ring lmRing, const ring tailRing, const int debugPrint)
Definition: simpleideals.cc:58
M
#define M
Definition: sirandom.c:24
PrintS
void PrintS(const char *s)
Definition: reporter.cc:283
id_DelLmEquals
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.
Definition: simpleideals.cc:313
omFreeSize
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:258
BOOLEAN
int BOOLEAN
Definition: auxiliary.h:85
sBucket_Merge_p
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:149
clapsing.h
binom
int binom(int n, int r)
Definition: simpleideals.cc:912
id_Array2Vector
poly id_Array2Vector(poly *m, unsigned n, const ring R)
for julia: convert an array of poly to vector
Definition: simpleideals.cc:1143
idSkipZeroes
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
Definition: simpleideals.cc:171
rField_is_Ring
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:476
id_DelEquals
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
Definition: simpleideals.cc:290
id_Module2Matrix
matrix id_Module2Matrix(ideal mod, const ring R)
Definition: simpleideals.cc:1200
sBucketCreate
sBucket_pt sBucketCreate(const ring r)
Definition: sbuckets.cc:97
h
static Poly * h
Definition: janet.cc:972
makemonoms
static void makemonoms(int vars, int actvar, int deg, int monomdeg, const ring r)
Definition: simpleideals.cc:961
ip_smatrix::m
poly * m
Definition: matpol.h:18
id_DelMultiples
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
Definition: simpleideals.cc:255
ivTriangIntern
void ivTriangIntern(intvec *imat, int &ready, int &all)
Definition: intvec.cc:385
pp_Mult_qq
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition: p_polys.h:1078
p_LtCmp
static int p_LtCmp(poly p, poly q, const ring r)
Definition: p_polys.h:1529
id_Jet
ideal id_Jet(const ideal i, int d, const ring R)
Definition: simpleideals.cc:1420
intvec
Definition: intvec.h:16
pIter
#define pIter(p)
Definition: monomials.h:41
omAlloc
#define omAlloc(size)
Definition: omAllocDecl.h:208
p_polys.h
p_DivisibleBy
static BOOLEAN p_DivisibleBy(poly a, poly b, const ring r)
Definition: p_polys.h:1803
p_MinDeg
int p_MinDeg(poly p, intvec *w, const ring R)
Definition: p_polys.cc:4328
idGetNextChoise
void idGetNextChoise(int r, int end, BOOLEAN *endch, int *choise)
Definition: simpleideals.cc:854
pp
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:253
p_IsUnit
static BOOLEAN p_IsUnit(const poly p, const ring r)
Definition: p_polys.h:1928
intvec.h
idpowerpoint
static int idpowerpoint
Definition: simpleideals.cc:32
id_Power
ideal id_Power(ideal given, int exp, const ring r)
Definition: simpleideals.cc:1060
p_ShallowDelete
void p_ShallowDelete(poly *p, const ring r)
mpNew
matrix mpNew(int r, int c)
create a r x c zero-matrix
Definition: matpol.cc:35
p_Shift
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition: p_polys.cc:4586
ringorder_lp
Definition: ring.h:83
pp_JetW
poly pp_JetW(poly p, int m, short *w, const ring R)
Definition: p_polys.cc:4283
sBucket
Definition: sbuckets.cc:31
exp
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
n_Sub
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
pp_Jet
poly pp_Jet(poly p, int m, const ring R)
Definition: p_polys.cc:4238
p_IsPurePower
int p_IsPurePower(const poly p, const ring r)
return i, if head depends only on var(i)
Definition: p_polys.cc:1215
IMATELEM
#define IMATELEM(M, I, J)
Definition: intvec.h:83
omBin
omBin_t * omBin
Definition: omStructs.h:11
p_Delete
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:842
p_Add_q
static poly p_Add_q(poly p, poly q, const ring r)
Definition: p_polys.h:877
p_One
poly p_One(const ring r)
Definition: p_polys.cc:1302
id_Delete_Pos
ideal id_Delete_Pos(const ideal I, const int p, const ring r)
Definition: simpleideals.cc:1826
sip_sideal
The following sip_sideal structure has many different uses thoughout Singular. Basic use-cases for it...
Definition: simpleideals.h:17
p_EqualPolys
BOOLEAN p_EqualPolys(poly p1, poly p2, const ring r)
Definition: p_polys.cc:4392
si_max
static int si_max(const int a, const int b)
Definition: auxiliary.h:138
idInitChoise
void idInitChoise(int r, int beg, int end, BOOLEAN *endch, int *choise)
Definition: simpleideals.cc:832
rRing_has_Comp
#define rRing_has_Comp(r)
Definition: monomials.h:265
id_JetW
ideal id_JetW(const ideal i, int d, intvec *iv, const ring R)
Definition: simpleideals.cc:1433
Print
#define Print
Definition: emacs.cc:79
id_Vec2Ideal
ideal id_Vec2Ideal(poly vec, const ring R)
Definition: simpleideals.cc:1134
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:36
pp_Test
#define pp_Test(p, lmRing, tailRing)
Definition: p_polys.h:157
p_Vec2Polys
void p_Vec2Polys(poly v, poly **p, int *len, const ring r)
Definition: p_polys.cc:3524
n_GreaterZero
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
id_TestTail
#define id_TestTail(A, lR, tR)
Definition: simpleideals.h:78
WerrorS
void WerrorS(const char *s)
Definition: feFopen.cc:24
p_GetExpDiff
static long p_GetExpDiff(poly p1, poly p2, int i, ring r)
Definition: p_polys.h:623
rField_has_simple_inverse
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:539
m
int m
Definition: cfEzgcd.cc:121
MATCOLS
#define MATCOLS(i)
Definition: matpol.h:27
WarnS
#define WarnS
Definition: emacs.cc:77
assume
#define assume(x)
Definition: mod2.h:384
NULL
#define NULL
Definition: omList.c:9
pSetm
#define pSetm(p)
Definition: polys.h:246
p_SetComp
static unsigned long p_SetComp(poly p, unsigned long c, ring r)
Definition: p_polys.h:238
l
int l
Definition: cfEzgcd.cc:93
id_ReadOutPivot
int id_ReadOutPivot(ideal arg, int *comp, const ring r)
Definition: simpleideals.cc:1457
id_CopyFirstK
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 (...
Definition: simpleideals.cc:225
R
#define R
Definition: sirandom.c:26
id_Mult
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...
Definition: simpleideals.cc:726
idpower
static poly * idpower
Definition: simpleideals.cc:30
p_Setm
static void p_Setm(poly p, const ring r)
Definition: p_polys.h:224
id_NextPotence
static void id_NextPotence(ideal given, ideal result, int begin, int end, int deg, int restdeg, poly ap, const ring r)
Definition: simpleideals.cc:1033
p_IncrExp
static long p_IncrExp(poly p, int v, ring r)
Definition: p_polys.h:579
id_MinDegW
int id_MinDegW(ideal M, intvec *w, const ring r)
Definition: simpleideals.cc:1610
p_Totaldegree
static long p_Totaldegree(poly p, const ring r)
Definition: p_polys.h:1435
p
int p
Definition: cfModGcd.cc:4019
p_IsConstantPoly
static BOOLEAN p_IsConstantPoly(const poly p, const ring r)
Definition: p_polys.h:1915
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
head
CanonicalForm head(const CanonicalForm &f)
Definition: canonicalform.h:353
IDELEMS
#define IDELEMS(i)
Definition: simpleideals.h:24
p_Norm
void p_Norm(poly p1, const ring r)
Definition: p_polys.cc:3653
id_Module2formatedMatrix
matrix id_Module2formatedMatrix(ideal mod, int rows, int cols, const ring R)
Definition: simpleideals.cc:1246
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition: facSparseHensel.h:25
Q
#define Q
Definition: sirandom.c:25
p_Mult_q
static poly p_Mult_q(poly p, poly q, const ring r)
Definition: p_polys.h:1035
id_Compactify
void id_Compactify(ideal id, const ring r)
Definition: simpleideals.cc:1086
id_Add
ideal id_Add(ideal h1, ideal h2, const ring r)
h1 + h2
Definition: simpleideals.cc:713
pGetCoeff
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:48
ivSolveKern
intvec * ivSolveKern(intvec *imat, int dimtr)
Definition: intvec.cc:423
id_Transp
ideal id_Transp(ideal a, const ring rRing)
transpose a module
Definition: simpleideals.cc:1630
_pp_Test
BOOLEAN _pp_Test(poly p, ring lmRing, ring tailRing, int level)
Definition: pDebug.cc:326
PrintLn
void PrintLn()
Definition: reporter.cc:309
sBucketDestroy
void sBucketDestroy(sBucket_pt *bucket)
Definition: sbuckets.cc:104
id_Test
#define id_Test(A, lR)
Definition: simpleideals.h:79
MATROWS
#define MATROWS(i)
Definition: matpol.h:26
omFreeBin
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:257
id_Head
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
Definition: simpleideals.cc:1110
p_MaxComp
static long p_MaxComp(poly p, ring lmRing, ring tailRing)
Definition: p_polys.h:283
sbuckets.h
n_SwitchChinRem
int n_SwitchChinRem
Definition: longrat.cc:2931
p_DivisibleByRingCase
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:1586
n_IsUnit
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
pNext
#define pNext(p)
Definition: monomials.h:40
pReverse
static poly pReverse(poly p)
Definition: p_polys.h:326
omAlloc0
#define omAlloc0(size)
Definition: omAllocDecl.h:209
p_SortMerge
static poly p_SortMerge(poly p, const ring r, BOOLEAN revert=FALSE)
Definition: p_polys.h:1160
omPrintAddrInfo
void omPrintAddrInfo(FILE *fd, void *addr, const char *s)
Definition: omDebugCheck.c:449
id_Subst
ideal id_Subst(ideal id, int n, poly e, const ring r)
Definition: simpleideals.cc:1282
id_Normalize
void id_Normalize(ideal I, const ring r)
normialize all polys in id
Definition: simpleideals.cc:1600
id_IsZeroDim
BOOLEAN id_IsZeroDim(ideal I, const ring r)
Definition: simpleideals.cc:1581
vec
fq_nmod_poly_t * vec
Definition: facHensel.cc:103
idGetNumberOfChoise
int idGetNumberOfChoise(int t, int d, int begin, int end, int *choise)
Definition: simpleideals.cc:880