My Project
Loading...
Searching...
No Matches
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
35ideal 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
57void 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
80int 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)
98ideal 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
123void 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
157void 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
181void 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
221int 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.)
237ideal 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
253void 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
267void 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
302void 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
325void 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)
352static 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)
388void 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)
453void 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
461BOOLEAN 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
474ideal 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!
486void 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!
537void 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.
590static 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
627intvec *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
722ideal 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
764BOOLEAN 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
783BOOLEAN 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 */
810BOOLEAN 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
838ideal 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)
851ideal 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
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
906long 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*/
928BOOLEAN 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
951BOOLEAN 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
974BOOLEAN 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*/
1001void 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*/
1023void 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*/
1049int 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*/
1081int 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
1104ideal 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*/
1135static 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 {
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 {
1164 makemonoms(vars,actvar+1,deg,monomdeg,r);
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*/
1183static 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*/
1221ideal 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
1275static 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
1302ideal 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;
1322 return result;
1323}
1324
1325/*2
1326*skips all zeroes and double elements, searches also for units
1327*/
1328void 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
1352ideal 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
1363ideal 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----------------*/
1376ideal 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
1385poly 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
1408ideal 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*/
1442matrix 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 {
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
1488matrix 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
1520ideal 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*/
1557ideal 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
1572BOOLEAN 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
1695ideal 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
1708ideal 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*/
1732int 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
1786static 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
1809intvec * 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
1856BOOLEAN id_IsZeroDim(ideal I, const ring r)
1857{
1858 BOOLEAN *UsedAxis=(BOOLEAN *)omAlloc0(rVar(r)*sizeof(BOOLEAN));
1859 int i,n;
1860 poly po;
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
1875void 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
1885int 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*/
1905ideal 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*/
1958ideal 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
2038ideal 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;
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
2087void 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
2101ideal 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:4081
int p
Definition: cfModGcd.cc:4077
cl
Definition: cfModGcd.cc:4099
CanonicalForm b
Definition: cfModGcd.cc:4102
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
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:3095
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)
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
intvec * id_QHomWeight(ideal id, 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
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)
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
#define Q
Definition: sirandom.c:26
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