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
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)
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
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
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
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
202{
203 assume (ide != NULL);
204
205 int k;
206 int j = -1;
207 int idelems=IDELEMS(ide);
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)
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 {
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
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
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;
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 {
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;
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 }
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
790{
791 id_Test(h1, R);
792 id_Test(h2, R);
793
794 if ( idIs0(h1) )
795 {
797 if (res->rank<h1->rank) res->rank=h1->rank;
798 return res;
799 }
800 if ( idIs0(h2) )
801 {
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
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
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 */
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
906{
907 id_Test(h1, r);
908 id_Test(h2, r);
909
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)
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
955 return hh;
956}
957
958/// returns true if h is the zero ideal
960{
961 assume (h != NULL); // will fail :(
962// if (h == NULL) return TRUE;
963
964 if (h->m!=NULL)
965 {
966 for( int i = IDELEMS(h)-1; i >= 0; i-- )
967 if(h->m[i] != NULL)
968 return FALSE;
969 }
970 return TRUE;
971}
972
973/// return the maximal component number found in any polynomial in s
975{
976 long j = 0;
977
978 if (rRing_has_Comp(tailRing) && rRing_has_Comp(lmRing))
979 {
980 poly *p=s->m;
981 for (unsigned int l=IDELEMS(s); l > 0; --l, ++p)
982 if (*p != NULL)
983 {
984 pp_Test(*p, lmRing, tailRing);
985 const long k = p_MaxComp(*p, lmRing, tailRing);
986 if (k>j) j = k;
987 }
988 }
989
990 return j; // return -1;
991}
992
994{
995 if ((src->VarOffset[0]== -1)
996 || (src->pCompIndex<0))
997 return FALSE; // ring without components
998 for (int i=0;i<IDELEMS(A);i++)
999 {
1000 if (A->m[i]!=NULL)
1001 {
1002 if (p_GetComp(A->m[i],src)>0)
1003 return TRUE;
1004 else
1005 return FALSE;
1006 }
1007 }
1008 return A->rank>1;
1009}
1010
1011
1012/*2
1013*returns true if id is homogeneous with respect to the actual weights
1014*/
1016{
1017 int i;
1018 BOOLEAN b;
1019 i = 0;
1020 b = TRUE;
1021 while ((i < IDELEMS(id)) && b)
1022 {
1023 b = p_IsHomogeneous(id->m[i],r);
1024 i++;
1025 }
1026 if ((b) && (Q!=NULL) && (IDELEMS(Q)>0))
1027 {
1028 i=0;
1029 while ((i < IDELEMS(Q)) && b)
1030 {
1031 b = p_IsHomogeneous(Q->m[i],r);
1032 i++;
1033 }
1034 }
1035 return b;
1036}
1037
1038/*2
1039*returns true if id is homogeneous with respect to totaldegree
1040*/
1042{
1043 int i;
1044 BOOLEAN b;
1045 i = 0;
1046 b = TRUE;
1047 while ((i < IDELEMS(id)) && b)
1048 {
1049 b = p_IsHomogeneousDP(id->m[i],r);
1050 i++;
1051 }
1052 if ((b) && (Q!=NULL) && (IDELEMS(Q)>0))
1053 {
1054 i=0;
1055 while ((i < IDELEMS(Q)) && b)
1056 {
1057 b = p_IsHomogeneousDP(Q->m[i],r);
1058 i++;
1059 }
1060 }
1061 return b;
1062}
1063
1065{
1066 int i;
1067 BOOLEAN b;
1068 i = 0;
1069 b = TRUE;
1070 while ((i < IDELEMS(id)) && b)
1071 {
1072 b = p_IsHomogeneousW(id->m[i],w,r);
1073 i++;
1074 }
1075 if ((b) && (Q!=NULL) && (IDELEMS(Q)>0))
1076 {
1077 i=0;
1078 while ((i < IDELEMS(Q)) && b)
1079 {
1080 b = p_IsHomogeneousW(Q->m[i],w,r);
1081 i++;
1082 }
1083 }
1084 return b;
1085}
1086
1088{
1089 int i;
1090 BOOLEAN b;
1091 i = 0;
1092 b = TRUE;
1093 while ((i < IDELEMS(id)) && b)
1094 {
1095 b = p_IsHomogeneousW(id->m[i],w,module_w,r);
1096 i++;
1097 }
1098 if ((b) && (Q!=NULL) && (IDELEMS(Q)>0))
1099 {
1100 i=0;
1101 while ((i < IDELEMS(Q)) && b)
1102 {
1103 b = p_IsHomogeneousW(Q->m[i],w,r);
1104 i++;
1105 }
1106 }
1107 return b;
1108}
1109
1110/*2
1111*initialized a field with r numbers between beg and end for the
1112*procedure idNextChoise
1113*/
1114void idInitChoise (int r,int beg,int end,BOOLEAN *endch,int * choise)
1115{
1116 /*returns the first choise of r numbers between beg and end*/
1117 int i;
1118 for (i=0; i<r; i++)
1119 {
1120 choise[i] = 0;
1121 }
1122 if (r <= end-beg+1)
1123 for (i=0; i<r; i++)
1124 {
1125 choise[i] = beg+i;
1126 }
1127 if (r > end-beg+1)
1128 *endch = TRUE;
1129 else
1130 *endch = FALSE;
1131}
1132
1133/*2
1134*returns the next choise of r numbers between beg and end
1135*/
1136void idGetNextChoise (int r,int end,BOOLEAN *endch,int * choise)
1137{
1138 int i = r-1,j;
1139 while ((i >= 0) && (choise[i] == end))
1140 {
1141 i--;
1142 end--;
1143 }
1144 if (i == -1)
1145 *endch = TRUE;
1146 else
1147 {
1148 choise[i]++;
1149 for (j=i+1; j<r; j++)
1150 {
1151 choise[j] = choise[i]+j-i;
1152 }
1153 *endch = FALSE;
1154 }
1155}
1156
1157/*2
1158*takes the field choise of d numbers between beg and end, cancels the t-th
1159*entree and searches for the ordinal number of that d-1 dimensional field
1160* w.r.t. the algorithm of construction
1161*/
1162int idGetNumberOfChoise(int t, int d, int begin, int end, int * choise)
1163{
1164 int * localchoise,i,result=0;
1165 BOOLEAN b=FALSE;
1166
1167 if (d<=1) return 1;
1168 localchoise=(int*)omAlloc((d-1)*sizeof(int));
1169 idInitChoise(d-1,begin,end,&b,localchoise);
1170 while (!b)
1171 {
1172 result++;
1173 i = 0;
1174 while ((i<t) && (localchoise[i]==choise[i])) i++;
1175 if (i>=t)
1176 {
1177 i = t+1;
1178 while ((i<d) && (localchoise[i-1]==choise[i])) i++;
1179 if (i>=d)
1180 {
1181 omFreeSize((ADDRESS)localchoise,(d-1)*sizeof(int));
1182 return result;
1183 }
1184 }
1185 idGetNextChoise(d-1,end,&b,localchoise);
1186 }
1187 omFreeSize((ADDRESS)localchoise,(d-1)*sizeof(int));
1188 return 0;
1189}
1190
1191/*2
1192*computes the binomial coefficient
1193*/
1194int binom (int n,int r)
1195{
1196 int i;
1197 int64 result;
1198
1199 if (r==0) return 1;
1200 if (n-r<r) return binom(n,n-r);
1201 result = n-r+1;
1202 for (i=2;i<=r;i++)
1203 {
1204 result *= n-r+i;
1205 result /= i;
1206 }
1207 if (result>MAX_INT_VAL)
1208 {
1209 WarnS("overflow in binomials");
1210 result=0;
1211 }
1212 return (int)result;
1213}
1214
1215
1216/// the free module of rank i
1218{
1219 assume(i >= 0);
1220 if (r->isLPring)
1221 {
1222 PrintS("In order to address bimodules, the command freeAlgebra should be used.");
1223 }
1224 ideal h = idInit(i, i);
1225
1226 for (int j=0; j<i; j++)
1227 {
1228 h->m[j] = p_One(r);
1229 p_SetComp(h->m[j],j+1,r);
1230 p_SetmComp(h->m[j],r);
1231 }
1232
1233 return h;
1234}
1235
1236/*2
1237*computes recursively all monomials of a certain degree
1238*in every step the actvar-th entry in the exponential
1239*vector is incremented and the other variables are
1240*computed by recursive calls of makemonoms
1241*if the last variable is reached, the difference to the
1242*degree is computed directly
1243*vars is the number variables
1244*actvar is the actual variable to handle
1245*deg is the degree of the monomials to compute
1246*monomdeg is the actual degree of the monomial in consideration
1247*/
1248static void makemonoms(int vars,int actvar,int deg,int monomdeg, const ring r)
1249{
1250 poly p;
1251 int i=0;
1252
1253 if ((idpowerpoint == 0) && (actvar ==1))
1254 {
1256 monomdeg = 0;
1257 }
1258 while (i<=deg)
1259 {
1260 if (deg == monomdeg)
1261 {
1263 idpowerpoint++;
1264 return;
1265 }
1266 if (actvar == vars)
1267 {
1271 idpowerpoint++;
1272 return;
1273 }
1274 else
1275 {
1277 makemonoms(vars,actvar+1,deg,monomdeg,r);
1279 }
1280 monomdeg++;
1284 i++;
1285 }
1286}
1287
1288#ifdef HAVE_SHIFTBBA
1289/*2
1290*computes recursively all letterplace monomials of a certain degree
1291*vars is the number of original variables (lV)
1292*deg is the degree of the monomials to compute
1293*
1294*NOTE: We use idpowerpoint as the last index of the previous call
1295*/
1296static void lpmakemonoms(int vars, int deg, const ring r)
1297{
1298 assume(deg <= r->N/r->isLPring);
1299 if (deg == 0)
1300 {
1301 idpower[0] = p_One(r);
1302 return;
1303 }
1304 else
1305 {
1306 lpmakemonoms(vars, deg - 1, r);
1307 }
1308
1309 int size = idpowerpoint + 1;
1310 for (int j = 2; j <= vars; j++)
1311 {
1312 for (int i = 0; i < size; i++)
1313 {
1314 idpowerpoint = (j-1)*size + i;
1316 }
1317 }
1318 for (int j = 1; j <= vars; j++)
1319 {
1320 for (int i = 0; i < size; i++)
1321 {
1322 idpowerpoint = (j-1)*size + i;
1323 p_SetExp(idpower[idpowerpoint], ((deg - 1) * r->isLPring) + j, 1, r);
1326 }
1327 }
1328}
1329#endif
1330
1331/*2
1332*returns the deg-th power of the maximal ideal of 0
1333*/
1334ideal id_MaxIdeal(int deg, const ring r)
1335{
1336 if (deg < 1)
1337 {
1338 ideal I=idInit(1,1);
1339 I->m[0]=p_One(r);
1340 return I;
1341 }
1342 if (deg == 1
1344 && !r->isLPring
1345#endif
1346 )
1347 {
1348 return id_MaxIdeal(r);
1349 }
1350
1351 int vars, i;
1352#ifdef HAVE_SHIFTBBA
1353 if (r->isLPring)
1354 {
1355 vars = r->isLPring - r->LPncGenCount;
1356 i = 1;
1357 // i = vars^deg
1358 for (int j = 0; j < deg; j++)
1359 {
1360 i *= vars;
1361 }
1362 }
1363 else
1364#endif
1365 {
1366 vars = rVar(r);
1367 i = binom(vars+deg-1,deg);
1368 }
1369 if (i<=0) return idInit(1,1);
1370 ideal id=idInit(i,1);
1371 idpower = id->m;
1372 idpowerpoint = 0;
1373#ifdef HAVE_SHIFTBBA
1374 if (r->isLPring)
1375 {
1376 lpmakemonoms(vars, deg, r);
1377 }
1378 else
1379#endif
1380 {
1381 makemonoms(vars,1,deg,0,r);
1382 }
1383 idpower = NULL;
1384 idpowerpoint = 0;
1385 return id;
1386}
1387
1389 int begin, int end, int deg, int restdeg, poly ap, const ring r)
1390{
1391 poly p;
1392 int i;
1393
1394 p = p_Power(p_Copy(given->m[begin],r),restdeg,r);
1395 i = result->nrows;
1396 result->m[i] = p_Mult_q(p_Copy(ap,r),p,r);
1397//PrintS(".");
1398 (result->nrows)++;
1399 if (result->nrows >= IDELEMS(result))
1400 {
1401 pEnlargeSet(&(result->m),IDELEMS(result),16);
1402 IDELEMS(result) += 16;
1403 }
1404 if (begin == end) return;
1405 for (i=restdeg-1;i>0;i--)
1406 {
1407 p = p_Power(p_Copy(given->m[begin],r),i,r);
1408 p = p_Mult_q(p_Copy(ap,r),p,r);
1409 id_NextPotence(given, result, begin+1, end, deg, restdeg-i, p,r);
1410 p_Delete(&p,r);
1411 }
1412 id_NextPotence(given, result, begin+1, end, deg, restdeg, ap,r);
1413}
1414
1416{
1418 poly p1;
1419 int i;
1420
1421 if (idIs0(given)) return idInit(1,1);
1422 temp = id_Copy(given,r);
1424 i = binom(IDELEMS(temp)+exp-1,exp);
1425 result = idInit(i,1);
1426 result->nrows = 0;
1427//Print("ideal contains %d elements\n",i);
1428 p1=p_One(r);
1430 p_Delete(&p1,r);
1431 id_Delete(&temp,r);
1432 result->nrows = 1;
1435 return result;
1436}
1437
1438/*2
1439*skips all zeroes and double elements, searches also for units
1440*/
1441void id_Compactify(ideal id, const ring r)
1442{
1443 int i;
1444 BOOLEAN b=FALSE;
1445
1446 i = IDELEMS(id)-1;
1447 while ((! b) && (i>=0))
1448 {
1449 b=p_IsUnit(id->m[i],r);
1450 i--;
1451 }
1452 if (b)
1453 {
1454 for(i=IDELEMS(id)-1;i>=0;i--) p_Delete(&id->m[i],r);
1455 id->m[0]=p_One(r);
1456 }
1457 else
1458 {
1459 id_DelMultiples(id,r);
1460 }
1461 idSkipZeroes(id);
1462}
1463
1464/// returns the ideals of initial terms
1466{
1467 ideal m = idInit(IDELEMS(h),h->rank);
1468
1469 if (r->cf->has_simple_Alloc)
1470 {
1471 for (int i=IDELEMS(h)-1;i>=0; i--)
1472 if (h->m[i]!=NULL)
1473 m->m[i]=p_CopyPowerProduct0(h->m[i],pGetCoeff(h->m[i]),r);
1474 }
1475 else
1476 {
1477 for (int i=IDELEMS(h)-1;i>=0; i--)
1478 if (h->m[i]!=NULL)
1479 m->m[i]=p_Head(h->m[i],r);
1480 }
1481
1482 return m;
1483}
1484
1486{
1487 ideal m = idInit(IDELEMS(h),h->rank);
1488 int i;
1489
1490 for (i=IDELEMS(h)-1;i>=0; i--)
1491 {
1492 m->m[i]=p_Homogen(h->m[i],varnum,r);
1493 }
1494 return m;
1495}
1496
1497/*------------------type conversions----------------*/
1499{
1500 ideal result=idInit(1,1);
1502 p_Vec2Polys(vec, &(result->m), &(IDELEMS(result)),R);
1503 return result;
1504}
1505
1506/// for julia: convert an array of poly to vector
1507poly id_Array2Vector(poly *m, unsigned n, const ring R)
1508{
1509 poly h;
1510 int l;
1511 sBucket_pt bucket = sBucketCreate(R);
1512
1513 for(unsigned j=0;j<n ;j++)
1514 {
1515 h = m[j];
1516 if (h!=NULL)
1517 {
1518 h=p_Copy(h, R);
1519 l=pLength(h);
1520 p_SetCompP(h,j+1, R);
1521 sBucket_Merge_p(bucket, h, l);
1522 }
1523 }
1524 sBucketClearMerge(bucket, &h, &l);
1525 sBucketDestroy(&bucket);
1526 return h;
1527}
1528
1529/// converts mat to module, destroys mat
1531{
1532 int mc=MATCOLS(mat);
1533 int mr=MATROWS(mat);
1534 ideal result = idInit(mc,mr);
1535 int i,j,l;
1536 poly h;
1537 sBucket_pt bucket = sBucketCreate(R);
1538
1539 for(j=0;j<mc /*MATCOLS(mat)*/;j++) /* j is also index in result->m */
1540 {
1541 for (i=0;i<mr /*MATROWS(mat)*/;i++)
1542 {
1543 h = MATELEM0(mat,i,j);
1544 if (h!=NULL)
1545 {
1546 l=pLength(h);
1547 MATELEM0(mat,i,j)=NULL;
1548 p_SetCompP(h,i+1, R);
1549 sBucket_Merge_p(bucket, h, l);
1550 }
1551 }
1552 sBucketClearMerge(bucket, &(result->m[j]), &l);
1553 }
1554 sBucketDestroy(&bucket);
1555
1556 // obachman: need to clean this up
1557 id_Delete((ideal*) &mat,R);
1558 return result;
1559}
1560
1561/*2
1562* converts a module into a matrix, destroys the input
1563*/
1565{
1566 matrix result = mpNew(mod->rank,IDELEMS(mod));
1567 long i; long cp;
1568 poly p,h;
1569
1570 for(i=0;i<IDELEMS(mod);i++)
1571 {
1572 p=pReverse(mod->m[i]);
1573 mod->m[i]=NULL;
1574 while (p!=NULL)
1575 {
1576 h=p;
1577 pIter(p);
1578 pNext(h)=NULL;
1579 cp = si_max(1L,p_GetComp(h, R)); // if used for ideals too
1580 //cp = p_GetComp(h,R);
1581 p_SetComp(h,0,R);
1582 p_SetmComp(h,R);
1583#ifdef TEST
1584 if (cp>mod->rank)
1585 {
1586 Print("## inv. rank %ld -> %ld\n",mod->rank,cp);
1587 int k,l,o=mod->rank;
1588 mod->rank=cp;
1589 matrix d=mpNew(mod->rank,IDELEMS(mod));
1590 for (l=0; l<o; l++)
1591 {
1592 for (k=0; k<IDELEMS(mod); k++)
1593 {
1596 }
1597 }
1598 id_Delete((ideal *)&result,R);
1599 result=d;
1600 }
1601#endif
1602 MATELEM0(result,cp-1,i) = p_Add_q(MATELEM0(result,cp-1,i),h,R);
1603 }
1604 }
1605 // obachman 10/99: added the following line, otherwise memory leak!
1606 id_Delete(&mod,R);
1607 return result;
1608}
1609
1610matrix id_Module2formatedMatrix(ideal mod,int rows, int cols, const ring R)
1611{
1612 matrix result = mpNew(rows,cols);
1613 int i,cp,r=id_RankFreeModule(mod,R),c=IDELEMS(mod);
1614 poly p,h;
1615
1616 if (r>rows) r = rows;
1617 if (c>cols) c = cols;
1618 for(i=0;i<c;i++)
1619 {
1620 p=pReverse(mod->m[i]);
1621 mod->m[i]=NULL;
1622 while (p!=NULL)
1623 {
1624 h=p;
1625 pIter(p);
1626 pNext(h)=NULL;
1627 cp = p_GetComp(h,R);
1628 if (cp<=r)
1629 {
1630 p_SetComp(h,0,R);
1631 p_SetmComp(h,R);
1632 MATELEM0(result,cp-1,i) = p_Add_q(MATELEM0(result,cp-1,i),h,R);
1633 }
1634 else
1635 p_Delete(&h,R);
1636 }
1637 }
1638 id_Delete(&mod,R);
1639 return result;
1640}
1641
1642ideal id_ResizeModule(ideal mod,int rows, int cols, const ring R)
1643{
1644 // columns?
1645 if (cols!=IDELEMS(mod))
1646 {
1647 for(int i=IDELEMS(mod)-1;i>=cols;i--) p_Delete(&mod->m[i],R);
1648 pEnlargeSet(&(mod->m),IDELEMS(mod),cols-IDELEMS(mod));
1649 IDELEMS(mod)=cols;
1650 }
1651 // rows?
1652 if (rows<mod->rank)
1653 {
1654 for(int i=IDELEMS(mod)-1;i>=0;i--)
1655 {
1656 if (mod->m[i]!=NULL)
1657 {
1658 while((mod->m[i]!=NULL) && (p_GetComp(mod->m[i],R)>rows))
1659 mod->m[i]=p_LmDeleteAndNext(mod->m[i],R);
1660 poly p=mod->m[i];
1661 while(pNext(p)!=NULL)
1662 {
1663 if (p_GetComp(pNext(p),R)>rows)
1665 else
1666 pIter(p);
1667 }
1668 }
1669 }
1670 }
1671 mod->rank=rows;
1672 return mod;
1673}
1674
1675/*2
1676* substitute the n-th variable by the monomial e in id
1677* destroy id
1678*/
1679ideal id_Subst(ideal id, int n, poly e, const ring r)
1680{
1681 int k=MATROWS((matrix)id)*MATCOLS((matrix)id);
1683
1684 res->rank = id->rank;
1685 for(k--;k>=0;k--)
1686 {
1687 res->m[k]=p_Subst(id->m[k],n,e,r);
1688 id->m[k]=NULL;
1689 }
1690 id_Delete(&id,r);
1691 return res;
1692}
1693
1695{
1696 if (w!=NULL) *w=NULL;
1697 if ((Q!=NULL) && (!id_HomIdeal(Q,NULL,R))) return FALSE;
1698 if (idIs0(m))
1699 {
1700 if (w!=NULL) (*w)=new intvec(m->rank);
1701 return TRUE;
1702 }
1703
1704 long cmax=1,order=0,ord,* diff,diffmin=32000;
1705 int *iscom;
1706 int i;
1707 poly p=NULL;
1708 pFDegProc d;
1709 if (R->pLexOrder && (R->order[0]==ringorder_lp))
1710 d=p_Totaldegree;
1711 else
1712 d=R->pFDeg;
1713 int length=IDELEMS(m);
1714 poly* P=m->m;
1715 poly* F=(poly*)omAlloc(length*sizeof(poly));
1716 for (i=length-1;i>=0;i--)
1717 {
1718 p=F[i]=P[i];
1720 }
1721 cmax++;
1722 diff = (long *)omAlloc0(cmax*sizeof(long));
1723 if (w!=NULL) *w=new intvec(cmax-1);
1724 iscom = (int *)omAlloc0(cmax*sizeof(int));
1725 i=0;
1726 while (i<=length)
1727 {
1728 if (i<length)
1729 {
1730 p=F[i];
1731 while ((p!=NULL) && (iscom[__p_GetComp(p,R)]==0)) pIter(p);
1732 }
1733 if ((p==NULL) && (i<length))
1734 {
1735 i++;
1736 }
1737 else
1738 {
1739 if (p==NULL) /* && (i==length) */
1740 {
1741 i=0;
1742 while ((i<length) && (F[i]==NULL)) i++;
1743 if (i>=length) break;
1744 p = F[i];
1745 }
1746 //if (pLexOrder && (currRing->order[0]==ringorder_lp))
1747 // order=pTotaldegree(p);
1748 //else
1749 // order = p->order;
1750 // order = pFDeg(p,currRing);
1751 order = d(p,R) +diff[__p_GetComp(p,R)];
1752 //order += diff[pGetComp(p)];
1753 p = F[i];
1754//Print("Actual p=F[%d]: ",i);pWrite(p);
1755 F[i] = NULL;
1756 i=0;
1757 }
1758 while (p!=NULL)
1759 {
1760 if (R->pLexOrder && (R->order[0]==ringorder_lp))
1761 ord=p_Totaldegree(p,R);
1762 else
1763 // ord = p->order;
1764 ord = R->pFDeg(p,R);
1765 if (iscom[__p_GetComp(p,R)]==0)
1766 {
1767 diff[__p_GetComp(p,R)] = order-ord;
1768 iscom[__p_GetComp(p,R)] = 1;
1769/*
1770*PrintS("new diff: ");
1771*for (j=0;j<cmax;j++) Print("%d ",diff[j]);
1772*PrintLn();
1773*PrintS("new iscom: ");
1774*for (j=0;j<cmax;j++) Print("%d ",iscom[j]);
1775*PrintLn();
1776*Print("new set %d, order %d, ord %d, diff %d\n",pGetComp(p),order,ord,diff[pGetComp(p)]);
1777*/
1778 }
1779 else
1780 {
1781/*
1782*PrintS("new diff: ");
1783*for (j=0;j<cmax;j++) Print("%d ",diff[j]);
1784*PrintLn();
1785*Print("order %d, ord %d, diff %d\n",order,ord,diff[pGetComp(p)]);
1786*/
1787 if (order != (ord+diff[__p_GetComp(p,R)]))
1788 {
1789 omFreeSize((ADDRESS) iscom,cmax*sizeof(int));
1790 omFreeSize((ADDRESS) diff,cmax*sizeof(long));
1791 omFreeSize((ADDRESS) F,length*sizeof(poly));
1792 delete *w;*w=NULL;
1793 return FALSE;
1794 }
1795 }
1796 pIter(p);
1797 }
1798 }
1799 omFreeSize((ADDRESS) iscom,cmax*sizeof(int));
1800 omFreeSize((ADDRESS) F,length*sizeof(poly));
1801 for (i=1;i<cmax;i++) (**w)[i-1]=(int)(diff[i]);
1802 for (i=1;i<cmax;i++)
1803 {
1804 if (diff[i]<diffmin) diffmin=diff[i];
1805 }
1806 if (w!=NULL)
1807 {
1808 for (i=1;i<cmax;i++)
1809 {
1810 (**w)[i-1]=(int)(diff[i]-diffmin);
1811 }
1812 }
1813 omFreeSize((ADDRESS) diff,cmax*sizeof(long));
1814 return TRUE;
1815}
1816
1817ideal id_Jet(const ideal i,int d, const ring R)
1818{
1819 ideal r=idInit((i->nrows)*(i->ncols),i->rank);
1820 r->nrows = i-> nrows;
1821 r->ncols = i-> ncols;
1822 //r->rank = i-> rank;
1823
1824 for(long k=((long)(i->nrows))*((long)(i->ncols))-1;k>=0; k--)
1825 r->m[k]=pp_Jet(i->m[k],d,R);
1826
1827 return r;
1828}
1829
1830ideal id_Jet0(const ideal i, const ring R)
1831{
1832 ideal r=idInit((i->nrows)*(i->ncols),i->rank);
1833 r->nrows = i-> nrows;
1834 r->ncols = i-> ncols;
1835 //r->rank = i-> rank;
1836
1837 for(long k=((long)(i->nrows))*((long)(i->ncols))-1;k>=0; k--)
1838 r->m[k]=pp_Jet0(i->m[k],R);
1839
1840 return r;
1841}
1842
1843ideal id_JetW(const ideal i,int d, intvec * iv, const ring R)
1844{
1845 ideal r=idInit(IDELEMS(i),i->rank);
1846 if (ecartWeights!=NULL)
1847 {
1848 WerrorS("cannot compute weighted jets now");
1849 }
1850 else
1851 {
1852 int *w=iv2array(iv,R);
1853 int k;
1854 for(k=0; k<IDELEMS(i); k++)
1855 {
1856 r->m[k]=pp_JetW(i->m[k],d,w,R);
1857 }
1858 omFreeSize((ADDRESS)w,(rVar(R)+1)*sizeof(int));
1859 }
1860 return r;
1861}
1862
1863#if 0
1864static void idDeleteComp(ideal arg,int red_comp)
1865{
1866 int i,j;
1867 poly p;
1868
1869 for (i=IDELEMS(arg)-1;i>=0;i--)
1870 {
1871 p = arg->m[i];
1872 while (p!=NULL)
1873 {
1874 j = pGetComp(p);
1875 if (j>red_comp)
1876 {
1877 pSetComp(p,j-1);
1878 pSetm(p);
1879 }
1880 pIter(p);
1881 }
1882 }
1883 (arg->rank)--;
1884}
1885#endif
1886
1888{
1889 poly head, tail;
1890 int k;
1891 int in=IDELEMS(id)-1, ready=0, all=0,
1892 coldim=rVar(r), rowmax=2*coldim;
1893 if (in<0) return NULL;
1894 intvec *imat=new intvec(rowmax+1,coldim,0);
1895
1896 do
1897 {
1898 head = id->m[in--];
1899 if (head!=NULL)
1900 {
1901 tail = pNext(head);
1902 while (tail!=NULL)
1903 {
1904 all++;
1905 for (k=1;k<=coldim;k++)
1906 IMATELEM(*imat,all,k) = p_GetExpDiff(head,tail,k,r);
1907 if (all==rowmax)
1908 {
1909 ivTriangIntern(imat, ready, all);
1910 if (ready==coldim)
1911 {
1912 delete imat;
1913 return NULL;
1914 }
1915 }
1916 pIter(tail);
1917 }
1918 }
1919 } while (in>=0);
1920 if (all>ready)
1921 {
1922 ivTriangIntern(imat, ready, all);
1923 if (ready==coldim)
1924 {
1925 delete imat;
1926 return NULL;
1927 }
1928 }
1929 intvec *result = ivSolveKern(imat, ready);
1930 delete imat;
1931 return result;
1932}
1933
1935{
1936 BOOLEAN *UsedAxis=(BOOLEAN *)omAlloc0(rVar(r)*sizeof(BOOLEAN));
1937 int i,n;
1938 poly po;
1940 for(i=IDELEMS(I)-1;i>=0;i--)
1941 {
1942 po=I->m[i];
1943 if ((po!=NULL) &&((n=p_IsPurePower(po,r))!=0)) UsedAxis[n-1]=TRUE;
1944 }
1945 for(i=rVar(r)-1;i>=0;i--)
1946 {
1947 if(UsedAxis[i]==FALSE) {res=FALSE; break;} // not zero-dim.
1948 }
1949 omFreeSize(UsedAxis,rVar(r)*sizeof(BOOLEAN));
1950 return res;
1951}
1952
1953void id_Normalize(ideal I,const ring r) /* for ideal/matrix */
1954{
1955 if (rField_has_simple_inverse(r)) return; /* Z/p, GF(p,n), R, long R/C */
1956 int i;
1957 for(i=I->nrows*I->ncols-1;i>=0;i--)
1958 {
1959 p_Normalize(I->m[i],r);
1960 }
1961}
1962
1964{
1965 int d=-1;
1966 for(int i=0;i<IDELEMS(M);i++)
1967 {
1968 if (M->m[i]!=NULL)
1969 {
1970 int d0=p_MinDeg(M->m[i],w,r);
1971 if(-1<d0&&((d0<d)||(d==-1)))
1972 d=d0;
1973 }
1974 }
1975 return d;
1976}
1977
1978// #include "kernel/clapsing.h"
1979
1980/*2
1981* transpose a module
1982*/
1984{
1985 int r = a->rank, c = IDELEMS(a);
1986 ideal b = idInit(r,c);
1987
1988 int i;
1989 for (i=c; i>0; i--)
1990 {
1991 poly p=a->m[i-1];
1992 while(p!=NULL)
1993 {
1994 poly h=p_Head(p, rRing);
1995 int co=__p_GetComp(h, rRing)-1;
1996 p_SetComp(h, i, rRing);
1997 p_Setm(h, rRing);
1998 h->next=b->m[co];
1999 b->m[co]=h;
2000 pIter(p);
2001 }
2002 }
2003 for (i=IDELEMS(b)-1; i>=0; i--)
2004 {
2005 poly p=b->m[i];
2006 if(p!=NULL)
2007 {
2008 b->m[i]=p_SortMerge(p,rRing,TRUE);
2009 }
2010 }
2011 return b;
2012}
2013
2014/*2
2015* The following is needed to compute the image of certain map used in
2016* the computation of cohomologies via BGG
2017* let M = { w_1, ..., w_k }, k = size(M) == ncols(M), n = nvars(currRing).
2018* assuming that nrows(M) <= m*n; the procedure computes:
2019* transpose(M) * transpose( var(1) I_m | ... | var(n) I_m ) :== transpose(module{f_1, ... f_k}),
2020* where f_i = \sum_{j=1}^{m} (w_i, v_j) gen(j), (w_i, v_j) is a `scalar` multiplication.
2021* that is, if w_i = (a^1_1, ... a^1_m) | (a^2_1, ..., a^2_m) | ... | (a^n_1, ..., a^n_m) then
2022
2023 (a^1_1, ... a^1_m) | (a^2_1, ..., a^2_m) | ... | (a^n_1, ..., a^n_m)
2024* var_1 ... var_1 | var_2 ... var_2 | ... | var_n ... var(n)
2025* gen_1 ... gen_m | gen_1 ... gen_m | ... | gen_1 ... gen_m
2026+ =>
2027 f_i =
2028
2029 a^1_1 * var(1) * gen(1) + ... + a^1_m * var(1) * gen(m) +
2030 a^2_1 * var(2) * gen(1) + ... + a^2_m * var(2) * gen(m) +
2031 ...
2032 a^n_1 * var(n) * gen(1) + ... + a^n_m * var(n) * gen(m);
2033
2034 NOTE: for every f_i we run only ONCE along w_i saving partial sums into a temporary array of polys of size m
2035*/
2036ideal id_TensorModuleMult(const int m, const ideal M, const ring rRing)
2037{
2038// #ifdef DEBU
2039// WarnS("tensorModuleMult!!!!");
2040
2041 assume(m > 0);
2042 assume(M != NULL);
2043
2044 const int n = rRing->N;
2045
2046 assume(M->rank <= m * n);
2047
2048 const int k = IDELEMS(M);
2049
2050 ideal idTemp = idInit(k,m); // = {f_1, ..., f_k }
2051
2052 for( int i = 0; i < k; i++ ) // for every w \in M
2053 {
2054 poly pTempSum = NULL;
2055
2056 poly w = M->m[i];
2057
2058 while(w != NULL) // for each term of w...
2059 {
2060 poly h = p_Head(w, rRing);
2061
2062 const int gen = __p_GetComp(h, rRing); // 1 ...
2063
2064 assume(gen > 0);
2065 assume(gen <= n*m);
2066
2067 // TODO: write a formula with %, / instead of while!
2068 /*
2069 int c = gen;
2070 int v = 1;
2071 while(c > m)
2072 {
2073 c -= m;
2074 v++;
2075 }
2076 */
2077
2078 int cc = gen % m;
2079 if( cc == 0) cc = m;
2080 int vv = 1 + (gen - cc) / m;
2081
2082// assume( cc == c );
2083// assume( vv == v );
2084
2085 // 1<= c <= m
2086 assume( cc > 0 );
2087 assume( cc <= m );
2088
2089 assume( vv > 0 );
2090 assume( vv <= n );
2091
2092 assume( (cc + (vv-1)*m) == gen );
2093
2094 p_IncrExp(h, vv, rRing); // h *= var(j) && // p_AddExp(h, vv, 1, rRing);
2095 p_SetComp(h, cc, rRing);
2096
2097 p_Setm(h, rRing); // adjust degree after the previous steps!
2098
2099 pTempSum = p_Add_q(pTempSum, h, rRing); // it is slow since h will be usually put to the back of pTempSum!!!
2100
2101 pIter(w);
2102 }
2103
2104 idTemp->m[i] = pTempSum;
2105 }
2106
2107 // simplify idTemp???
2108
2110
2112
2113 return(idResult);
2114}
2115
2117{
2118 int cnt=0;int rw=0; int cl=0;
2119 int i,j;
2120 // find max. size of xx[.]:
2121 for(j=rl-1;j>=0;j--)
2122 {
2123 i=IDELEMS(xx[j])*xx[j]->nrows;
2124 if (i>cnt) cnt=i;
2125 if (xx[j]->nrows >rw) rw=xx[j]->nrows; // for lifting matrices
2126 if (xx[j]->ncols >cl) cl=xx[j]->ncols; // for lifting matrices
2127 }
2128 if (rw*cl !=cnt)
2129 {
2130 WerrorS("format mismatch in CRT");
2131 return NULL;
2132 }
2133 ideal result=idInit(cnt,xx[0]->rank);
2134 result->nrows=rw; // for lifting matrices
2135 result->ncols=cl; // for lifting matrices
2136 number *x=(number *)omAlloc(rl*sizeof(number));
2137 poly *p=(poly *)omAlloc(rl*sizeof(poly));
2139 EXTERN_VAR int n_SwitchChinRem; //TEST
2142 for(i=cnt-1;i>=0;i--)
2143 {
2144 for(j=rl-1;j>=0;j--)
2145 {
2146 if(i>=IDELEMS(xx[j])*xx[j]->nrows) // out of range of this ideal
2147 p[j]=NULL;
2148 else
2149 p[j]=xx[j]->m[i];
2150 }
2152 for(j=rl-1;j>=0;j--)
2153 {
2154 if(i<IDELEMS(xx[j])*xx[j]->nrows) xx[j]->m[i]=p[j];
2155 }
2156 }
2158 omFreeSize(p,rl*sizeof(poly));
2159 omFreeSize(x,rl*sizeof(number));
2160 for(i=rl-1;i>=0;i--) id_Delete(&(xx[i]),r);
2161 omFreeSize(xx,rl*sizeof(ideal));
2162 return result;
2163}
2164
2165void id_Shift(ideal M, int s, const ring r)
2166{
2167// id_Test( M, r );
2168
2169// assume( s >= 0 ); // negative is also possible // TODO: verify input ideal in such a case!?
2170
2171 for(int i=IDELEMS(M)-1; i>=0;i--)
2172 p_Shift(&(M->m[i]),s,r);
2173
2174 M->rank += s;
2175
2176// id_Test( M, r );
2177}
2178
2179ideal id_Delete_Pos(const ideal I, const int p, const ring r)
2180{
2181 if ((p<0)||(p>=IDELEMS(I))) return NULL;
2182 ideal ret=idInit(IDELEMS(I)-1,I->rank);
2183 for(int i=0;i<p;i++) ret->m[i]=p_Copy(I->m[i],r);
2184 for(int i=p+1;i<IDELEMS(I);i++) ret->m[i-1]=p_Copy(I->m[i],r);
2185 return ret;
2186}
2187
2188ideal id_PermIdeal(ideal I,int R, int C,const int *perm, const ring src, const ring dst,
2189 nMapFunc nMap, const int *par_perm, int P, BOOLEAN use_mult)
2190{
2191 ideal II=(ideal)mpNew(R,C);
2192 II->rank=I->rank;
2193 for(int i=R*C-1; i>=0; i--)
2194 {
2195 II->m[i]=p_PermPoly(I->m[i],perm,src,dst,nMap,par_perm,P,use_mult);
2196 }
2197 return II;
2198}
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
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: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
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:85
STATIC_VAR Poly * h
Definition janet.cc:971
poly p_ChineseRemainder(poly *xx, mpz_ptr *x, mpz_ptr *q, int rl, mpz_ptr *C, const ring R)
VAR int n_SwitchChinRem
Definition longrat.cc:3085
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)
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:4399
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:4645
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:3999
void p_Vec2Polys(poly v, poly **p, int *len, const ring r)
Definition p_polys.cc:3665
void p_Shift(poly *p, int i, const ring r)
shifts components of the vector p by i
Definition p_polys.cc:4775
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:4171
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:3854
void p_Norm(poly p1, const ring r)
Definition p_polys.cc:3759
poly pp_Jet0(poly p, const ring R)
Definition p_polys.cc:4427
int p_MinDeg(poly p, intvec *w, const ring R)
Definition p_polys.cc:4517
unsigned long p_GetShortExpVector(const poly p, const ring r)
Definition p_polys.cc:4849
BOOLEAN p_IsHomogeneousW(poly p, const intvec *w, const ring r)
Definition p_polys.cc:3366
poly p_One(const ring r)
Definition p_polys.cc:1314
void pEnlargeSet(poly **p, int l, int increment)
Definition p_polys.cc:3736
BOOLEAN p_IsHomogeneous(poly p, const ring r)
Definition p_polys.cc:3323
poly pp_JetW(poly p, int m, int *w, const ring R)
Definition p_polys.cc:4472
poly p_CopyPowerProduct0(const poly p, number n, const ring r)
like p_Head, but with coefficient n
Definition p_polys.cc:5037
BOOLEAN p_IsHomogeneousDP(poly p, const ring r)
Definition p_polys.cc:3347
BOOLEAN p_EqualPolys(poly p1, poly p2, const ring r)
Definition p_polys.cc:4581
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:636
static poly p_Add_q(poly p, poly q, const ring r)
Definition p_polys.h:937
static poly p_Mult_q(poly p, poly q, const ring r)
Definition p_polys.h:1119
#define p_LmEqual(p1, p2, r)
Definition p_polys.h:1738
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:255
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:489
#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:248
static long p_IncrExp(poly p, int v, ring r)
Definition p_polys.h:592
static void p_Setm(poly p, const ring r)
Definition p_polys.h:234
#define p_SetmComp
Definition p_polys.h:245
static poly p_SortMerge(poly p, const ring r, BOOLEAN revert=FALSE)
Definition p_polys.h:1244
static poly pReverse(poly p)
Definition p_polys.h:336
static int p_LtCmp(poly p, poly q, const ring r)
Definition p_polys.h:1636
static BOOLEAN p_LmIsConstantComp(const poly p, const ring r)
Definition p_polys.h:1007
static poly p_Head(const poly p, const ring r)
copy the (leading) term of p
Definition p_polys.h:861
static BOOLEAN p_LmShortDivisibleBy(poly a, unsigned long sev_a, poly b, unsigned long not_sev_b, const ring r)
Definition p_polys.h:1925
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:470
static BOOLEAN p_LmDivisibleBy(poly a, poly b, const ring r)
Definition p_polys.h:1906
static long p_MaxComp(poly p, ring lmRing, ring tailRing)
Definition p_polys.h:293
static void p_Delete(poly *p, const ring r)
Definition p_polys.h:902
static poly pp_Mult_qq(poly p, poly q, const ring r)
Definition p_polys.h:1161
static void p_LmFree(poly p, ring)
Definition p_polys.h:684
static BOOLEAN p_IsUnit(const poly p, const ring r)
Definition p_polys.h:2006
static poly p_LmDeleteAndNext(poly p, const ring r)
Definition p_polys.h:756
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition p_polys.h:847
static long p_Totaldegree(poly p, const ring r)
Definition p_polys.h:1522
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:1993
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:597
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition ring.h:553
#define rField_is_Ring(R)
Definition ring.h:490
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
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)
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 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