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