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