source: git/kernel/ideals.cc @ d81e39d

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