ideals.cc File Reference

#include <kernel/mod2.h>
#include <omalloc/omalloc.h>
#include <misc/options.h>
#include <misc/intvec.h>
#include <coeffs/coeffs.h>
#include <coeffs/numbers.h>
#include <polys/monomials/ring.h>
#include <polys/matpol.h>
#include <polys/weight.h>
#include <polys/sparsmat.h>
#include <polys/prCopy.h>
#include <polys/nc/nc.h>
#include <kernel/ideals.h>
#include <kernel/polys.h>
#include <kernel/GBEngine/kstd1.h>
#include <kernel/GBEngine/syz.h>
#include <polys/clapsing.h>

Go to the source code of this file.

Data Structures
struct	poly_sort

Functions
ideal	idMinBase (ideal h1)
ideal	idSectWithElim (ideal h1, ideal h2)
ideal	idSect (ideal h1, ideal h2)
ideal	idMultSect (resolvente arg, int length)
static ideal	idPrepare (ideal h1, tHomog hom, int syzcomp, intvec **w)
ideal	idSyzygies (ideal h1, tHomog h, intvec **w, BOOLEAN setSyzComp, BOOLEAN setRegularity, int *deg)
ideal	idXXX (ideal h1, int k)
ideal	idLiftStd (ideal h1, matrix *ma, tHomog hi, ideal *syz)
static void	idPrepareStd (ideal s_temp, int k)
ideal	idLift (ideal mod, ideal submod, ideal *rest, BOOLEAN goodShape, BOOLEAN isSB, BOOLEAN divide, matrix *unit)
void	idLiftW (ideal P, ideal Q, int n, matrix &T, ideal &R, short *w)
static ideal	idInitializeQuot (ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN *addOnlyOne, int *kkmax)
ideal	idQuot (ideal h1, ideal h2, BOOLEAN h1IsStb, BOOLEAN resultIsIdeal)
ideal	idElimination (ideal h1, poly delVar, intvec *hilb)
ideal	idMinors (matrix a, int ar, ideal R)
	compute all ar-minors of the matrix a the caller of mpRecMin the elements of the result are not in R (if R!=NULL) More...
BOOLEAN	idIsSubModule (ideal id1, ideal id2)
BOOLEAN	idTestHomModule (ideal m, ideal Q, intvec *w)
ideal	idSeries (int n, ideal M, matrix U, intvec *w)
matrix	idDiff (matrix i, int k)
matrix	idDiffOp (ideal I, ideal J, BOOLEAN multiply)
ideal	idModulo (ideal h2, ideal h1, tHomog hom, intvec **w)
intvec *	idMWLift (ideal mod, intvec *weights)
ideal	idCreateSpecialKbase (ideal kBase, intvec **convert)
int	idIndexOfKBase (poly monom, ideal kbase)
poly	idDecompose (poly monom, poly how, ideal kbase, int *pos)
matrix	idCoeffOfKBase (ideal arg, ideal kbase, poly how)
static void	idDeleteComps (ideal arg, int *red_comp, int del)
ideal	idMinEmbedding (ideal arg, BOOLEAN inPlace, intvec **w)
poly	id_GCD (poly f, poly g, const ring r)
ideal	id_Farey (ideal x, number N, const ring r)
void	idKeepFirstK (ideal id, const int k)
	keeps the first k (>= 1) entries of the given ideal (Note that the kept polynomials may be zero.) More...
int	pCompare_qsort (const void *a, const void *b)
void	idSort_qsort (poly_sort *id_sort, int idsize)
void	idDelEquals (ideal id)

---

Data Structure Documentation

poly_sort

struct poly_sort

Definition at line 2543 of file ideals.cc.

Data Fields
int	index
poly	p

Function Documentation

id_Farey()

ideal id_Farey	(	ideal	x,
		number	N,
		const ring	r
	)

Definition at line 2455 of file ideals.cc.

{
  int cnt=IDELEMS(x)*x->nrows;
  ideal result=idInit(cnt,x->rank);
  result->nrows=x->nrows; // for lifting matrices
  result->ncols=x->ncols; // for lifting matrices

  int i;
  for(i=cnt-1;i>=0;i--)
  {
    result->m[i]=p_Farey(x->m[i],N,r);
  }
  return result;
}

id_GCD()

poly id_GCD	(	poly	f,
		poly	g,
		const ring	r
	)

Definition at line 2355 of file ideals.cc.

{
  ideal I=idInit(2,1); I->m[0]=f; I->m[1]=g;
  intvec *w = NULL;

  ring save_r = currRing; rChangeCurrRing(r); ideal S=idSyzygies(I,testHomog,&w); rChangeCurrRing(save_r);

  if (w!=NULL) delete w;
  poly gg=p_TakeOutComp(&(S->m[0]), 2, r);
  id_Delete(&S, r);
  poly gcd_p=singclap_pdivide(f,gg, r);
  p_Delete(&gg, r);

  return gcd_p;
}

idCoeffOfKBase()

matrix idCoeffOfKBase	(	ideal	arg,
		ideal	kbase,
		poly	how
	)

Definition at line 2231 of file ideals.cc.

{
  matrix result;
  ideal tempKbase;
  poly p,q;
  intvec * convert;
  int i=IDELEMS(kbase),j=IDELEMS(arg),k,pos;
#if 0
  while ((i>0) && (kbase->m[i-1]==NULL)) i--;
  if (idIs0(arg))
    return mpNew(i,1);
  while ((j>0) && (arg->m[j-1]==NULL)) j--;
  result = mpNew(i,j);
#else
  result = mpNew(i, j);
  while ((j>0) && (arg->m[j-1]==NULL)) j--;
#endif

  tempKbase = idCreateSpecialKbase(kbase,&convert);
  for (k=0;k<j;k++)
  {
    p = arg->m[k];
    while (p!=NULL)
    {
      q = idDecompose(p,how,tempKbase,&pos);
      if (pos>=0)
      {
        MATELEM(result,(*convert)[pos],k+1) =
            pAdd(MATELEM(result,(*convert)[pos],k+1),q);
      }
      else
        p_Delete(&q,currRing);
      pIter(p);
    }
  }
  idDelete(&tempKbase);
  return result;
}

idCreateSpecialKbase()

ideal idCreateSpecialKbase	(	ideal	kBase,
		intvec **	convert
	)

Definition at line 2145 of file ideals.cc.

{
  int i;
  ideal result;

  if (idIs0(kBase)) return NULL;
  result = idInit(IDELEMS(kBase),kBase->rank);
  *convert = idSort(kBase,FALSE);
  for (i=0;i<(*convert)->length();i++)
  {
    result->m[i] = pCopy(kBase->m[(**convert)[i]-1]);
  }
  return result;
}

idDecompose()

poly idDecompose	(	poly	monom,
		poly	how,
		ideal	kbase,
		int *	pos
	)

Definition at line 2199 of file ideals.cc.

{
  int i;
  poly coeff=pOne(), base=pOne();

  for (i=1;i<=(currRing->N);i++)
  {
    if (pGetExp(how,i)>0)
    {
      pSetExp(base,i,pGetExp(monom,i));
    }
    else
    {
      pSetExp(coeff,i,pGetExp(monom,i));
    }
  }
  pSetComp(base,pGetComp(monom));
  pSetm(base);
  pSetCoeff(coeff,nCopy(pGetCoeff(monom)));
  pSetm(coeff);
  *pos = idIndexOfKBase(base,kbase);
  if (*pos<0)
    p_Delete(&coeff,currRing);
  p_Delete(&base,currRing);
  return coeff;
}

idDelEquals()

void idDelEquals

(

ideal

id

)

Definition at line 2563 of file ideals.cc.

{
  int idsize = IDELEMS(id);
  poly_sort *id_sort = (poly_sort *)omAlloc0(idsize*sizeof(poly_sort));
  for (int i = 0; i < idsize; i++)
  {
    id_sort[i].p = id->m[i];
    id_sort[i].index = i;
  }
  idSort_qsort(id_sort, idsize);
  int index, index_i, index_j;
  int i = 0;
  for (int j = 1; j < idsize; j++)
  {
    if (id_sort[i].p != NULL && pEqualPolys(id_sort[i].p, id_sort[j].p))
    {
      index_i = id_sort[i].index;
      index_j = id_sort[j].index;
      if (index_j > index_i)
      {
        index = index_j;
      }
      else
      {
        index = index_i;
        i = j;
      }
      pDelete(&id->m[index]);
    }
    else
    {
      i = j;
    }
  }
  omFreeSize((ADDRESS)(id_sort), idsize*sizeof(poly_sort));
}

idDeleteComps()

static void idDeleteComps ( ideal  arg, int *  red_comp, int  del  )

static

Definition at line 2270 of file ideals.cc.

{
  int i,j;
  poly p;

  for (i=IDELEMS(arg)-1;i>=0;i--)
  {
    p = arg->m[i];
    while (p!=NULL)
    {
      j = pGetComp(p);
      if (red_comp[j]!=j)
      {
        pSetComp(p,red_comp[j]);
        pSetmComp(p);
      }
      pIter(p);
    }
  }
  (arg->rank) -= del;
}

idDiff()

matrix idDiff	(	matrix	i,
		int	k
	)

Definition at line 1903 of file ideals.cc.

{
  int e=MATCOLS(i)*MATROWS(i);
  matrix r=mpNew(MATROWS(i),MATCOLS(i));
  r->rank=i->rank;
  int j;
  for(j=0; j<e; j++)
  {
    r->m[j]=pDiff(i->m[j],k);
  }
  return r;
}

idDiffOp()

matrix idDiffOp	(	ideal	I,
		ideal	J,
		BOOLEAN	multiply
	)

Definition at line 1916 of file ideals.cc.

{
  matrix r=mpNew(IDELEMS(I),IDELEMS(J));
  int i,j;
  for(i=0; i<IDELEMS(I); i++)
  {
    for(j=0; j<IDELEMS(J); j++)
    {
      MATELEM(r,i+1,j+1)=pDiffOp(I->m[i],J->m[j],multiply);
    }
  }
  return r;
}

idElimination()

ideal idElimination	(	ideal	h1,
		poly	delVar,
		intvec *	hilb
	)

Definition at line 1353 of file ideals.cc.

{
  int    i,j=0,k,l;
  ideal  h,hh, h3;
  int    *ord,*block0,*block1;
  int    ordersize=2;
  int    **wv;
  tHomog hom;
  intvec * w;
  ring tmpR;
  ring origR = currRing;

  if (delVar==NULL)
  {
    return idCopy(h1);
  }
  if ((currRing->qideal!=NULL) && rIsPluralRing(origR))
  {
    WerrorS("cannot eliminate in a qring");
    return NULL;
  }
  if (idIs0(h1)) return idInit(1,h1->rank);
#ifdef HAVE_PLURAL
  if (rIsPluralRing(origR))
    /* in the NC case, we have to check the admissibility of */
    /* the subalgebra to be intersected with */
  {
    if ((ncRingType(origR) != nc_skew) && (ncRingType(origR) != nc_exterior)) /* in (quasi)-commutative algebras every subalgebra is admissible */
    {
      if (nc_CheckSubalgebra(delVar,origR))
      {
        WerrorS("no elimination is possible: subalgebra is not admissible");
        return NULL;
      }
    }
  }
#endif
  hom=(tHomog)idHomModule(h1,NULL,&w); //sets w to weight vector or NULL
  h3=idInit(16,h1->rank);
  for (k=0;; k++)
  {
    if (origR->order[k]!=0) ordersize++;
    else break;
  }
#if 0
  if (rIsPluralRing(origR)) // we have too keep the odering: it may be needed
                            // for G-algebra
  {
    for (k=0;k<ordersize-1; k++)
    {
      block0[k+1] = origR->block0[k];
      block1[k+1] = origR->block1[k];
      ord[k+1] = origR->order[k];
      if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
    }
  }
  else
  {
    block0[1] = 1;
    block1[1] = (currRing->N);
    if (origR->OrdSgn==1) ord[1] = ringorder_wp;
    else                  ord[1] = ringorder_ws;
    wv[1]=(int*)omAlloc0((currRing->N)*sizeof(int));
    double wNsqr = (double)2.0 / (double)(currRing->N);
    wFunctional = wFunctionalBuch;
    int  *x= (int * )omAlloc(2 * ((currRing->N) + 1) * sizeof(int));
    int sl=IDELEMS(h1) - 1;
    wCall(h1->m, sl, x, wNsqr);
    for (sl = (currRing->N); sl!=0; sl--)
      wv[1][sl-1] = x[sl + (currRing->N) + 1];
    omFreeSize((ADDRESS)x, 2 * ((currRing->N) + 1) * sizeof(int));

    ord[2]=ringorder_C;
    ord[3]=0;
  }
#else
#endif
  if ((hom==TRUE) && (origR->OrdSgn==1) && (!rIsPluralRing(origR)))
  {
    #if 1
    // we change to an ordering:
    // aa(1,1,1,...,0,0,0),wp(...),C
    // this seems to be better than version 2 below,
    // according to Tst/../elimiate_[3568].tat (- 17 %)
    ord=(int*)omAlloc0(4*sizeof(int));
    block0=(int*)omAlloc0(4*sizeof(int));
    block1=(int*)omAlloc0(4*sizeof(int));
    wv=(int**) omAlloc0(4*sizeof(int**));
    block0[0] = block0[1] = 1;
    block1[0] = block1[1] = rVar(origR);
    wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
    // use this special ordering: like ringorder_a, except that pFDeg, pWeights
    // ignore it
    ord[0] = ringorder_aa;
    for (j=0;j<rVar(origR);j++)
      if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
    BOOLEAN wp=FALSE;
    for (j=0;j<rVar(origR);j++)
      if (p_Weight(j+1,origR)!=1) { wp=TRUE;break; }
    if (wp)
    {
      wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
      for (j=0;j<rVar(origR);j++)
        wv[1][j]=p_Weight(j+1,origR);
      ord[1] = ringorder_wp;
    }
    else
      ord[1] = ringorder_dp;
    #else
    // we change to an ordering:
    // a(w1,...wn),wp(1,...0.....),C
    ord=(int*)omAlloc0(4*sizeof(int));
    block0=(int*)omAlloc0(4*sizeof(int));
    block1=(int*)omAlloc0(4*sizeof(int));
    wv=(int**) omAlloc0(4*sizeof(int**));
    block0[0] = block0[1] = 1;
    block1[0] = block1[1] = rVar(origR);
    wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
    wv[1]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
    ord[0] = ringorder_a;
    for (j=0;j<rVar(origR);j++)
      wv[0][j]=pWeight(j+1,origR);
    ord[1] = ringorder_wp;
    for (j=0;j<rVar(origR);j++)
      if (pGetExp(delVar,j+1)!=0) wv[1][j]=1;
    #endif
    ord[2] = ringorder_C;
    ord[3] = 0;
  }
  else
  {
    // we change to an ordering:
    // aa(....),orig_ordering
    ord=(int*)omAlloc0(ordersize*sizeof(int));
    block0=(int*)omAlloc0(ordersize*sizeof(int));
    block1=(int*)omAlloc0(ordersize*sizeof(int));
    wv=(int**) omAlloc0(ordersize*sizeof(int**));
    for (k=0;k<ordersize-1; k++)
    {
      block0[k+1] = origR->block0[k];
      block1[k+1] = origR->block1[k];
      ord[k+1] = origR->order[k];
      if (origR->wvhdl[k]!=NULL) wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
    }
    block0[0] = 1;
    block1[0] = rVar(origR);
    wv[0]=(int*)omAlloc0((rVar(origR) + 1)*sizeof(int));
    for (j=0;j<rVar(origR);j++)
      if (pGetExp(delVar,j+1)!=0) wv[0][j]=1;
    // use this special ordering: like ringorder_a, except that pFDeg, pWeights
    // ignore it
    ord[0] = ringorder_aa;
  }
  // fill in tmp ring to get back the data later on
  tmpR  = rCopy0(origR,FALSE,FALSE); // qring==NULL
  //rUnComplete(tmpR);
  tmpR->p_Procs=NULL;
  tmpR->order = ord;
  tmpR->block0 = block0;
  tmpR->block1 = block1;
  tmpR->wvhdl = wv;
  rComplete(tmpR, 1);

#ifdef HAVE_PLURAL
  /* update nc structure on tmpR */
  if (rIsPluralRing(origR))
  {
    if ( nc_rComplete(origR, tmpR, false) ) // no quotient ideal!
    {
      WerrorS("no elimination is possible: ordering condition is violated");
      // cleanup
      rDelete(tmpR);
      if (w!=NULL)
        delete w;
      return NULL;
    }
  }
#endif
  // change into the new ring
  //pChangeRing((currRing->N),currRing->OrdSgn,ord,block0,block1,wv);
  rChangeCurrRing(tmpR);

  //h = idInit(IDELEMS(h1),h1->rank);
  // fetch data from the old ring
  //for (k=0;k<IDELEMS(h1);k++) h->m[k] = prCopyR( h1->m[k], origR);
  h=idrCopyR(h1,origR,currRing);
  if (origR->qideal!=NULL)
  {
    WarnS("eliminate in q-ring: experimental");
    ideal q=idrCopyR(origR->qideal,origR,currRing);
    ideal s=idSimpleAdd(h,q);
    idDelete(&h);
    idDelete(&q);
    h=s;
  }
  // compute kStd
#if 1
  //rWrite(tmpR);PrintLn();
  //BITSET save1;
  //SI_SAVE_OPT1(save1);
  //si_opt_1 |=1;
  //Print("h: %d gen, rk=%d\n",IDELEMS(h),h->rank);
  //extern char * showOption();
  //Print("%s\n",showOption());
  hh = kStd(h,NULL,hom,&w,hilb);
  //SI_RESTORE_OPT1(save1);
  idDelete(&h);
#else
  extern ideal kGroebner(ideal F, ideal Q);
  hh=kGroebner(h,NULL);
#endif
  // go back to the original ring
  rChangeCurrRing(origR);
  i = IDELEMS(hh)-1;
  while ((i >= 0) && (hh->m[i] == NULL)) i--;
  j = -1;
  // fetch data from temp ring
  for (k=0; k<=i; k++)
  {
    l=(currRing->N);
    while ((l>0) && (p_GetExp( hh->m[k],l,tmpR)*pGetExp(delVar,l)==0)) l--;
    if (l==0)
    {
      j++;
      if (j >= IDELEMS(h3))
      {
        pEnlargeSet(&(h3->m),IDELEMS(h3),16);
        IDELEMS(h3) += 16;
      }
      h3->m[j] = prMoveR( hh->m[k], tmpR,origR);
      hh->m[k] = NULL;
    }
  }
  id_Delete(&hh, tmpR);
  idSkipZeroes(h3);
  rDelete(tmpR);
  if (w!=NULL)
    delete w;
  return h3;
}

idIndexOfKBase()

int idIndexOfKBase	(	poly	monom,
		ideal	kbase
	)

Definition at line 2163 of file ideals.cc.

{
  int j=IDELEMS(kbase);

  while ((j>0) && (kbase->m[j-1]==NULL)) j--;
  if (j==0) return -1;
  int i=(currRing->N);
  while (i>0)
  {
    loop
    {
      if (pGetExp(monom,i)>pGetExp(kbase->m[j-1],i)) return -1;
      if (pGetExp(monom,i)==pGetExp(kbase->m[j-1],i)) break;
      j--;
      if (j==0) return -1;
    }
    if (i==1)
    {
      while(j>0)
      {
        if (pGetComp(monom)==pGetComp(kbase->m[j-1])) return j-1;
        if (pGetComp(monom)>pGetComp(kbase->m[j-1])) return -1;
        j--;
      }
    }
    i--;
  }
  return -1;
}

idInitializeQuot()

static ideal idInitializeQuot ( ideal  h1, ideal  h2, BOOLEAN  h1IsStb, BOOLEAN *  addOnlyOne, int *  kkmax  )

static

addOnlyOne &&

Definition at line 1151 of file ideals.cc.

{
  idTest(h1);
  idTest(h2);

  ideal temph1;
  poly     p,q = NULL;
  int i,l,ll,k,kkk,kmax;
  int j = 0;
  int k1 = id_RankFreeModule(h1,currRing);
  int k2 = id_RankFreeModule(h2,currRing);
  tHomog   hom=isNotHomog;
  k=si_max(k1,k2);
  if (k==0)
    k = 1;
  if ((k2==0) && (k>1)) *addOnlyOne = FALSE;
  intvec * weights;
  hom = (tHomog)idHomModule(h1,currRing->qideal,&weights);
  if /**addOnlyOne &&*/ (/*(*/ !h1IsStb /*)*/)
    temph1 = kStd(h1,currRing->qideal,hom,&weights,NULL);
  else
    temph1 = idCopy(h1);
  if (weights!=NULL) delete weights;
  idTest(temph1);
/*--- making a single vector from h2 ---------------------*/
  for (i=0; i<IDELEMS(h2); i++)
  {
    if (h2->m[i] != NULL)
    {
      p = pCopy(h2->m[i]);
      if (k2 == 0)
        p_Shift(&p,j*k+1,currRing);
      else
        p_Shift(&p,j*k,currRing);
      q = pAdd(q,p);
      j++;
    }
  }
  *kkmax = kmax = j*k+1;
/*--- adding a monomial for the result (syzygy) ----------*/
  p = q;
  while (pNext(p)!=NULL) pIter(p);
  pNext(p) = pOne();
  pIter(p);
  pSetComp(p,kmax);
  pSetmComp(p);
/*--- constructing the big matrix ------------------------*/
  ideal h4 = idInit(16,kmax+k-1);
  h4->m[0] = q;
  if (k2 == 0)
  {
    if (k > IDELEMS(h4))
    {
      pEnlargeSet(&(h4->m),IDELEMS(h4),k-IDELEMS(h4));
      IDELEMS(h4) = k;
    }
    for (i=1; i<k; i++)
    {
      if (h4->m[i-1]!=NULL)
      {
        p = p_Copy_noCheck(h4->m[i-1], currRing); p_Shift(&p,1,currRing);
        // pTest(p);
        h4->m[i] = p;
      }
    }
  }
  idSkipZeroes(h4);
  kkk = IDELEMS(h4);
  i = IDELEMS(temph1);
  for (l=0; l<i; l++)
  {
    if(temph1->m[l]!=NULL)
    {
      for (ll=0; ll<j; ll++)
      {
        p = pCopy(temph1->m[l]);
        if (k1 == 0)
          p_Shift(&p,ll*k+1,currRing);
        else
          p_Shift(&p,ll*k,currRing);
        if (kkk >= IDELEMS(h4))
        {
          pEnlargeSet(&(h4->m),IDELEMS(h4),16);
          IDELEMS(h4) += 16;
        }
        h4->m[kkk] = p;
        kkk++;
      }
    }
  }
/*--- if h2 goes in as single vector - the h1-part is just SB ---*/
  if (*addOnlyOne)
  {
    idSkipZeroes(h4);
    p = h4->m[0];
    for (i=0;i<IDELEMS(h4)-1;i++)
    {
      h4->m[i] = h4->m[i+1];
    }
    h4->m[IDELEMS(h4)-1] = p;
    if(!rField_is_Ring(currRing)) si_opt_1 |= Sy_bit(OPT_SB_1);
  }
  idDelete(&temph1);
  //idTest(h4);//see remark at the beginning
  return h4;
}

idIsSubModule()

BOOLEAN idIsSubModule	(	ideal	id1,
		ideal	id2
	)

Definition at line 1813 of file ideals.cc.

{
  int i;
  poly p;

  if (idIs0(id1)) return TRUE;
  for (i=0;i<IDELEMS(id1);i++)
  {
    if (id1->m[i] != NULL)
    {
      p = kNF(id2,currRing->qideal,id1->m[i]);
      if (p != NULL)
      {
        p_Delete(&p,currRing);
        return FALSE;
      }
    }
  }
  return TRUE;
}

idKeepFirstK()

void idKeepFirstK	(	ideal	id,
		const int	k
	)

keeps the first k (>= 1) entries of the given ideal (Note that the kept polynomials may be zero.)

Definition at line 2531 of file ideals.cc.

{
   for (int i = IDELEMS(id)-1; i >= k; i--)
   {
      if (id->m[i] != NULL) pDelete(&id->m[i]);
   }
   int kk=k;
   if (k==0) kk=1; /* ideals must have at least one element(0)*/
   pEnlargeSet(&(id->m), IDELEMS(id), kk-IDELEMS(id));
   IDELEMS(id) = kk;
}

idLift()

ideal idLift	(	ideal	mod,
		ideal	submod,
		ideal *	rest,
		BOOLEAN	goodShape,
		BOOLEAN	isSB,
		BOOLEAN	divide,
		matrix *	unit
	)

Definition at line 891 of file ideals.cc.

{
  int lsmod =id_RankFreeModule(submod,currRing), j, k;
  int comps_to_add=0;
  poly p;

  if (idIs0(submod))
  {
    if (unit!=NULL)
    {
      *unit=mpNew(1,1);
      MATELEM(*unit,1,1)=pOne();
    }
    if (rest!=NULL)
    {
      *rest=idInit(1,mod->rank);
    }
    return idInit(1,mod->rank);
  }
  if (idIs0(mod)) /* and not idIs0(submod) */
  {
    WerrorS("2nd module does not lie in the first");
    return NULL;
  }
  if (unit!=NULL)
  {
    comps_to_add = IDELEMS(submod);
    while ((comps_to_add>0) && (submod->m[comps_to_add-1]==NULL))
      comps_to_add--;
  }
  k=si_max(id_RankFreeModule(mod,currRing),id_RankFreeModule(submod,currRing));
  if  ((k!=0) && (lsmod==0)) lsmod=1;
  k=si_max(k,(int)mod->rank);
  if (k<submod->rank) { WarnS("rk(submod) > rk(mod) ?");k=submod->rank; }

  ring orig_ring=currRing;
  ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);  rChangeCurrRing(syz_ring);
  rSetSyzComp(k,syz_ring);

  ideal s_mod, s_temp;
  if (orig_ring != syz_ring)
  {
    s_mod = idrCopyR_NoSort(mod,orig_ring,syz_ring);
    s_temp = idrCopyR_NoSort(submod,orig_ring,syz_ring);
  }
  else
  {
    s_mod = mod;
    s_temp = idCopy(submod);
  }
  ideal s_h3;
  if (isSB)
  {
    s_h3 = idCopy(s_mod);
    idPrepareStd(s_h3, k+comps_to_add);
  }
  else
  {
    s_h3 = idPrepare(s_mod,(tHomog)FALSE,k+comps_to_add,NULL);
  }
  if (!goodShape)
  {
    for (j=0;j<IDELEMS(s_h3);j++)
    {
      if ((s_h3->m[j] != NULL) && (pMinComp(s_h3->m[j]) > k))
        p_Delete(&(s_h3->m[j]),currRing);
    }
  }
  idSkipZeroes(s_h3);
  if (lsmod==0)
  {
    id_Shift(s_temp,1,currRing);
  }
  if (unit!=NULL)
  {
    for(j = 0;j<comps_to_add;j++)
    {
      p = s_temp->m[j];
      if (p!=NULL)
      {
        while (pNext(p)!=NULL) pIter(p);
        pNext(p) = pOne();
        pIter(p);
        pSetComp(p,1+j+k);
        pSetmComp(p);
        p = pNeg(p);
      }
    }
    s_temp->rank += (k+comps_to_add);
  }
  ideal s_result = kNF(s_h3,currRing->qideal,s_temp,k);
  s_result->rank = s_h3->rank;
  ideal s_rest = idInit(IDELEMS(s_result),k);
  idDelete(&s_h3);
  idDelete(&s_temp);

  for (j=0;j<IDELEMS(s_result);j++)
  {
    if (s_result->m[j]!=NULL)
    {
      if (pGetComp(s_result->m[j])<=k)
      {
        if (!divide)
        {
          if (isSB)
          {
            WarnS("first module not a standardbasis\n"
              "// ** or second not a proper submodule");
          }
          else
            WerrorS("2nd module does not lie in the first");
          idDelete(&s_result);
          idDelete(&s_rest);
          s_result=idInit(IDELEMS(submod),submod->rank);
          break;
        }
        else
        {
          p = s_rest->m[j] = s_result->m[j];
          while ((pNext(p)!=NULL) && (pGetComp(pNext(p))<=k)) pIter(p);
          s_result->m[j] = pNext(p);
          pNext(p) = NULL;
        }
      }
      p_Shift(&(s_result->m[j]),-k,currRing);
      pNeg(s_result->m[j]);
    }
  }
  if ((lsmod==0) && (s_rest!=NULL))
  {
    for (j=IDELEMS(s_rest);j>0;j--)
    {
      if (s_rest->m[j-1]!=NULL)
      {
        p_Shift(&(s_rest->m[j-1]),-1,currRing);
        s_rest->m[j-1] = s_rest->m[j-1];
      }
    }
  }
  if(syz_ring!=orig_ring)
  {
    idDelete(&s_mod);
    rChangeCurrRing(orig_ring);
    s_result = idrMoveR_NoSort(s_result, syz_ring, orig_ring);
    s_rest = idrMoveR_NoSort(s_rest, syz_ring, orig_ring);
    rDelete(syz_ring);
  }
  if (rest!=NULL)
    *rest = s_rest;
  else
    idDelete(&s_rest);
//idPrint(s_result);
  if (unit!=NULL)
  {
    *unit=mpNew(comps_to_add,comps_to_add);
    int i;
    for(i=0;i<IDELEMS(s_result);i++)
    {
      poly p=s_result->m[i];
      poly q=NULL;
      while(p!=NULL)
      {
        if(pGetComp(p)<=comps_to_add)
        {
          pSetComp(p,0);
          if (q!=NULL)
          {
            pNext(q)=pNext(p);
          }
          else
          {
            pIter(s_result->m[i]);
          }
          pNext(p)=NULL;
          MATELEM(*unit,i+1,i+1)=pAdd(MATELEM(*unit,i+1,i+1),p);
          if(q!=NULL)   p=pNext(q);
          else          p=s_result->m[i];
        }
        else
        {
          q=p;
          pIter(p);
        }
      }
      p_Shift(&s_result->m[i],-comps_to_add,currRing);
    }
  }
  return s_result;
}

idLiftStd()

ideal idLiftStd	(	ideal	h1,
		matrix *	ma,
		tHomog	hi,
		ideal *	syz
	)

Definition at line 704 of file ideals.cc.

{
  int  i, j, t, inputIsIdeal=id_RankFreeModule(h1,currRing);
  long k;
  poly  p=NULL, q;
  intvec *w=NULL;

  idDelete((ideal*)ma);
  BOOLEAN lift3=FALSE;
  if (syz!=NULL) { lift3=TRUE; idDelete(syz); }
  if (idIs0(h1))
  {
    *ma=mpNew(1,0);
    if (lift3)
    {
      *syz=idFreeModule(IDELEMS(h1));
    }
    return idInit(1,h1->rank);
  }

  BITSET save2;
  SI_SAVE_OPT2(save2);

  k=si_max(1L,id_RankFreeModule(h1,currRing));

  if ((k==1) && (!lift3)) si_opt_2 |=Sy_bit(V_IDLIFT);

  ring orig_ring = currRing;
  ring syz_ring = rAssure_SyzOrder(orig_ring,TRUE);  rChangeCurrRing(syz_ring);
  rSetSyzComp(k,syz_ring);

  ideal s_h1=h1;

  if (orig_ring != syz_ring)
    s_h1 = idrCopyR_NoSort(h1,orig_ring,syz_ring);
  else
    s_h1 = h1;

  ideal s_h3=idPrepare(s_h1,hi,k,&w); // main (syz) GB computation

  ideal s_h2 = idInit(IDELEMS(s_h3), s_h3->rank);

  if (lift3) (*syz)=idInit(IDELEMS(s_h3),IDELEMS(h1));

  if (w!=NULL) delete w;
  i = 0;

  // now sort the result, SB : leave in s_h3
  //                      T:  put in s_h2
  //                      syz: put in *syz
  for (j=0; j<IDELEMS(s_h3); j++)
  {
    if (s_h3->m[j] != NULL)
    {
      //if (p_MinComp(s_h3->m[j],syz_ring) <= k)
      if (pGetComp(s_h3->m[j]) <= k) // syz_ring == currRing
      {
        i++;
        q = s_h3->m[j];
        while (pNext(q) != NULL)
        {
          if (pGetComp(pNext(q)) > k)
          {
            s_h2->m[j] = pNext(q);
            pNext(q) = NULL;
          }
          else
          {
            pIter(q);
          }
        }
        if (!inputIsIdeal) p_Shift(&(s_h3->m[j]), -1,currRing);
      }
      else
      {
        // we a syzygy here:
        if (lift3)
        {
          p_Shift(&s_h3->m[j], -k,currRing);
          (*syz)->m[j]=s_h3->m[j];
          s_h3->m[j]=NULL;
        }
        else
          p_Delete(&(s_h3->m[j]),currRing);
      }
    }
  }
  idSkipZeroes(s_h3);
  //extern char * iiStringMatrix(matrix im, int dim,char ch);
  //PrintS("SB: ----------------------------------------\n");
  //PrintS(iiStringMatrix((matrix)s_h3,k,'\n'));
  //PrintLn();
  //PrintS("T: ----------------------------------------\n");
  //PrintS(iiStringMatrix((matrix)s_h2,h1->rank,'\n'));
  //PrintLn();

  if (lift3) idSkipZeroes(*syz);

  j = IDELEMS(s_h1);


  if (syz_ring!=orig_ring)
  {
    idDelete(&s_h1);
    rChangeCurrRing(orig_ring);
  }

  *ma = mpNew(j,i);

  i = 1;
  for (j=0; j<IDELEMS(s_h2); j++)
  {
    if (s_h2->m[j] != NULL)
    {
      q = prMoveR( s_h2->m[j], syz_ring,orig_ring);
      s_h2->m[j] = NULL;

      if (q!=NULL)
      {
        q=pReverse(q);
        while (q != NULL)
        {
          p = q;
          pIter(q);
          pNext(p) = NULL;
          t=pGetComp(p);
          pSetComp(p,0);
          pSetmComp(p);
          MATELEM(*ma,t-k,i) = pAdd(MATELEM(*ma,t-k,i),p);
        }
      }
      i++;
    }
  }
  idDelete(&s_h2);

  for (i=0; i<IDELEMS(s_h3); i++)
  {
    s_h3->m[i] = prMoveR_NoSort(s_h3->m[i], syz_ring,orig_ring);
  }
  if (lift3)
  {
    for (i=0; i<IDELEMS(*syz); i++)
    {
      (*syz)->m[i] = prMoveR_NoSort((*syz)->m[i], syz_ring,orig_ring);
    }
  }

  if (syz_ring!=orig_ring) rDelete(syz_ring);
  SI_RESTORE_OPT2(save2);
  return s_h3;
}

idLiftW()

void idLiftW	(	ideal	P,
		ideal	Q,
		int	n,
		matrix &	T,
		ideal &	R,
		short *	w
	)

Definition at line 1086 of file ideals.cc.

{
  long N=0;
  int i;
  for(i=IDELEMS(Q)-1;i>=0;i--)
    if(w==NULL)
      N=si_max(N,p_Deg(Q->m[i],currRing));
    else
      N=si_max(N,p_DegW(Q->m[i],w,currRing));
  N+=n;

  T=mpNew(IDELEMS(Q),IDELEMS(P));
  R=idInit(IDELEMS(P),P->rank);

  for(i=IDELEMS(P)-1;i>=0;i--)
  {
    poly p;
    if(w==NULL)
      p=ppJet(P->m[i],N);
    else
      p=ppJetW(P->m[i],N,w);

    int j=IDELEMS(Q)-1;
    while(p!=NULL)
    {
      if(pDivisibleBy(Q->m[j],p))
      {
        poly p0=p_DivideM(pHead(p),pHead(Q->m[j]),currRing);
        if(w==NULL)
          p=pJet(pSub(p,ppMult_mm(Q->m[j],p0)),N);
        else
          p=pJetW(pSub(p,ppMult_mm(Q->m[j],p0)),N,w);
        pNormalize(p);
        if(((w==NULL)&&(p_Deg(p0,currRing)>n))||((w!=NULL)&&(p_DegW(p0,w,currRing)>n)))
          p_Delete(&p0,currRing);
        else
          MATELEM(T,j+1,i+1)=pAdd(MATELEM(T,j+1,i+1),p0);
        j=IDELEMS(Q)-1;
      }
      else
      {
        if(j==0)
        {
          poly p0=p;
          pIter(p);
          pNext(p0)=NULL;
          if(((w==NULL)&&(p_Deg(p0,currRing)>n))
          ||((w!=NULL)&&(p_DegW(p0,w,currRing)>n)))
            p_Delete(&p0,currRing);
          else
            R->m[i]=pAdd(R->m[i],p0);
          j=IDELEMS(Q)-1;
        }
        else
          j--;
      }
    }
  }
}

idMinBase()

ideal idMinBase

(

ideal

h1

)

Definition at line 45 of file ideals.cc.

{
  ideal h2, h3,h4,e;
  int j,k;
  int i,l,ll;
  intvec * wth;
  BOOLEAN homog;
  if(rField_is_Ring(currRing))
  {
      WarnS("minbase applies only to the local or homogeneous case over coefficient fields");
      e=idCopy(h1);
      return e;
  }
  homog = idHomModule(h1,currRing->qideal,&wth);
  if (rHasGlobalOrdering(currRing))
  {
    if(!homog)
    {
      WarnS("minbase applies only to the local or homogeneous case over coefficient fields");
      e=idCopy(h1);
      return e;
    }
    else
    {
      ideal re=kMin_std(h1,currRing->qideal,(tHomog)homog,&wth,h2,NULL,0,3);
      idDelete(&re);
      return h2;
    }
  }
  e=idInit(1,h1->rank);
  if (idIs0(h1))
  {
    return e;
  }
  pEnlargeSet(&(e->m),IDELEMS(e),15);
  IDELEMS(e) = 16;
  h2 = kStd(h1,currRing->qideal,isNotHomog,NULL);
  h3 = idMaxIdeal(1);
  h4=idMult(h2,h3);
  idDelete(&h3);
  h3=kStd(h4,currRing->qideal,isNotHomog,NULL);
  k = IDELEMS(h3);
  while ((k > 0) && (h3->m[k-1] == NULL)) k--;
  j = -1;
  l = IDELEMS(h2);
  while ((l > 0) && (h2->m[l-1] == NULL)) l--;
  for (i=l-1; i>=0; i--)
  {
    if (h2->m[i] != NULL)
    {
      ll = 0;
      while ((ll < k) && ((h3->m[ll] == NULL)
      || !pDivisibleBy(h3->m[ll],h2->m[i])))
        ll++;
      if (ll >= k)
      {
        j++;
        if (j > IDELEMS(e)-1)
        {
          pEnlargeSet(&(e->m),IDELEMS(e),16);
          IDELEMS(e) += 16;
        }
        e->m[j] = pCopy(h2->m[i]);
      }
    }
  }
  idDelete(&h2);
  idDelete(&h3);
  idDelete(&h4);
  if (currRing->qideal!=NULL)
  {
    h3=idInit(1,e->rank);
    h2=kNF(h3,currRing->qideal,e);
    idDelete(&h3);
    idDelete(&e);
    e=h2;
  }
  idSkipZeroes(e);
  return e;
}

idMinEmbedding()

ideal idMinEmbedding	(	ideal	arg,
		BOOLEAN	inPlace,
		intvec **	w
	)

Definition at line 2297 of file ideals.cc.

{
  if (idIs0(arg)) return idInit(1,arg->rank);
  int i,next_gen,next_comp;
  ideal res=arg;
  if (!inPlace) res = idCopy(arg);
  res->rank=si_max(res->rank,id_RankFreeModule(res,currRing));
  int *red_comp=(int*)omAlloc((res->rank+1)*sizeof(int));
  for (i=res->rank;i>=0;i--) red_comp[i]=i;

  int del=0;
  loop
  {
    next_gen = id_ReadOutPivot(res, &next_comp, currRing);
    if (next_gen<0) break;
    del++;
    syGaussForOne(res,next_gen,next_comp,0,IDELEMS(res));
    for(i=next_comp+1;i<=arg->rank;i++) red_comp[i]--;
    if ((w !=NULL)&&(*w!=NULL))
    {
      for(i=next_comp;i<(*w)->length();i++) (**w)[i-1]=(**w)[i];
    }
  }

  idDeleteComps(res,red_comp,del);
  idSkipZeroes(res);
  omFree(red_comp);

  if ((w !=NULL)&&(*w!=NULL) &&(del>0))
  {
    int nl=si_max((*w)->length()-del,1);
    intvec *wtmp=new intvec(nl);
    for(i=0;i<res->rank;i++) (*wtmp)[i]=(**w)[i];
    delete *w;
    *w=wtmp;
  }
  return res;
}

idMinors()

ideal idMinors	(	matrix	a,
		int	ar,
		ideal	R
	)

compute all ar-minors of the matrix a the caller of mpRecMin the elements of the result are not in R (if R!=NULL)

Definition at line 1744 of file ideals.cc.

{

  const ring origR=currRing;
  id_Test((ideal)a, origR);

  const int r = a->nrows;
  const int c = a->ncols;

  if((ar<=0) || (ar>r) || (ar>c))
  {
    Werror("%d-th minor, matrix is %dx%d",ar,r,c);
    return NULL;
  }

  ideal h = id_Matrix2Module(mp_Copy(a,origR),origR);
  long bound = sm_ExpBound(h,c,r,ar,origR);
  id_Delete(&h, origR);

  ring tmpR = sm_RingChange(origR,bound);

  matrix b = mpNew(r,c);

  for (int i=r*c-1;i>=0;i--)
    if (a->m[i] != NULL)
      b->m[i] = prCopyR(a->m[i],origR,tmpR);

  id_Test( (ideal)b, tmpR);

  if (R!=NULL)
  {
    R = idrCopyR(R,origR,tmpR); // TODO: overwrites R? memory leak?
    //if (ar>1) // otherwise done in mpMinorToResult
    //{
    //  matrix bb=(matrix)kNF(R,currRing->qideal,(ideal)b);
    //  bb->rank=b->rank; bb->nrows=b->nrows; bb->ncols=b->ncols;
    //  idDelete((ideal*)&b); b=bb;
    //}
    id_Test( R, tmpR);
  }


  ideal result = idInit(32,1);

  int elems = 0;

  if(ar>1)
    mp_RecMin(ar-1,result,elems,b,r,c,NULL,R,tmpR);
  else
    mp_MinorToResult(result,elems,b,r,c,R,tmpR);

  id_Test( (ideal)b, tmpR);

  id_Delete((ideal *)&b, tmpR);

  if (R!=NULL) id_Delete(&R,tmpR);

  idSkipZeroes(result);
  rChangeCurrRing(origR);
  result = idrMoveR(result,tmpR,origR);
  sm_KillModifiedRing(tmpR);
  idTest(result);
  return result;
}

idModulo()

ideal idModulo	(	ideal	h2,
		ideal	h1,
		tHomog	hom,
		intvec **	w
	)

Definition at line 1988 of file ideals.cc.

{
  intvec *wtmp=NULL;

  int i,k,rk,flength=0,slength,length;
  poly p,q;

  if (idIs0(h2))
    return idFreeModule(si_max(1,h2->ncols));
  if (!idIs0(h1))
    flength = id_RankFreeModule(h1,currRing);
  slength = id_RankFreeModule(h2,currRing);
  length  = si_max(flength,slength);
  if (length==0)
  {
    length = 1;
  }
  ideal temp = idInit(IDELEMS(h2),length+IDELEMS(h2));
  if ((w!=NULL)&&((*w)!=NULL))
  {
    //Print("input weights:");(*w)->show(1);PrintLn();
    int d;
    int k;
    wtmp=new intvec(length+IDELEMS(h2));
    for (i=0;i<length;i++)
      ((*wtmp)[i])=(**w)[i];
    for (i=0;i<IDELEMS(h2);i++)
    {
      poly p=h2->m[i];
      if (p!=NULL)
      {
        d = p_Deg(p,currRing);
        k= pGetComp(p);
        if (slength>0) k--;
        d +=((**w)[k]);
        ((*wtmp)[i+length]) = d;
      }
    }
    //Print("weights:");wtmp->show(1);PrintLn();
  }
  for (i=0;i<IDELEMS(h2);i++)
  {
    temp->m[i] = pCopy(h2->m[i]);
    q = pOne();
    pSetComp(q,i+1+length);
    pSetmComp(q);
    if(temp->m[i]!=NULL)
    {
      if (slength==0) p_Shift(&(temp->m[i]),1,currRing);
      p = temp->m[i];
      while (pNext(p)!=NULL) pIter(p);
      pNext(p) = q; // will be sorted later correctly
    }
    else
      temp->m[i]=q;
  }
  rk = k = IDELEMS(h2);
  if (!idIs0(h1))
  {
    pEnlargeSet(&(temp->m),IDELEMS(temp),IDELEMS(h1));
    IDELEMS(temp) += IDELEMS(h1);
    for (i=0;i<IDELEMS(h1);i++)
    {
      if (h1->m[i]!=NULL)
      {
        temp->m[k] = pCopy(h1->m[i]);
        if (flength==0) p_Shift(&(temp->m[k]),1,currRing);
        k++;
      }
    }
  }

  ring orig_ring=currRing;
  ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE); rChangeCurrRing(syz_ring);
  // we can use OPT_RETURN_SB only, if syz_ring==orig_ring,
  // therefore we disable OPT_RETURN_SB for modulo:
  // (see tr. #701)
  //if (TEST_OPT_RETURN_SB)
  //  rSetSyzComp(IDELEMS(h2)+length, syz_ring);
  //else
    rSetSyzComp(length, syz_ring);
  ideal s_temp;

  if (syz_ring != orig_ring)
  {
    s_temp = idrMoveR_NoSort(temp, orig_ring, syz_ring);
  }
  else
  {
    s_temp = temp;
  }

  idTest(s_temp);
  ideal s_temp1 = kStd(s_temp,currRing->qideal,hom,&wtmp,NULL,length);

  //if (wtmp!=NULL)  Print("output weights:");wtmp->show(1);PrintLn();
  if ((w!=NULL) && (*w !=NULL) && (wtmp!=NULL))
  {
    delete *w;
    *w=new intvec(IDELEMS(h2));
    for (i=0;i<IDELEMS(h2);i++)
      ((**w)[i])=(*wtmp)[i+length];
  }
  if (wtmp!=NULL) delete wtmp;

  for (i=0;i<IDELEMS(s_temp1);i++)
  {
    if ((s_temp1->m[i]!=NULL)
    && (((int)pGetComp(s_temp1->m[i]))<=length))
    {
      p_Delete(&(s_temp1->m[i]),currRing);
    }
    else
    {
      p_Shift(&(s_temp1->m[i]),-length,currRing);
    }
  }
  s_temp1->rank = rk;
  idSkipZeroes(s_temp1);

  if (syz_ring!=orig_ring)
  {
    rChangeCurrRing(orig_ring);
    s_temp1 = idrMoveR_NoSort(s_temp1, syz_ring, orig_ring);
    rDelete(syz_ring);
    // Hmm ... here seems to be a memory leak
    // However, simply deleting it causes memory trouble
    // idDelete(&s_temp);
  }
  else
  {
    idDelete(&temp);
  }
  idTest(s_temp1);
  return s_temp1;
}

idMultSect()

ideal idMultSect	(	resolvente	arg,
		int	length
	)

Definition at line 340 of file ideals.cc.

{
  int i,j=0,k=0,syzComp,l,maxrk=-1,realrki;
  ideal bigmat,tempstd,result;
  poly p;
  int isIdeal=0;
  intvec * w=NULL;

  /* find 0-ideals and max rank -----------------------------------*/
  for (i=0;i<length;i++)
  {
    if (!idIs0(arg[i]))
    {
      realrki=id_RankFreeModule(arg[i],currRing);
      k++;
      j += IDELEMS(arg[i]);
      if (realrki>maxrk) maxrk = realrki;
    }
    else
    {
      if (arg[i]!=NULL)
      {
        return idInit(1,arg[i]->rank);
      }
    }
  }
  if (maxrk == 0)
  {
    isIdeal = 1;
    maxrk = 1;
  }
  /* init -----------------------------------------------------------*/
  j += maxrk;
  syzComp = k*maxrk;

  ring orig_ring=currRing;
  ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE); rChangeCurrRing(syz_ring);
  rSetSyzComp(syzComp, syz_ring);

  bigmat = idInit(j,(k+1)*maxrk);
  /* create unit matrices ------------------------------------------*/
  for (i=0;i<maxrk;i++)
  {
    for (j=0;j<=k;j++)
    {
      p = pOne();
      pSetComp(p,i+1+j*maxrk);
      pSetmComp(p);
      bigmat->m[i] = pAdd(bigmat->m[i],p);
    }
  }
  /* enter given ideals ------------------------------------------*/
  i = maxrk;
  k = 0;
  for (j=0;j<length;j++)
  {
    if (arg[j]!=NULL)
    {
      for (l=0;l<IDELEMS(arg[j]);l++)
      {
        if (arg[j]->m[l]!=NULL)
        {
          if (syz_ring==orig_ring)
            bigmat->m[i] = pCopy(arg[j]->m[l]);
          else
            bigmat->m[i] = prCopyR(arg[j]->m[l], orig_ring,currRing);
          p_Shift(&(bigmat->m[i]),k*maxrk+isIdeal,currRing);
          i++;
        }
      }
      k++;
    }
  }
  /* std computation --------------------------------------------*/
  tempstd = kStd(bigmat,currRing->qideal,testHomog,&w,NULL,syzComp);
  if (w!=NULL) delete w;
  idDelete(&bigmat);

  if(syz_ring!=orig_ring)
    rChangeCurrRing(orig_ring);

  /* interprete result ----------------------------------------*/
  result = idInit(IDELEMS(tempstd),maxrk);
  k = 0;
  for (j=0;j<IDELEMS(tempstd);j++)
  {
    if ((tempstd->m[j]!=NULL) && (p_GetComp(tempstd->m[j],syz_ring)>syzComp))
    {
      if (syz_ring==orig_ring)
        p = pCopy(tempstd->m[j]);
      else
        p = prCopyR(tempstd->m[j], syz_ring,currRing);
      p_Shift(&p,-syzComp-isIdeal,currRing);
      result->m[k] = p;
      k++;
    }
  }
  /* clean up ----------------------------------------------------*/
  if(syz_ring!=orig_ring)
    rChangeCurrRing(syz_ring);
  idDelete(&tempstd);
  if(syz_ring!=orig_ring)
  {
    rChangeCurrRing(orig_ring);
    rDelete(syz_ring);
  }
  idSkipZeroes(result);
  return result;
}

idMWLift()

intvec* idMWLift	(	ideal	mod,
		intvec *	weights
	)

Definition at line 2128 of file ideals.cc.

{
  if (idIs0(mod)) return new intvec(2);
  int i=IDELEMS(mod);
  while ((i>0) && (mod->m[i-1]==NULL)) i--;
  intvec *result = new intvec(i+1);
  while (i>0)
  {
    (*result)[i]=currRing->pFDeg(mod->m[i],currRing)+(*weights)[pGetComp(mod->m[i])];
  }
  return result;
}

idPrepare()

static ideal idPrepare ( ideal  h1, tHomog  hom, int  syzcomp, intvec **  w  )

static

Definition at line 455 of file ideals.cc.

{
  ideal   h2, h3;
  int     j,k;
  poly    p,q;

  if (idIs0(h1)) return NULL;
  k = id_RankFreeModule(h1,currRing);
  h2=idCopy(h1);
  int i = IDELEMS(h2);
  if (k == 0)
  {
    id_Shift(h2,1,currRing);
    k = 1;
  }
  if (syzcomp<k)
  {
    Warn("syzcomp too low, should be %d instead of %d",k,syzcomp);
    syzcomp = k;
    rSetSyzComp(k,currRing);
  }
  h2->rank = syzcomp+i;

  //if (hom==testHomog)
  //{
  //  if(idHomIdeal(h1,currRing->qideal))
  //  {
  //    hom=TRUE;
  //  }
  //}

  for (j=0; j<i; j++)
  {
    p = h2->m[j];
    q = pOne();
    pSetComp(q,syzcomp+1+j);
    pSetmComp(q);
    if (p!=NULL)
    {
      while (pNext(p)) pIter(p);
      p->next = q;
    }
    else
      h2->m[j]=q;
  }

  idTest(h2);

  h3 = kStd(h2,currRing->qideal,hom,w,NULL,syzcomp);

  idDelete(&h2);
  return h3;
}

idPrepareStd()

static void idPrepareStd ( ideal  s_temp, int  k  )

static

Definition at line 857 of file ideals.cc.

{
  int j,rk=id_RankFreeModule(s_temp,currRing);
  poly p,q;

  if (rk == 0)
  {
    for (j=0; j<IDELEMS(s_temp); j++)
    {
      if (s_temp->m[j]!=NULL) pSetCompP(s_temp->m[j],1);
    }
    k = si_max(k,1);
  }
  for (j=0; j<IDELEMS(s_temp); j++)
  {
    if (s_temp->m[j]!=NULL)
    {
      p = s_temp->m[j];
      q = pOne();
      //pGetCoeff(q)=nInpNeg(pGetCoeff(q));   //set q to -1
      pSetComp(q,k+1+j);
      pSetmComp(q);
      while (pNext(p)) pIter(p);
      pNext(p) = q;
    }
  }
  s_temp->rank = k+IDELEMS(s_temp);
}

idQuot()

ideal idQuot	(	ideal	h1,
		ideal	h2,
		BOOLEAN	h1IsStb,
		BOOLEAN	resultIsIdeal
	)

Definition at line 1260 of file ideals.cc.

{
  // first check for special case h1:(0)
  if (idIs0(h2))
  {
    ideal res;
    if (resultIsIdeal)
    {
      res = idInit(1,1);
      res->m[0] = pOne();
    }
    else
      res = idFreeModule(h1->rank);
    return res;
  }
  BITSET old_test1;
  SI_SAVE_OPT1(old_test1);
  int i, kmax;
  BOOLEAN  addOnlyOne=TRUE;
  tHomog   hom=isNotHomog;
  intvec * weights1;

  ideal s_h4 = idInitializeQuot (h1,h2,h1IsStb,&addOnlyOne,&kmax);

  hom = (tHomog)idHomModule(s_h4,currRing->qideal,&weights1);

  ring orig_ring=currRing;
  ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);  rChangeCurrRing(syz_ring);
  rSetSyzComp(kmax-1,syz_ring);
  if (orig_ring!=syz_ring)
  //  s_h4 = idrMoveR_NoSort(s_h4,orig_ring, syz_ring);
    s_h4 = idrMoveR(s_h4,orig_ring, syz_ring);
  idTest(s_h4);
  #if 0
  void ipPrint_MA0(matrix m, const char *name);
  matrix m=idModule2Matrix(idCopy(s_h4));
  PrintS("start:\n");
  ipPrint_MA0(m,"Q");
  idDelete((ideal *)&m);
  PrintS("last elem:");wrp(s_h4->m[IDELEMS(s_h4)-1]);PrintLn();
  #endif
  ideal s_h3;
  if (addOnlyOne)
  {
    s_h3 = kStd(s_h4,currRing->qideal,hom,&weights1,NULL,0/*kmax-1*/,IDELEMS(s_h4)-1);
  }
  else
  {
    s_h3 = kStd(s_h4,currRing->qideal,hom,&weights1,NULL,kmax-1);
  }
  SI_RESTORE_OPT1(old_test1);
  #if 0
  // only together with the above debug stuff
  idSkipZeroes(s_h3);
  m=idModule2Matrix(idCopy(s_h3));
  Print("result, kmax=%d:\n",kmax);
  ipPrint_MA0(m,"S");
  idDelete((ideal *)&m);
  #endif
  idTest(s_h3);
  if (weights1!=NULL) delete weights1;
  idDelete(&s_h4);

  for (i=0;i<IDELEMS(s_h3);i++)
  {
    if ((s_h3->m[i]!=NULL) && (pGetComp(s_h3->m[i])>=kmax))
    {
      if (resultIsIdeal)
        p_Shift(&s_h3->m[i],-kmax,currRing);
      else
        p_Shift(&s_h3->m[i],-kmax+1,currRing);
    }
    else
      p_Delete(&s_h3->m[i],currRing);
  }
  if (resultIsIdeal)
    s_h3->rank = 1;
  else
    s_h3->rank = h1->rank;
  if(syz_ring!=orig_ring)
  {
    rChangeCurrRing(orig_ring);
    s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
    rDelete(syz_ring);
  }
  idSkipZeroes(s_h3);
  idTest(s_h3);
  return s_h3;
}

idSect()

ideal idSect	(	ideal	h1,
		ideal	h2
	)

Definition at line 201 of file ideals.cc.

{
  int i,j,k,length;
  int flength = id_RankFreeModule(h1,currRing);
  int slength = id_RankFreeModule(h2,currRing);
  int rank=si_max(h1->rank,h2->rank);
  if ((idIs0(h1)) || (idIs0(h2)))  return idInit(1,rank);

  ideal first,second,temp,temp1,result;
  poly p,q;

  if (IDELEMS(h1)<IDELEMS(h2))
  {
    first = h1;
    second = h2;
  }
  else
  {
    first = h2;
    second = h1;
    int t=flength; flength=slength; slength=t;
  }
  length  = si_max(flength,slength);
  if (length==0)
  {
    if ((currRing->qideal==NULL)
    && (currRing->OrdSgn==1)
    && (!rIsPluralRing(currRing))
    && ((TEST_V_INTERSECT_ELIM) || (!TEST_V_INTERSECT_SYZ)))
      return idSectWithElim(first,second);
    else length = 1;
  }
  if (TEST_OPT_PROT) PrintS("intersect by syzygy methods\n");
  j = IDELEMS(first);

  ring orig_ring=currRing;
  ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE); rChangeCurrRing(syz_ring);
  rSetSyzComp(length, syz_ring);

  while ((j>0) && (first->m[j-1]==NULL)) j--;
  temp = idInit(j /*IDELEMS(first)*/+IDELEMS(second),length+j);
  k = 0;
  for (i=0;i<j;i++)
  {
    if (first->m[i]!=NULL)
    {
      if (syz_ring==orig_ring)
        temp->m[k] = pCopy(first->m[i]);
      else
        temp->m[k] = prCopyR(first->m[i], orig_ring, syz_ring);
      q = pOne();
      pSetComp(q,i+1+length);
      pSetmComp(q);
      if (flength==0) p_Shift(&(temp->m[k]),1,currRing);
      p = temp->m[k];
      while (pNext(p)!=NULL) pIter(p);
      pNext(p) = q;
      k++;
    }
  }
  for (i=0;i<IDELEMS(second);i++)
  {
    if (second->m[i]!=NULL)
    {
      if (syz_ring==orig_ring)
        temp->m[k] = pCopy(second->m[i]);
      else
        temp->m[k] = prCopyR(second->m[i], orig_ring,currRing);
      if (slength==0) p_Shift(&(temp->m[k]),1,currRing);
      k++;
    }
  }
  intvec *w=NULL;
  temp1 = kStd(temp,currRing->qideal,testHomog,&w,NULL,length);
  if (w!=NULL) delete w;
  idDelete(&temp);
  if(syz_ring!=orig_ring)
    rChangeCurrRing(orig_ring);

  result = idInit(IDELEMS(temp1),rank);
  j = 0;
  for (i=0;i<IDELEMS(temp1);i++)
  {
    if ((temp1->m[i]!=NULL)
    && (p_GetComp(temp1->m[i],syz_ring)>length))
    {
      if(syz_ring==orig_ring)
      {
        p = temp1->m[i];
      }
      else
      {
        p = prMoveR(temp1->m[i], syz_ring,orig_ring);
      }
      temp1->m[i]=NULL;
      while (p!=NULL)
      {
        q = pNext(p);
        pNext(p) = NULL;
        k = pGetComp(p)-1-length;
        pSetComp(p,0);
        pSetmComp(p);
        /* Warning! multiply only from the left! it's very important for Plural */
        result->m[j] = pAdd(result->m[j],pMult(p,pCopy(first->m[k])));
        p = q;
      }
      j++;
    }
  }
  if(syz_ring!=orig_ring)
  {
    rChangeCurrRing(syz_ring);
    idDelete(&temp1);
    rChangeCurrRing(orig_ring);
    rDelete(syz_ring);
  }
  else
  {
    idDelete(&temp1);
  }

  idSkipZeroes(result);
  if (TEST_OPT_RETURN_SB)
  {
     w=NULL;
     temp1=kStd(result,currRing->qideal,testHomog,&w);
     if (w!=NULL) delete w;
     idDelete(&result);
     idSkipZeroes(temp1);
     return temp1;
  }
  else //temp1=kInterRed(result,currRing->qideal);
    return result;
}

idSectWithElim()

ideal idSectWithElim	(	ideal	h1,
		ideal	h2
	)

Definition at line 131 of file ideals.cc.

{
  if (TEST_OPT_PROT) PrintS("intersect by elimination method\n");
  assume(!idIs0(h1));
  assume(!idIs0(h2));
  assume(IDELEMS(h1)<=IDELEMS(h2));
  assume(id_RankFreeModule(h1,currRing)==0);
  assume(id_RankFreeModule(h2,currRing)==0);
  // add a new variable:
  int j;
  ring origRing=currRing;
  ring r=rCopy0(origRing);
  r->N++;
  r->block0[0]=1;
  r->block1[0]= r->N;
  omFree(r->order);
  r->order=(int*)omAlloc0(3*sizeof(int*));
  r->order[0]=ringorder_dp;
  r->order[1]=ringorder_C;
  char **names=(char**)omAlloc0(rVar(r) * sizeof(char_ptr));
  for (j=0;j<r->N-1;j++) names[j]=r->names[j];
  names[r->N-1]=omStrDup("@");
  omFree(r->names);
  r->names=names;
  rComplete(r,TRUE);
  // fetch h1, h2
  ideal h;
  h1=idrCopyR(h1,origRing,r);
  h2=idrCopyR(h2,origRing,r);
  // switch to temp. ring r
  rChangeCurrRing(r);
  // create 1-t, t
  poly omt=p_One(currRing);
  p_SetExp(omt,r->N,1,currRing);
  poly t=p_Copy(omt,currRing);
  p_Setm(omt,currRing);
  omt=p_Neg(omt,currRing);
  omt=p_Add_q(omt,pOne(),currRing);
  // compute (1-t)*h1
  h1=(ideal)mp_MultP((matrix)h1,omt,currRing);
  // compute t*h2
  h2=(ideal)mp_MultP((matrix)h2,pCopy(t),currRing);
  // (1-t)h1 + t*h2
  h=idInit(IDELEMS(h1)+IDELEMS(h2),1);
  int l;
  for (l=IDELEMS(h1)-1; l>=0; l--)
  {
    h->m[l] = h1->m[l];  h1->m[l]=NULL;
  }
  j=IDELEMS(h1);
  for (l=IDELEMS(h2)-1; l>=0; l--)
  {
    h->m[l+j] = h2->m[l];  h2->m[l]=NULL;
  }
  idDelete(&h1);
  idDelete(&h2);
  // eliminate t:

  ideal res=idElimination(h,t);
  // cleanup
  idDelete(&h);
  if (res!=NULL) res=idrMoveR(res,r,origRing);
  rChangeCurrRing(origRing);
  rDelete(r);
  return res;
}

idSeries()

ideal idSeries	(	int	n,
		ideal	M,
		matrix	U,
		intvec *	w
	)

Definition at line 1886 of file ideals.cc.

{
  for(int i=IDELEMS(M)-1;i>=0;i--)
  {
    if(U==NULL)
      M->m[i]=pSeries(n,M->m[i],NULL,w);
    else
    {
      M->m[i]=pSeries(n,M->m[i],MATELEM(U,i+1,i+1),w);
      MATELEM(U,i+1,i+1)=NULL;
    }
  }
  if(U!=NULL)
    idDelete((ideal*)&U);
  return M;
}

idSort_qsort()

void idSort_qsort	(	poly_sort *	id_sort,
		int	idsize
	)

Definition at line 2554 of file ideals.cc.

{
  qsort(id_sort, idsize, sizeof(poly_sort), pCompare_qsort);
}

idSyzygies()

ideal idSyzygies	(	ideal	h1,
		tHomog	h,
		intvec **	w,
		BOOLEAN	setSyzComp,
		BOOLEAN	setRegularity,
		int *	deg
	)

Definition at line 515 of file ideals.cc.

{
  ideal s_h1;
  int   j, k, length=0,reg;
  BOOLEAN isMonomial=TRUE;
  int ii, idElemens_h1;

  assume(h1 != NULL);

  idElemens_h1=IDELEMS(h1);
#ifdef PDEBUG
  for(ii=0;ii<idElemens_h1 /*IDELEMS(h1)*/;ii++) pTest(h1->m[ii]);
#endif
  if (idIs0(h1))
  {
    ideal result=idFreeModule(idElemens_h1/*IDELEMS(h1)*/);
    return result;
  }
  int slength=(int)id_RankFreeModule(h1,currRing);
  k=si_max(1,slength /*id_RankFreeModule(h1)*/);

  assume(currRing != NULL);
  ring orig_ring=currRing;
  ring syz_ring=rAssure_SyzComp(orig_ring,TRUE); rChangeCurrRing(syz_ring);

  if (setSyzComp)
    rSetSyzComp(k,syz_ring);

  if (orig_ring != syz_ring)
  {
    s_h1=idrCopyR_NoSort(h1,orig_ring,syz_ring);
  }
  else
  {
    s_h1 = h1;
  }

  idTest(s_h1);

  ideal s_h3=idPrepare(s_h1,h,k,w); // main (syz) GB computation

  if (s_h3==NULL)
  {
    return idFreeModule( idElemens_h1 /*IDELEMS(h1)*/);
  }

  if (orig_ring != syz_ring)
  {
    idDelete(&s_h1);
    for (j=0; j<IDELEMS(s_h3); j++)
    {
      if (s_h3->m[j] != NULL)
      {
        if (p_MinComp(s_h3->m[j],syz_ring) > k)
          p_Shift(&s_h3->m[j], -k,syz_ring);
        else
          p_Delete(&s_h3->m[j],syz_ring);
      }
    }
    idSkipZeroes(s_h3);
    s_h3->rank -= k;
    rChangeCurrRing(orig_ring);
    s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
    rDelete(syz_ring);
    #ifdef HAVE_PLURAL
    if (rIsPluralRing(orig_ring))
    {
      id_DelMultiples(s_h3,orig_ring);
      idSkipZeroes(s_h3);
    }
    #endif
    idTest(s_h3);
    return s_h3;
  }

  ideal e = idInit(IDELEMS(s_h3), s_h3->rank);

  for (j=IDELEMS(s_h3)-1; j>=0; j--)
  {
    if (s_h3->m[j] != NULL)
    {
      if (p_MinComp(s_h3->m[j],syz_ring) <= k)
      {
        e->m[j] = s_h3->m[j];
        isMonomial=isMonomial && (pNext(s_h3->m[j])==NULL);
        p_Delete(&pNext(s_h3->m[j]),syz_ring);
        s_h3->m[j] = NULL;
      }
    }
  }

  idSkipZeroes(s_h3);
  idSkipZeroes(e);

  if ((deg != NULL)
  && (!isMonomial)
  && (!TEST_OPT_NOTREGULARITY)
  && (setRegularity)
  && (h==isHomog)
  && (!rIsPluralRing(currRing))
  && (!rField_is_Ring(currRing))
  )
  {
    ring dp_C_ring = rAssure_dp_C(syz_ring); // will do rChangeCurrRing later
    if (dp_C_ring != syz_ring)
    {
      rChangeCurrRing(dp_C_ring);
      e = idrMoveR_NoSort(e, syz_ring, dp_C_ring);
    }
    resolvente res = sySchreyerResolvente(e,-1,&length,TRUE, TRUE);
    intvec * dummy = syBetti(res,length,&reg, *w);
    *deg = reg+2;
    delete dummy;
    for (j=0;j<length;j++)
    {
      if (res[j]!=NULL) idDelete(&(res[j]));
    }
    omFreeSize((ADDRESS)res,length*sizeof(ideal));
    idDelete(&e);
    if (dp_C_ring != syz_ring)
    {
      rChangeCurrRing(syz_ring);
      rDelete(dp_C_ring);
    }
  }
  else
  {
    idDelete(&e);
  }
  idTest(s_h3);
  if (currRing->qideal != NULL)
  {
    ideal ts_h3=kStd(s_h3,currRing->qideal,h,w);
    idDelete(&s_h3);
    s_h3 = ts_h3;
  }
  return s_h3;
}

idTestHomModule()

BOOLEAN idTestHomModule	(	ideal	m,
		ideal	Q,
		intvec *	w
	)

Definition at line 1834 of file ideals.cc.

{
  if ((Q!=NULL) && (!idHomIdeal(Q,NULL)))  { PrintS(" Q not hom\n"); return FALSE;}
  if (idIs0(m)) return TRUE;

  int cmax=-1;
  int i;
  poly p=NULL;
  int length=IDELEMS(m);
  polyset P=m->m;
  for (i=length-1;i>=0;i--)
  {
    p=P[i];
    if (p!=NULL) cmax=si_max(cmax,(int)pMaxComp(p)+1);
  }
  if (w != NULL)
  if (w->length()+1 < cmax)
  {
    // Print("length: %d - %d \n", w->length(),cmax);
    return FALSE;
  }

  if(w!=NULL)
    p_SetModDeg(w, currRing);

  for (i=length-1;i>=0;i--)
  {
    p=P[i];
    if (p!=NULL)
    {
      int d=currRing->pFDeg(p,currRing);
      loop
      {
        pIter(p);
        if (p==NULL) break;
        if (d!=currRing->pFDeg(p,currRing))
        {
          //pWrite(q); wrp(p); Print(" -> %d - %d\n",d,pFDeg(p,currRing));
          if(w!=NULL)
            p_SetModDeg(NULL, currRing);
          return FALSE;
        }
      }
    }
  }

  if(w!=NULL)
    p_SetModDeg(NULL, currRing);

  return TRUE;
}

idXXX()

ideal idXXX	(	ideal	h1,
		int	k
	)

Definition at line 657 of file ideals.cc.

{
  ideal s_h1;
  intvec *w=NULL;

  assume(currRing != NULL);
  ring orig_ring=currRing;
  ring syz_ring=rAssure_SyzComp(orig_ring,TRUE); rChangeCurrRing(syz_ring);

  rSetSyzComp(k,syz_ring);

  if (orig_ring != syz_ring)
  {
    s_h1=idrCopyR_NoSort(h1,orig_ring, syz_ring);
  }
  else
  {
    s_h1 = h1;
  }

  ideal s_h3=kStd(s_h1,NULL,testHomog,&w,NULL,k);

  if (s_h3==NULL)
  {
    return idFreeModule(IDELEMS(h1));
  }

  if (orig_ring != syz_ring)
  {
    idDelete(&s_h1);
    idSkipZeroes(s_h3);
    rChangeCurrRing(orig_ring);
    s_h3 = idrMoveR_NoSort(s_h3, syz_ring, orig_ring);
    rDelete(syz_ring);
    idTest(s_h3);
    return s_h3;
  }

  idSkipZeroes(s_h3);
  idTest(s_h3);
  return s_h3;
}

pCompare_qsort()

int pCompare_qsort	(	const void *	a,
		const void *	b
	)

Definition at line 2549 of file ideals.cc.

{
  return (p_Compare(((poly_sort *)a)->p, ((poly_sort *)b)->p,currRing));
}