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