source: git/kernel/ideals.cc @ f5d2647

spielwiese
Last change on this file since f5d2647 was dc4782, checked in by Hans Schoenemann <hannes@…>, 10 years ago
chg: factory/libfac is not optional, removing HAVE_FACTORY/HAVE_LIBFAC
  • Property mode set to 100644
File size: 58.2 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/*
5* ABSTRACT - all basic methods to manipulate ideals
6*/
7
8/* includes */
9#ifdef HAVE_CONFIG_H
10#include "singularconfig.h"
11#endif /* HAVE_CONFIG_H */
12#include "mod2.h"
13
14#include <omalloc/omalloc.h>
15
16#ifndef NDEBUG
17# define MYTEST 0
18#else /* ifndef NDEBUG */
19# define MYTEST 0
20#endif /* ifndef NDEBUG */
21
22#include <omalloc/omalloc.h>
23
24#include <misc/options.h>
25#include <misc/intvec.h>
26
27#include <coeffs/coeffs.h>
28#include <coeffs/numbers.h>
29
30#include <kernel/polys.h>
31#include <polys/monomials/ring.h>
32#include <polys/matpol.h>
33#include <polys/weight.h>
34#include <polys/sparsmat.h>
35#include <polys/prCopy.h>
36#include <polys/nc/nc.h>
37
38
39#include <kernel/ideals.h>
40
41#include <kernel/febase.h>
42#include <kernel/kstd1.h>
43#include <kernel/syz.h>
44
45#include <libpolys/coeffs/longrat.h>
46
47
48/* #define WITH_OLD_MINOR */
49#define pCopy_noCheck(p) pCopy(p)
50
51/*0 implementation*/
52
53/*2
54*returns a minimized set of generators of h1
55*/
56ideal idMinBase (ideal h1)
57{
58  ideal h2, h3,h4,e;
59  int j,k;
60  int i,l,ll;
61  intvec * wth;
62  BOOLEAN homog;
63
64  homog = idHomModule(h1,currQuotient,&wth);
65  if (rHasGlobalOrdering(currRing))
66  {
67    if(!homog)
68    {
69      WarnS("minbase applies only to the local or homogeneous case");
70      e=idCopy(h1);
71      return e;
72    }
73    else
74    {
75      ideal re=kMin_std(h1,currQuotient,(tHomog)homog,&wth,h2,NULL,0,3);
76      idDelete(&re);
77      return h2;
78    }
79  }
80  e=idInit(1,h1->rank);
81  if (idIs0(h1))
82  {
83    return e;
84  }
85  pEnlargeSet(&(e->m),IDELEMS(e),15);
86  IDELEMS(e) = 16;
87  h2 = kStd(h1,currQuotient,isNotHomog,NULL);
88  h3 = idMaxIdeal(1);
89  h4=idMult(h2,h3);
90  idDelete(&h3);
91  h3=kStd(h4,currQuotient,isNotHomog,NULL);
92  k = IDELEMS(h3);
93  while ((k > 0) && (h3->m[k-1] == NULL)) k--;
94  j = -1;
95  l = IDELEMS(h2);
96  while ((l > 0) && (h2->m[l-1] == NULL)) l--;
97  for (i=l-1; i>=0; i--)
98  {
99    if (h2->m[i] != NULL)
100    {
101      ll = 0;
102      while ((ll < k) && ((h3->m[ll] == NULL)
103      || !pDivisibleBy(h3->m[ll],h2->m[i])))
104        ll++;
105      if (ll >= k)
106      {
107        j++;
108        if (j > IDELEMS(e)-1)
109        {
110          pEnlargeSet(&(e->m),IDELEMS(e),16);
111          IDELEMS(e) += 16;
112        }
113        e->m[j] = pCopy(h2->m[i]);
114      }
115    }
116  }
117  idDelete(&h2);
118  idDelete(&h3);
119  idDelete(&h4);
120  if (currQuotient!=NULL)
121  {
122    h3=idInit(1,e->rank);
123    h2=kNF(h3,currQuotient,e);
124    idDelete(&h3);
125    idDelete(&e);
126    e=h2;
127  }
128  idSkipZeroes(e);
129  return e;
130}
131
132
133/*2
134*initialized a field with r numbers between beg and end for the
135*procedure idNextChoise
136*/
137ideal idSectWithElim (ideal h1,ideal h2)
138// does not destroy h1,h2
139{
140  if (TEST_OPT_PROT) PrintS("intersect by elimination method\n");
141  assume(!idIs0(h1));
142  assume(!idIs0(h2));
143  assume(IDELEMS(h1)<=IDELEMS(h2));
144  assume(id_RankFreeModule(h1,currRing)==0);
145  assume(id_RankFreeModule(h2,currRing)==0);
146  // add a new variable:
147  int j;
148  ring origRing=currRing;
149  ring r=rCopy0(origRing);
150  r->N++;
151  r->block0[0]=1;
152  r->block1[0]= r->N;
153  omFree(r->order);
154  r->order=(int*)omAlloc0(3*sizeof(int*));
155  r->order[0]=ringorder_dp;
156  r->order[1]=ringorder_C;
157  char **names=(char**)omAlloc0(rVar(r) * sizeof(char_ptr));
158  for (j=0;j<r->N-1;j++) names[j]=r->names[j];
159  names[r->N-1]=omStrDup("@");
160  omFree(r->names);
161  r->names=names;
162  rComplete(r,TRUE);
163  // fetch h1, h2
164  ideal h;
165  h1=idrCopyR(h1,origRing,r);
166  h2=idrCopyR(h2,origRing,r);
167  // switch to temp. ring r
168  rChangeCurrRing(r);
169  // create 1-t, t
170  poly omt=p_One(currRing);
171  p_SetExp(omt,r->N,1,currRing);
172  poly t=p_Copy(omt,currRing);
173  p_Setm(omt,currRing);
174  omt=p_Neg(omt,currRing);
175  omt=p_Add_q(omt,pOne(),currRing);
176  // compute (1-t)*h1
177  h1=(ideal)mp_MultP((matrix)h1,omt,currRing);
178  // compute t*h2
179  h2=(ideal)mp_MultP((matrix)h2,pCopy(t),currRing);
180  // (1-t)h1 + t*h2
181  h=idInit(IDELEMS(h1)+IDELEMS(h2),1);
182  int l;
183  for (l=IDELEMS(h1)-1; l>=0; l--)
184  {
185    h->m[l] = h1->m[l];  h1->m[l]=NULL;
186  }
187  j=IDELEMS(h1);
188  for (l=IDELEMS(h2)-1; l>=0; l--)
189  {
190    h->m[l+j] = h2->m[l];  h2->m[l]=NULL;
191  }
192  idDelete(&h1);
193  idDelete(&h2);
194  // eliminate t:
195
196  ideal res=idElimination(h,t);
197  // cleanup
198  idDelete(&h);
199  if (res!=NULL) res=idrMoveR(res,r,origRing);
200  rChangeCurrRing(origRing);
201  rDelete(r);
202  return res;
203}
204/*2
205* h3 := h1 intersect h2
206*/
207ideal idSect (ideal h1,ideal h2)
208{
209  int i,j,k,length;
210  int flength = id_RankFreeModule(h1,currRing);
211  int slength = id_RankFreeModule(h2,currRing);
212  int rank=si_min(flength,slength);
213  if ((idIs0(h1)) || (idIs0(h2)))  return idInit(1,rank);
214
215  ideal first,second,temp,temp1,result;
216  poly p,q;
217
218  if (IDELEMS(h1)<IDELEMS(h2))
219  {
220    first = h1;
221    second = h2;
222  }
223  else
224  {
225    first = h2;
226    second = h1;
227    int t=flength; flength=slength; slength=t;
228  }
229  length  = si_max(flength,slength);
230  if (length==0)
231  {
232    if ((currQuotient==NULL)
233    && (currRing->OrdSgn==1)
234    && (!rIsPluralRing(currRing))
235    && ((TEST_V_INTERSECT_ELIM) || (!TEST_V_INTERSECT_SYZ)))
236      return idSectWithElim(first,second);
237    else length = 1;
238  }
239  if (TEST_OPT_PROT) PrintS("intersect by syzygy methods\n");
240  j = IDELEMS(first);
241
242  ring orig_ring=currRing;
243  ring syz_ring=rAssure_SyzComp(orig_ring,TRUE); rChangeCurrRing(syz_ring);
244  rSetSyzComp(length, syz_ring);
245
246  while ((j>0) && (first->m[j-1]==NULL)) j--;
247  temp = idInit(j /*IDELEMS(first)*/+IDELEMS(second),length+j);
248  k = 0;
249  for (i=0;i<j;i++)
250  {
251    if (first->m[i]!=NULL)
252    {
253      if (syz_ring==orig_ring)
254        temp->m[k] = pCopy(first->m[i]);
255      else
256        temp->m[k] = prCopyR(first->m[i], orig_ring, syz_ring);
257      q = pOne();
258      pSetComp(q,i+1+length);
259      pSetmComp(q);
260      if (flength==0) p_Shift(&(temp->m[k]),1,currRing);
261      p = temp->m[k];
262      while (pNext(p)!=NULL) pIter(p);
263      pNext(p) = q;
264      k++;
265    }
266  }
267  for (i=0;i<IDELEMS(second);i++)
268  {
269    if (second->m[i]!=NULL)
270    {
271      if (syz_ring==orig_ring)
272        temp->m[k] = pCopy(second->m[i]);
273      else
274        temp->m[k] = prCopyR(second->m[i], orig_ring,currRing);
275      if (slength==0) p_Shift(&(temp->m[k]),1,currRing);
276      k++;
277    }
278  }
279  intvec *w=NULL;
280  temp1 = kStd(temp,currQuotient,testHomog,&w,NULL,length);
281  if (w!=NULL) delete w;
282  idDelete(&temp);
283  if(syz_ring!=orig_ring)
284    rChangeCurrRing(orig_ring);
285
286  result = idInit(IDELEMS(temp1),rank);
287  j = 0;
288  for (i=0;i<IDELEMS(temp1);i++)
289  {
290    if ((temp1->m[i]!=NULL)
291    && (p_GetComp(temp1->m[i],syz_ring)>length))
292    {
293      if(syz_ring==orig_ring)
294      {
295        p = temp1->m[i];
296      }
297      else
298      {
299        p = prMoveR(temp1->m[i], syz_ring,orig_ring);
300      }
301      temp1->m[i]=NULL;
302      while (p!=NULL)
303      {
304        q = pNext(p);
305        pNext(p) = NULL;
306        k = pGetComp(p)-1-length;
307        pSetComp(p,0);
308        pSetmComp(p);
309        /* Warning! multiply only from the left! it's very important for Plural */
310        result->m[j] = pAdd(result->m[j],pMult(p,pCopy(first->m[k])));
311        p = q;
312      }
313      j++;
314    }
315  }
316  if(syz_ring!=orig_ring)
317  {
318    rChangeCurrRing(syz_ring);
319    idDelete(&temp1);
320    rChangeCurrRing(orig_ring);
321    rDelete(syz_ring);
322  }
323  else
324  {
325    idDelete(&temp1);
326  }
327
328  idSkipZeroes(result);
329  if (TEST_OPT_RETURN_SB)
330  {
331     w=NULL;
332     temp1=kStd(result,currQuotient,testHomog,&w);
333     if (w!=NULL) delete w;
334     idDelete(&result);
335     idSkipZeroes(temp1);
336     return temp1;
337  }
338  else //temp1=kInterRed(result,currQuotient);
339    return result;
340}
341
342/*2
343* ideal/module intersection for a list of objects
344* given as 'resolvente'
345*/
346ideal idMultSect(resolvente arg, int length)
347{
348  int i,j=0,k=0,syzComp,l,maxrk=-1,realrki;
349  ideal bigmat,tempstd,result;
350  poly p;
351  int isIdeal=0;
352  intvec * w=NULL;
353
354  /* find 0-ideals and max rank -----------------------------------*/
355  for (i=0;i<length;i++)
356  {
357    if (!idIs0(arg[i]))
358    {
359      realrki=id_RankFreeModule(arg[i],currRing);
360      k++;
361      j += IDELEMS(arg[i]);
362      if (realrki>maxrk) maxrk = realrki;
363    }
364    else
365    {
366      if (arg[i]!=NULL)
367      {
368        return idInit(1,arg[i]->rank);
369      }
370    }
371  }
372  if (maxrk == 0)
373  {
374    isIdeal = 1;
375    maxrk = 1;
376  }
377  /* init -----------------------------------------------------------*/
378  j += maxrk;
379  syzComp = k*maxrk;
380
381  ring orig_ring=currRing;
382  ring syz_ring=rAssure_SyzComp(orig_ring,TRUE); rChangeCurrRing(syz_ring);
383  rSetSyzComp(syzComp, syz_ring);
384
385  bigmat = idInit(j,(k+1)*maxrk);
386  /* create unit matrices ------------------------------------------*/
387  for (i=0;i<maxrk;i++)
388  {
389    for (j=0;j<=k;j++)
390    {
391      p = pOne();
392      pSetComp(p,i+1+j*maxrk);
393      pSetmComp(p);
394      bigmat->m[i] = pAdd(bigmat->m[i],p);
395    }
396  }
397  /* enter given ideals ------------------------------------------*/
398  i = maxrk;
399  k = 0;
400  for (j=0;j<length;j++)
401  {
402    if (arg[j]!=NULL)
403    {
404      for (l=0;l<IDELEMS(arg[j]);l++)
405      {
406        if (arg[j]->m[l]!=NULL)
407        {
408          if (syz_ring==orig_ring)
409            bigmat->m[i] = pCopy(arg[j]->m[l]);
410          else
411            bigmat->m[i] = prCopyR(arg[j]->m[l], orig_ring,currRing);
412          p_Shift(&(bigmat->m[i]),k*maxrk+isIdeal,currRing);
413          i++;
414        }
415      }
416      k++;
417    }
418  }
419  /* std computation --------------------------------------------*/
420  tempstd = kStd(bigmat,currQuotient,testHomog,&w,NULL,syzComp);
421  if (w!=NULL) delete w;
422  idDelete(&bigmat);
423
424  if(syz_ring!=orig_ring)
425    rChangeCurrRing(orig_ring);
426
427  /* interprete result ----------------------------------------*/
428  result = idInit(IDELEMS(tempstd),maxrk);
429  k = 0;
430  for (j=0;j<IDELEMS(tempstd);j++)
431  {
432    if ((tempstd->m[j]!=NULL) && (p_GetComp(tempstd->m[j],syz_ring)>syzComp))
433    {
434      if (syz_ring==orig_ring)
435        p = pCopy(tempstd->m[j]);
436      else
437        p = prCopyR(tempstd->m[j], syz_ring,currRing);
438      p_Shift(&p,-syzComp-isIdeal,currRing);
439      result->m[k] = p;
440      k++;
441    }
442  }
443  /* clean up ----------------------------------------------------*/
444  if(syz_ring!=orig_ring)
445    rChangeCurrRing(syz_ring);
446  idDelete(&tempstd);
447  if(syz_ring!=orig_ring)
448  {
449    rChangeCurrRing(orig_ring);
450    rDelete(syz_ring);
451  }
452  idSkipZeroes(result);
453  return result;
454}
455
456/*2
457*computes syzygies of h1,
458*if quot != NULL it computes in the quotient ring modulo "quot"
459*works always in a ring with ringorder_s
460*/
461static ideal idPrepare (ideal  h1, tHomog hom, int syzcomp, intvec **w)
462{
463  ideal   h2, h3;
464  int     i;
465  int     j,k;
466  poly    p,q;
467
468  if (idIs0(h1)) return NULL;
469  k = id_RankFreeModule(h1,currRing);
470  h2=idCopy(h1);
471  i = IDELEMS(h2)-1;
472  if (k == 0)
473  {
474    for (j=0; j<=i; j++) p_Shift(&(h2->m[j]),1,currRing);
475    k = 1;
476  }
477  if (syzcomp<k)
478  {
479    Warn("syzcomp too low, should be %d instead of %d",k,syzcomp);
480    syzcomp = k;
481    rSetSyzComp(k,currRing);
482  }
483  h2->rank = syzcomp+i+1;
484
485  //if (hom==testHomog)
486  //{
487  //  if(idHomIdeal(h1,currQuotient))
488  //  {
489  //    hom=TRUE;
490  //  }
491  //}
492
493#if MYTEST
494#ifdef RDEBUG
495  Print("Prepare::h2: ");
496  idPrint(h2);
497
498  for(j=0;j<IDELEMS(h2);j++) pTest(h2->m[j]);
499
500#endif
501#endif
502
503  for (j=0; j<=i; j++)
504  {
505    p = h2->m[j];
506    q = pOne();
507    pSetComp(q,syzcomp+1+j);
508    pSetmComp(q);
509    if (p!=NULL)
510    {
511      while (pNext(p)) pIter(p);
512      p->next = q;
513    }
514    else
515      h2->m[j]=q;
516  }
517
518#ifdef PDEBUG
519  for(j=0;j<IDELEMS(h2);j++) pTest(h2->m[j]);
520
521#if MYTEST
522#ifdef RDEBUG
523  Print("Prepare::Input: ");
524  idPrint(h2);
525
526  Print("Prepare::currQuotient: ");
527  idPrint(currQuotient);
528#endif
529#endif
530
531#endif
532
533  idTest(h2);
534
535  h3 = kStd(h2,currQuotient,hom,w,NULL,syzcomp);
536
537#if MYTEST
538#ifdef RDEBUG
539  Print("Prepare::Output: ");
540  idPrint(h3);
541  for(j=0;j<IDELEMS(h2);j++) pTest(h3->m[j]);
542#endif
543#endif
544
545
546  idDelete(&h2);
547  return h3;
548}
549
550/*2
551* compute the syzygies of h1 in R/quot,
552* weights of components are in w
553* if setRegularity, return the regularity in deg
554* do not change h1,  w
555*/
556ideal idSyzygies (ideal  h1, tHomog h,intvec **w, BOOLEAN setSyzComp,
557                  BOOLEAN setRegularity, int *deg)
558{
559  ideal s_h1;
560  int   j, k, length=0,reg;
561  BOOLEAN isMonomial=TRUE;
562  int ii, idElemens_h1;
563
564  assume(h1 != NULL);
565
566  idElemens_h1=IDELEMS(h1);
567#ifdef PDEBUG
568  for(ii=0;ii<idElemens_h1 /*IDELEMS(h1)*/;ii++) pTest(h1->m[ii]);
569#endif
570  if (idIs0(h1))
571  {
572    ideal result=idFreeModule(idElemens_h1/*IDELEMS(h1)*/);
573    int curr_syz_limit=rGetCurrSyzLimit(currRing);
574    if (curr_syz_limit>0)
575    for (ii=0;ii<idElemens_h1/*IDELEMS(h1)*/;ii++)
576    {
577      if (h1->m[ii]!=NULL)
578        p_Shift(&h1->m[ii],curr_syz_limit,currRing);
579    }
580    return result;
581  }
582  int slength=(int)id_RankFreeModule(h1,currRing);
583  k=si_max(1,slength /*id_RankFreeModule(h1)*/);
584
585  assume(currRing != NULL);
586  ring orig_ring=currRing;
587  ring syz_ring=rAssure_SyzComp(orig_ring,TRUE); rChangeCurrRing(syz_ring);
588
589  if (setSyzComp)
590    rSetSyzComp(k,syz_ring);
591
592  if (orig_ring != syz_ring)
593  {
594    s_h1=idrCopyR_NoSort(h1,orig_ring,syz_ring);
595  }
596  else
597  {
598    s_h1 = h1;
599  }
600
601  idTest(s_h1);
602
603  ideal s_h3=idPrepare(s_h1,h,k,w); // main (syz) GB computation
604
605  if (s_h3==NULL)
606  {
607    return idFreeModule( idElemens_h1 /*IDELEMS(h1)*/);
608  }
609
610  if (orig_ring != syz_ring)
611  {
612    idDelete(&s_h1);
613    for (j=0; j<IDELEMS(s_h3); j++)
614    {
615      if (s_h3->m[j] != NULL)
616      {
617        if (p_MinComp(s_h3->m[j],syz_ring) > k)
618          p_Shift(&s_h3->m[j], -k,syz_ring);
619        else
620          p_Delete(&s_h3->m[j],syz_ring);
621      }
622    }
623    idSkipZeroes(s_h3);
624    s_h3->rank -= k;
625    rChangeCurrRing(orig_ring);
626    s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
627    rDelete(syz_ring);
628    #ifdef HAVE_PLURAL
629    if (rIsPluralRing(orig_ring))
630    {
631      id_DelMultiples(s_h3,orig_ring);
632      idSkipZeroes(s_h3);
633    }
634    #endif
635    idTest(s_h3);
636    return s_h3;
637  }
638
639  ideal e = idInit(IDELEMS(s_h3), s_h3->rank);
640
641  for (j=IDELEMS(s_h3)-1; j>=0; j--)
642  {
643    if (s_h3->m[j] != NULL)
644    {
645      if (p_MinComp(s_h3->m[j],syz_ring) <= k)
646      {
647        e->m[j] = s_h3->m[j];
648        isMonomial=isMonomial && (pNext(s_h3->m[j])==NULL);
649        p_Delete(&pNext(s_h3->m[j]),syz_ring);
650        s_h3->m[j] = NULL;
651      }
652    }
653  }
654
655  idSkipZeroes(s_h3);
656  idSkipZeroes(e);
657
658  if ((deg != NULL)
659  && (!isMonomial)
660  && (!TEST_OPT_NOTREGULARITY)
661  && (setRegularity)
662  && (h==isHomog)
663  && (!rIsPluralRing(currRing))
664  )
665  {
666    ring dp_C_ring = rAssure_dp_C(syz_ring); // will do rChangeCurrRing later
667    if (dp_C_ring != syz_ring)
668    {
669      rChangeCurrRing(dp_C_ring);
670      e = idrMoveR_NoSort(e, syz_ring, dp_C_ring);
671    }
672    resolvente res = sySchreyerResolvente(e,-1,&length,TRUE, TRUE);
673    intvec * dummy = syBetti(res,length,&reg, *w);
674    *deg = reg+2;
675    delete dummy;
676    for (j=0;j<length;j++)
677    {
678      if (res[j]!=NULL) idDelete(&(res[j]));
679    }
680    omFreeSize((ADDRESS)res,length*sizeof(ideal));
681    idDelete(&e);
682    if (dp_C_ring != syz_ring)
683    {
684      rChangeCurrRing(syz_ring);
685      rDelete(dp_C_ring);
686    }
687  }
688  else
689  {
690    idDelete(&e);
691  }
692  idTest(s_h3);
693  if (currQuotient != NULL)
694  {
695    ideal ts_h3=kStd(s_h3,currQuotient,h,w);
696    idDelete(&s_h3);
697    s_h3 = ts_h3;
698  }
699  return s_h3;
700}
701
702/*2
703*/
704ideal idXXX (ideal  h1, int k)
705{
706  ideal s_h1;
707  intvec *w=NULL;
708
709  assume(currRing != NULL);
710  ring orig_ring=currRing;
711  ring syz_ring=rAssure_SyzComp(orig_ring,TRUE); rChangeCurrRing(syz_ring);
712
713  rSetSyzComp(k,syz_ring);
714
715  if (orig_ring != syz_ring)
716  {
717    s_h1=idrCopyR_NoSort(h1,orig_ring, syz_ring);
718  }
719  else
720  {
721    s_h1 = h1;
722  }
723
724  ideal s_h3=kStd(s_h1,NULL,testHomog,&w,NULL,k);
725
726  if (s_h3==NULL)
727  {
728    return idFreeModule(IDELEMS(h1));
729  }
730
731  if (orig_ring != syz_ring)
732  {
733    idDelete(&s_h1);
734    idSkipZeroes(s_h3);
735    rChangeCurrRing(orig_ring);
736    s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
737    rDelete(syz_ring);
738    idTest(s_h3);
739    return s_h3;
740  }
741
742  idSkipZeroes(s_h3);
743  idTest(s_h3);
744  return s_h3;
745}
746
747/*
748*computes a standard basis for h1 and stores the transformation matrix
749* in ma
750*/
751ideal idLiftStd (ideal  h1, matrix* ma, tHomog hi, ideal * syz)
752{
753  int  i, j, t, inputIsIdeal=id_RankFreeModule(h1,currRing);
754  long k;
755  poly  p=NULL, q;
756  intvec *w=NULL;
757
758  idDelete((ideal*)ma);
759  BOOLEAN lift3=FALSE;
760  if (syz!=NULL) { lift3=TRUE; idDelete(syz); }
761  if (idIs0(h1))
762  {
763    *ma=mpNew(1,0);
764    if (lift3)
765    {
766      *syz=idFreeModule(IDELEMS(h1));
767      int curr_syz_limit=rGetCurrSyzLimit(currRing);
768      if (curr_syz_limit>0)
769      for (int ii=0;ii<IDELEMS(h1);ii++)
770      {
771        if (h1->m[ii]!=NULL)
772          p_Shift(&h1->m[ii],curr_syz_limit,currRing);
773      }
774    }
775    return idInit(1,h1->rank);
776  }
777
778  BITSET save2;
779  SI_SAVE_OPT2(save2);
780
781  k=si_max((long)1,id_RankFreeModule(h1,currRing));
782
783  if ((k==1) && (!lift3)) si_opt_2 |=Sy_bit(V_IDLIFT);
784
785  ring orig_ring = currRing;
786  ring syz_ring = rAssure_SyzComp(orig_ring,TRUE);  rChangeCurrRing(syz_ring);
787  rSetSyzComp(k,syz_ring);
788
789  ideal s_h1=h1;
790
791  if (orig_ring != syz_ring)
792    s_h1 = idrCopyR_NoSort(h1,orig_ring,syz_ring);
793  else
794    s_h1 = h1;
795
796  ideal s_h3=idPrepare(s_h1,hi,k,&w); // main (syz) GB computation
797
798  ideal s_h2 = idInit(IDELEMS(s_h3), s_h3->rank);
799
800  if (lift3) (*syz)=idInit(IDELEMS(s_h3),IDELEMS(h1));
801
802  if (w!=NULL) delete w;
803  i = 0;
804
805  // now sort the result, SB : leave in s_h3
806  //                      T:  put in s_h2
807  //                      syz: put in *syz
808  for (j=0; j<IDELEMS(s_h3); j++)
809  {
810    if (s_h3->m[j] != NULL)
811    {
812      //if (p_MinComp(s_h3->m[j],syz_ring) <= k)
813      if (pGetComp(s_h3->m[j]) <= k) // syz_ring == currRing
814      {
815        i++;
816        q = s_h3->m[j];
817        while (pNext(q) != NULL)
818        {
819          if (pGetComp(pNext(q)) > k)
820          {
821            s_h2->m[j] = pNext(q);
822            pNext(q) = NULL;
823          }
824          else
825          {
826            pIter(q);
827          }
828        }
829        if (!inputIsIdeal) p_Shift(&(s_h3->m[j]), -1,currRing);
830      }
831      else
832      {
833        // we a syzygy here:
834        if (lift3)
835        {
836          p_Shift(&s_h3->m[j], -k,currRing);
837          (*syz)->m[j]=s_h3->m[j];
838          s_h3->m[j]=NULL;
839        }
840        else
841          p_Delete(&(s_h3->m[j]),currRing);
842      }
843    }
844  }
845  idSkipZeroes(s_h3);
846  //extern char * iiStringMatrix(matrix im, int dim,char ch);
847  //PrintS("SB: ----------------------------------------\n");
848  //PrintS(iiStringMatrix((matrix)s_h3,k,'\n'));
849  //PrintLn();
850  //PrintS("T: ----------------------------------------\n");
851  //PrintS(iiStringMatrix((matrix)s_h2,h1->rank,'\n'));
852  //PrintLn();
853
854  if (lift3) idSkipZeroes(*syz);
855
856  j = IDELEMS(s_h1);
857
858
859  if (syz_ring!=orig_ring)
860  {
861    idDelete(&s_h1);
862    rChangeCurrRing(orig_ring);
863  }
864
865  *ma = mpNew(j,i);
866
867  i = 1;
868  for (j=0; j<IDELEMS(s_h2); j++)
869  {
870    if (s_h2->m[j] != NULL)
871    {
872      q = prMoveR( s_h2->m[j], syz_ring,orig_ring);
873      s_h2->m[j] = NULL;
874
875      while (q != NULL)
876      {
877        p = q;
878        pIter(q);
879        pNext(p) = NULL;
880        t=pGetComp(p);
881        pSetComp(p,0);
882        pSetmComp(p);
883        MATELEM(*ma,t-k,i) = pAdd(MATELEM(*ma,t-k,i),p);
884      }
885      i++;
886    }
887  }
888  idDelete(&s_h2);
889
890  for (i=0; i<IDELEMS(s_h3); i++)
891  {
892    s_h3->m[i] = prMoveR_NoSort(s_h3->m[i], syz_ring,orig_ring);
893  }
894  if (lift3)
895  {
896    for (i=0; i<IDELEMS(*syz); i++)
897    {
898      (*syz)->m[i] = prMoveR_NoSort((*syz)->m[i], syz_ring,orig_ring);
899    }
900  }
901
902  if (syz_ring!=orig_ring) rDelete(syz_ring);
903  SI_RESTORE_OPT2(save2);
904  return s_h3;
905}
906
907static void idPrepareStd(ideal s_temp, int k)
908{
909  int j,rk=id_RankFreeModule(s_temp,currRing);
910  poly p,q;
911
912  if (rk == 0)
913  {
914    for (j=0; j<IDELEMS(s_temp); j++)
915    {
916      if (s_temp->m[j]!=NULL) pSetCompP(s_temp->m[j],1);
917    }
918    k = si_max(k,1);
919  }
920  for (j=0; j<IDELEMS(s_temp); j++)
921  {
922    if (s_temp->m[j]!=NULL)
923    {
924      p = s_temp->m[j];
925      q = pOne();
926      //pGetCoeff(q)=nNeg(pGetCoeff(q));   //set q to -1
927      pSetComp(q,k+1+j);
928      pSetmComp(q);
929      while (pNext(p)) pIter(p);
930      pNext(p) = q;
931    }
932  }
933}
934
935/*2
936*computes a representation of the generators of submod with respect to those
937* of mod
938*/
939
940ideal idLift(ideal mod, ideal submod,ideal *rest, BOOLEAN goodShape,
941             BOOLEAN isSB, BOOLEAN divide, matrix *unit)
942{
943  int lsmod =id_RankFreeModule(submod,currRing), j, k;
944  int comps_to_add=0;
945  poly p;
946
947  if (idIs0(submod))
948  {
949    if (unit!=NULL)
950    {
951      *unit=mpNew(1,1);
952      MATELEM(*unit,1,1)=pOne();
953    }
954    if (rest!=NULL)
955    {
956      *rest=idInit(1,mod->rank);
957    }
958    return idInit(1,mod->rank);
959  }
960  if (idIs0(mod)) /* and not idIs0(submod) */
961  {
962    WerrorS("2nd module does not lie in the first");
963    return NULL;
964  }
965  if (unit!=NULL)
966  {
967    comps_to_add = IDELEMS(submod);
968    while ((comps_to_add>0) && (submod->m[comps_to_add-1]==NULL))
969      comps_to_add--;
970  }
971  k=si_max(id_RankFreeModule(mod,currRing),id_RankFreeModule(submod,currRing));
972  if  ((k!=0) && (lsmod==0)) lsmod=1;
973  k=si_max(k,(int)mod->rank);
974  if (k<submod->rank) { WarnS("rk(submod) > rk(mod) ?");k=submod->rank; }
975
976  ring orig_ring=currRing;
977  ring syz_ring=rAssure_SyzComp(orig_ring,TRUE);  rChangeCurrRing(syz_ring);
978  rSetSyzComp(k,syz_ring);
979
980  ideal s_mod, s_temp;
981  if (orig_ring != syz_ring)
982  {
983    s_mod = idrCopyR_NoSort(mod,orig_ring,syz_ring);
984    s_temp = idrCopyR_NoSort(submod,orig_ring,syz_ring);
985  }
986  else
987  {
988    s_mod = mod;
989    s_temp = idCopy(submod);
990  }
991  ideal s_h3;
992  if (isSB)
993  {
994    s_h3 = idCopy(s_mod);
995    idPrepareStd(s_h3, k+comps_to_add);
996  }
997  else
998  {
999    s_h3 = idPrepare(s_mod,(tHomog)FALSE,k+comps_to_add,NULL);
1000  }
1001  if (!goodShape)
1002  {
1003    for (j=0;j<IDELEMS(s_h3);j++)
1004    {
1005      if ((s_h3->m[j] != NULL) && (pMinComp(s_h3->m[j]) > k))
1006        p_Delete(&(s_h3->m[j]),currRing);
1007    }
1008  }
1009  idSkipZeroes(s_h3);
1010  if (lsmod==0)
1011  {
1012    for (j=IDELEMS(s_temp);j>0;j--)
1013    {
1014      if (s_temp->m[j-1]!=NULL)
1015        p_Shift(&(s_temp->m[j-1]),1,currRing);
1016    }
1017  }
1018  if (unit!=NULL)
1019  {
1020    for(j = 0;j<comps_to_add;j++)
1021    {
1022      p = s_temp->m[j];
1023      if (p!=NULL)
1024      {
1025        while (pNext(p)!=NULL) pIter(p);
1026        pNext(p) = pOne();
1027        pIter(p);
1028        pSetComp(p,1+j+k);
1029        pSetmComp(p);
1030        p = pNeg(p);
1031      }
1032    }
1033  }
1034  ideal s_result = kNF(s_h3,currQuotient,s_temp,k);
1035  s_result->rank = s_h3->rank;
1036  ideal s_rest = idInit(IDELEMS(s_result),k);
1037  idDelete(&s_h3);
1038  idDelete(&s_temp);
1039
1040  for (j=0;j<IDELEMS(s_result);j++)
1041  {
1042    if (s_result->m[j]!=NULL)
1043    {
1044      if (pGetComp(s_result->m[j])<=k)
1045      {
1046        if (!divide)
1047        {
1048          if (isSB)
1049          {
1050            WarnS("first module not a standardbasis\n"
1051              "// ** or second not a proper submodule");
1052          }
1053          else
1054            WerrorS("2nd module does not lie in the first");
1055          idDelete(&s_result);
1056          idDelete(&s_rest);
1057          s_result=idInit(IDELEMS(submod),submod->rank);
1058          break;
1059        }
1060        else
1061        {
1062          p = s_rest->m[j] = s_result->m[j];
1063          while ((pNext(p)!=NULL) && (pGetComp(pNext(p))<=k)) pIter(p);
1064          s_result->m[j] = pNext(p);
1065          pNext(p) = NULL;
1066        }
1067      }
1068      p_Shift(&(s_result->m[j]),-k,currRing);
1069      pNeg(s_result->m[j]);
1070    }
1071  }
1072  if ((lsmod==0) && (!idIs0(s_rest)))
1073  {
1074    for (j=IDELEMS(s_rest);j>0;j--)
1075    {
1076      if (s_rest->m[j-1]!=NULL)
1077      {
1078        p_Shift(&(s_rest->m[j-1]),-1,currRing);
1079        s_rest->m[j-1] = s_rest->m[j-1];
1080      }
1081    }
1082  }
1083  if(syz_ring!=orig_ring)
1084  {
1085    idDelete(&s_mod);
1086    rChangeCurrRing(orig_ring);
1087    s_result = idrMoveR_NoSort(s_result, syz_ring, orig_ring);
1088    s_rest = idrMoveR_NoSort(s_rest, syz_ring, orig_ring);
1089    rDelete(syz_ring);
1090  }
1091  if (rest!=NULL)
1092    *rest = s_rest;
1093  else
1094    idDelete(&s_rest);
1095//idPrint(s_result);
1096  if (unit!=NULL)
1097  {
1098    *unit=mpNew(comps_to_add,comps_to_add);
1099    int i;
1100    for(i=0;i<IDELEMS(s_result);i++)
1101    {
1102      poly p=s_result->m[i];
1103      poly q=NULL;
1104      while(p!=NULL)
1105      {
1106        if(pGetComp(p)<=comps_to_add)
1107        {
1108          pSetComp(p,0);
1109          if (q!=NULL)
1110          {
1111            pNext(q)=pNext(p);
1112          }
1113          else
1114          {
1115            pIter(s_result->m[i]);
1116          }
1117          pNext(p)=NULL;
1118          MATELEM(*unit,i+1,i+1)=pAdd(MATELEM(*unit,i+1,i+1),p);
1119          if(q!=NULL)   p=pNext(q);
1120          else          p=s_result->m[i];
1121        }
1122        else
1123        {
1124          q=p;
1125          pIter(p);
1126        }
1127      }
1128      p_Shift(&s_result->m[i],-comps_to_add,currRing);
1129    }
1130  }
1131  return s_result;
1132}
1133
1134/*2
1135*computes division of P by Q with remainder up to (w-weighted) degree n
1136*P, Q, and w are not changed
1137*/
1138void idLiftW(ideal P,ideal Q,int n,matrix &T, ideal &R,short *w)
1139{
1140  long N=0;
1141  int i;
1142  for(i=IDELEMS(Q)-1;i>=0;i--)
1143    if(w==NULL)
1144      N=si_max(N,p_Deg(Q->m[i],currRing));
1145    else
1146      N=si_max(N,p_DegW(Q->m[i],w,currRing));
1147  N+=n;
1148
1149  T=mpNew(IDELEMS(Q),IDELEMS(P));
1150  R=idInit(IDELEMS(P),P->rank);
1151
1152  for(i=IDELEMS(P)-1;i>=0;i--)
1153  {
1154    poly p;
1155    if(w==NULL)
1156      p=ppJet(P->m[i],N);
1157    else
1158      p=ppJetW(P->m[i],N,w);
1159
1160    int j=IDELEMS(Q)-1;
1161    while(p!=NULL)
1162    {
1163      if(pDivisibleBy(Q->m[j],p))
1164      {
1165        poly p0=p_DivideM(pHead(p),pHead(Q->m[j]),currRing);
1166        if(w==NULL)
1167          p=pJet(pSub(p,ppMult_mm(Q->m[j],p0)),N);
1168        else
1169          p=pJetW(pSub(p,ppMult_mm(Q->m[j],p0)),N,w);
1170        pNormalize(p);
1171        if(((w==NULL)&&(p_Deg(p0,currRing)>n))||((w!=NULL)&&(p_DegW(p0,w,currRing)>n)))
1172          p_Delete(&p0,currRing);
1173        else
1174          MATELEM(T,j+1,i+1)=pAdd(MATELEM(T,j+1,i+1),p0);
1175        j=IDELEMS(Q)-1;
1176      }
1177      else
1178      {
1179        if(j==0)
1180        {
1181          poly p0=p;
1182          pIter(p);
1183          pNext(p0)=NULL;
1184          if(((w==NULL)&&(p_Deg(p0,currRing)>n))
1185          ||((w!=NULL)&&(p_DegW(p0,w,currRing)>n)))
1186            p_Delete(&p0,currRing);
1187          else
1188            R->m[i]=pAdd(R->m[i],p0);
1189          j=IDELEMS(Q)-1;
1190        }
1191        else
1192          j--;
1193      }
1194    }
1195  }
1196}
1197
1198/*2
1199*computes the quotient of h1,h2 : internal routine for idQuot
1200*BEWARE: the returned ideals may contain incorrectly ordered polys !
1201*
1202*/
1203static ideal idInitializeQuot (ideal  h1, ideal h2, BOOLEAN h1IsStb,
1204                               BOOLEAN *addOnlyOne, int *kkmax)
1205{
1206  ideal temph1;
1207  poly     p,q = NULL;
1208  int i,l,ll,k,kkk,kmax;
1209  int j = 0;
1210  int k1 = id_RankFreeModule(h1,currRing);
1211  int k2 = id_RankFreeModule(h2,currRing);
1212  tHomog   hom=isNotHomog;
1213
1214  k=si_max(k1,k2);
1215  if (k==0)
1216    k = 1;
1217  if ((k2==0) && (k>1)) *addOnlyOne = FALSE;
1218
1219  intvec * weights;
1220  hom = (tHomog)idHomModule(h1,currQuotient,&weights);
1221  if /**addOnlyOne &&*/ (/*(*/ !h1IsStb /*)*/)
1222    temph1 = kStd(h1,currQuotient,hom,&weights,NULL);
1223  else
1224    temph1 = idCopy(h1);
1225  if (weights!=NULL) delete weights;
1226  idTest(temph1);
1227/*--- making a single vector from h2 ---------------------*/
1228  for (i=0; i<IDELEMS(h2); i++)
1229  {
1230    if (h2->m[i] != NULL)
1231    {
1232      p = pCopy(h2->m[i]);
1233      if (k2 == 0)
1234        p_Shift(&p,j*k+1,currRing);
1235      else
1236        p_Shift(&p,j*k,currRing);
1237      q = pAdd(q,p);
1238      j++;
1239    }
1240  }
1241  *kkmax = kmax = j*k+1;
1242/*--- adding a monomial for the result (syzygy) ----------*/
1243  p = q;
1244  while (pNext(p)!=NULL) pIter(p);
1245  pNext(p) = pOne();
1246  pIter(p);
1247  pSetComp(p,kmax);
1248  pSetmComp(p);
1249/*--- constructing the big matrix ------------------------*/
1250  ideal h4 = idInit(16,kmax+k-1);
1251  h4->m[0] = q;
1252  if (k2 == 0)
1253  {
1254    if (k > IDELEMS(h4))
1255    {
1256      pEnlargeSet(&(h4->m),IDELEMS(h4),k-IDELEMS(h4));
1257      IDELEMS(h4) = k;
1258    }
1259    for (i=1; i<k; i++)
1260    {
1261      if (h4->m[i-1]!=NULL)
1262      {
1263        p = pCopy_noCheck(h4->m[i-1]);
1264        p_Shift(&p,1,currRing);
1265        h4->m[i] = p;
1266      }
1267    }
1268  }
1269  idSkipZeroes(h4);
1270  kkk = IDELEMS(h4);
1271  i = IDELEMS(temph1);
1272  for (l=0; l<i; l++)
1273  {
1274    if(temph1->m[l]!=NULL)
1275    {
1276      for (ll=0; ll<j; ll++)
1277      {
1278        p = pCopy(temph1->m[l]);
1279        if (k1 == 0)
1280          p_Shift(&p,ll*k+1,currRing);
1281        else
1282          p_Shift(&p,ll*k,currRing);
1283        if (kkk >= IDELEMS(h4))
1284        {
1285          pEnlargeSet(&(h4->m),IDELEMS(h4),16);
1286          IDELEMS(h4) += 16;
1287        }
1288        h4->m[kkk] = p;
1289        kkk++;
1290      }
1291    }
1292  }
1293/*--- if h2 goes in as single vector - the h1-part is just SB ---*/
1294  if (*addOnlyOne)
1295  {
1296    idSkipZeroes(h4);
1297    p = h4->m[0];
1298    for (i=0;i<IDELEMS(h4)-1;i++)
1299    {
1300      h4->m[i] = h4->m[i+1];
1301    }
1302    h4->m[IDELEMS(h4)-1] = p;
1303    si_opt_1 |= Sy_bit(OPT_SB_1);
1304  }
1305  idDelete(&temph1);
1306  return h4;
1307}
1308/*2
1309*computes the quotient of h1,h2
1310*/
1311ideal idQuot (ideal  h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN resultIsIdeal)
1312{
1313  // first check for special case h1:(0)
1314  if (idIs0(h2))
1315  {
1316    ideal res;
1317    if (resultIsIdeal)
1318    {
1319      res = idInit(1,1);
1320      res->m[0] = pOne();
1321    }
1322    else
1323      res = idFreeModule(h1->rank);
1324    return res;
1325  }
1326  BITSET old_test1;
1327  SI_SAVE_OPT1(old_test1);
1328  int i, kmax;
1329  BOOLEAN  addOnlyOne=TRUE;
1330  tHomog   hom=isNotHomog;
1331  intvec * weights1;
1332
1333  ideal s_h4 = idInitializeQuot (h1,h2,h1IsStb,&addOnlyOne,&kmax);
1334
1335  hom = (tHomog)idHomModule(s_h4,currQuotient,&weights1);
1336
1337  ring orig_ring=currRing;
1338  ring syz_ring=rAssure_SyzComp(orig_ring,TRUE);  rChangeCurrRing(syz_ring);
1339  rSetSyzComp(kmax-1,syz_ring);
1340  if (orig_ring!=syz_ring)
1341  //  s_h4 = idrMoveR_NoSort(s_h4,orig_ring, syz_ring);
1342    s_h4 = idrMoveR(s_h4,orig_ring, syz_ring);
1343  idTest(s_h4);
1344  #if 0
1345  void ipPrint_MA0(matrix m, const char *name);
1346  matrix m=idModule2Matrix(idCopy(s_h4));
1347  PrintS("start:\n");
1348  ipPrint_MA0(m,"Q");
1349  idDelete((ideal *)&m);
1350  PrintS("last elem:");wrp(s_h4->m[IDELEMS(s_h4)-1]);PrintLn();
1351  #endif
1352  ideal s_h3;
1353  if (addOnlyOne)
1354  {
1355    s_h3 = kStd(s_h4,currQuotient,hom,&weights1,NULL,0/*kmax-1*/,IDELEMS(s_h4)-1);
1356  }
1357  else
1358  {
1359    s_h3 = kStd(s_h4,currQuotient,hom,&weights1,NULL,kmax-1);
1360  }
1361  SI_RESTORE_OPT1(old_test1);
1362  #if 0
1363  // only together with the above debug stuff
1364  idSkipZeroes(s_h3);
1365  m=idModule2Matrix(idCopy(s_h3));
1366  Print("result, kmax=%d:\n",kmax);
1367  ipPrint_MA0(m,"S");
1368  idDelete((ideal *)&m);
1369  #endif
1370  idTest(s_h3);
1371  if (weights1!=NULL) delete weights1;
1372  idDelete(&s_h4);
1373
1374  for (i=0;i<IDELEMS(s_h3);i++)
1375  {
1376    if ((s_h3->m[i]!=NULL) && (pGetComp(s_h3->m[i])>=kmax))
1377    {
1378      if (resultIsIdeal)
1379        p_Shift(&s_h3->m[i],-kmax,currRing);
1380      else
1381        p_Shift(&s_h3->m[i],-kmax+1,currRing);
1382    }
1383    else
1384      p_Delete(&s_h3->m[i],currRing);
1385  }
1386  if (resultIsIdeal)
1387    s_h3->rank = 1;
1388  else
1389    s_h3->rank = h1->rank;
1390  if(syz_ring!=orig_ring)
1391  {
1392    rChangeCurrRing(orig_ring);
1393    s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
1394    rDelete(syz_ring);
1395  }
1396  idSkipZeroes(s_h3);
1397  idTest(s_h3);
1398  return s_h3;
1399}
1400
1401/*2
1402* eliminate delVar (product of vars) in h1
1403*/
1404ideal idElimination (ideal h1,poly delVar,intvec *hilb)
1405{
1406  int    i,j=0,k,l;
1407  ideal  h,hh, h3;
1408  int    *ord,*block0,*block1;
1409  int    ordersize=2;
1410  int    **wv;
1411  tHomog hom;
1412  intvec * w;
1413  ring tmpR;
1414  ring origR = currRing;
1415
1416  if (delVar==NULL)
1417  {
1418    return idCopy(h1);
1419  }
1420  if ((currQuotient!=NULL) && rIsPluralRing(origR))
1421  {
1422    WerrorS("cannot eliminate in a qring");
1423    return NULL;
1424  }
1425  if (idIs0(h1)) return idInit(1,h1->rank);
1426#ifdef HAVE_PLURAL
1427  if (rIsPluralRing(origR))
1428    /* in the NC case, we have to check the admissibility of */
1429    /* the subalgebra to be intersected with */
1430  {
1431    if ((ncRingType(origR) != nc_skew) && (ncRingType(origR) != nc_exterior)) /* in (quasi)-commutative algebras every subalgebra is admissible */
1432    {
1433      if (nc_CheckSubalgebra(delVar,origR))
1434      {
1435        WerrorS("no elimination is possible: subalgebra is not admissible");
1436        return NULL;
1437      }
1438    }
1439  }
1440#endif
1441  hom=(tHomog)idHomModule(h1,NULL,&w); //sets w to weight vector or NULL
1442  h3=idInit(16,h1->rank);
1443  for (k=0;; k++)
1444  {
1445    if (origR->order[k]!=0) ordersize++;
1446    else break;
1447  }
1448#if 0
1449  if (rIsPluralRing(origR)) // we have too keep the odering: it may be needed
1450                            // for G-algebra
1451  {
1452    for (k=0;k<ordersize-1; k++)
1453    {
1454      block0[k+1] = origR->block0[k];
1455      block1[k+1] = origR->block1[k];
1456      ord[k+1] = origR->order[k];
1457      if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
1458    }
1459  }
1460  else
1461  {
1462    block0[1] = 1;
1463    block1[1] = (currRing->N);
1464    if (origR->OrdSgn==1) ord[1] = ringorder_wp;
1465    else                  ord[1] = ringorder_ws;
1466    wv[1]=(int*)omAlloc0((currRing->N)*sizeof(int));
1467    double wNsqr = (double)2.0 / (double)(currRing->N);
1468    wFunctional = wFunctionalBuch;
1469    int  *x= (int * )omAlloc(2 * ((currRing->N) + 1) * sizeof(int));
1470    int sl=IDELEMS(h1) - 1;
1471    wCall(h1->m, sl, x, wNsqr);
1472    for (sl = (currRing->N); sl!=0; sl--)
1473      wv[1][sl-1] = x[sl + (currRing->N) + 1];
1474    omFreeSize((ADDRESS)x, 2 * ((currRing->N) + 1) * sizeof(int));
1475
1476    ord[2]=ringorder_C;
1477    ord[3]=0;
1478  }
1479#else
1480#endif
1481  if ((hom==TRUE) && (origR->OrdSgn==1) && (!rIsPluralRing(origR)))
1482  {
1483    #if 1
1484    // we change to an ordering:
1485    // aa(1,1,1,...,0,0,0),wp(...),C
1486    // this seems to be better than version 2 below,
1487    // according to Tst/../elimiate_[3568].tat (- 17 %)
1488    ord=(int*)omAlloc0(4*sizeof(int));
1489    block0=(int*)omAlloc0(4*sizeof(int));
1490    block1=(int*)omAlloc0(4*sizeof(int));
1491    wv=(int**) omAlloc0(4*sizeof(int**));
1492    block0[0] = block0[1] = 1;
1493    block1[0] = block1[1] = rVar(origR);
1494    wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1495    // use this special ordering: like ringorder_a, except that pFDeg, pWeights
1496    // ignore it
1497    ord[0] = ringorder_aa;
1498    for (j=0;j<rVar(origR);j++)
1499      if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
1500    BOOLEAN wp=FALSE;
1501    for (j=0;j<rVar(origR);j++)
1502      if (pWeight(j+1,origR)!=1) { wp=TRUE;break; }
1503    if (wp)
1504    {
1505      wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1506      for (j=0;j<rVar(origR);j++)
1507        wv[1][j]=pWeight(j+1,origR);
1508      ord[1] = ringorder_wp;
1509    }
1510    else
1511      ord[1] = ringorder_dp;
1512    #else
1513    // we change to an ordering:
1514    // a(w1,...wn),wp(1,...0.....),C
1515    ord=(int*)omAlloc0(4*sizeof(int));
1516    block0=(int*)omAlloc0(4*sizeof(int));
1517    block1=(int*)omAlloc0(4*sizeof(int));
1518    wv=(int**) omAlloc0(4*sizeof(int**));
1519    block0[0] = block0[1] = 1;
1520    block1[0] = block1[1] = rVar(origR);
1521    wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1522    wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1523    ord[0] = ringorder_a;
1524    for (j=0;j<rVar(origR);j++)
1525      wv[0][j]=pWeight(j+1,origR);
1526    ord[1] = ringorder_wp;
1527    for (j=0;j<rVar(origR);j++)
1528      if (pGetExp(delVar,j+1)!=0) wv[1][j]=1;
1529    #endif
1530    ord[2] = ringorder_C;
1531    ord[3] = 0;
1532  }
1533  else
1534  {
1535    // we change to an ordering:
1536    // aa(....),orig_ordering
1537    ord=(int*)omAlloc0(ordersize*sizeof(int));
1538    block0=(int*)omAlloc0(ordersize*sizeof(int));
1539    block1=(int*)omAlloc0(ordersize*sizeof(int));
1540    wv=(int**) omAlloc0(ordersize*sizeof(int**));
1541    for (k=0;k<ordersize-1; k++)
1542    {
1543      block0[k+1] = origR->block0[k];
1544      block1[k+1] = origR->block1[k];
1545      ord[k+1] = origR->order[k];
1546      if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
1547    }
1548    block0[0] = 1;
1549    block1[0] = rVar(origR);
1550    wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
1551    for (j=0;j<rVar(origR);j++)
1552      if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
1553    // use this special ordering: like ringorder_a, except that pFDeg, pWeights
1554    // ignore it
1555    ord[0] = ringorder_aa;
1556  }
1557  // fill in tmp ring to get back the data later on
1558  tmpR  = rCopy0(origR,FALSE,FALSE); // qring==NULL
1559  //rUnComplete(tmpR);
1560  tmpR->p_Procs=NULL;
1561  tmpR->order = ord;
1562  tmpR->block0 = block0;
1563  tmpR->block1 = block1;
1564  tmpR->wvhdl = wv;
1565  rComplete(tmpR, 1);
1566
1567#ifdef HAVE_PLURAL
1568  /* update nc structure on tmpR */
1569  if (rIsPluralRing(origR))
1570  {
1571    if ( nc_rComplete(origR, tmpR, false) ) // no quotient ideal!
1572    {
1573      Werror("no elimination is possible: ordering condition is violated");
1574      // cleanup
1575      rDelete(tmpR);
1576      if (w!=NULL)
1577        delete w;
1578      return NULL;
1579    }
1580  }
1581#endif
1582  // change into the new ring
1583  //pChangeRing((currRing->N),currRing->OrdSgn,ord,block0,block1,wv);
1584  rChangeCurrRing(tmpR);
1585
1586  //h = idInit(IDELEMS(h1),h1->rank);
1587  // fetch data from the old ring
1588  //for (k=0;k<IDELEMS(h1);k++) h->m[k] = prCopyR( h1->m[k], origR);
1589  h=idrCopyR(h1,origR,currRing);
1590  if (origR->qideal!=NULL)
1591  {
1592    WarnS("eliminate in q-ring: experimental");
1593    ideal q=idrCopyR(origR->qideal,origR,currRing);
1594    ideal s=idSimpleAdd(h,q);
1595    idDelete(&h);
1596    idDelete(&q);
1597    h=s;
1598  }
1599  // compute kStd
1600#if 1
1601  //rWrite(tmpR);PrintLn();
1602  //BITSET save1;
1603  //SI_SAVE_OPT1(save1);
1604  //si_opt_1 |=1;
1605  //Print("h: %d gen, rk=%d\n",IDELEMS(h),h->rank);
1606  //extern char * showOption();
1607  //Print("%s\n",showOption());
1608  hh = kStd(h,NULL,hom,&w,hilb);
1609  //SI_RESTORE_OPT1(save1);
1610  idDelete(&h);
1611#else
1612  extern ideal kGroebner(ideal F, ideal Q);
1613  hh=kGroebner(h,NULL);
1614#endif
1615  // go back to the original ring
1616  rChangeCurrRing(origR);
1617  i = IDELEMS(hh)-1;
1618  while ((i >= 0) && (hh->m[i] == NULL)) i--;
1619  j = -1;
1620  // fetch data from temp ring
1621  for (k=0; k<=i; k++)
1622  {
1623    l=(currRing->N);
1624    while ((l>0) && (p_GetExp( hh->m[k],l,tmpR)*pGetExp(delVar,l)==0)) l--;
1625    if (l==0)
1626    {
1627      j++;
1628      if (j >= IDELEMS(h3))
1629      {
1630        pEnlargeSet(&(h3->m),IDELEMS(h3),16);
1631        IDELEMS(h3) += 16;
1632      }
1633      h3->m[j] = prMoveR( hh->m[k], tmpR,origR);
1634      hh->m[k] = NULL;
1635    }
1636  }
1637  id_Delete(&hh, tmpR);
1638  idSkipZeroes(h3);
1639  rDelete(tmpR);
1640  if (w!=NULL)
1641    delete w;
1642  return h3;
1643}
1644
1645/*2
1646* compute the which-th ar-minor of the matrix a
1647*/
1648poly idMinor(matrix a, int ar, unsigned long which, ideal R)
1649{
1650  int     i,j/*,k,size*/;
1651  unsigned long curr;
1652  int *rowchoise,*colchoise;
1653  BOOLEAN rowch,colch;
1654  // ideal result;
1655  matrix tmp;
1656  poly p,q;
1657
1658  i = binom(a->rows(),ar);
1659  j = binom(a->cols(),ar);
1660
1661  rowchoise=(int *)omAlloc(ar*sizeof(int));
1662  colchoise=(int *)omAlloc(ar*sizeof(int));
1663  // if ((i>512) || (j>512) || (i*j >512)) size=512;
1664  // else size=i*j;
1665  // result=idInit(size,1);
1666  tmp=mpNew(ar,ar);
1667  // k = 0; /* the index in result*/
1668  curr = 0; /* index of current minor */
1669  idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
1670  while (!rowch)
1671  {
1672    idInitChoise(ar,1,a->cols(),&colch,colchoise);
1673    while (!colch)
1674    {
1675      if (curr == which)
1676      {
1677        for (i=1; i<=ar; i++)
1678        {
1679          for (j=1; j<=ar; j++)
1680          {
1681            MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
1682          }
1683        }
1684        p = mp_DetBareiss(tmp,currRing);
1685        if (p!=NULL)
1686        {
1687          if (R!=NULL)
1688          {
1689            q = p;
1690            p = kNF(R,currQuotient,q);
1691            p_Delete(&q,currRing);
1692          }
1693          /*delete the matrix tmp*/
1694          for (i=1; i<=ar; i++)
1695          {
1696            for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
1697          }
1698          idDelete((ideal*)&tmp);
1699          omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
1700          omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
1701          return (p);
1702        }
1703      }
1704      curr++;
1705      idGetNextChoise(ar,a->cols(),&colch,colchoise);
1706    }
1707    idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
1708  }
1709  return (poly) 1;
1710}
1711
1712#ifdef WITH_OLD_MINOR
1713/*2
1714* compute all ar-minors of the matrix a
1715*/
1716ideal idMinors(matrix a, int ar, ideal R)
1717{
1718  int     i,j,/*k,*/size;
1719  int *rowchoise,*colchoise;
1720  BOOLEAN rowch,colch;
1721  ideal result;
1722  matrix tmp;
1723  poly p,q;
1724
1725  i = binom(a->rows(),ar);
1726  j = binom(a->cols(),ar);
1727
1728  rowchoise=(int *)omAlloc(ar*sizeof(int));
1729  colchoise=(int *)omAlloc(ar*sizeof(int));
1730  if ((i>512) || (j>512) || (i*j >512)) size=512;
1731  else size=i*j;
1732  result=idInit(size,1);
1733  tmp=mpNew(ar,ar);
1734  // k = 0; /* the index in result*/
1735  idInitChoise(ar,1,a->rows(),&rowch,rowchoise);
1736  while (!rowch)
1737  {
1738    idInitChoise(ar,1,a->cols(),&colch,colchoise);
1739    while (!colch)
1740    {
1741      for (i=1; i<=ar; i++)
1742      {
1743        for (j=1; j<=ar; j++)
1744        {
1745          MATELEM(tmp,i,j) = MATELEM(a,rowchoise[i-1],colchoise[j-1]);
1746        }
1747      }
1748      p = mp_DetBareiss(tmp,vcurrRing);
1749      if (p!=NULL)
1750      {
1751        if (R!=NULL)
1752        {
1753          q = p;
1754          p = kNF(R,currQuotient,q);
1755          p_Delete(&q,currRing);
1756        }
1757        if (p!=NULL)
1758        {
1759          if (k>=size)
1760          {
1761            pEnlargeSet(&result->m,size,32);
1762            size += 32;
1763          }
1764          result->m[k] = p;
1765          k++;
1766        }
1767      }
1768      idGetNextChoise(ar,a->cols(),&colch,colchoise);
1769    }
1770    idGetNextChoise(ar,a->rows(),&rowch,rowchoise);
1771  }
1772  /*delete the matrix tmp*/
1773  for (i=1; i<=ar; i++)
1774  {
1775    for (j=1; j<=ar; j++) MATELEM(tmp,i,j) = NULL;
1776  }
1777  idDelete((ideal*)&tmp);
1778  if (k==0)
1779  {
1780    k=1;
1781    result->m[0]=NULL;
1782  }
1783  omFreeSize((ADDRESS)rowchoise,ar*sizeof(int));
1784  omFreeSize((ADDRESS)colchoise,ar*sizeof(int));
1785  pEnlargeSet(&result->m,size,k-size);
1786  IDELEMS(result) = k;
1787  return (result);
1788}
1789#else
1790/*2
1791* compute all ar-minors of the matrix a
1792* the caller of mpRecMin
1793* the elements of the result are not in R (if R!=NULL)
1794*/
1795ideal idMinors(matrix a, int ar, ideal R)
1796{
1797  int elems=0;
1798  int r=a->nrows,c=a->ncols;
1799  int i;
1800  matrix b;
1801  ideal result,h;
1802  ring origR=currRing;
1803  ring tmpR;
1804  long bound;
1805
1806  if((ar<=0) || (ar>r) || (ar>c))
1807  {
1808    Werror("%d-th minor, matrix is %dx%d",ar,r,c);
1809    return NULL;
1810  }
1811  h = id_Matrix2Module(mp_Copy(a,origR),origR);
1812  bound = sm_ExpBound(h,c,r,ar,origR);
1813  idDelete(&h);
1814  tmpR=sm_RingChange(origR,bound);
1815  b = mpNew(r,c);
1816  for (i=r*c-1;i>=0;i--)
1817  {
1818    if (a->m[i])
1819      b->m[i] = prCopyR(a->m[i],origR,tmpR);
1820  }
1821  if (R!=NULL)
1822  {
1823    R = idrCopyR(R,origR,tmpR);
1824    //if (ar>1) // otherwise done in mpMinorToResult
1825    //{
1826    //  matrix bb=(matrix)kNF(R,currQuotient,(ideal)b);
1827    //  bb->rank=b->rank; bb->nrows=b->nrows; bb->ncols=b->ncols;
1828    //  idDelete((ideal*)&b); b=bb;
1829    //}
1830  }
1831  result=idInit(32,1);
1832  if(ar>1) mp_RecMin(ar-1,result,elems,b,r,c,NULL,R,tmpR);
1833  else mp_MinorToResult(result,elems,b,r,c,R,tmpR);
1834  idDelete((ideal *)&b);
1835  if (R!=NULL) idDelete(&R);
1836  idSkipZeroes(result);
1837  rChangeCurrRing(origR);
1838  result = idrMoveR(result,tmpR,origR);
1839  sm_KillModifiedRing(tmpR);
1840  idTest(result);
1841  return result;
1842}
1843#endif
1844
1845/*2
1846*returns TRUE if id1 is a submodule of id2
1847*/
1848BOOLEAN idIsSubModule(ideal id1,ideal id2)
1849{
1850  int i;
1851  poly p;
1852
1853  if (idIs0(id1)) return TRUE;
1854  for (i=0;i<IDELEMS(id1);i++)
1855  {
1856    if (id1->m[i] != NULL)
1857    {
1858      p = kNF(id2,currQuotient,id1->m[i]);
1859      if (p != NULL)
1860      {
1861        p_Delete(&p,currRing);
1862        return FALSE;
1863      }
1864    }
1865  }
1866  return TRUE;
1867}
1868
1869BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
1870{
1871  if ((Q!=NULL) && (!idHomIdeal(Q,NULL)))  { PrintS(" Q not hom\n"); return FALSE;}
1872  if (idIs0(m)) return TRUE;
1873
1874  int cmax=-1;
1875  int i;
1876  poly p=NULL;
1877  int length=IDELEMS(m);
1878  polyset P=m->m;
1879  for (i=length-1;i>=0;i--)
1880  {
1881    p=P[i];
1882    if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
1883  }
1884  if (w != NULL)
1885  if (w->length()+1 < cmax)
1886  {
1887    // Print("length: %d - %d \n", w->length(),cmax);
1888    return FALSE;
1889  }
1890
1891  if(w!=NULL)
1892    p_SetModDeg(w, currRing);
1893
1894  for (i=length-1;i>=0;i--)
1895  {
1896    p=P[i];
1897    if (p!=NULL)
1898    {
1899      int d=currRing->pFDeg(p,currRing);
1900      loop
1901      {
1902        pIter(p);
1903        if (p==NULL) break;
1904        if (d!=currRing->pFDeg(p,currRing))
1905        {
1906          //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
1907          if(w!=NULL)
1908            p_SetModDeg(NULL, currRing);
1909          return FALSE;
1910        }
1911      }
1912    }
1913  }
1914
1915  if(w!=NULL)
1916    p_SetModDeg(NULL, currRing);
1917
1918  return TRUE;
1919}
1920
1921ideal idSeries(int n,ideal M,matrix U,intvec *w)
1922{
1923  for(int i=IDELEMS(M)-1;i>=0;i--)
1924  {
1925    if(U==NULL)
1926      M->m[i]=pSeries(n,M->m[i],NULL,w);
1927    else
1928    {
1929      M->m[i]=pSeries(n,M->m[i],MATELEM(U,i+1,i+1),w);
1930      MATELEM(U,i+1,i+1)=NULL;
1931    }
1932  }
1933  if(U!=NULL)
1934    idDelete((ideal*)&U);
1935  return M;
1936}
1937
1938matrix idDiff(matrix i, int k)
1939{
1940  int e=MATCOLS(i)*MATROWS(i);
1941  matrix r=mpNew(MATROWS(i),MATCOLS(i));
1942  r->rank=i->rank;
1943  int j;
1944  for(j=0; j<e; j++)
1945  {
1946    r->m[j]=pDiff(i->m[j],k);
1947  }
1948  return r;
1949}
1950
1951matrix idDiffOp(ideal I, ideal J,BOOLEAN multiply)
1952{
1953  matrix r=mpNew(IDELEMS(I),IDELEMS(J));
1954  int i,j;
1955  for(i=0; i<IDELEMS(I); i++)
1956  {
1957    for(j=0; j<IDELEMS(J); j++)
1958    {
1959      MATELEM(r,i+1,j+1)=pDiffOp(I->m[i],J->m[j],multiply);
1960    }
1961  }
1962  return r;
1963}
1964
1965/*3
1966*handles for some ideal operations the ring/syzcomp managment
1967*returns all syzygies (componentwise-)shifted by -syzcomp
1968*or -syzcomp-1 (in case of ideals as input)
1969static ideal idHandleIdealOp(ideal arg,int syzcomp,int isIdeal=FALSE)
1970{
1971  ring orig_ring=currRing;
1972  ring syz_ring=rAssure_SyzComp(orig_ring, TRUE); rChangeCurrRing(syz_ring);
1973  rSetSyzComp(length, syz_ring);
1974
1975  ideal s_temp;
1976  if (orig_ring!=syz_ring)
1977    s_temp=idrMoveR_NoSort(arg,orig_ring, syz_ring);
1978  else
1979    s_temp=arg;
1980
1981  ideal s_temp1 = kStd(s_temp,currQuotient,testHomog,&w,NULL,length);
1982  if (w!=NULL) delete w;
1983
1984  if (syz_ring!=orig_ring)
1985  {
1986    idDelete(&s_temp);
1987    rChangeCurrRing(orig_ring);
1988  }
1989
1990  idDelete(&temp);
1991  ideal temp1=idRingCopy(s_temp1,syz_ring);
1992
1993  if (syz_ring!=orig_ring)
1994  {
1995    rChangeCurrRing(syz_ring);
1996    idDelete(&s_temp1);
1997    rChangeCurrRing(orig_ring);
1998    rDelete(syz_ring);
1999  }
2000
2001  for (i=0;i<IDELEMS(temp1);i++)
2002  {
2003    if ((temp1->m[i]!=NULL)
2004    && (pGetComp(temp1->m[i])<=length))
2005    {
2006      pDelete(&(temp1->m[i]));
2007    }
2008    else
2009    {
2010      p_Shift(&(temp1->m[i]),-length,currRing);
2011    }
2012  }
2013  temp1->rank = rk;
2014  idSkipZeroes(temp1);
2015
2016  return temp1;
2017}
2018*/
2019/*2
2020* represents (h1+h2)/h2=h1/(h1 intersect h2)
2021*/
2022//ideal idModulo (ideal h2,ideal h1)
2023ideal idModulo (ideal h2,ideal h1, tHomog hom, intvec ** w)
2024{
2025  intvec *wtmp=NULL;
2026
2027  int i,k,rk,flength=0,slength,length;
2028  poly p,q;
2029
2030  if (idIs0(h2))
2031    return idFreeModule(si_max(1,h2->ncols));
2032  if (!idIs0(h1))
2033    flength = id_RankFreeModule(h1,currRing);
2034  slength = id_RankFreeModule(h2,currRing);
2035  length  = si_max(flength,slength);
2036  if (length==0)
2037  {
2038    length = 1;
2039  }
2040  ideal temp = idInit(IDELEMS(h2),length+IDELEMS(h2));
2041  if ((w!=NULL)&&((*w)!=NULL))
2042  {
2043    //Print("input weights:");(*w)->show(1);PrintLn();
2044    int d;
2045    int k;
2046    wtmp=new intvec(length+IDELEMS(h2));
2047    for (i=0;i<length;i++)
2048      ((*wtmp)[i])=(**w)[i];
2049    for (i=0;i<IDELEMS(h2);i++)
2050    {
2051      poly p=h2->m[i];
2052      if (p!=NULL)
2053      {
2054        d = p_Deg(p,currRing);
2055        k= pGetComp(p);
2056        if (slength>0) k--;
2057        d +=((**w)[k]);
2058        ((*wtmp)[i+length]) = d;
2059      }
2060    }
2061    //Print("weights:");wtmp->show(1);PrintLn();
2062  }
2063  for (i=0;i<IDELEMS(h2);i++)
2064  {
2065    temp->m[i] = pCopy(h2->m[i]);
2066    q = pOne();
2067    pSetComp(q,i+1+length);
2068    pSetmComp(q);
2069    if(temp->m[i]!=NULL)
2070    {
2071      if (slength==0) p_Shift(&(temp->m[i]),1,currRing);
2072      p = temp->m[i];
2073      while (pNext(p)!=NULL) pIter(p);
2074      pNext(p) = q;
2075    }
2076    else
2077      temp->m[i]=q;
2078  }
2079  rk = k = IDELEMS(h2);
2080  if (!idIs0(h1))
2081  {
2082    pEnlargeSet(&(temp->m),IDELEMS(temp),IDELEMS(h1));
2083    IDELEMS(temp) += IDELEMS(h1);
2084    for (i=0;i<IDELEMS(h1);i++)
2085    {
2086      if (h1->m[i]!=NULL)
2087      {
2088        temp->m[k] = pCopy(h1->m[i]);
2089        if (flength==0) p_Shift(&(temp->m[k]),1,currRing);
2090        k++;
2091      }
2092    }
2093  }
2094
2095  ring orig_ring=currRing;
2096  ring syz_ring=rAssure_SyzComp(orig_ring, TRUE); rChangeCurrRing(syz_ring);
2097  rSetSyzComp(length, syz_ring);
2098  ideal s_temp;
2099
2100  if (syz_ring != orig_ring)
2101  {
2102    s_temp = idrMoveR_NoSort(temp, orig_ring, syz_ring);
2103  }
2104  else
2105  {
2106    s_temp = temp;
2107  }
2108
2109  idTest(s_temp);
2110  ideal s_temp1 = kStd(s_temp,currQuotient,hom,&wtmp,NULL,length);
2111
2112  //if (wtmp!=NULL)  Print("output weights:");wtmp->show(1);PrintLn();
2113  if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
2114  {
2115    delete *w;
2116    *w=new intvec(IDELEMS(h2));
2117    for (i=0;i<IDELEMS(h2);i++)
2118      ((**w)[i])=(*wtmp)[i+length];
2119  }
2120  if (wtmp!=NULL) delete wtmp;
2121
2122  for (i=0;i<IDELEMS(s_temp1);i++)
2123  {
2124    if ((s_temp1->m[i]!=NULL)
2125    && (((int)pGetComp(s_temp1->m[i]))<=length))
2126    {
2127      p_Delete(&(s_temp1->m[i]),currRing);
2128    }
2129    else
2130    {
2131      p_Shift(&(s_temp1->m[i]),-length,currRing);
2132    }
2133  }
2134  s_temp1->rank = rk;
2135  idSkipZeroes(s_temp1);
2136
2137  if (syz_ring!=orig_ring)
2138  {
2139    rChangeCurrRing(orig_ring);
2140    s_temp1 = idrMoveR_NoSort(s_temp1, syz_ring, orig_ring);
2141    rDelete(syz_ring);
2142    // Hmm ... here seems to be a memory leak
2143    // However, simply deleting it causes memory trouble
2144    // idDelete(&s_temp);
2145  }
2146  else
2147  {
2148    idDelete(&temp);
2149  }
2150  idTest(s_temp1);
2151  return s_temp1;
2152}
2153
2154/*
2155*computes module-weights for liftings of homogeneous modules
2156*/
2157intvec * idMWLift(ideal mod,intvec * weights)
2158{
2159  if (idIs0(mod)) return new intvec(2);
2160  int i=IDELEMS(mod);
2161  while ((i>0) && (mod->m[i-1]==NULL)) i--;
2162  intvec *result = new intvec(i+1);
2163  while (i>0)
2164  {
2165    (*result)[i]=currRing->pFDeg(mod->m[i],currRing)+(*weights)[pGetComp(mod->m[i])];
2166  }
2167  return result;
2168}
2169
2170/*2
2171*sorts the kbase for idCoef* in a special way (lexicographically
2172*with x_max,...,x_1)
2173*/
2174ideal idCreateSpecialKbase(ideal kBase,intvec ** convert)
2175{
2176  int i;
2177  ideal result;
2178
2179  if (idIs0(kBase)) return NULL;
2180  result = idInit(IDELEMS(kBase),kBase->rank);
2181  *convert = idSort(kBase,FALSE);
2182  for (i=0;i<(*convert)->length();i++)
2183  {
2184    result->m[i] = pCopy(kBase->m[(**convert)[i]-1]);
2185  }
2186  return result;
2187}
2188
2189/*2
2190*returns the index of a given monom in the list of the special kbase
2191*/
2192int idIndexOfKBase(poly monom, ideal kbase)
2193{
2194  int j=IDELEMS(kbase);
2195
2196  while ((j>0) && (kbase->m[j-1]==NULL)) j--;
2197  if (j==0) return -1;
2198  int i=(currRing->N);
2199  while (i>0)
2200  {
2201    loop
2202    {
2203      if (pGetExp(monom,i)>pGetExp(kbase->m[j-1],i)) return -1;
2204      if (pGetExp(monom,i)==pGetExp(kbase->m[j-1],i)) break;
2205      j--;
2206      if (j==0) return -1;
2207    }
2208    if (i==1)
2209    {
2210      while(j>0)
2211      {
2212        if (pGetComp(monom)==pGetComp(kbase->m[j-1])) return j-1;
2213        if (pGetComp(monom)>pGetComp(kbase->m[j-1])) return -1;
2214        j--;
2215      }
2216    }
2217    i--;
2218  }
2219  return -1;
2220}
2221
2222/*2
2223*decomposes the monom in a part of coefficients described by the
2224*complement of how and a monom in variables occuring in how, the
2225*index of which in kbase is returned as integer pos (-1 if it don't
2226*exists)
2227*/
2228poly idDecompose(poly monom, poly how, ideal kbase, int * pos)
2229{
2230  int i;
2231  poly coeff=pOne(), base=pOne();
2232
2233  for (i=1;i<=(currRing->N);i++)
2234  {
2235    if (pGetExp(how,i)>0)
2236    {
2237      pSetExp(base,i,pGetExp(monom,i));
2238    }
2239    else
2240    {
2241      pSetExp(coeff,i,pGetExp(monom,i));
2242    }
2243  }
2244  pSetComp(base,pGetComp(monom));
2245  pSetm(base);
2246  pSetCoeff(coeff,nCopy(pGetCoeff(monom)));
2247  pSetm(coeff);
2248  *pos = idIndexOfKBase(base,kbase);
2249  if (*pos<0)
2250    p_Delete(&coeff,currRing);
2251  p_Delete(&base,currRing);
2252  return coeff;
2253}
2254
2255/*2
2256*returns a matrix A of coefficients with kbase*A=arg
2257*if all monomials in variables of how occur in kbase
2258*the other are deleted
2259*/
2260matrix idCoeffOfKBase(ideal arg, ideal kbase, poly how)
2261{
2262  matrix result;
2263  ideal tempKbase;
2264  poly p,q;
2265  intvec * convert;
2266  int i=IDELEMS(kbase),j=IDELEMS(arg),k,pos;
2267#if 0
2268  while ((i>0) && (kbase->m[i-1]==NULL)) i--;
2269  if (idIs0(arg))
2270    return mpNew(i,1);
2271  while ((j>0) && (arg->m[j-1]==NULL)) j--;
2272  result = mpNew(i,j);
2273#else
2274  result = mpNew(i, j);
2275  while ((j>0) && (arg->m[j-1]==NULL)) j--;
2276#endif
2277
2278  tempKbase = idCreateSpecialKbase(kbase,&convert);
2279  for (k=0;k<j;k++)
2280  {
2281    p = arg->m[k];
2282    while (p!=NULL)
2283    {
2284      q = idDecompose(p,how,tempKbase,&pos);
2285      if (pos>=0)
2286      {
2287        MATELEM(result,(*convert)[pos],k+1) =
2288            pAdd(MATELEM(result,(*convert)[pos],k+1),q);
2289      }
2290      else
2291        p_Delete(&q,currRing);
2292      pIter(p);
2293    }
2294  }
2295  idDelete(&tempKbase);
2296  return result;
2297}
2298
2299static void idDeleteComps(ideal arg,int* red_comp,int del)
2300// red_comp is an array [0..args->rank]
2301{
2302  int i,j;
2303  poly p;
2304
2305  for (i=IDELEMS(arg)-1;i>=0;i--)
2306  {
2307    p = arg->m[i];
2308    while (p!=NULL)
2309    {
2310      j = pGetComp(p);
2311      if (red_comp[j]!=j)
2312      {
2313        pSetComp(p,red_comp[j]);
2314        pSetmComp(p);
2315      }
2316      pIter(p);
2317    }
2318  }
2319  (arg->rank) -= del;
2320}
2321
2322/*2
2323* returns the presentation of an isomorphic, minimally
2324* embedded  module (arg represents the quotient!)
2325*/
2326ideal idMinEmbedding(ideal arg,BOOLEAN inPlace, intvec **w)
2327{
2328  if (idIs0(arg)) return idInit(1,arg->rank);
2329  int i,next_gen,next_comp;
2330  ideal res=arg;
2331  if (!inPlace) res = idCopy(arg);
2332  res->rank=si_max(res->rank,id_RankFreeModule(res,currRing));
2333  int *red_comp=(int*)omAlloc((res->rank+1)*sizeof(int));
2334  for (i=res->rank;i>=0;i--) red_comp[i]=i;
2335
2336  int del=0;
2337  loop
2338  {
2339    next_gen = id_ReadOutPivot(res, &next_comp, currRing);
2340    if (next_gen<0) break;
2341    del++;
2342    syGaussForOne(res,next_gen,next_comp,0,IDELEMS(res));
2343    for(i=next_comp+1;i<=arg->rank;i++) red_comp[i]--;
2344    if ((w !=NULL)&&(*w!=NULL))
2345    {
2346      for(i=next_comp;i<(*w)->length();i++) (**w)[i-1]=(**w)[i];
2347    }
2348  }
2349
2350  idDeleteComps(res,red_comp,del);
2351  idSkipZeroes(res);
2352  omFree(red_comp);
2353
2354  if ((w !=NULL)&&(*w!=NULL) &&(del>0))
2355  {
2356    intvec *wtmp=new intvec((*w)->length()-del);
2357    for(i=0;i<res->rank;i++) (*wtmp)[i]=(**w)[i];
2358    delete *w;
2359    *w=wtmp;
2360  }
2361  return res;
2362}
2363
2364#include <polys/clapsing.h>
2365
2366#if 0
2367poly id_GCD(poly f, poly g, const ring r)
2368{
2369  ring save_r=currRing;
2370  rChangeCurrRing(r);
2371  ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
2372  intvec *w = NULL;
2373  ideal S=idSyzygies(I,testHomog,&w);
2374  if (w!=NULL) delete w;
2375  poly gg=pTakeOutComp(&(S->m[0]),2);
2376  idDelete(&S);
2377  poly gcd_p=singclap_pdivide(f,gg,r);
2378  p_Delete(&gg,r);
2379  rChangeCurrRing(save_r);
2380  return gcd_p;
2381}
2382#else
2383poly id_GCD(poly f, poly g, const ring r)
2384{
2385  ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
2386  intvec *w = NULL;
2387
2388  ring save_r = currRing; rChangeCurrRing(r); ideal S=idSyzygies(I,testHomog,&w); rChangeCurrRing(save_r);
2389
2390  if (w!=NULL) delete w;
2391  poly gg=p_TakeOutComp(&(S->m[0]), 2, r);
2392  id_Delete(&S, r);
2393  poly gcd_p=singclap_pdivide(f,gg, r);
2394  p_Delete(&gg, r);
2395
2396  return gcd_p;
2397}
2398#endif
2399
2400#if 0
2401/*2
2402* xx,q: arrays of length 0..rl-1
2403* xx[i]: SB mod q[i]
2404* assume: char=0
2405* assume: q[i]!=0
2406* destroys xx
2407*/
2408ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring R)
2409{
2410  int cnt=IDELEMS(xx[0])*xx[0]->nrows;
2411  ideal result=idInit(cnt,xx[0]->rank);
2412  result->nrows=xx[0]->nrows; // for lifting matrices
2413  result->ncols=xx[0]->ncols; // for lifting matrices
2414  int i,j;
2415  poly r,h,hh,res_p;
2416  number *x=(number *)omAlloc(rl*sizeof(number));
2417  for(i=cnt-1;i>=0;i--)
2418  {
2419    res_p=NULL;
2420    loop
2421    {
2422      r=NULL;
2423      for(j=rl-1;j>=0;j--)
2424      {
2425        h=xx[j]->m[i];
2426        if ((h!=NULL)
2427        &&((r==NULL)||(p_LmCmp(r,h,R)==-1)))
2428          r=h;
2429      }
2430      if (r==NULL) break;
2431      h=p_Head(r, R);
2432      for(j=rl-1;j>=0;j--)
2433      {
2434        hh=xx[j]->m[i];
2435        if ((hh!=NULL) && (p_LmCmp(r,hh, R)==0))
2436        {
2437          x[j]=p_GetCoeff(hh, R);
2438          hh=p_LmFreeAndNext(hh, R);
2439          xx[j]->m[i]=hh;
2440        }
2441        else
2442          x[j]=n_Init(0, R->cf); // is R->cf really n_Q???, yes!
2443      }
2444
2445      number n=n_ChineseRemainder(x,q,rl, R->cf);
2446
2447      for(j=rl-1;j>=0;j--)
2448      {
2449        x[j]=NULL; // nlInit(0...) takes no memory
2450      }
2451      if (n_IsZero(n, R->cf)) p_Delete(&h, R);
2452      else
2453      {
2454        p_SetCoeff(h,n, R);
2455        //Print("new mon:");pWrite(h);
2456        res_p=p_Add_q(res_p, h, R);
2457      }
2458    }
2459    result->m[i]=res_p;
2460  }
2461  omFree(x);
2462  for(i=rl-1;i>=0;i--) id_Delete(&(xx[i]), R);
2463  omFree(xx);
2464  return result;
2465}
2466#endif
2467/* currently unsed:
2468ideal idChineseRemainder(ideal *xx, intvec *iv)
2469{
2470  int rl=iv->length();
2471  number *q=(number *)omAlloc(rl*sizeof(number));
2472  int i;
2473  for(i=0; i<rl; i++)
2474  {
2475    q[i]=nInit((*iv)[i]);
2476  }
2477  return idChineseRemainder(xx,q,rl);
2478}
2479*/
2480/*
2481 * lift ideal with coeffs over Z (mod N) to Q via Farey
2482 */
2483ideal id_Farey(ideal x, number N, const ring r)
2484{
2485  int cnt=IDELEMS(x)*x->nrows;
2486  ideal result=idInit(cnt,x->rank);
2487  result->nrows=x->nrows; // for lifting matrices
2488  result->ncols=x->ncols; // for lifting matrices
2489
2490  int i;
2491  for(i=cnt-1;i>=0;i--)
2492  {
2493    result->m[i]=p_Farey(x->m[i],N,r);
2494  }
2495  return result;
2496}
2497
2498
2499
2500
2501// uses glabl vars via pSetModDeg
2502/*
2503BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
2504{
2505  if ((Q!=NULL) && (!idHomIdeal(Q,NULL)))  { PrintS(" Q not hom\n"); return FALSE;}
2506  if (idIs0(m)) return TRUE;
2507
2508  int cmax=-1;
2509  int i;
2510  poly p=NULL;
2511  int length=IDELEMS(m);
2512  poly* P=m->m;
2513  for (i=length-1;i>=0;i--)
2514  {
2515    p=P[i];
2516    if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
2517  }
2518  if (w != NULL)
2519  if (w->length()+1 < cmax)
2520  {
2521    // Print("length: %d - %d \n", w->length(),cmax);
2522    return FALSE;
2523  }
2524
2525  if(w!=NULL)
2526    p_SetModDeg(w, currRing);
2527
2528  for (i=length-1;i>=0;i--)
2529  {
2530    p=P[i];
2531    poly q=p;
2532    if (p!=NULL)
2533    {
2534      int d=p_FDeg(p,currRing);
2535      loop
2536      {
2537        pIter(p);
2538        if (p==NULL) break;
2539        if (d!=p_FDeg(p,currRing))
2540        {
2541          //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
2542          if(w!=NULL)
2543            p_SetModDeg(NULL, currRing);
2544          return FALSE;
2545        }
2546      }
2547    }
2548  }
2549
2550  if(w!=NULL)
2551    p_SetModDeg(NULL, currRing);
2552
2553  return TRUE;
2554}
2555*/
2556
2557/// keeps the first k (>= 1) entries of the given ideal
2558/// (Note that the kept polynomials may be zero.)
2559void idKeepFirstK(ideal id, const int k)
2560{
2561   for (int i = IDELEMS(id)-1; i >= k; i--)
2562   {
2563      if (id->m[i] != NULL) pDelete(&id->m[i]);
2564   }
2565   int kk=k;
2566   if (k==0) kk=1; /* ideals must have at least one element(0)*/
2567   pEnlargeSet(&(id->m), IDELEMS(id), kk-IDELEMS(id));
2568   IDELEMS(id) = kk;
2569}
2570
2571/*
2572* compare the leading terms of a and b
2573*/
2574static int tCompare(const poly a, const poly b)
2575{
2576  if (b == NULL) return(a != NULL);
2577  if (a == NULL) return(-1);
2578
2579  /* a != NULL && b != NULL */
2580  int r = pLmCmp(a, b);
2581  if (r != 0) return(r);
2582  number h = nSub(pGetCoeff(a), pGetCoeff(b));
2583  r = -1 + nIsZero(h) + 2*nGreaterZero(h);   /* -1: <, 0:==, 1: > */
2584  nDelete(&h);
2585  return(r);
2586}
2587
2588/*
2589* compare a and b (rev-lex on terms)
2590*/
2591static int pCompare(const poly a, const poly b)
2592{
2593  int r = tCompare(a, b);
2594  if (r != 0) return(r);
2595
2596  poly aa = a;
2597  poly bb = b;
2598  while (r == 0 && aa != NULL && bb != NULL)
2599  {
2600    pIter(aa);
2601    pIter(bb);
2602    r = tCompare(aa, bb);
2603  }
2604  return(r);
2605}
2606
2607typedef struct
2608{
2609  poly p;
2610  int index;
2611} poly_sort;
2612
2613int pCompare_qsort(const void *a, const void *b)
2614{
2615  int res = pCompare(((poly_sort *)a)->p, ((poly_sort *)b)->p);
2616  return(res);
2617}
2618
2619void idSort_qsort(poly_sort *id_sort, int idsize)
2620{
2621  qsort(id_sort, idsize, sizeof(poly_sort), pCompare_qsort);
2622}
2623
2624/*2
2625* ideal id = (id[i])
2626* if id[i] = id[j] then id[j] is deleted for j > i
2627*/
2628void idDelEquals(ideal id)
2629{
2630  int idsize = IDELEMS(id);
2631  poly_sort *id_sort = (poly_sort *)omAlloc0(idsize*sizeof(poly_sort));
2632  for (int i = 0; i < idsize; i++)
2633  {
2634    id_sort[i].p = id->m[i];
2635    id_sort[i].index = i;
2636  }
2637  idSort_qsort(id_sort, idsize);
2638  int index, index_i, index_j;
2639  int i = 0;
2640  for (int j = 1; j < idsize; j++)
2641  {
2642    if (id_sort[i].p != NULL && pEqualPolys(id_sort[i].p, id_sort[j].p))
2643    {
2644      index_i = id_sort[i].index;
2645      index_j = id_sort[j].index;
2646      if (index_j > index_i)
2647      {
2648        index = index_j;
2649      }
2650      else
2651      {
2652        index = index_i;
2653        i = j;
2654      }
2655      pDelete(&id->m[index]);
2656    }
2657    else
2658    {
2659      i = j;
2660    }
2661  }
2662  omFreeSize((ADDRESS)(id_sort), idsize*sizeof(poly_sort));
2663}
Note: See TracBrowser for help on using the repository browser.