source: git/kernel/ideals.cc @ 10ed4a3

spielwiese
Last change on this file since 10ed4a3 was 10ed4a3, checked in by Hans Schönemann <hannes@…>, 15 years ago
idElim tests... git-svn-id: file:///usr/local/Singular/svn/trunk@11188 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 78.0 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id: ideals.cc,v 1.61 2008-11-12 12:41:03 Singular Exp $ */
5/*
6* ABSTRACT - all basic methods to manipulate ideals
7*/
8
9/* includes */
10#include "mod2.h"
11#include "structs.h"
12#include "omalloc.h"
13#include "febase.h"
14#include "numbers.h"
15#include "longrat.h"
16#include "polys.h"
17#include "ring.h"
18#include "kstd1.h"
19#include "matpol.h"
20#include "weight.h"
21#include "intvec.h"
22#include "syz.h"
23#include "sparsmat.h"
24#include "ideals.h"
25#include "prCopy.h"
26
27
28#define MYTEST 0
29
30
31/* #define WITH_OLD_MINOR */
32#define pCopy_noCheck(p) pCopy(p)
33
34static poly * idpower;
35/*collects the monomials in makemonoms, must be allocated befor*/
36static int idpowerpoint;
37/*index of the actual monomial in idpower*/
38static poly * givenideal;
39/*the ideal from which a power is computed*/
40
41/*0 implementation*/
42
43/*2
44* initialise an ideal
45*/
46#ifdef PDEBUG
47ideal idDBInit(int idsize, int rank, const char *f, int l)
48#else
49ideal idInit(int idsize, int rank)
50#endif
51{
52  /*- initialise an ideal -*/
53  ideal hh = (ideal )omAllocBin(sip_sideal_bin);
54  hh->nrows = 1;
55  hh->rank = rank;
56  IDELEMS(hh) = idsize;
57  if (idsize>0)
58  {
59    hh->m = (poly *)omAlloc0(idsize*sizeof(poly));
60  }
61  else
62    hh->m=NULL;
63  return hh;
64}
65
66//#ifndef __OPTIMIZE__
67// this is mainly for outputting an ideal within the debugger
68void idShow(ideal id)
69{
70  if( id == NULL )
71    Print("(NULL)");
72  else
73  {
74    Print("Module of rank %d,real rank %d and %d generators.\n",
75           id->rank,idRankFreeModule(id),IDELEMS(id));
76    for (int i=0;i<id->ncols*id->nrows;i++)
77    {
78      if (id->m[i]!=NULL)
79      {
80        Print("generator %d: ",i);pWrite(id->m[i]);
81      }
82    }
83  }
84}
85//#endif
86
87/*2
88* initialise the maximal ideal (at 0)
89*/
90ideal idMaxIdeal (void)
91{
92  int l;
93  ideal hh=NULL;
94
95  hh=idInit(pVariables,1);
96  for (l=0; l<pVariables; l++)
97  {
98    hh->m[l] = pOne();
99    pSetExp(hh->m[l],l+1,1);
100    pSetm(hh->m[l]);
101  }
102  return hh;
103}
104
105/*2
106* deletes an ideal/matrix
107*/
108void id_Delete (ideal * h, ring r)
109{
110  int j,elems;
111  if (*h == NULL)
112    return;
113  elems=j=(*h)->nrows*(*h)->ncols;
114  if (j>0)
115  {
116    do
117    {
118      p_Delete(&((*h)->m[--j]), r);
119    }
120    while (j>0);
121    omFreeSize((ADDRESS)((*h)->m),sizeof(poly)*elems);
122  }
123  omFreeBin((ADDRESS)*h, sip_sideal_bin);
124  *h=NULL;
125}
126
127
128/*2
129* Shallowdeletes an ideal/matrix
130*/
131void id_ShallowDelete (ideal *h, ring r)
132{
133  int j,elems;
134  if (*h == NULL)
135    return;
136  elems=j=(*h)->nrows*(*h)->ncols;
137  if (j>0)
138  {
139    do
140    {
141      p_ShallowDelete(&((*h)->m[--j]), r);
142    }
143    while (j>0);
144    omFreeSize((ADDRESS)((*h)->m),sizeof(poly)*elems);
145  }
146  omFreeBin((ADDRESS)*h, sip_sideal_bin);
147  *h=NULL;
148}
149
150/*2
151*gives an ideal the minimal possible size
152*/
153void idSkipZeroes (ideal ide)
154{
155  int k;
156  int j = -1;
157  BOOLEAN change=FALSE;
158  for (k=0; k<IDELEMS(ide); k++)
159  {
160    if (ide->m[k] != NULL)
161    {
162      j++;
163      if (change)
164      {
165        ide->m[j] = ide->m[k];
166      }
167    }
168    else
169    {
170      change=TRUE;
171    }
172  }
173  if (change)
174  {
175    if (j == -1)
176      j = 0;
177    else
178    {
179      for (k=j+1; k<IDELEMS(ide); k++)
180        ide->m[k] = NULL;
181    }
182    pEnlargeSet(&(ide->m),IDELEMS(ide),j+1-IDELEMS(ide));
183    IDELEMS(ide) = j+1;
184  }
185}
186
187/*2
188* ideal id = (id[i])
189* result is leadcoeff(id[i]) = 1
190*/
191void idNorm(ideal id)
192{
193  for (int i=IDELEMS(id)-1; i>=0; i--)
194  {
195    if (id->m[i] != NULL)
196    {
197      pNorm(id->m[i]);
198    }
199  }
200}
201
202/*2
203* ideal id = (id[i]), c any number
204* if id[i] = c*id[j] then id[j] is deleted for j > i
205*/
206void idDelMultiples(ideal id)
207{
208  int i, j;
209  int k = IDELEMS(id)-1;
210  for (i=k; i>=0; i--)
211  {
212    if (id->m[i]!=NULL)
213    {
214      for (j=k; j>i; j--)
215      {
216        if ((id->m[j]!=NULL)
217        && (pComparePolys(id->m[i], id->m[j])))
218        {
219          pDelete(&id->m[j]);
220        }
221      }
222    }
223  }
224}
225
226/*2
227* ideal id = (id[i])
228* if id[i] = id[j] then id[j] is deleted for j > i
229*/
230void idDelEquals(ideal id)
231{
232  int i, j;
233  int k = IDELEMS(id)-1;
234  for (i=k; i>=0; i--)
235  {
236    if (id->m[i]!=NULL)
237    {
238      for (j=k; j>i; j--)
239      {
240        if ((id->m[j]!=NULL)
241        && (pEqualPolys(id->m[i], id->m[j])))
242        {
243          pDelete(&id->m[j]);
244        }
245      }
246    }
247  }
248}
249
250//
251// Delete id[j], if Lm(j) == Lm(i) and j > i
252//
253void idDelLmEquals(ideal id)
254{
255  int i, j;
256  int k = IDELEMS(id)-1;
257  for (i=k; i>=0; i--)
258  {
259    if (id->m[i] != NULL)
260    {
261      for (j=k; j>i; j--)
262      {
263        if ((id->m[j] != NULL)
264        && pLmEqual(id->m[i], id->m[j]))
265        {
266          pDelete(&id->m[j]);
267        }
268      }
269    }
270  }
271}
272
273void idDelDiv(ideal id)
274{
275  int i, j;
276  int k = IDELEMS(id)-1;
277  for (i=k; i>=0; i--)
278  {
279    if (id->m[i] != NULL)
280    {
281      for (j=k; j>i; j--)
282      {
283        if (id->m[j]!=NULL)
284        {
285          if(pDivisibleBy(id->m[i], id->m[j]))
286          {
287            pDelete(&id->m[j]);
288          }
289          else if(pDivisibleBy(id->m[j], id->m[i]))
290          {
291            pDelete(&id->m[i]);
292            break;
293          }
294        }
295      }
296    }
297  }
298}
299
300/*2
301*test if the ideal has only constant polynomials
302*/
303BOOLEAN idIsConstant(ideal id)
304{
305  int k;
306  for (k = IDELEMS(id)-1; k>=0; k--)
307  {
308    if (pIsConstantPoly(id->m[k]) == FALSE)
309      return FALSE;
310  }
311  return TRUE;
312}
313
314/*2
315* copy an ideal
316*/
317#ifdef PDEBUG
318ideal idDBCopy(ideal h1,const char *f,int l)
319{
320  int i;
321  ideal h2;
322
323  idDBTest(h1,PDEBUG,f,l);
324//#ifdef TEST
325  if (h1 == NULL)
326  {
327    h2=idDBInit(1,1,f,l);
328  }
329  else
330//#endif
331  {
332    h2=idDBInit(IDELEMS(h1),h1->rank,f,l);
333    for (i=IDELEMS(h1)-1; i>=0; i--)
334      h2->m[i] = pCopy(h1->m[i]);
335  }
336  return h2;
337}
338#endif
339
340ideal id_Copy (ideal h1, const ring r)
341{
342  int i;
343  ideal h2;
344
345//#ifdef TEST
346  if (h1 == NULL)
347  {
348    h2=idInit(1,1);
349  }
350  else
351//#endif
352  {
353    h2=idInit(IDELEMS(h1),h1->rank);
354    for (i=IDELEMS(h1)-1; i>=0; i--)
355      h2->m[i] = p_Copy(h1->m[i],r);
356  }
357  return h2;
358}
359
360#ifdef PDEBUG
361void idDBTest(ideal h1, int level, const char *f,const int l)
362{
363  int i;
364
365  if (h1 != NULL)
366  {
367    // assume(IDELEMS(h1) > 0); for ideal/module, does not apply to matrix
368    omCheckAddrSize(h1,sizeof(*h1));
369    omdebugAddrSize(h1->m,h1->ncols*h1->nrows*sizeof(poly));
370    /* to be able to test matrices: */
371    for (i=(h1->ncols*h1->nrows)-1; i>=0; i--)
372      _p_Test(h1->m[i], currRing, level);
373    int new_rk=idRankFreeModule(h1);
374    if(new_rk > h1->rank)
375    {
376      dReportError("wrong rank %d (should be %d) in %s:%d\n",
377                   h1->rank, new_rk, f,l);
378      omPrintAddrInfo(stderr, h1, " for ideal");
379      h1->rank=new_rk;
380    }
381  }
382}
383#endif
384
385/*3
386* for idSort: compare a and b revlex inclusive module comp.
387*/
388static int pComp_RevLex(poly a, poly b,BOOLEAN nolex)
389{
390  if (b==NULL) return 1;
391  if (a==NULL) return -1;
392
393  if (nolex) return pLmCmp(a,b);
394  int l=pVariables;
395  while ((l>0) && (pGetExp(a,l)==pGetExp(b,l))) l--;
396  if (l==0)
397  {
398    if (pGetComp(a)==pGetComp(b)) return 0;
399    if (pGetComp(a)>pGetComp(b)) return 1;
400  }
401  else if (pGetExp(a,l)>pGetExp(b,l))
402    return 1;
403  return -1;
404}
405
406/*2
407*sorts the ideal w.r.t. the actual ringordering
408*uses lex-ordering when nolex = FALSE
409*/
410intvec *idSort(ideal id,BOOLEAN nolex)
411{
412  poly p,q;
413  intvec * result = new intvec(IDELEMS(id));
414  int i, j, actpos=0, newpos, l;
415  int diff, olddiff, lastcomp, newcomp;
416  BOOLEAN notFound;
417
418  for (i=0;i<IDELEMS(id);i++)
419  {
420    if (id->m[i]!=NULL)
421    {
422      notFound = TRUE;
423      newpos = actpos / 2;
424      diff = (actpos+1) / 2;
425      diff = (diff+1) / 2;
426      lastcomp = pComp_RevLex(id->m[i],id->m[(*result)[newpos]],nolex);
427      if (lastcomp<0)
428      {
429        newpos -= diff;
430      }
431      else if (lastcomp>0)
432      {
433        newpos += diff;
434      }
435      else
436      {
437        notFound = FALSE;
438      }
439      //while ((newpos>=0) && (newpos<actpos) && (notFound))
440      while (notFound && (newpos>=0) && (newpos<actpos))
441      {
442        newcomp = pComp_RevLex(id->m[i],id->m[(*result)[newpos]],nolex);
443        olddiff = diff;
444        if (diff>1)
445        {
446          diff = (diff+1) / 2;
447          if ((newcomp==1)
448          && (actpos-newpos>1)
449          && (diff>1)
450          && (newpos+diff>=actpos))
451          {
452            diff = actpos-newpos-1;
453          }
454          else if ((newcomp==-1)
455          && (diff>1)
456          && (newpos<diff))
457          {
458            diff = newpos;
459          }
460        }
461        if (newcomp<0)
462        {
463          if ((olddiff==1) && (lastcomp>0))
464            notFound = FALSE;
465          else
466            newpos -= diff;
467        }
468        else if (newcomp>0)
469        {
470          if ((olddiff==1) && (lastcomp<0))
471          {
472            notFound = FALSE;
473            newpos++;
474          }
475          else
476          {
477            newpos += diff;
478          }
479        }
480        else
481        {
482          notFound = FALSE;
483        }
484        lastcomp = newcomp;
485        if (diff==0) notFound=FALSE; /*hs*/
486      }
487      if (newpos<0) newpos = 0;
488      if (newpos>actpos) newpos = actpos;
489      while ((newpos<actpos) && (pComp_RevLex(id->m[i],id->m[(*result)[newpos]],nolex)==0))
490        newpos++;
491      for (j=actpos;j>newpos;j--)
492      {
493        (*result)[j] = (*result)[j-1];
494      }
495      (*result)[newpos] = i;
496      actpos++;
497    }
498  }
499  for (j=0;j<actpos;j++) (*result)[j]++;
500  return result;
501}
502
503/*2
504* concat the lists h1 and h2 without zeros
505*/
506ideal idSimpleAdd (ideal h1,ideal h2)
507{
508  int i,j,r,l;
509  ideal result;
510
511  if (h1==NULL) return idCopy(h2);
512  if (h2==NULL) return idCopy(h1);
513  j = IDELEMS(h1)-1;
514  while ((j >= 0) && (h1->m[j] == NULL)) j--;
515  i = IDELEMS(h2)-1;
516  while ((i >= 0) && (h2->m[i] == NULL)) i--;
517  r = si_max(h1->rank,h2->rank);
518  if (i+j==(-2))
519    return idInit(1,r);
520  else
521    result=idInit(i+j+2,r);
522  for (l=j; l>=0; l--)
523  {
524    result->m[l] = pCopy(h1->m[l]);
525  }
526  r = i+j+1;
527  for (l=i; l>=0; l--, r--)
528  {
529    result->m[r] = pCopy(h2->m[l]);
530  }
531  return result;
532}
533
534/*2
535* h1 + h2
536*/
537ideal idAdd (ideal h1,ideal h2)
538{
539  ideal result = idSimpleAdd(h1,h2);
540  idCompactify(result);
541  return result;
542}
543
544/*2
545* h1 * h2
546*/
547ideal  idMult (ideal h1,ideal  h2)
548{
549  int i,j,k;
550  ideal  hh;
551
552  j = IDELEMS(h1);
553  while ((j > 0) && (h1->m[j-1] == NULL)) j--;
554  i = IDELEMS(h2);
555  while ((i > 0) && (h2->m[i-1] == NULL)) i--;
556  j = j * i;
557  if (j == 0)
558    hh = idInit(1,1);
559  else
560    hh=idInit(j,1);
561  if (h1->rank<h2->rank)
562    hh->rank = h2->rank;
563  else
564    hh->rank = h1->rank;
565  if (j==0) return hh;
566  k = 0;
567  for (i=0; i<IDELEMS(h1); i++)
568  {
569    if (h1->m[i] != NULL)
570    {
571      for (j=0; j<IDELEMS(h2); j++)
572      {
573        if (h2->m[j] != NULL)
574        {
575          hh->m[k] = ppMult_qq(h1->m[i],h2->m[j]);
576          k++;
577        }
578      }
579    }
580  }
581  {
582    idCompactify(hh);
583    return hh;
584  }
585}
586
587/*2
588*returns true if h is the zero ideal
589*/
590BOOLEAN idIs0 (ideal h)
591{
592  int i;
593
594  if (h == NULL) return TRUE;
595  i = IDELEMS(h)-1;
596  while ((i >= 0) && (h->m[i] == NULL))
597  {
598    i--;
599  }
600  if (i < 0)
601    return TRUE;
602  else
603    return FALSE;
604}
605
606/*2
607* return the maximal component number found in any polynomial in s
608*/
609long idRankFreeModule (ideal s, ring lmRing, ring tailRing)
610{
611  if (s!=NULL)
612  {
613    int  j=0;
614
615    if (rRing_has_Comp(tailRing) && rRing_has_Comp(lmRing))
616    {
617      int  l=IDELEMS(s);
618      poly *p=s->m;
619      int  k;
620      for (; l != 0; l--)
621      {
622        if (*p!=NULL)
623        {
624          pp_Test(*p, lmRing, tailRing);
625          k = p_MaxComp(*p, lmRing, tailRing);
626          if (k>j) j = k;
627        }
628        p++;
629      }
630    }
631    return j;
632  }
633  return -1;
634}
635
636BOOLEAN idIsModule(ideal id, ring r)
637{
638  if (id != NULL && rRing_has_Comp(r))
639  {
640    int j, l = IDELEMS(id);
641    for (j=0; j<l; j++)
642    {
643      if (id->m[j] != NULL && p_GetComp(id->m[j], r) > 0) return TRUE;
644    }
645  }
646  return FALSE;
647}
648
649
650/*2
651*returns true if id is homogenous with respect to the aktual weights
652*/
653BOOLEAN idHomIdeal (ideal id, ideal Q)
654{
655  int i;
656  BOOLEAN     b;
657  if ((id == NULL) || (IDELEMS(id) == 0)) return TRUE;
658  i = 0;
659  b = TRUE;
660  while ((i < IDELEMS(id)) && b)
661  {
662    b = pIsHomogeneous(id->m[i]);
663    i++;
664  }
665  if ((b) && (Q!=NULL) && (IDELEMS(Q)>0))
666  {
667    i=0;
668    while ((i < IDELEMS(Q)) && b)
669    {
670      b = pIsHomogeneous(Q->m[i]);
671      i++;
672    }
673  }
674  return b;
675}
676
677/*2
678*returns a minimized set of generators of h1
679*/
680ideal idMinBase (ideal h1)
681{
682  ideal h2, h3,h4,e;
683  int j,k;
684  int i,l,ll;
685  intvec * wth;
686  BOOLEAN homog;
687
688  homog = idHomModule(h1,currQuotient,&wth);
689  if ((currRing->OrdSgn == 1) && (!homog))
690  {
691    Warn("minbase applies only to the local or homogeneous case");
692    e=idCopy(h1);
693    return e;
694  }
695  if ((currRing->OrdSgn == 1) && (homog))
696  {
697    ideal re=kMin_std(h1,currQuotient,(tHomog)homog,&wth,h2,NULL,0,3);
698    idDelete(&re);
699    return h2;
700  }
701  e=idInit(1,h1->rank);
702  if (idIs0(h1))
703  {
704    return e;
705  }
706  pEnlargeSet(&(e->m),IDELEMS(e),15);
707  IDELEMS(e) = 16;
708  h2 = kStd(h1,currQuotient,isNotHomog,NULL);
709  h3 = idMaxIdeal();
710  h4=idMult(h2,h3);
711  idDelete(&h3);
712  h3=kStd(h4,currQuotient,isNotHomog,NULL);
713  k = IDELEMS(h3);
714  while ((k > 0) && (h3->m[k-1] == NULL)) k--;
715  j = -1;
716  l = IDELEMS(h2);
717  while ((l > 0) && (h2->m[l-1] == NULL)) l--;
718  for (i=l-1; i>=0; i--)
719  {
720    if (h2->m[i] != NULL)
721    {
722      ll = 0;
723      while ((ll < k) && ((h3->m[ll] == NULL)
724      || !pDivisibleBy(h3->m[ll],h2->m[i])))
725        ll++;
726      if (ll >= k)
727      {
728        j++;
729        if (j > IDELEMS(e)-1)
730        {
731          pEnlargeSet(&(e->m),IDELEMS(e),16);
732          IDELEMS(e) += 16;
733        }
734        e->m[j] = pCopy(h2->m[i]);
735      }
736    }
737  }
738  idDelete(&h2);
739  idDelete(&h3);
740  idDelete(&h4);
741  if (currQuotient!=NULL)
742  {
743    h3=idInit(1,e->rank);
744    h2=kNF(h3,currQuotient,e);
745    idDelete(&h3);
746    idDelete(&e);
747    e=h2;
748  }
749  idSkipZeroes(e);
750  return e;
751}
752
753/*2
754*the minimal index of used variables - 1
755*/
756int pLowVar (poly p)
757{
758  int k,l,lex;
759
760  if (p == NULL) return -1;
761
762  k = 32000;/*a very large dummy value*/
763  while (p != NULL)
764  {
765    l = 1;
766    lex = pGetExp(p,l);
767    while ((l < pVariables) && (lex == 0))
768    {
769      l++;
770      lex = pGetExp(p,l);
771    }
772    l--;
773    if (l < k) k = l;
774    pIter(p);
775  }
776  return k;
777}
778
779/*3
780*multiplies p with t (!cas) or  (t-1)
781*the index of t is:1, so we have to shift all variables
782*p is NOT in the actual ring, it has no t
783*/
784static poly pMultWithT (poly p,BOOLEAN cas)
785{
786  /*qp is the working pointer in p*/
787  /*result is the result, qresult is the working pointer*/
788  /*pp is p in the actual ring(shifted), qpp the working pointer*/
789  poly result,qp,pp;
790  poly qresult=NULL;
791  poly qpp=NULL;
792  int  i,j,lex;
793  number n;
794
795  pp = NULL;
796  result = NULL;
797  qp = p;
798  while (qp != NULL)
799  {
800    i = 0;
801    if (result == NULL)
802    {/*first monomial*/
803      result = pInit();
804      qresult = result;
805    }
806    else
807    {
808      qresult->next = pInit();
809      pIter(qresult);
810    }
811    for (j=pVariables-1; j>0; j--)
812    {
813      lex = pGetExp(qp,j);
814      pSetExp(qresult,j+1,lex);/*copy all variables*/
815    }
816    lex = pGetComp(qp);
817    pSetComp(qresult,lex);
818    n=nCopy(pGetCoeff(qp));
819    pSetCoeff0(qresult,n);
820    qresult->next = NULL;
821    pSetm(qresult);
822    /*qresult is now qp brought into the actual ring*/
823    if (cas)
824    { /*case: mult with t-1*/
825      pSetExp(qresult,1,0);
826      pSetm(qresult);
827      if (pp == NULL)
828      { /*first monomial*/
829        pp = pCopy(qresult);
830        qpp = pp;
831      }
832      else
833      {
834        qpp->next = pCopy(qresult);
835        pIter(qpp);
836      }
837      pGetCoeff(qpp)=nNeg(pGetCoeff(qpp));
838      /*now qpp contains -1*qp*/
839    }
840    pSetExp(qresult,1,1);/*this is mult. by t*/
841    pSetm(qresult);
842    pIter(qp);
843  }
844  /*
845  *now p is processed:
846  *result contains t*p
847  * if cas: pp contains -1*p (in the new ring)
848  */
849  if (cas)  qresult->next = pp;
850  /*  else      qresult->next = NULL;*/
851  return result;
852}
853
854/*2
855*dehomogenized the generators of the ideal id1 with the leading
856*monomial of p replaced by n
857*/
858ideal idDehomogen (ideal id1,poly p,number n)
859{
860  int i;
861  ideal result;
862
863  if (idIs0(id1))
864  {
865    return idInit(1,id1->rank);
866  }
867  result=idInit(IDELEMS(id1),id1->rank);
868  for (i=0; i<IDELEMS(id1); i++)
869  {
870    result->m[i] = pDehomogen(id1->m[i],p,n);
871  }
872  return result;
873}
874
875/*2
876* verschiebt die Indizees der Modulerzeugenden um i
877*/
878void pShift (poly * p,int i)
879{
880  poly qp1 = *p,qp2 = *p;/*working pointers*/
881  int     j = pMaxComp(*p),k = pMinComp(*p);
882
883  if (j+i < 0) return ;
884  while (qp1 != NULL)
885  {
886    if ((pGetComp(qp1)+i > 0) || ((j == -i) && (j == k)))
887    {
888      pSetComp(qp1,pGetComp(qp1)+i);
889      pSetmComp(qp1);
890      qp2 = qp1;
891      pIter(qp1);
892    }
893    else
894    {
895      if (qp2 == *p)
896      {
897        pIter(*p);
898        pDeleteLm(&qp2);
899        qp2 = *p;
900        qp1 = *p;
901      }
902      else
903      {
904        qp2->next = qp1->next;
905        pDeleteLm(&qp1);
906        qp1 = qp2->next;
907      }
908    }
909  }
910}
911
912/*2
913*initialized a field with r numbers between beg and end for the
914*procedure idNextChoise
915*/
916void idInitChoise (int r,int beg,int end,BOOLEAN  *endch,int * choise)
917{
918  /*returns the first choise of r numbers between beg and end*/
919  int i;
920  for (i=0; i<r; i++)
921  {
922    choise[i] = 0;
923  }
924  if (r <= end-beg+1)
925    for (i=0; i<r; i++)
926    {
927      choise[i] = beg+i;
928    }
929  if (r > end-beg+1)
930    *endch = TRUE;
931  else
932    *endch = FALSE;
933}
934
935/*2
936*returns the next choise of r numbers between beg and end
937*/
938void idGetNextChoise (int r,int end,BOOLEAN  *endch,int * choise)
939{
940  int i = r-1,j;
941  while ((i >= 0) && (choise[i] == end))
942  {
943    i--;
944    end--;
945  }
946  if (i == -1)
947    *endch = TRUE;
948  else
949  {
950    choise[i]++;
951    for (j=i+1; j<r; j++)
952    {
953      choise[j] = choise[i]+j-i;
954    }
955    *endch = FALSE;
956  }
957}
958
959/*2
960*takes the field choise of d numbers between beg and end, cancels the t-th
961*entree and searches for the ordinal number of that d-1 dimensional field
962* w.r.t. the algorithm of construction
963*/
964int idGetNumberOfChoise(int t, int d, int begin, int end, int * choise)
965{
966  int * localchoise,i,result=0;
967  BOOLEAN b=FALSE;
968
969  if (d<=1) return 1;
970  localchoise=(int*)omAlloc((d-1)*sizeof(int));
971  idInitChoise(d-1,begin,end,&b,localchoise);
972  while (!b)
973  {
974    result++;
975    i = 0;
976    while ((i<t) && (localchoise[i]==choise[i])) i++;
977    if (i>=t)
978    {
979      i = t+1;
980      while ((i<d) && (localchoise[i-1]==choise[i])) i++;
981      if (i>=d)
982      {
983        omFreeSize((ADDRESS)localchoise,(d-1)*sizeof(int));
984        return result;
985      }
986    }
987    idGetNextChoise(d-1,end,&b,localchoise);
988  }
989  omFreeSize((ADDRESS)localchoise,(d-1)*sizeof(int));
990  return 0;
991}
992
993/*2
994*computes the binomial coefficient
995*/
996int binom (int n,int r)
997{
998  int i,result;
999
1000  if (r==0) return 1;
1001  if (n-r<r) return binom(n,n-r);
1002  result = n-r+1;
1003  for (i=2;i<=r;i++)
1004  {
1005    result *= n-r+i;
1006    if (result<0)
1007    {
1008      WarnS("overflow in binomials");
1009      return 0;
1010    }
1011    result /= i;
1012  }
1013  return result;
1014}
1015
1016/*2
1017*the free module of rank i
1018*/
1019ideal idFreeModule (int i)
1020{
1021  int j;
1022  ideal h;
1023
1024  h=idInit(i,i);
1025  for (j=0; j<i; j++)
1026  {
1027    h->m[j] = pOne();
1028    pSetComp(h->m[j],j+1);
1029    pSetmComp(h->m[j]);
1030  }
1031  return h;
1032}
1033
1034/*2
1035* h3 := h1 intersect h2
1036*/
1037ideal idSect (ideal h1,ideal h2)
1038{
1039  int i,j,k,length;
1040  int flength = idRankFreeModule(h1);
1041  int slength = idRankFreeModule(h2);
1042  int rank=si_min(flength,slength);
1043  if ((idIs0(h1)) || (idIs0(h2)))  return idInit(1,rank);
1044
1045  ideal first,second,temp,temp1,result;
1046  poly p,q;
1047
1048  if (IDELEMS(h1)<IDELEMS(h2))
1049  {
1050    first = h1;
1051    second = h2;
1052  }
1053  else
1054  {
1055    first = h2;
1056    second = h1;
1057    int t=flength; flength=slength; slength=t;
1058  }
1059  length  = si_max(flength,slength);
1060  if (length==0)
1061  {
1062    length = 1;
1063  }
1064  j = IDELEMS(first);
1065
1066  ring orig_ring=currRing;
1067  ring syz_ring=rCurrRingAssure_SyzComp();
1068  rSetSyzComp(length);
1069
1070  while ((j>0) && (first->m[j-1]==NULL)) j--;
1071  temp = idInit(j /*IDELEMS(first)*/+IDELEMS(second),length+j);
1072  k = 0;
1073  for (i=0;i<j;i++)
1074  {
1075    if (first->m[i]!=NULL)
1076    {
1077      if (syz_ring==orig_ring)
1078        temp->m[k] = pCopy(first->m[i]);
1079      else
1080        temp->m[k] = prCopyR(first->m[i], orig_ring);
1081      q = pOne();
1082      pSetComp(q,i+1+length);
1083      pSetmComp(q);
1084      if (flength==0) pShift(&(temp->m[k]),1);
1085      p = temp->m[k];
1086      while (pNext(p)!=NULL) pIter(p);
1087      pNext(p) = q;
1088      k++;
1089    }
1090  }
1091  for (i=0;i<IDELEMS(second);i++)
1092  {
1093    if (second->m[i]!=NULL)
1094    {
1095      if (syz_ring==orig_ring)
1096        temp->m[k] = pCopy(second->m[i]);
1097      else
1098        temp->m[k] = prCopyR(second->m[i], orig_ring);
1099      if (slength==0) pShift(&(temp->m[k]),1);
1100      k++;
1101    }
1102  }
1103  intvec *w=NULL;
1104  temp1 = kStd(temp,currQuotient,testHomog,&w,NULL,length);
1105  if (w!=NULL) delete w;
1106  idDelete(&temp);
1107
1108  if(syz_ring!=orig_ring)
1109    rChangeCurrRing(orig_ring);
1110
1111  result = idInit(IDELEMS(temp1),rank);
1112  j = 0;
1113  for (i=0;i<IDELEMS(temp1);i++)
1114  {
1115    if ((temp1->m[i]!=NULL)
1116    && (p_GetComp(temp1->m[i],syz_ring)>length))
1117    {
1118      if(syz_ring==orig_ring)
1119      {
1120        p = temp1->m[i];
1121      }
1122      else
1123      {
1124        p = prMoveR(temp1->m[i], syz_ring);
1125      }
1126      temp1->m[i]=NULL;
1127      while (p!=NULL)
1128      {
1129        q = pNext(p);
1130        pNext(p) = NULL;
1131        k = pGetComp(p)-1-length;
1132        pSetComp(p,0);
1133        pSetmComp(p);
1134        /* Warning! multiply only from the left! it's very important for Plural */
1135        result->m[j] = pAdd(result->m[j],pMult(p,pCopy(first->m[k])));
1136        p = q;
1137      }
1138      j++;
1139    }
1140  }
1141  if(syz_ring!=orig_ring)
1142  {
1143    rChangeCurrRing(syz_ring);
1144    idDelete(&temp1);
1145    rChangeCurrRing(orig_ring);
1146    rKill(syz_ring);
1147  }
1148  else
1149  {
1150    idDelete(&temp1);
1151  }
1152
1153  idSkipZeroes(result);
1154  if (TEST_OPT_RETURN_SB)
1155  {
1156     w=NULL;
1157     temp1=kStd(result,currQuotient,testHomog,&w);
1158     if (w!=NULL) delete w;
1159     idDelete(&result);
1160     idSkipZeroes(temp1);
1161     return temp1;
1162  }
1163  else //temp1=kInterRed(result,currQuotient);
1164    return result;
1165}
1166
1167/*2
1168* ideal/module intersection for a list of objects
1169* given as 'resolvente'
1170*/
1171ideal idMultSect(resolvente arg, int length)
1172{
1173  int i,j=0,k=0,syzComp,l,maxrk=-1,realrki;
1174  ideal bigmat,tempstd,result;
1175  poly p;
1176  int isIdeal=0;
1177  intvec * w=NULL;
1178
1179  /* find 0-ideals and max rank -----------------------------------*/
1180  for (i=0;i<length;i++)
1181  {
1182    if (!idIs0(arg[i]))
1183    {
1184      realrki=idRankFreeModule(arg[i]);
1185      k++;
1186      j += IDELEMS(arg[i]);
1187      if (realrki>maxrk) maxrk = realrki;
1188    }
1189    else
1190    {
1191      if (arg[i]!=NULL)
1192      {
1193        return idInit(1,arg[i]->rank);
1194      }
1195    }
1196  }
1197  if (maxrk == 0)
1198  {
1199    isIdeal = 1;
1200    maxrk = 1;
1201  }
1202  /* init -----------------------------------------------------------*/
1203  j += maxrk;
1204  syzComp = k*maxrk;
1205
1206  ring orig_ring=currRing;
1207  ring syz_ring=rCurrRingAssure_SyzComp();
1208  rSetSyzComp(syzComp);
1209
1210  bigmat = idInit(j,(k+1)*maxrk);
1211  /* create unit matrices ------------------------------------------*/
1212  for (i=0;i<maxrk;i++)
1213  {
1214    for (j=0;j<=k;j++)
1215    {
1216      p = pOne();
1217      pSetComp(p,i+1+j*maxrk);
1218      pSetmComp(p);
1219      bigmat->m[i] = pAdd(bigmat->m[i],p);
1220    }
1221  }
1222  /* enter given ideals ------------------------------------------*/
1223  i = maxrk;
1224  k = 0;
1225  for (j=0;j<length;j++)
1226  {
1227    if (arg[j]!=NULL)
1228    {
1229      for (l=0;l<IDELEMS(arg[j]);l++)
1230      {
1231        if (arg[j]->m[l]!=NULL)
1232        {
1233          if (syz_ring==orig_ring)
1234            bigmat->m[i] = pCopy(arg[j]->m[l]);
1235          else
1236            bigmat->m[i] = prCopyR(arg[j]->m[l], orig_ring);
1237          pShift(&(bigmat->m[i]),k*maxrk+isIdeal);
1238          i++;
1239        }
1240      }
1241      k++;
1242    }
1243  }
1244  /* std computation --------------------------------------------*/
1245  tempstd = kStd(bigmat,currQuotient,testHomog,&w,NULL,syzComp);
1246  if (w!=NULL) delete w;
1247  idDelete(&bigmat);
1248
1249  if(syz_ring!=orig_ring)
1250    rChangeCurrRing(orig_ring);
1251
1252  /* interprete result ----------------------------------------*/
1253  result = idInit(IDELEMS(tempstd),maxrk);
1254  k = 0;
1255  for (j=0;j<IDELEMS(tempstd);j++)
1256  {
1257    if ((tempstd->m[j]!=NULL) && (p_GetComp(tempstd->m[j],syz_ring)>syzComp))
1258    {
1259      if (syz_ring==orig_ring)
1260        p = pCopy(tempstd->m[j]);
1261      else
1262        p = prCopyR(tempstd->m[j], syz_ring);
1263      pShift(&p,-syzComp-isIdeal);
1264      result->m[k] = p;
1265      k++;
1266    }
1267  }
1268  /* clean up ----------------------------------------------------*/
1269  if(syz_ring!=orig_ring)
1270    rChangeCurrRing(syz_ring);
1271  idDelete(&tempstd);
1272  if(syz_ring!=orig_ring)
1273  {
1274    rChangeCurrRing(orig_ring);
1275    rKill(syz_ring);
1276  }
1277  idSkipZeroes(result);
1278  return result;
1279}
1280
1281/*2
1282*computes syzygies of h1,
1283*if quot != NULL it computes in the quotient ring modulo "quot"
1284*works always in a ring with ringorder_s
1285*/
1286static ideal idPrepare (ideal  h1, tHomog h, int syzcomp, intvec **w)
1287{
1288  ideal   h2, h3;
1289  int     i;
1290  int     j,jj=0,k;
1291  poly    p,q;
1292
1293  if (idIs0(h1)) return NULL;
1294  k = idRankFreeModule(h1);
1295  h2=idCopy(h1);
1296  i = IDELEMS(h2)-1;
1297  if (k == 0)
1298  {
1299    for (j=0; j<=i; j++) pShift(&(h2->m[j]),1);
1300    k = 1;
1301  }
1302  if (syzcomp<k)
1303  {
1304    Warn("syzcomp too low, should be %d instead of %d",k,syzcomp);
1305    syzcomp = k;
1306    rSetSyzComp(k);
1307  }
1308  h2->rank = syzcomp+i+1;
1309
1310#if MYTEST
1311#ifdef RDEBUG
1312  Print("Prepare::h2: ");
1313  idPrint(h2);
1314#endif 
1315#endif
1316 
1317  for (j=0; j<=i; j++)
1318  {
1319    p = h2->m[j];
1320    q = pOne();
1321    pSetComp(q,syzcomp+1+j);
1322    pSetmComp(q);
1323    if (p!=NULL)
1324    {
1325      while (pNext(p)) pIter(p);
1326      p->next = q;
1327    }
1328    else
1329      h2->m[j]=q;
1330  }
1331
1332#ifdef PDEBUG
1333  for(j=0;j<IDELEMS(h2);j++) pTest(h2->m[j]);
1334
1335#if MYTEST
1336#ifdef RDEBUG
1337  Print("Prepare::Input: ");
1338  idPrint(h2);
1339
1340  Print("Prepare::currQuotient: ");
1341  idPrint(currQuotient);
1342#endif 
1343#endif
1344 
1345#endif
1346
1347 
1348  h3 = kStd(h2,currQuotient,h,w,NULL,syzcomp);
1349  idDelete(&h2);
1350  return h3;
1351}
1352
1353/*2
1354* compute the syzygies of h1 in R/quot,
1355* weights of components are in w
1356* if setRegularity, return the regularity in deg
1357* do not change h1,  w
1358*/
1359ideal idSyzygies (ideal  h1, tHomog h,intvec **w, BOOLEAN setSyzComp,
1360                  BOOLEAN setRegularity, int *deg)
1361{
1362  ideal s_h1;
1363  poly  p;
1364  int   j, k, length=0,reg;
1365  BOOLEAN isMonomial=TRUE;
1366  int ii, idElemens_h1;
1367
1368  idElemens_h1=IDELEMS(h1);
1369#ifdef PDEBUG
1370  for(ii=0;ii<idElemens_h1 /*IDELEMS(h1)*/;ii++) pTest(h1->m[ii]);
1371#endif
1372  if (idIs0(h1))
1373  {
1374    ideal result=idFreeModule(idElemens_h1/*IDELEMS(h1)*/);
1375    int curr_syz_limit=rGetCurrSyzLimit();
1376    if (curr_syz_limit>0)
1377    for (ii=0;ii<idElemens_h1/*IDELEMS(h1)*/;ii++)
1378    {
1379      if (h1->m[ii]!=NULL)
1380        pShift(&h1->m[ii],curr_syz_limit);
1381    }
1382    return result;
1383  }
1384  int slength=(int)idRankFreeModule(h1);
1385  k=si_max(1,slength /*idRankFreeModule(h1)*/);
1386
1387  assume(currRing != NULL);
1388  ring orig_ring=currRing;
1389  ring syz_ring=rCurrRingAssure_SyzComp();
1390
1391  if (setSyzComp)
1392    rSetSyzComp(k);
1393
1394  if (orig_ring != syz_ring)
1395  {
1396    s_h1=idrCopyR_NoSort(h1,orig_ring);
1397  }
1398  else
1399  {
1400    s_h1 = h1;
1401  }
1402
1403  ideal s_h3=idPrepare(s_h1,h,k,w);
1404
1405  if (s_h3==NULL)
1406  {
1407    return idFreeModule( idElemens_h1 /*IDELEMS(h1)*/);
1408  }
1409
1410  if (orig_ring != syz_ring)
1411  {
1412    idDelete(&s_h1);
1413    for (j=0; j<IDELEMS(s_h3); j++)
1414    {
1415      if (s_h3->m[j] != NULL)
1416      {
1417        if (p_MinComp(s_h3->m[j],syz_ring) > k)
1418          pShift(&s_h3->m[j], -k);
1419        else
1420          pDelete(&s_h3->m[j]);
1421      }
1422    }
1423    idSkipZeroes(s_h3);
1424    s_h3->rank -= k;
1425    rChangeCurrRing(orig_ring);
1426    s_h3 = idrMoveR_NoSort(s_h3, syz_ring);
1427    rKill(syz_ring);
1428    idTest(s_h3);
1429    return s_h3;
1430  }
1431
1432  ideal e = idInit(IDELEMS(s_h3), s_h3->rank);
1433
1434  for (j=IDELEMS(s_h3)-1; j>=0; j--)
1435  {
1436    if (s_h3->m[j] != NULL)
1437    {
1438      if (p_MinComp(s_h3->m[j],syz_ring) <= k)
1439      {
1440        e->m[j] = s_h3->m[j];
1441        isMonomial=isMonomial && (pNext(s_h3->m[j])==NULL);
1442        pDelete(&pNext(s_h3->m[j]));
1443        s_h3->m[j] = NULL;
1444      }
1445    }
1446  }
1447
1448  idSkipZeroes(s_h3);
1449  idSkipZeroes(e);
1450
1451  if ((deg != NULL)
1452  && (!isMonomial)
1453  && (!TEST_OPT_NOTREGULARITY)
1454  && (setRegularity)
1455  && (h==isHomog)
1456  && (!rIsPluralRing(currRing))
1457  )
1458  {
1459    ring dp_C_ring = rCurrRingAssure_dp_C();
1460    if (dp_C_ring != syz_ring)
1461      e = idrMoveR_NoSort(e, syz_ring);
1462    resolvente res = sySchreyerResolvente(e,-1,&length,TRUE, TRUE);
1463    intvec * dummy = syBetti(res,length,&reg, *w);
1464    *deg = reg+2;
1465    delete dummy;
1466    for (j=0;j<length;j++)
1467    {
1468      if (res[j]!=NULL) idDelete(&(res[j]));
1469    }
1470    omFreeSize((ADDRESS)res,length*sizeof(ideal));
1471    idDelete(&e);
1472    if (dp_C_ring != syz_ring)
1473    {
1474      rChangeCurrRing(syz_ring);
1475      rKill(dp_C_ring);
1476    }
1477  }
1478  else
1479  {
1480    idDelete(&e);
1481  }
1482  idTest(s_h3);
1483  if (currQuotient != NULL)
1484  {
1485    ideal ts_h3=kStd(s_h3,currQuotient,h,w);
1486    idDelete(&s_h3);
1487    s_h3 = ts_h3;
1488  }
1489  return s_h3;
1490}
1491
1492/*2
1493*/
1494ideal idXXX (ideal  h1, int k)
1495{
1496  ideal s_h1;
1497  int j;
1498  intvec *w=NULL;
1499
1500  assume(currRing != NULL);
1501  ring orig_ring=currRing;
1502  ring syz_ring=rCurrRingAssure_SyzComp();
1503
1504  rSetSyzComp(k);
1505
1506  if (orig_ring != syz_ring)
1507  {
1508    s_h1=idrCopyR_NoSort(h1,orig_ring);
1509  }
1510  else
1511  {
1512    s_h1 = h1;
1513  }
1514
1515  ideal s_h3=kStd(s_h1,NULL,testHomog,&w,NULL,k);
1516
1517  if (s_h3==NULL)
1518  {
1519    return idFreeModule(IDELEMS(h1));
1520  }
1521
1522  if (orig_ring != syz_ring)
1523  {
1524    idDelete(&s_h1);
1525    idSkipZeroes(s_h3);
1526    rChangeCurrRing(orig_ring);
1527    s_h3 = idrMoveR_NoSort(s_h3, syz_ring);
1528    rKill(syz_ring);
1529    idTest(s_h3);
1530    return s_h3;
1531  }
1532
1533  idSkipZeroes(s_h3);
1534  idTest(s_h3);
1535  return s_h3;
1536}
1537
1538/*
1539*computes a standard basis for h1 and stores the transformation matrix
1540* in ma
1541*/
1542ideal idLiftStd (ideal  h1, matrix* ma, tHomog h)
1543{
1544  int   i, j, k, t, inputIsIdeal=idRankFreeModule(h1);
1545  poly  p=NULL, q, qq;
1546  intvec *w=NULL;
1547
1548  idDelete((ideal*)ma);
1549  *ma=mpNew(1,0);
1550  if (idIs0(h1))
1551    return idInit(1,h1->rank);
1552
1553  BITSET save_verbose=verbose;
1554
1555  k=si_max(1,(int)idRankFreeModule(h1));
1556
1557  if (k==1) verbose |=Sy_bit(V_IDLIFT);
1558
1559  ring orig_ring = currRing;
1560  ring syz_ring = rCurrRingAssure_SyzComp();
1561  rSetSyzComp(k);
1562
1563 
1564#if MYTEST
1565#ifdef RDEBUG
1566  rWrite(syz_ring);
1567  rDebugPrint(syz_ring);
1568#endif 
1569#endif
1570 
1571  ideal s_h1=h1;
1572
1573  if (orig_ring != syz_ring)
1574    s_h1 = idrCopyR_NoSort(h1,orig_ring);
1575  else
1576    s_h1 = h1;
1577
1578#if MYTEST
1579#ifdef RDEBUG
1580  Print("Input: ");
1581  idPrint(s_h1);
1582#endif 
1583#endif
1584 
1585
1586  ideal s_h3=idPrepare(s_h1,h,k,&w);
1587
1588#if MYTEST
1589#ifdef RDEBUG
1590  Print("Prepare: ");
1591  idPrint(s_h3);
1592#endif 
1593#endif
1594
1595  ideal s_h2 = idInit(IDELEMS(s_h3), s_h3->rank);
1596
1597#if MYTEST
1598#ifdef RDEBUG
1599  Print("Temp: ");
1600  idPrint(s_h2);
1601#endif 
1602#endif
1603 
1604  if (w!=NULL) delete w;
1605  i = 0;
1606
1607  for (j=0; j<IDELEMS(s_h3); j++)
1608  {
1609    if ((s_h3->m[j] != NULL) && (p_MinComp(s_h3->m[j],syz_ring) <= k))
1610    {
1611      i++;
1612      q = s_h3->m[j];
1613      while (pNext(q) != NULL)
1614      {
1615        if (pGetComp(pNext(q)) > k)
1616        {
1617          s_h2->m[j] = pNext(q);
1618          pNext(q) = NULL;
1619        }
1620        else
1621        {
1622          pIter(q);
1623        }
1624      }
1625      if (!inputIsIdeal) pShift(&(s_h3->m[j]), -1);
1626    }
1627    else
1628    {
1629      pDelete(&(s_h3->m[j]));
1630    }
1631  }
1632
1633  idSkipZeroes(s_h3);
1634
1635#if MYTEST
1636#ifdef RDEBUG
1637  Print("Input'': ");
1638  idPrint(s_h3);
1639#endif 
1640#endif
1641
1642  j = IDELEMS(s_h1);
1643
1644
1645#if MYTEST
1646#ifdef RDEBUG
1647  Print("Temp Result: ");
1648  idPrint(s_h2);
1649#endif 
1650#endif
1651
1652 
1653  if (syz_ring!=orig_ring)
1654  {
1655    idDelete(&s_h1);
1656    rChangeCurrRing(orig_ring);
1657  }
1658
1659  idDelete((ideal*)ma);
1660  *ma = mpNew(j,i);
1661
1662  i = 1;
1663  for (j=0; j<IDELEMS(s_h2); j++)
1664  {
1665    if (s_h2->m[j] != NULL)
1666    {
1667      q = prMoveR( s_h2->m[j], syz_ring);
1668      s_h2->m[j] = NULL;
1669
1670      while (q != NULL)
1671      {
1672        p = q;
1673        pIter(q);
1674        pNext(p) = NULL;
1675        t=pGetComp(p);
1676        pSetComp(p,0);
1677        pSetmComp(p);
1678        MATELEM(*ma,t-k,i) = pAdd(MATELEM(*ma,t-k,i),p);
1679      }
1680      i++;
1681    }
1682  }
1683  idDelete(&s_h2);
1684
1685  for (i=0; i<IDELEMS(s_h3); i++)
1686  {
1687    s_h3->m[i] = prMoveR_NoSort(s_h3->m[i], syz_ring);
1688  }
1689
1690#if MYTEST
1691#ifdef RDEBUG
1692  Print("Output STD Ideal: ");
1693  idPrint(s_h3);
1694
1695  Print("Output Matrix: ");
1696  iiWriteMatrix(*ma, "ma", 2, 4);
1697#endif 
1698#endif
1699 
1700
1701  if (syz_ring!=orig_ring) rKill(syz_ring);
1702  verbose = save_verbose;
1703  return s_h3;
1704}
1705
1706static void idPrepareStd(ideal s_temp, int k)
1707{
1708  int j,rk=idRankFreeModule(s_temp);
1709  poly p,q;
1710
1711  if (rk == 0)
1712  {
1713    for (j=0; j<IDELEMS(s_temp); j++)
1714    {
1715      if (s_temp->m[j]!=NULL) pSetCompP(s_temp->m[j],1);
1716    }
1717    k = si_max(k,1);
1718  }
1719  for (j=0; j<IDELEMS(s_temp); j++)
1720  {
1721    if (s_temp->m[j]!=NULL)
1722    {
1723      p = s_temp->m[j];
1724      q = pOne();
1725      //pGetCoeff(q)=nNeg(pGetCoeff(q));   //set q to -1
1726      pSetComp(q,k+1+j);
1727      pSetmComp(q);
1728      while (pNext(p)) pIter(p);
1729      pNext(p) = q;
1730    }
1731  }
1732}
1733
1734/*2
1735*computes a representation of the generators of submod with respect to those
1736* of mod
1737*/
1738
1739ideal idLift(ideal mod, ideal submod,ideal *rest, BOOLEAN goodShape,
1740             BOOLEAN isSB, BOOLEAN divide, matrix *unit)
1741{
1742  int lsmod =idRankFreeModule(submod), i, j, k;
1743  int comps_to_add=0;
1744  poly p;
1745
1746  if (idIs0(submod))
1747  {
1748    if (unit!=NULL)
1749    {
1750      *unit=mpNew(1,1);
1751      MATELEM(*unit,1,1)=pOne();
1752    }
1753    if (rest!=NULL)
1754    {
1755      *rest=idInit(1,mod->rank);
1756    }
1757    return idInit(1,mod->rank);
1758  }
1759  if (idIs0(mod))
1760  {
1761    if (unit!=NULL)
1762    {
1763      i=IDELEMS(submod);
1764      *unit=mpNew(i,i);
1765      for (j=i;j>0;j--)
1766      {
1767        MATELEM(*unit,j,j)=pOne();
1768      }
1769    }
1770    if (rest!=NULL)
1771    {
1772      *rest=idCopy(submod);
1773    }
1774    return idInit(1,mod->rank);
1775  }
1776  if (unit!=NULL)
1777  {
1778    comps_to_add = IDELEMS(submod);
1779    while ((comps_to_add>0) && (submod->m[comps_to_add-1]==NULL))
1780      comps_to_add--;
1781  }
1782  k=idRankFreeModule(mod);
1783  if  ((k!=0) && (lsmod==0)) lsmod=1;
1784  k=si_max(k,1);
1785
1786  ring orig_ring=currRing;
1787  ring syz_ring=rCurrRingAssure_SyzComp();
1788  rSetSyzComp(k);
1789
1790  ideal s_mod, s_temp;
1791  if (orig_ring != syz_ring)
1792  {
1793    s_mod = idrCopyR_NoSort(mod,orig_ring);
1794    s_temp = idrCopyR_NoSort(submod,orig_ring);
1795  }
1796  else
1797  {
1798    s_mod = mod;
1799    s_temp = idCopy(submod);
1800  }
1801  ideal s_h3;
1802  if (isSB)
1803  {
1804    s_h3 = idCopy(s_mod);
1805    idPrepareStd(s_h3, k+comps_to_add);
1806  }
1807  else
1808  {
1809    s_h3 = idPrepare(s_mod,(tHomog)FALSE,k+comps_to_add,NULL);
1810  }
1811  if (!goodShape)
1812  {
1813    for (j=0;j<IDELEMS(s_h3);j++)
1814    {
1815      if ((s_h3->m[j] != NULL) && (pMinComp(s_h3->m[j]) > k))
1816        pDelete(&(s_h3->m[j]));
1817    }
1818  }
1819  idSkipZeroes(s_h3);
1820  if (lsmod==0)
1821  {
1822    for (j=IDELEMS(s_temp);j>0;j--)
1823    {
1824      if (s_temp->m[j-1]!=NULL)
1825        pShift(&(s_temp->m[j-1]),1);
1826    }
1827  }
1828  if (unit!=NULL)
1829  {
1830    for(j = 0;j<comps_to_add;j++)
1831    {
1832      p = s_temp->m[j];
1833      if (p!=NULL)
1834      {
1835        while (pNext(p)!=NULL) pIter(p);
1836        pNext(p) = pOne();
1837        pIter(p);
1838        pSetComp(p,1+j+k);
1839        pSetmComp(p);
1840        p = pNeg(p);
1841      }
1842    }
1843  }
1844  ideal s_result = kNF(s_h3,currQuotient,s_temp,k);
1845  s_result->rank = s_h3->rank;
1846  ideal s_rest = idInit(IDELEMS(s_result),k);
1847  idDelete(&s_h3);
1848  idDelete(&s_temp);
1849
1850  for (j=0;j<IDELEMS(s_result);j++)
1851  {
1852    if (s_result->m[j]!=NULL)
1853    {
1854      if (pGetComp(s_result->m[j])<=k)
1855      {
1856        if (!divide)
1857        {
1858          if (isSB)
1859          {
1860            WarnS("first module not a standardbasis\n"
1861              "// ** or second not a proper submodule");
1862          }
1863          else
1864            WerrorS("2nd module does not lie in the first");
1865          idDelete(&s_result);
1866          idDelete(&s_rest);
1867          s_result=idInit(IDELEMS(submod),submod->rank);
1868          break;
1869        }
1870        else
1871        {
1872          p = s_rest->m[j] = s_result->m[j];
1873          while ((pNext(p)!=NULL) && (pGetComp(pNext(p))<=k)) pIter(p);
1874          s_result->m[j] = pNext(p);
1875          pNext(p) = NULL;
1876        }
1877      }
1878      pShift(&(s_result->m[j]),-k);
1879      pNeg(s_result->m[j]);
1880    }
1881  }
1882  if ((lsmod==0) && (!idIs0(s_rest)))
1883  {
1884    for (j=IDELEMS(s_rest);j>0;j--)
1885    {
1886      if (s_rest->m[j-1]!=NULL)
1887      {
1888        pShift(&(s_rest->m[j-1]),-1);
1889        s_rest->m[j-1] = s_rest->m[j-1];
1890      }
1891    }
1892  }
1893  if(syz_ring!=orig_ring)
1894  {
1895    idDelete(&s_mod);
1896    rChangeCurrRing(orig_ring);
1897    s_result = idrMoveR_NoSort(s_result, syz_ring);
1898    s_rest = idrMoveR_NoSort(s_rest, syz_ring);
1899    rKill(syz_ring);
1900  }
1901  if (rest!=NULL)
1902    *rest = s_rest;
1903  else
1904    idDelete(&s_rest);
1905//idPrint(s_result);
1906  if (unit!=NULL)
1907  {
1908    *unit=mpNew(comps_to_add,comps_to_add);
1909    int i;
1910    for(i=0;i<IDELEMS(s_result);i++)
1911    {
1912      poly p=s_result->m[i];
1913      poly q=NULL;
1914      while(p!=NULL)
1915      {
1916        if(pGetComp(p)<=comps_to_add)
1917        {
1918          pSetComp(p,0);
1919          if (q!=NULL)
1920          {
1921            pNext(q)=pNext(p);
1922          }
1923          else
1924          {
1925            pIter(s_result->m[i]);
1926          }
1927          pNext(p)=NULL;
1928          MATELEM(*unit,i+1,i+1)=pAdd(MATELEM(*unit,i+1,i+1),p);
1929          if(q!=NULL)   p=pNext(q);
1930          else          p=s_result->m[i];
1931        }
1932        else
1933        {
1934          q=p;
1935          pIter(p);
1936        }
1937      }
1938      pShift(&s_result->m[i],-comps_to_add);
1939    }
1940  }
1941  return s_result;
1942}
1943
1944/*2
1945*computes division of P by Q with remainder up to (w-weighted) degree n
1946*P, Q, and w are not changed
1947*/
1948void idLiftW(ideal P,ideal Q,int n,matrix &T, ideal &R,short *w)
1949{
1950  long N=0;
1951  int i;
1952  for(i=IDELEMS(Q)-1;i>=0;i--)
1953    if(w==NULL)
1954      N=si_max(N,pDeg(Q->m[i]));
1955    else
1956      N=si_max(N,pDegW(Q->m[i],w));
1957  N+=n;
1958
1959  T=mpNew(IDELEMS(Q),IDELEMS(P));
1960  R=idInit(IDELEMS(P),P->rank);
1961
1962  for(i=IDELEMS(P)-1;i>=0;i--)
1963  {
1964    poly p;
1965    if(w==NULL)
1966      p=ppJet(P->m[i],N);
1967    else
1968      p=ppJetW(P->m[i],N,w);
1969
1970    int j=IDELEMS(Q)-1;
1971    while(p!=NULL)
1972    {
1973      if(pDivisibleBy(Q->m[j],p))
1974      {
1975        poly p0=pDivideM(pHead(p),pHead(Q->m[j]));
1976        if(w==NULL)
1977          p=pJet(pSub(p,ppMult_mm(Q->m[j],p0)),N);
1978        else
1979          p=pJetW(pSub(p,ppMult_mm(Q->m[j],p0)),N,w);
1980        pNormalize(p);
1981        if((w==NULL)&&(pDeg(p0)>n)||(w!=NULL)&&(pDegW(p0,w)>n))
1982          pDelete(&p0);
1983        else
1984          MATELEM(T,j+1,i+1)=pAdd(MATELEM(T,j+1,i+1),p0);
1985        j=IDELEMS(Q)-1;
1986      }
1987      else
1988      {
1989        if(j==0)
1990        {
1991          poly p0=p;
1992          pIter(p);
1993          pNext(p0)=NULL;
1994          if(((w==NULL)&&(pDeg(p0)>n))
1995          ||((w!=NULL)&&(pDegW(p0,w)>n)))
1996            pDelete(&p0);
1997          else
1998            R->m[i]=pAdd(R->m[i],p0);
1999          j=IDELEMS(Q)-1;
2000        }
2001        else
2002          j--;
2003      }
2004    }
2005  }
2006}
2007
2008/*2
2009*computes the quotient of h1,h2 : internal routine for idQuot
2010*BEWARE: the returned ideals may contain incorrectly ordered polys !
2011*
2012*/
2013static ideal idInitializeQuot (ideal  h1, ideal h2, BOOLEAN h1IsStb,
2014                               BOOLEAN *addOnlyOne, int *kkmax)
2015{
2016  ideal temph1;
2017  poly     p,q = NULL;
2018  int i,l,ll,k,kkk,kmax;
2019  int j = 0;
2020  int k1 = idRankFreeModule(h1);
2021  int k2 = idRankFreeModule(h2);
2022  tHomog   hom=isNotHomog;
2023
2024  k=si_max(k1,k2);
2025  if (k==0)
2026    k = 1;
2027  if ((k2==0) && (k>1)) *addOnlyOne = FALSE;
2028
2029  intvec * weights;
2030  hom = (tHomog)idHomModule(h1,currQuotient,&weights);
2031  if (addOnlyOne && (!h1IsStb))
2032    temph1 = kStd(h1,currQuotient,hom,&weights,NULL);
2033  else
2034    temph1 = idCopy(h1);
2035  if (weights!=NULL) delete weights;
2036  idTest(temph1);
2037/*--- making a single vector from h2 ---------------------*/
2038  for (i=0; i<IDELEMS(h2); i++)
2039  {
2040    if (h2->m[i] != NULL)
2041    {
2042      p = pCopy(h2->m[i]);
2043      if (k2 == 0)
2044        pShift(&p,j*k+1);
2045      else
2046        pShift(&p,j*k);
2047      q = pAdd(q,p);
2048      j++;
2049    }
2050  }
2051  *kkmax = kmax = j*k+1;
2052/*--- adding a monomial for the result (syzygy) ----------*/
2053  p = q;
2054  while (pNext(p)!=NULL) pIter(p);
2055  pNext(p) = pOne();
2056  pIter(p);
2057  pSetComp(p,kmax);
2058  pSetmComp(p);
2059/*--- constructing the big matrix ------------------------*/
2060  ideal h4 = idInit(16,kmax+k-1);
2061  h4->m[0] = q;
2062  if (k2 == 0)
2063  {
2064    if (k > IDELEMS(h4))
2065    {
2066      pEnlargeSet(&(h4->m),IDELEMS(h4),k-IDELEMS(h4));
2067      IDELEMS(h4) = k;
2068    }
2069    for (i=1; i<k; i++)
2070    {
2071      p = pCopy_noCheck(h4->m[i-1]);
2072      pShift(&p,1);
2073      h4->m[i] = p;
2074    }
2075  }
2076
2077  kkk = IDELEMS(h4);
2078  i = IDELEMS(temph1);
2079  while ((i>0) && (temph1->m[i-1]==NULL)) i--;
2080  for (l=0; l<i; l++)
2081  {
2082    if(temph1->m[l]!=NULL)
2083    {
2084      for (ll=0; ll<j; ll++)
2085      {
2086        p = pCopy(temph1->m[l]);
2087        if (k1 == 0)
2088          pShift(&p,ll*k+1);
2089        else
2090          pShift(&p,ll*k);
2091        if (kkk >= IDELEMS(h4))
2092        {
2093          pEnlargeSet(&(h4->m),IDELEMS(h4),16);
2094          IDELEMS(h4) += 16;
2095        }
2096        h4->m[kkk] = p;
2097        kkk++;
2098      }
2099    }
2100  }
2101/*--- if h2 goes in as single vector - the h1-part is just SB ---*/
2102  if (*addOnlyOne)
2103  {
2104    p = h4->m[0];
2105    for (i=0;i<IDELEMS(h4)-1;i++)
2106    {
2107      h4->m[i] = h4->m[i+1];
2108    }
2109    h4->m[IDELEMS(h4)-1] = p;
2110    idSkipZeroes(h4);
2111    test |= Sy_bit(OPT_SB_1);
2112  }
2113  idDelete(&temph1);
2114  return h4;
2115}
2116/*2
2117*computes the quotient of h1,h2
2118*/
2119ideal idQuot (ideal  h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN resultIsIdeal)
2120{
2121  // first check for special case h1:(0)
2122  if (idIs0(h2))
2123  {
2124    ideal res;
2125    if (resultIsIdeal)
2126    {
2127      res = idInit(1,1);
2128      res->m[0] = pOne();
2129    }
2130    else
2131      res = idFreeModule(h1->rank);
2132    return res;
2133  }
2134  BITSET old_test=test;
2135  poly     p,q = NULL;
2136  int i,l,ll,k,kkk,kmax;
2137  BOOLEAN  addOnlyOne=TRUE;
2138  tHomog   hom=isNotHomog;
2139  intvec * weights1;
2140
2141  ideal s_h4 = idInitializeQuot (h1,h2,h1IsStb,&addOnlyOne,&kmax);
2142
2143  hom = (tHomog)idHomModule(s_h4,currQuotient,&weights1);
2144
2145  ring orig_ring=currRing;
2146  ring syz_ring=rCurrRingAssure_SyzComp();
2147  rSetSyzComp(kmax-1);
2148  if (orig_ring!=syz_ring)
2149  //  s_h4 = idrMoveR_NoSort(s_h4,orig_ring);
2150    s_h4 = idrMoveR(s_h4,orig_ring);
2151  idTest(s_h4);
2152  ideal s_h3;
2153  if (addOnlyOne)
2154  {
2155    s_h3 = kStd(s_h4,currQuotient,hom,&weights1,NULL,kmax-1,IDELEMS(s_h4)-1);
2156  }
2157  else
2158  {
2159    s_h3 = kStd(s_h4,currQuotient,hom,&weights1,NULL,kmax-1);
2160  }
2161  idTest(s_h3);
2162  if (weights1!=NULL) delete weights1;
2163  idDelete(&s_h4);
2164
2165
2166  for (i=0;i<IDELEMS(s_h3);i++)
2167  {
2168    if ((s_h3->m[i]!=NULL) && (pGetComp(s_h3->m[i])>=kmax))
2169    {
2170      if (resultIsIdeal)
2171        pShift(&s_h3->m[i],-kmax);
2172      else
2173        pShift(&s_h3->m[i],-kmax+1);
2174    }
2175    else
2176      pDelete(&s_h3->m[i]);
2177  }
2178  if (resultIsIdeal)
2179    s_h3->rank = 1;
2180  else
2181    s_h3->rank = h1->rank;
2182  if(syz_ring!=orig_ring)
2183  {
2184//    pDelete(&q);
2185    rChangeCurrRing(orig_ring);
2186    s_h3 = idrMoveR_NoSort(s_h3, syz_ring);
2187    rKill(syz_ring);
2188  }
2189  idSkipZeroes(s_h3);
2190  test = old_test;
2191  idTest(s_h3);
2192  return s_h3;
2193}
2194
2195/*2
2196*computes recursively all monomials of a certain degree
2197*in every step the actvar-th entry in the exponential
2198*vector is incremented and the other variables are
2199*computed by recursive calls of makemonoms
2200*if the last variable is reached, the difference to the
2201*degree is computed directly
2202*vars is the number variables
2203*actvar is the actual variable to handle
2204*deg is the degree of the monomials to compute
2205*monomdeg is the actual degree of the monomial in consideration
2206*/
2207static void makemonoms(int vars,int actvar,int deg,int monomdeg)
2208{
2209  poly p;
2210  int i=0;
2211
2212  if ((idpowerpoint == 0) && (actvar ==1))
2213  {
2214    idpower[idpowerpoint] = pOne();
2215    monomdeg = 0;
2216  }
2217  while (i<=deg)
2218  {
2219    if (deg == monomdeg)
2220    {
2221      pSetm(idpower[idpowerpoint]);
2222      idpowerpoint++;
2223      return;
2224    }
2225    if (actvar == vars)
2226    {
2227      pSetExp(idpower[idpowerpoint],actvar,deg-monomdeg);
2228      pSetm(idpower[idpowerpoint]);
2229      pTest(idpower[idpowerpoint]);
2230      idpowerpoint++;
2231      return;
2232    }
2233    else
2234    {
2235      p = pCopy(idpower[idpowerpoint]);
2236      makemonoms(vars,actvar+1,deg,monomdeg);
2237      idpower[idpowerpoint] = p;
2238    }
2239    monomdeg++;
2240    pSetExp(idpower[idpowerpoint],actvar,pGetExp(idpower[idpowerpoint],actvar)+1);
2241    pSetm(idpower[idpowerpoint]);
2242    pTest(idpower[idpowerpoint]);
2243    i++;
2244  }
2245}
2246
2247/*2
2248*returns the deg-th power of the maximal ideal of 0
2249*/
2250ideal idMaxIdeal(int deg)
2251{
2252  if (deg < 0)
2253  {
2254    WarnS("maxideal: power must be non-negative");
2255  }
2256  if (deg < 1)
2257  {
2258    ideal I=idInit(1,1);
2259    I->m[0]=pOne();
2260    return I;
2261  }
2262  if (deg == 1)
2263  {
2264    return idMaxIdeal();
2265  }
2266
2267  int vars = currRing->N;
2268  int i = binom(vars+deg-1,deg);
2269  if (i<=0) return idInit(1,1);
2270  ideal id=idInit(i,1);
2271  idpower = id->m;
2272  idpowerpoint = 0;
2273  makemonoms(vars,1,deg,0);
2274  idpower = NULL;
2275  idpowerpoint = 0;
2276  return id;
2277}
2278
2279/*2
2280*computes recursively all generators of a certain degree
2281*of the ideal "givenideal"
2282*elms is the number elements in the given ideal
2283*actelm is the actual element to handle
2284*deg is the degree of the power to compute
2285*gendeg is the actual degree of the generator in consideration
2286*/
2287static void makepotence(int elms,int actelm,int deg,int gendeg)
2288{
2289  poly p;
2290  int i=0;
2291
2292  if ((idpowerpoint == 0) && (actelm ==1))
2293  {
2294    idpower[idpowerpoint] = pOne();
2295    gendeg = 0;
2296  }
2297  while (i<=deg)
2298  {
2299    if (deg == gendeg)
2300    {
2301      idpowerpoint++;
2302      return;
2303    }
2304    if (actelm == elms)
2305    {
2306      p=pPower(pCopy(givenideal[actelm-1]),deg-gendeg);
2307      idpower[idpowerpoint]=pMult(idpower[idpowerpoint],p);
2308      idpowerpoint++;
2309      return;
2310    }
2311    else
2312    {
2313      p = pCopy(idpower[idpowerpoint]);
2314      makepotence(elms,actelm+1,deg,gendeg);
2315      idpower[idpowerpoint] = p;
2316    }
2317    gendeg++;
2318    idpower[idpowerpoint]=pMult(idpower[idpowerpoint],pCopy(givenideal[actelm-1]));
2319    i++;
2320  }
2321}
2322
2323/*2
2324*returns the deg-th power of the ideal gid
2325*/
2326//ideal idPower(ideal gid,int deg)
2327//{
2328//  int i;
2329//  ideal id;
2330//
2331//  if (deg < 1) deg = 1;
2332//  i = binom(IDELEMS(gid)+deg-1,deg);
2333//  id=idInit(i,1);
2334//  idpower = id->m;
2335//  givenideal = gid->m;
2336//  idpowerpoint = 0;
2337//  makepotence(IDELEMS(gid),1,deg,0);
2338//  idpower = NULL;
2339//  givenideal = NULL;
2340//  idpowerpoint = 0;
2341//  return id;
2342//}
2343static void idNextPotence(ideal given, ideal result,
2344  int begin, int end, int deg, int restdeg, poly ap)
2345{
2346  poly p;
2347  int i;
2348
2349  p = pPower(pCopy(given->m[begin]),restdeg);
2350  i = result->nrows;
2351  result->m[i] = pMult(pCopy(ap),p);
2352//PrintS(".");
2353  (result->nrows)++;
2354  if (result->nrows >= IDELEMS(result))
2355  {
2356    pEnlargeSet(&(result->m),IDELEMS(result),16);
2357    IDELEMS(result) += 16;
2358  }
2359  if (begin == end) return;
2360  for (i=restdeg-1;i>0;i--)
2361  {
2362    p = pPower(pCopy(given->m[begin]),i);
2363    p = pMult(pCopy(ap),p);
2364    idNextPotence(given, result, begin+1, end, deg, restdeg-i, p);
2365    pDelete(&p);
2366  }
2367  idNextPotence(given, result, begin+1, end, deg, restdeg, ap);
2368}
2369
2370ideal idPower(ideal given,int exp)
2371{
2372  ideal result,temp;
2373  poly p1;
2374  int i;
2375
2376  if (idIs0(given)) return idInit(1,1);
2377  temp = idCopy(given);
2378  idSkipZeroes(temp);
2379  i = binom(IDELEMS(temp)+exp-1,exp);
2380  result = idInit(i,1);
2381  result->nrows = 0;
2382//Print("ideal contains %d elements\n",i);
2383  p1=pOne();
2384  idNextPotence(temp,result,0,IDELEMS(temp)-1,exp,exp,p1);
2385  pDelete(&p1);
2386  idDelete(&temp);
2387  result->nrows = 1;
2388  idDelEquals(result);
2389  idSkipZeroes(result);
2390  return result;
2391}
2392
2393/*2
2394* eliminate delVar (product of vars) in h1
2395*/
2396ideal idElimination (ideal h1,poly delVar,intvec *hilb)
2397{
2398  int    i,j=0,k,l;
2399  ideal  h,hh, h3;
2400  int    *ord,*block0,*block1;
2401  int    ordersize=2;
2402  int    **wv;
2403  tHomog hom;
2404  intvec * w;
2405  ring tmpR;
2406  ring origR = currRing;
2407
2408  if (delVar==NULL)
2409  {
2410    return idCopy(h1);
2411  }
2412  if (currQuotient!=NULL)
2413  {
2414    WerrorS("cannot eliminate in a qring");
2415    return idCopy(h1);
2416  }
2417  if (idIs0(h1)) return idInit(1,h1->rank);
2418#ifdef HAVE_PLURAL
2419  if (rIsPluralRing(origR))
2420    /* in the NC case, we have to check the admissibility of */
2421    /* the subalgebra to be intersected with */
2422  {
2423    if ((ncRingType(origR) != nc_skew) && (ncRingType(origR) != nc_exterior)) /* in (quasi)-commutative algebras every subalgebra is admissible */
2424    {
2425      if (nc_CheckSubalgebra(delVar,origR))
2426      {
2427        WerrorS("no elimination is possible: subalgebra is not admissible");
2428        return idCopy(h1);
2429      }
2430    }
2431  }
2432#endif
2433  hom=(tHomog)idHomModule(h1,NULL,&w); //sets w to weight vector or NULL
2434  h3=idInit(16,h1->rank);
2435  for (k=0;; k++)
2436  {
2437    if (origR->order[k]!=0) ordersize++;
2438    else break;
2439  }
2440  ord=(int*)omAlloc0(ordersize*sizeof(int));
2441  block0=(int*)omAlloc0(ordersize*sizeof(int));
2442  block1=(int*)omAlloc0(ordersize*sizeof(int));
2443  wv=(int**) omAlloc0(ordersize*sizeof(int**));
2444  if (rIsPluralRing(origR)) // we have too keep the odering: it may be needed
2445                            // for G-algebra
2446  {
2447    for (k=0;k<ordersize-1; k++)
2448    {
2449      block0[k+1] = origR->block0[k];
2450      block1[k+1] = origR->block1[k];
2451      ord[k+1] = origR->order[k];
2452      if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
2453    }
2454  }
2455  else
2456  {
2457    block0[1] = 1;
2458    block1[1] = pVariables;
2459    if (origR->OrdSgn==1) ord[1] = ringorder_wp;
2460    else                  ord[1] = ringorder_ws;
2461    wv[1]=(int*)omAlloc0(pVariables*sizeof(int));
2462    double wNsqr = (double)2.0 / (double)pVariables;
2463    wFunctional = wFunctionalBuch;
2464    int  *x= (int * )omAlloc(2 * (pVariables + 1) * sizeof(int));
2465    int sl=IDELEMS(h1) - 1;
2466    wCall(h1->m, sl, x, wNsqr);
2467    for (sl = pVariables; sl!=0; sl--)
2468      wv[1][sl-1] = x[sl + pVariables + 1]; 
2469    omFreeSize((ADDRESS)x, 2 * (pVariables + 1) * sizeof(int));
2470
2471#if 0
2472    for (k=0;k<ordersize-1; k++)
2473    {
2474      if ( (origR->order[k]==ringorder_c)
2475      || (origR->order[k]==ringorder_C))
2476      {
2477        ord[2]=origR->order[k];
2478        break;
2479      }
2480    }
2481#else
2482    ord[2]=ringorder_C;
2483#endif
2484    ord[3]=0;
2485  }
2486  block0[0] = 1;
2487  block1[0] = rVar(origR);
2488  wv[0]=(int*)omAlloc((rVar(origR) + 1)*sizeof(int));
2489  memset(wv[0],0,(rVar(origR) + 1)*sizeof(int));
2490  for (j=0;j<rVar(origR);j++)
2491    if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
2492  // use this special ordering: like ringorder_a, except that pFDeg, pWeights
2493  // ignore it
2494  ord[0] = ringorder_aa;
2495
2496  // fill in tmp ring to get back the data later on
2497  tmpR  = rCopy0(origR,FALSE,FALSE); // qring==NULL
2498  //rUnComplete(tmpR);
2499  tmpR->order = ord;
2500  tmpR->block0 = block0;
2501  tmpR->block1 = block1;
2502  tmpR->wvhdl = wv;
2503  tmpR->p_Procs=NULL;
2504
2505  rComplete(tmpR, 1);
2506
2507#ifdef HAVE_PLURAL
2508  /* update nc structure on tmpR */
2509  if (rIsPluralRing(origR))
2510  {
2511    if ( nc_rComplete(origR, tmpR, false) ) // no quotient ideal!
2512    {
2513      Werror("no elimination is possible: ordering condition is violated");
2514      // cleanup
2515      rDelete(tmpR);
2516      if (w!=NULL)
2517        delete w;
2518      return idCopy(h1);
2519    }
2520  }
2521#endif
2522  // change into the new ring
2523  //pChangeRing(pVariables,currRing->OrdSgn,ord,block0,block1,wv);
2524  rChangeCurrRing(tmpR);
2525
2526  //h = idInit(IDELEMS(h1),h1->rank);
2527  // fetch data from the old ring
2528  //for (k=0;k<IDELEMS(h1);k++) h->m[k] = prCopyR( h1->m[k], origR);
2529  h=idrCopyR(h1,origR,currRing);
2530  // compute kStd
2531#if 1
2532  //rWrite(tmpR);PrintLn();
2533  BITSET save=test;
2534  //test |=1;
2535  //Print("h: %d gen, rk=%d\n",IDELEMS(h),h->rank);
2536  //extern char * showOption();
2537  //Print("%s\n",showOption());
2538  hh = kStd(h,NULL,hom,&w,hilb);
2539  test=save;
2540  idDelete(&h);
2541#else
2542  extern ideal kGroebner(ideal F, ideal Q);
2543  hh=kGroebner(h,NULL);
2544#endif
2545  // go back to the original ring
2546  rChangeCurrRing(origR);
2547  i = IDELEMS(hh)-1;
2548  while ((i >= 0) && (hh->m[i] == NULL)) i--;
2549  j = -1;
2550  // fetch data from temp ring
2551  for (k=0; k<=i; k++)
2552  {
2553    l=pVariables;
2554    while ((l>0) && (p_GetExp( hh->m[k],l,tmpR)*pGetExp(delVar,l)==0)) l--;
2555    if (l==0)
2556    {
2557      j++;
2558      if (j >= IDELEMS(h3))
2559      {
2560        pEnlargeSet(&(h3->m),IDELEMS(h3),16);
2561        IDELEMS(h3) += 16;
2562      }
2563      h3->m[j] = prMoveR( hh->m[k], tmpR);
2564      hh->m[k] = NULL;
2565    }
2566  }
2567  id_Delete(&hh, tmpR);
2568  idSkipZeroes(h3);
2569  rDelete(tmpR);
2570  if (w!=NULL)
2571    delete w;
2572  return h3;
2573}
2574
2575/*2
2576* compute the which-th ar-minor of the matrix a
2577*/
2578poly idMinor(matrix a, int ar, unsigned long which, ideal R)
2579{
2580  int     i,j,k,size;
2581  unsigned long curr;
2582  int *rowchoise,*colchoise;
2583  BOOLEAN rowch,colch;
2584  ideal result;
2585  matrix tmp;
2586  poly p,q;
2587
2588  i = binom(a->rows(),ar);
2589  j = binom(a->cols(),ar);
2590
2591  rowchoise=(int *)omAlloc(ar*sizeof(int));
2592  colchoise=(int *)omAlloc(ar*sizeof(int));
2593  if ((i>512) || (j>512) || (i*j >512)) size=512;
2594  else size=i*j;
2595  result=idInit(size,1);
2596  tmp=mpNew(ar,ar);
2597  k = 0; /* the index in result*/
2598  curr = 0; /* index of current minor */
2599  idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
2600  while (!rowch)
2601  {
2602    idInitChoise(ar,1,a->cols(),&colch,colchoise);
2603    while (!colch)
2604    {
2605      if (curr == which)
2606      {
2607        for (i=1; i<=ar; i++)
2608        {
2609          for (j=1; j<=ar; j++)
2610          {
2611            MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
2612          }
2613        }
2614        p = mpDetBareiss(tmp);
2615        if (p!=NULL)
2616        {
2617          if (R!=NULL)
2618          {
2619            q = p;
2620            p = kNF(R,currQuotient,q);
2621            pDelete(&q);
2622          }
2623          /*delete the matrix tmp*/
2624          for (i=1; i<=ar; i++)
2625          {
2626            for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
2627          }
2628          idDelete((ideal*)&tmp);
2629          omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
2630          omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
2631          return (p);
2632        }
2633      }
2634      curr++;
2635      idGetNextChoise(ar,a->cols(),&colch,colchoise);
2636    }
2637    idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
2638  }
2639  return (poly) 1;
2640}
2641
2642#ifdef WITH_OLD_MINOR
2643/*2
2644* compute all ar-minors of the matrix a
2645*/
2646ideal idMinors(matrix a, int ar, ideal R)
2647{
2648  int     i,j,k,size;
2649  int *rowchoise,*colchoise;
2650  BOOLEAN rowch,colch;
2651  ideal result;
2652  matrix tmp;
2653  poly p,q;
2654
2655  i = binom(a->rows(),ar);
2656  j = binom(a->cols(),ar);
2657
2658  rowchoise=(int *)omAlloc(ar*sizeof(int));
2659  colchoise=(int *)omAlloc(ar*sizeof(int));
2660  if ((i>512) || (j>512) || (i*j >512)) size=512;
2661  else size=i*j;
2662  result=idInit(size,1);
2663  tmp=mpNew(ar,ar);
2664  k = 0; /* the index in result*/
2665  idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
2666  while (!rowch)
2667  {
2668    idInitChoise(ar,1,a->cols(),&colch,colchoise);
2669    while (!colch)
2670    {
2671      for (i=1; i<=ar; i++)
2672      {
2673        for (j=1; j<=ar; j++)
2674        {
2675          MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
2676        }
2677      }
2678      p = mpDetBareiss(tmp);
2679      if (p!=NULL)
2680      {
2681        if (R!=NULL)
2682        {
2683          q = p;
2684          p = kNF(R,currQuotient,q);
2685          pDelete(&q);
2686        }
2687        if (p!=NULL)
2688        {
2689          if (k>=size)
2690          {
2691            pEnlargeSet(&result->m,size,32);
2692            size += 32;
2693          }
2694          result->m[k] = p;
2695          k++;
2696        }
2697      }
2698      idGetNextChoise(ar,a->cols(),&colch,colchoise);
2699    }
2700    idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
2701  }
2702  /*delete the matrix tmp*/
2703  for (i=1; i<=ar; i++)
2704  {
2705    for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
2706  }
2707  idDelete((ideal*)&tmp);
2708  if (k==0)
2709  {
2710    k=1;
2711    result->m[0]=NULL;
2712  }
2713  omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
2714  omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
2715  pEnlargeSet(&result->m,size,k-size);
2716  IDELEMS(result) = k;
2717  return (result);
2718}
2719#else
2720/*2
2721* compute all ar-minors of the matrix a
2722* the caller of mpRecMin
2723* the elements of the result are not in R (if R!=NULL)
2724*/
2725ideal idMinors(matrix a, int ar, ideal R)
2726{
2727  int elems=0;
2728  int r=a->nrows,c=a->ncols;
2729  int i;
2730  matrix b;
2731  ideal result,h;
2732  ring origR;
2733  sip_sring tmpR;
2734  Exponent_t bound;
2735
2736  if((ar<=0) || (ar>r) || (ar>c))
2737  {
2738    Werror("%d-th minor, matrix is %dx%d",ar,r,c);
2739    return NULL;
2740  }
2741  h = idMatrix2Module(mpCopy(a));
2742  bound = smExpBound(h,c,r,ar);
2743  idDelete(&h);
2744  smRingChange(&origR,tmpR,bound);
2745  b = mpNew(r,c);
2746  for (i=r*c-1;i>=0;i--)
2747  {
2748    if (a->m[i])
2749      b->m[i] = prCopyR(a->m[i],origR);
2750  }
2751  if (R) R = idrCopyR(R,origR);
2752  result=idInit(32,1);
2753  if(ar>1) mpRecMin(ar-1,result,elems,b,r,c,NULL,R);
2754  else mpMinorToResult(result,elems,b,r,c,R);
2755  idDelete((ideal *)&b);
2756  if (R) idDelete(&R);
2757  idSkipZeroes(result);
2758  rChangeCurrRing(origR);
2759  result = idrMoveR(result,&tmpR);
2760  smRingClean(origR,tmpR);
2761  idTest(result);
2762  return result;
2763}
2764#endif
2765
2766/*2
2767*skips all zeroes and double elements, searches also for units
2768*/
2769void idCompactify(ideal id)
2770{
2771  int i,j;
2772  BOOLEAN b=FALSE;
2773
2774  i = IDELEMS(id)-1;
2775  while ((! b) && (i>=0))
2776  {
2777    b=pIsUnit(id->m[i]);
2778    i--;
2779  }
2780  if (b)
2781  {
2782    for(i=IDELEMS(id)-1;i>=0;i--) pDelete(&id->m[i]);
2783    id->m[0]=pOne();
2784  }
2785  else
2786  {
2787    idDelMultiples(id);
2788  }
2789  idSkipZeroes(id);
2790}
2791
2792/*2
2793*returns TRUE if id1 is a submodule of id2
2794*/
2795BOOLEAN idIsSubModule(ideal id1,ideal id2)
2796{
2797  int i;
2798  poly p;
2799
2800  if (idIs0(id1)) return TRUE;
2801  for (i=0;i<IDELEMS(id1);i++)
2802  {
2803    if (id1->m[i] != NULL)
2804    {
2805      p = kNF(id2,currQuotient,id1->m[i]);
2806      if (p != NULL)
2807      {
2808        pDelete(&p);
2809        return FALSE;
2810      }
2811    }
2812  }
2813  return TRUE;
2814}
2815
2816/*2
2817* returns the ideals of initial terms
2818*/
2819ideal idHead(ideal h)
2820{
2821  ideal m = idInit(IDELEMS(h),h->rank);
2822  int i;
2823
2824  for (i=IDELEMS(h)-1;i>=0; i--)
2825  {
2826    if (h->m[i]!=NULL) m->m[i]=pHead(h->m[i]);
2827  }
2828  return m;
2829}
2830
2831ideal idHomogen(ideal h, int varnum)
2832{
2833  ideal m = idInit(IDELEMS(h),h->rank);
2834  int i;
2835
2836  for (i=IDELEMS(h)-1;i>=0; i--)
2837  {
2838    m->m[i]=pHomogen(h->m[i],varnum);
2839  }
2840  return m;
2841}
2842
2843/*------------------type conversions----------------*/
2844ideal idVec2Ideal(poly vec)
2845{
2846   ideal result=idInit(1,1);
2847   omFree((ADDRESS)result->m);
2848   result->m=NULL; // remove later
2849   pVec2Polys(vec, &(result->m), &(IDELEMS(result)));
2850   return result;
2851}
2852
2853#define NEW_STUFF
2854#ifndef NEW_STUFF
2855// converts mat to module, destroys mat
2856ideal idMatrix2Module(matrix mat)
2857{
2858  int mc=MATCOLS(mat);
2859  int mr=MATROWS(mat);
2860  ideal result = idInit(si_max(mc,1),si_max(mr,1));
2861  int i,j;
2862  poly h;
2863
2864  for(j=0;j<mc /*MATCOLS(mat)*/;j++) /* j is also index in result->m */
2865  {
2866    for (i=1;i<=mr /*MATROWS(mat)*/;i++)
2867    {
2868      h = MATELEM(mat,i,j+1);
2869      if (h!=NULL)
2870      {
2871        MATELEM(mat,i,j+1)=NULL;
2872        pSetCompP(h,i);
2873        result->m[j] = pAdd(result->m[j],h);
2874      }
2875    }
2876  }
2877  // obachman: need to clean this up
2878  idDelete((ideal*) &mat);
2879  return result;
2880}
2881#else
2882
2883#include "sbuckets.h"
2884
2885// converts mat to module, destroys mat
2886ideal idMatrix2Module(matrix mat)
2887{
2888  int mc=MATCOLS(mat);
2889  int mr=MATROWS(mat);
2890  ideal result = idInit(si_max(mc,1),si_max(mr,1));
2891  int i,j, l;
2892  poly h;
2893  poly p;
2894  sBucket_pt bucket = sBucketCreate(currRing);
2895
2896  for(j=0;j<mc /*MATCOLS(mat)*/;j++) /* j is also index in result->m */
2897  {
2898    for (i=1;i<=mr /*MATROWS(mat)*/;i++)
2899    {
2900      h = MATELEM(mat,i,j+1);
2901      if (h!=NULL)
2902      {
2903        l=pLength(h);
2904        MATELEM(mat,i,j+1)=NULL;
2905        p_SetCompP(h,i, currRing);
2906        sBucket_Merge_p(bucket, h, l);
2907      }
2908    }
2909    sBucketClearMerge(bucket, &(result->m[j]), &l);
2910  }
2911  sBucketDestroy(&bucket);
2912
2913  // obachman: need to clean this up
2914  idDelete((ideal*) &mat);
2915  return result;
2916}
2917#endif
2918
2919/*2
2920* converts a module into a matrix, destroyes the input
2921*/
2922matrix idModule2Matrix(ideal mod)
2923{
2924  matrix result = mpNew(mod->rank,IDELEMS(mod));
2925  int i,cp;
2926  poly p,h;
2927
2928  for(i=0;i<IDELEMS(mod);i++)
2929  {
2930    p=mod->m[i];
2931    mod->m[i]=NULL;
2932    while (p!=NULL)
2933    {
2934      h=p;
2935      pIter(p);
2936      pNext(h)=NULL;
2937//      cp = si_max(1,pGetComp(h));     // if used for ideals too
2938      cp = pGetComp(h);
2939      pSetComp(h,0);
2940      pSetmComp(h);
2941#ifdef TEST
2942      if (cp>mod->rank)
2943      {
2944        Print("## inv. rank %d -> %d\n",mod->rank,cp);
2945        int k,l,o=mod->rank;
2946        mod->rank=cp;
2947        matrix d=mpNew(mod->rank,IDELEMS(mod));
2948        for (l=1; l<=o; l++)
2949        {
2950          for (k=1; k<=IDELEMS(mod); k++)
2951          {
2952            MATELEM(d,l,k)=MATELEM(result,l,k);
2953            MATELEM(result,l,k)=NULL;
2954          }
2955        }
2956        idDelete((ideal *)&result);
2957        result=d;
2958      }
2959#endif
2960      MATELEM(result,cp,i+1) = pAdd(MATELEM(result,cp,i+1),h);
2961    }
2962  }
2963  // obachman 10/99: added the following line, otherwise memory leack!
2964  idDelete(&mod);
2965  return result;
2966}
2967
2968matrix idModule2formatedMatrix(ideal mod,int rows, int cols)
2969{
2970  matrix result = mpNew(rows,cols);
2971  int i,cp,r=idRankFreeModule(mod),c=IDELEMS(mod);
2972  poly p,h;
2973
2974  if (r>rows) r = rows;
2975  if (c>cols) c = cols;
2976  for(i=0;i<c;i++)
2977  {
2978    p=mod->m[i];
2979    mod->m[i]=NULL;
2980    while (p!=NULL)
2981    {
2982      h=p;
2983      pIter(p);
2984      pNext(h)=NULL;
2985      cp = pGetComp(h);
2986      if (cp<=r)
2987      {
2988        pSetComp(h,0);
2989        pSetmComp(h);
2990        MATELEM(result,cp,i+1) = pAdd(MATELEM(result,cp,i+1),h);
2991      }
2992      else
2993        pDelete(&h);
2994    }
2995  }
2996  idDelete(&mod);
2997  return result;
2998}
2999
3000/*2
3001* substitute the n-th variable by the monomial e in id
3002* destroy id
3003*/
3004ideal  idSubst(ideal id, int n, poly e)
3005{
3006  int k=MATROWS((matrix)id)*MATCOLS((matrix)id);
3007  ideal res=(ideal)mpNew(MATROWS((matrix)id),MATCOLS((matrix)id));
3008
3009  res->rank = id->rank;
3010  for(k--;k>=0;k--)
3011  {
3012    res->m[k]=pSubst(id->m[k],n,e);
3013    id->m[k]=NULL;
3014  }
3015  idDelete(&id);
3016  return res;
3017}
3018
3019BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
3020{
3021  if (w!=NULL) *w=NULL;
3022  if ((Q!=NULL) && (!idHomIdeal(Q,NULL))) return FALSE;
3023  if (idIs0(m))
3024  {
3025    if (w!=NULL) (*w)=new intvec(m->rank);
3026    return TRUE;
3027  }
3028
3029  int i,j,cmax=2,order=0,ord,* diff,* iscom,diffmin=32000;
3030  poly p=NULL;
3031  int length=IDELEMS(m);
3032  polyset P=m->m;
3033  polyset F=(polyset)omAlloc(length*sizeof(poly));
3034  for (i=length-1;i>=0;i--)
3035  {
3036    p=F[i]=P[i];
3037    cmax=si_max(cmax,(int)pMaxComp(p)+1);
3038  }
3039  diff = (int *)omAlloc0(cmax*sizeof(int));
3040  if (w!=NULL) *w=new intvec(cmax-1);
3041  iscom = (int *)omAlloc0(cmax*sizeof(int));
3042  i=0;
3043  while (i<=length)
3044  {
3045    if (i<length)
3046    {
3047      p=F[i];
3048      while ((p!=NULL) && (!iscom[pGetComp(p)])) pIter(p);
3049    }
3050    if ((p==NULL) && (i<length))
3051    {
3052      i++;
3053    }
3054    else
3055    {
3056      if (p==NULL)
3057      {
3058        i=0;
3059        while ((i<length) && (F[i]==NULL)) i++;
3060        if (i>=length) break;
3061        p = F[i];
3062      }
3063      if (pLexOrder && (currRing->order[0]==ringorder_lp))
3064        order=pTotaldegree(p);
3065      else
3066      //  order = p->order;
3067        order = pFDeg(p,currRing);
3068      order += diff[pGetComp(p)];
3069      p = F[i];
3070//Print("Actual p=F[%d]: ",i);pWrite(p);
3071      F[i] = NULL;
3072      i=0;
3073    }
3074    while (p!=NULL)
3075    {
3076      //if (pLexOrder)
3077      //  ord=pTotaldegree(p);
3078      //else
3079      //  ord = p->order;
3080      ord = pFDeg(p,currRing);
3081      if (!iscom[pGetComp(p)])
3082      {
3083        diff[pGetComp(p)] = order-ord;
3084        iscom[pGetComp(p)] = 1;
3085/*
3086*PrintS("new diff: ");
3087*for (j=0;j<cmax;j++) Print("%d ",diff[j]);
3088*PrintLn();
3089*PrintS("new iscom: ");
3090*for (j=0;j<cmax;j++) Print("%d ",iscom[j]);
3091*PrintLn();
3092*Print("new set %d, order %d, ord %d, diff %d\n",pGetComp(p),order,ord,diff[pGetComp(p)]);
3093*/
3094      }
3095      else
3096      {
3097/*
3098*PrintS("new diff: ");
3099*for (j=0;j<cmax;j++) Print("%d ",diff[j]);
3100*PrintLn();
3101*Print("order %d, ord %d, diff %d\n",order,ord,diff[pGetComp(p)]);
3102*/
3103        if (order != ord+diff[pGetComp(p)])
3104        {
3105          omFreeSize((ADDRESS) iscom,cmax*sizeof(int));
3106          omFreeSize((ADDRESS) diff,cmax*sizeof(int));
3107          omFreeSize((ADDRESS) F,length*sizeof(poly));
3108          delete *w;*w=NULL;
3109          return FALSE;
3110        }
3111      }
3112      pIter(p);
3113    }
3114  }
3115  omFreeSize((ADDRESS) iscom,cmax*sizeof(int));
3116  omFreeSize((ADDRESS) F,length*sizeof(poly));
3117  for (i=1;i<cmax;i++) (**w)[i-1]=diff[i];
3118  for (i=1;i<cmax;i++)
3119  {
3120    if (diff[i]<diffmin) diffmin=diff[i];
3121  }
3122  if (w!=NULL)
3123  {
3124    for (i=1;i<cmax;i++)
3125    {
3126      (**w)[i-1]=diff[i]-diffmin;
3127    }
3128  }
3129  omFreeSize((ADDRESS) diff,cmax*sizeof(int));
3130  return TRUE;
3131}
3132
3133BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
3134{
3135  if ((Q!=NULL) && (!idHomIdeal(Q,NULL)))  { PrintS(" Q not hom\n"); return FALSE;}
3136  if (idIs0(m)) return TRUE;
3137
3138  int cmax=-1;
3139  int i;
3140  poly p=NULL;
3141  int length=IDELEMS(m);
3142  polyset P=m->m;
3143  for (i=length-1;i>=0;i--)
3144  {
3145    p=P[i];
3146    if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
3147  }
3148  if (w != NULL)
3149  if (w->length()+1 < cmax)
3150  {
3151    // Print("length: %d - %d \n", w->length(),cmax);
3152    return FALSE;
3153  }
3154
3155  if(w!=NULL)
3156    pSetModDeg(w);
3157
3158  for (i=length-1;i>=0;i--)
3159  {
3160    p=P[i];
3161    poly q=p;
3162    if (p!=NULL)
3163    {
3164      int d=pFDeg(p,currRing);
3165      loop
3166      {
3167        pIter(p);
3168        if (p==NULL) break;
3169        if (d!=pFDeg(p,currRing))
3170        {
3171          //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
3172          if(w!=NULL)
3173            pSetModDeg(NULL);
3174          return FALSE;
3175        }
3176      }
3177    }
3178  }
3179
3180  if(w!=NULL)
3181    pSetModDeg(NULL);
3182
3183  return TRUE;
3184}
3185
3186ideal idJet(ideal i,int d)
3187{
3188  ideal r=idInit((i->nrows)*(i->ncols),i->rank);
3189  r->nrows = i-> nrows;
3190  r->ncols = i-> ncols;
3191  //r->rank = i-> rank;
3192  int k;
3193  for(k=(i->nrows)*(i->ncols)-1;k>=0; k--)
3194  {
3195    r->m[k]=ppJet(i->m[k],d);
3196  }
3197  return r;
3198}
3199
3200ideal idJetW(ideal i,int d, intvec * iv)
3201{
3202  ideal r=idInit(IDELEMS(i),i->rank);
3203  if (ecartWeights!=NULL)
3204  {
3205    WerrorS("cannot compute weighted jets now");
3206  }
3207  else
3208  {
3209    short *w=iv2array(iv);
3210    int k;
3211    for(k=0; k<IDELEMS(i); k++)
3212    {
3213      r->m[k]=ppJetW(i->m[k],d,w);
3214    }
3215    omFreeSize((ADDRESS)w,(pVariables+1)*sizeof(short));
3216  }
3217  return r;
3218}
3219
3220int idMinDegW(ideal M,intvec *w)
3221{
3222  int d=-1;
3223  for(int i=0;i<IDELEMS(M);i++)
3224  {
3225    int d0=pMinDeg(M->m[i],w);
3226    if(-1<d0&&(d0<d||d==-1))
3227      d=d0;
3228  }
3229  return d;
3230}
3231
3232ideal idSeries(int n,ideal M,matrix U,intvec *w)
3233{
3234  for(int i=IDELEMS(M)-1;i>=0;i--)
3235  {
3236    if(U==NULL)
3237      M->m[i]=pSeries(n,M->m[i],NULL,w);
3238    else
3239    {
3240      M->m[i]=pSeries(n,M->m[i],MATELEM(U,i+1,i+1),w);
3241      MATELEM(U,i+1,i+1)=NULL;
3242    }
3243  }
3244  if(U!=NULL)
3245    idDelete((ideal*)&U);
3246  return M;
3247}
3248
3249matrix idDiff(matrix i, int k)
3250{
3251  int e=MATCOLS(i)*MATROWS(i);
3252  matrix r=mpNew(MATROWS(i),MATCOLS(i));
3253  int j;
3254  for(j=0; j<e; j++)
3255  {
3256    r->m[j]=pDiff(i->m[j],k);
3257  }
3258  return r;
3259}
3260
3261matrix idDiffOp(ideal I, ideal J,BOOLEAN multiply)
3262{
3263  matrix r=mpNew(IDELEMS(I),IDELEMS(J));
3264  int i,j;
3265  for(i=0; i<IDELEMS(I); i++)
3266  {
3267    for(j=0; j<IDELEMS(J); j++)
3268    {
3269      MATELEM(r,i+1,j+1)=pDiffOp(I->m[i],J->m[j],multiply);
3270    }
3271  }
3272  return r;
3273}
3274
3275/*3
3276*handles for some ideal operations the ring/syzcomp managment
3277*returns all syzygies (componentwise-)shifted by -syzcomp
3278*or -syzcomp-1 (in case of ideals as input)
3279static ideal idHandleIdealOp(ideal arg,int syzcomp,int isIdeal=FALSE)
3280{
3281  ring orig_ring=currRing;
3282  ring syz_ring=rCurrRingAssure_SyzComp();
3283  rSetSyzComp(length);
3284
3285  ideal s_temp;
3286  if (orig_ring!=syz_ring)
3287    s_temp=idrMoveR_NoSort(arg,orig_ring);
3288  else
3289    s_temp=arg;
3290
3291  ideal s_temp1 = kStd(s_temp,currQuotient,testHomog,&w,NULL,length);
3292  if (w!=NULL) delete w;
3293
3294  if (syz_ring!=orig_ring)
3295  {
3296    idDelete(&s_temp);
3297    rChangeCurrRing(orig_ring);
3298  }
3299
3300  idDelete(&temp);
3301  ideal temp1=idRingCopy(s_temp1,syz_ring);
3302
3303  if (syz_ring!=orig_ring)
3304  {
3305    rChangeCurrRing(syz_ring);
3306    idDelete(&s_temp1);
3307    rChangeCurrRing(orig_ring);
3308    rKill(syz_ring);
3309  }
3310
3311  for (i=0;i<IDELEMS(temp1);i++)
3312  {
3313    if ((temp1->m[i]!=NULL)
3314    && (pGetComp(temp1->m[i])<=length))
3315    {
3316      pDelete(&(temp1->m[i]));
3317    }
3318    else
3319    {
3320      pShift(&(temp1->m[i]),-length);
3321    }
3322  }
3323  temp1->rank = rk;
3324  idSkipZeroes(temp1);
3325
3326  return temp1;
3327}
3328*/
3329/*2
3330* represents (h1+h2)/h2=h1/(h1 intersect h2)
3331*/
3332//ideal idModulo (ideal h2,ideal h1)
3333ideal idModulo (ideal h2,ideal h1, tHomog hom, intvec ** w)
3334{
3335  intvec *wtmp=NULL;
3336
3337  int i,j,k,rk,flength=0,slength,length;
3338  poly p,q;
3339
3340  if (idIs0(h2))
3341    return idFreeModule(si_max(1,h2->ncols));
3342  if (!idIs0(h1))
3343    flength = idRankFreeModule(h1);
3344  slength = idRankFreeModule(h2);
3345  length  = si_max(flength,slength);
3346  if (length==0)
3347  {
3348    length = 1;
3349  }
3350  ideal temp = idInit(IDELEMS(h2),length+IDELEMS(h2));
3351  if ((w!=NULL)&&((*w)!=NULL))
3352  {
3353    //Print("input weights:");(*w)->show(1);PrintLn();
3354    int d;
3355    int k;
3356    wtmp=new intvec(length+IDELEMS(h2));
3357    for (i=0;i<length;i++)
3358      ((*wtmp)[i])=(**w)[i];
3359    for (i=0;i<IDELEMS(h2);i++)
3360    {
3361      poly p=h2->m[i];
3362      if (p!=NULL)
3363      {
3364        d = pDeg(p);
3365        k= pGetComp(p);
3366        if (slength>0) k--;
3367        d +=((**w)[k]);
3368        ((*wtmp)[i+length]) = d;
3369      }
3370    }
3371    //Print("weights:");wtmp->show(1);PrintLn();
3372  }
3373  for (i=0;i<IDELEMS(h2);i++)
3374  {
3375    temp->m[i] = pCopy(h2->m[i]);
3376    q = pOne();
3377    pSetComp(q,i+1+length);
3378    pSetmComp(q);
3379    if(temp->m[i]!=NULL)
3380    {
3381      if (slength==0) pShift(&(temp->m[i]),1);
3382      p = temp->m[i];
3383      while (pNext(p)!=NULL) pIter(p);
3384      pNext(p) = q;
3385    }
3386    else
3387      temp->m[i]=q;
3388  }
3389  rk = k = IDELEMS(h2);
3390  if (!idIs0(h1))
3391  {
3392    pEnlargeSet(&(temp->m),IDELEMS(temp),IDELEMS(h1));
3393    IDELEMS(temp) += IDELEMS(h1);
3394    for (i=0;i<IDELEMS(h1);i++)
3395    {
3396      if (h1->m[i]!=NULL)
3397      {
3398        temp->m[k] = pCopy(h1->m[i]);
3399        if (flength==0) pShift(&(temp->m[k]),1);
3400        k++;
3401      }
3402    }
3403  }
3404
3405  ring orig_ring=currRing;
3406  ring syz_ring=rCurrRingAssure_SyzComp();
3407  rSetSyzComp(length);
3408  ideal s_temp;
3409
3410  if (syz_ring != orig_ring)
3411  {
3412    s_temp = idrMoveR_NoSort(temp, orig_ring);
3413  }
3414  else
3415  {
3416    s_temp = temp;
3417  }
3418
3419  idTest(s_temp);
3420  ideal s_temp1 = kStd(s_temp,currQuotient,hom,&wtmp,NULL,length);
3421
3422  //if (wtmp!=NULL)  Print("output weights:");wtmp->show(1);PrintLn();
3423  if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
3424  {
3425    delete *w;
3426    *w=new intvec(IDELEMS(h2));
3427    for (i=0;i<IDELEMS(h2);i++)
3428      ((**w)[i])=(*wtmp)[i+length];
3429  }
3430  if (wtmp!=NULL) delete wtmp;
3431
3432  for (i=0;i<IDELEMS(s_temp1);i++)
3433  {
3434    if ((s_temp1->m[i]!=NULL)
3435    && (pGetComp(s_temp1->m[i])<=length))
3436    {
3437      pDelete(&(s_temp1->m[i]));
3438    }
3439    else
3440    {
3441      pShift(&(s_temp1->m[i]),-length);
3442    }
3443  }
3444  s_temp1->rank = rk;
3445  idSkipZeroes(s_temp1);
3446
3447  if (syz_ring!=orig_ring)
3448  {
3449    rChangeCurrRing(orig_ring);
3450    s_temp1 = idrMoveR_NoSort(s_temp1, syz_ring);
3451    rKill(syz_ring);
3452    // Hmm ... here seems to be a memory leak
3453    // However, simply deleting it causes memory trouble
3454    // idDelete(&s_temp);
3455  }
3456  else
3457  {
3458    idDelete(&temp);
3459  }
3460  idTest(s_temp1);
3461  return s_temp1;
3462}
3463
3464int idElem(const ideal F)
3465{
3466  int i=0,j=IDELEMS(F)-1;
3467
3468  while(j>=0)
3469  {
3470    if ((F->m)[j]!=NULL) i++;
3471    j--;
3472  }
3473  return i;
3474}
3475
3476/*
3477*computes module-weights for liftings of homogeneous modules
3478*/
3479intvec * idMWLift(ideal mod,intvec * weights)
3480{
3481  if (idIs0(mod)) return new intvec(2);
3482  int i=IDELEMS(mod);
3483  while ((i>0) && (mod->m[i-1]==NULL)) i--;
3484  intvec *result = new intvec(i+1);
3485  while (i>0)
3486  {
3487    (*result)[i]=pFDeg(mod->m[i],currRing)+(*weights)[pGetComp(mod->m[i])];
3488  }
3489  return result;
3490}
3491
3492/*2
3493*sorts the kbase for idCoef* in a special way (lexicographically
3494*with x_max,...,x_1)
3495*/
3496ideal idCreateSpecialKbase(ideal kBase,intvec ** convert)
3497{
3498  int i;
3499  ideal result;
3500
3501  if (idIs0(kBase)) return NULL;
3502  result = idInit(IDELEMS(kBase),kBase->rank);
3503  *convert = idSort(kBase,FALSE);
3504  for (i=0;i<(*convert)->length();i++)
3505  {
3506    result->m[i] = pCopy(kBase->m[(**convert)[i]-1]);
3507  }
3508  return result;
3509}
3510
3511/*2
3512*returns the index of a given monom in the list of the special kbase
3513*/
3514int idIndexOfKBase(poly monom, ideal kbase)
3515{
3516  int j=IDELEMS(kbase);
3517
3518  while ((j>0) && (kbase->m[j-1]==NULL)) j--;
3519  if (j==0) return -1;
3520  int i=pVariables;
3521  while (i>0)
3522  {
3523    loop
3524    {
3525      if (pGetExp(monom,i)>pGetExp(kbase->m[j-1],i)) return -1;
3526      if (pGetExp(monom,i)==pGetExp(kbase->m[j-1],i)) break;
3527      j--;
3528      if (j==0) return -1;
3529    }
3530    if (i==1)
3531    {
3532      while(j>0)
3533      {
3534        if (pGetComp(monom)==pGetComp(kbase->m[j-1])) return j-1;
3535        if (pGetComp(monom)>pGetComp(kbase->m[j-1])) return -1;
3536        j--;
3537      }
3538    }
3539    i--;
3540  }
3541  return -1;
3542}
3543
3544/*2
3545*decomposes the monom in a part of coefficients described by the
3546*complement of how and a monom in variables occuring in how, the
3547*index of which in kbase is returned as integer pos (-1 if it don't
3548*exists)
3549*/
3550poly idDecompose(poly monom, poly how, ideal kbase, int * pos)
3551{
3552  int i;
3553  poly coeff=pOne(), base=pOne();
3554
3555  for (i=1;i<=pVariables;i++)
3556  {
3557    if (pGetExp(how,i)>0)
3558    {
3559      pSetExp(base,i,pGetExp(monom,i));
3560    }
3561    else
3562    {
3563      pSetExp(coeff,i,pGetExp(monom,i));
3564    }
3565  }
3566  pSetComp(base,pGetComp(monom));
3567  pSetm(base);
3568  pSetCoeff(coeff,nCopy(pGetCoeff(monom)));
3569  pSetm(coeff);
3570  *pos = idIndexOfKBase(base,kbase);
3571  if (*pos<0)
3572    pDelete(&coeff);
3573  pDelete(&base);
3574  return coeff;
3575}
3576
3577/*2
3578*returns a matrix A of coefficients with kbase*A=arg
3579*if all monomials in variables of how occur in kbase
3580*the other are deleted
3581*/
3582matrix idCoeffOfKBase(ideal arg, ideal kbase, poly how)
3583{
3584  matrix result;
3585  ideal tempKbase;
3586  poly p,q;
3587  intvec * convert;
3588  int i=IDELEMS(kbase),j=IDELEMS(arg),k,pos;
3589#if 0
3590  while ((i>0) && (kbase->m[i-1]==NULL)) i--;
3591  if (idIs0(arg))
3592    return mpNew(i,1);
3593  while ((j>0) && (arg->m[j-1]==NULL)) j--;
3594  result = mpNew(i,j);
3595#else
3596  result = mpNew(i, j);
3597  while ((j>0) && (arg->m[j-1]==NULL)) j--;
3598#endif
3599
3600  tempKbase = idCreateSpecialKbase(kbase,&convert);
3601  for (k=0;k<j;k++)
3602  {
3603    p = arg->m[k];
3604    while (p!=NULL)
3605    {
3606      q = idDecompose(p,how,tempKbase,&pos);
3607      if (pos>=0)
3608      {
3609        MATELEM(result,(*convert)[pos],k+1) =
3610            pAdd(MATELEM(result,(*convert)[pos],k+1),q);
3611      }
3612      else
3613        pDelete(&q);
3614      pIter(p);
3615    }
3616  }
3617  idDelete(&tempKbase);
3618  return result;
3619}
3620
3621/*3
3622* searches for units in the components of the module arg and
3623* returns the first one
3624*/
3625static int idReadOutUnits(ideal arg,int* comp)
3626{
3627  if (idIs0(arg)) return -1;
3628  int i=0,j, generator=-1;
3629  int rk_arg=arg->rank; //idRankFreeModule(arg);
3630  int * componentIsUsed =(int *)omAlloc((rk_arg+1)*sizeof(int));
3631  poly p,q;
3632
3633  while ((generator<0) && (i<IDELEMS(arg)))
3634  {
3635    memset(componentIsUsed,0,(rk_arg+1)*sizeof(int));
3636    p = arg->m[i];
3637    while (p!=NULL)
3638    {
3639      j = pGetComp(p);
3640      if (componentIsUsed[j]==0)
3641      {
3642        if (pLmIsConstantComp(p))
3643        {
3644          generator = i;
3645          componentIsUsed[j] = 1;
3646        }
3647        else
3648        {
3649          componentIsUsed[j] = -1;
3650        }
3651      }
3652      else if (componentIsUsed[j]>0)
3653      {
3654        (componentIsUsed[j])++;
3655      }
3656      pIter(p);
3657    }
3658    i++;
3659  }
3660  i = 0;
3661  *comp = -1;
3662  for (j=0;j<=rk_arg;j++)
3663  {
3664    if (componentIsUsed[j]>0)
3665    {
3666      if ((*comp==-1) || (componentIsUsed[j]<i))
3667      {
3668        *comp = j;
3669        i= componentIsUsed[j];
3670      }
3671    }
3672  }
3673  omFree(componentIsUsed);
3674  return generator;
3675}
3676
3677#if 0
3678static void idDeleteComp(ideal arg,int red_comp)
3679{
3680  int i,j;
3681  poly p;
3682
3683  for (i=IDELEMS(arg)-1;i>=0;i--)
3684  {
3685    p = arg->m[i];
3686    while (p!=NULL)
3687    {
3688      j = pGetComp(p);
3689      if (j>red_comp)
3690      {
3691        pSetComp(p,j-1);
3692        pSetm(p);
3693      }
3694      pIter(p);
3695    }
3696  }
3697  (arg->rank)--;
3698}
3699#endif
3700
3701static void idDeleteComps(ideal arg,int* red_comp,int del)
3702// red_comp is an array [0..args->rank]
3703{
3704  int i,j;
3705  poly p;
3706
3707  for (i=IDELEMS(arg)-1;i>=0;i--)
3708  {
3709    p = arg->m[i];
3710    while (p!=NULL)
3711    {
3712      j = pGetComp(p);
3713      if (red_comp[j]!=j)
3714      {
3715        pSetComp(p,red_comp[j]);
3716        pSetmComp(p);
3717      }
3718      pIter(p);
3719    }
3720  }
3721  (arg->rank) -= del;
3722}
3723
3724/*2
3725* returns the presentation of an isomorphic, minimally
3726* embedded  module (arg represents the quotient!)
3727*/
3728ideal idMinEmbedding(ideal arg,BOOLEAN inPlace, intvec **w)
3729{
3730  if (idIs0(arg)) return idInit(1,arg->rank);
3731  int i,next_gen,next_comp;
3732  ideal res=arg;
3733
3734  if (!inPlace) res = idCopy(arg);
3735  res->rank=si_max(res->rank,idRankFreeModule(res));
3736  int *red_comp=(int*)omAlloc((res->rank+1)*sizeof(int));
3737  for (i=res->rank;i>=0;i--) red_comp[i]=i;
3738
3739  int del=0;
3740  loop
3741  {
3742    next_gen = idReadOutUnits(res,&next_comp);
3743    if (next_gen<0) break;
3744    del++;
3745    syGaussForOne(res,next_gen,next_comp,0,IDELEMS(res));
3746    for(i=next_comp+1;i<=arg->rank;i++) red_comp[i]--;
3747    if ((w !=NULL)&&(*w!=NULL))
3748    {
3749      for(i=next_comp;i<(*w)->length();i++) (**w)[i-1]=(**w)[i];
3750    }
3751  }
3752
3753  idDeleteComps(res,red_comp,del);
3754  idSkipZeroes(res);
3755  omFree(red_comp);
3756
3757  if ((w !=NULL)&&(*w!=NULL) &&(del>0))
3758  {
3759    intvec *wtmp=new intvec((*w)->length()-del);
3760    for(i=0;i<res->rank;i++) (*wtmp)[i]=(**w)[i];
3761    delete *w;
3762    *w=wtmp;
3763  }
3764  return res;
3765}
3766
3767/*2
3768* transpose a module
3769*/
3770ideal idTransp(ideal a)
3771{
3772  int r = a->rank, c = IDELEMS(a);
3773  ideal b =  idInit(r,c);
3774
3775  for (int i=c; i>0; i--)
3776  {
3777    poly p=a->m[i-1];
3778    while(p!=NULL)
3779    {
3780      poly h=pHead(p);
3781      int co=pGetComp(h)-1;
3782      pSetComp(h,i);
3783      pSetmComp(h);
3784      b->m[co]=pAdd(b->m[co],h);
3785      pIter(p);
3786    }
3787  }
3788  return b;
3789}
3790
3791intvec * idQHomWeight(ideal id)
3792{
3793  poly head, tail;
3794  int k;
3795  int in=IDELEMS(id)-1, ready=0, all=0,
3796      coldim=pVariables, rowmax=2*coldim;
3797  if (in<0) return NULL;
3798  intvec *imat=new intvec(rowmax+1,coldim,0);
3799
3800  do
3801  {
3802    head = id->m[in--];
3803    if (head!=NULL)
3804    {
3805      tail = pNext(head);
3806      while (tail!=NULL)
3807      {
3808        all++;
3809        for (k=1;k<=coldim;k++)
3810          IMATELEM(*imat,all,k) = pGetExpDiff(head,tail,k);
3811        if (all==rowmax)
3812        {
3813          ivTriangIntern(imat, ready, all);
3814          if (ready==coldim)
3815          {
3816            delete imat;
3817            return NULL;
3818          }
3819        }
3820        pIter(tail);
3821      }
3822    }
3823  } while (in>=0);
3824  if (all>ready)
3825  {
3826    ivTriangIntern(imat, ready, all);
3827    if (ready==coldim)
3828    {
3829      delete imat;
3830      return NULL;
3831    }
3832  }
3833  intvec *result = ivSolveKern(imat, ready);
3834  delete imat;
3835  return result;
3836}
3837
3838BOOLEAN idIsZeroDim(ideal I)
3839{
3840  BOOLEAN *UsedAxis=(BOOLEAN *)omAlloc0(pVariables*sizeof(BOOLEAN));
3841  int i,n;
3842  poly po;
3843  BOOLEAN res=TRUE;
3844  for(i=IDELEMS(I)-1;i>=0;i--)
3845  {
3846    po=I->m[i];
3847    if ((po!=NULL) &&((n=pIsPurePower(po))!=0)) UsedAxis[n-1]=TRUE;
3848  }
3849  for(i=pVariables-1;i>=0;i--)
3850  {
3851    if(UsedAxis[i]==FALSE) {res=FALSE; break;} // not zero-dim.
3852  }
3853  omFreeSize(UsedAxis,pVariables*sizeof(BOOLEAN));
3854  return res;
3855}
3856
3857void idNormalize(ideal I)
3858{
3859  if (rField_has_simple_inverse()) return; /* Z/p, GF(p,n), R, long R/C */
3860  int i;
3861  poly p;
3862  for(i=IDELEMS(I)-1;i>=0;i--)
3863  {
3864    p=I->m[i] ;
3865    while(p!=NULL)
3866    {
3867      nNormalize(pGetCoeff(p));
3868      pIter(p);
3869    }
3870  }
3871}
3872
3873#include "clapsing.h"
3874
3875poly id_GCD(poly f, poly g, const ring r)
3876{
3877  ring save_r=currRing;
3878  rChangeCurrRing(r);
3879  ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
3880  intvec *w = NULL;
3881  ideal S=idSyzygies(I,testHomog,&w);
3882  if (w!=NULL) delete w;
3883  poly gg=pTakeOutComp(&(S->m[0]),2);
3884  idDelete(&S);
3885  poly gcd_p=singclap_pdivide(f,gg);
3886  pDelete(&gg);
3887  rChangeCurrRing(save_r);
3888  return gcd_p;
3889}
3890
3891/*2
3892* xx,q: arrays of length 0..rl-1
3893* xx[i]: SB mod q[i]
3894* assume: char=0
3895* assume: q[i]!=0
3896* destroys xx
3897*/
3898ideal idChineseRemainder(ideal *xx, number *q, int rl)
3899{
3900  ideal result=idInit(IDELEMS(xx[0]),1);
3901  int i,j;
3902  poly r,h,hh,res_p;
3903  number *x=(number *)omAlloc(rl*sizeof(number));
3904  for(i=IDELEMS(result)-1;i>=0;i--)
3905  {
3906    res_p=NULL;
3907    loop
3908    {
3909      r=NULL;
3910      for(j=rl-1;j>=0;j--)
3911      {
3912        h=xx[j]->m[i];
3913        if ((h!=NULL)
3914        &&((r==NULL)||(pLmCmp(r,h)==-1)))
3915          r=h;
3916      }
3917      if (r==NULL) break;
3918      h=pHead(r);
3919      for(j=rl-1;j>=0;j--)
3920      {
3921        hh=xx[j]->m[i];
3922        if ((hh!=NULL) && (pLmCmp(r,hh)==0))
3923        {
3924          x[j]=pGetCoeff(hh);
3925          hh=pLmFreeAndNext(hh);
3926          xx[j]->m[i]=hh;
3927        }
3928        else
3929          x[j]=nlInit(0);
3930      }
3931      number n=nlChineseRemainder(x,q,rl);
3932      for(j=rl-1;j>=0;j--)
3933      {
3934        nlDelete(&(x[j]),currRing);
3935      }
3936      pSetCoeff(h,n);
3937      //Print("new mon:");pWrite(h);
3938      res_p=pAdd(res_p,h);
3939    }
3940    result->m[i]=res_p;
3941  }
3942  omFree(x);
3943  for(i=rl-1;i>=0;i--) idDelete(&(xx[i]));
3944  omFree(xx);
3945  return result;
3946}
3947ideal idChineseRemainder(ideal *xx, intvec *iv)
3948{
3949  int rl=iv->length();
3950  number *q=(number *)omAlloc(rl*sizeof(number));
3951  int i;
3952  for(i=0; i<rl; i++)
3953  {
3954    q[i]=nInit((*iv)[i]);
3955  }
3956  return idChineseRemainder(xx,q,rl);
3957}
Note: See TracBrowser for help on using the repository browser.