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