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