ideals.h File Reference

#include "polys/monomials/ring.h"
#include "polys/monomials/p_polys.h"
#include "polys/simpleideals.h"
#include "kernel/structs.h"

Go to the source code of this file.

Macros
#define	idDelete(H)
	delete an ideal
#define	idMaxIdeal(D)
	initialise the maximal ideal (at 0)
#define	idPosConstant(I)
	index of generator with leading term in ground ring (if any); otherwise -1
#define	idIsConstant(I)
#define	idSimpleAdd(A, B)
#define	idPrint(id)
#define	idTest(id)

Typedefs
typedef ideal *	resolvente

Enumerations
enum	GbVariant {   GbDefault =0 , GbStd , GbSlimgb , GbSba ,   GbGroebner , GbModstd , GbFfmod , GbNfmod ,   GbStdSat , GbSingmatic }

Functions
static ideal	idCopyFirstK (const ideal ide, const int k)
void	idKeepFirstK (ideal ide, const int k)
	keeps the first k (>= 1) entries of the given ideal (Note that the kept polynomials may be zero.)
void	idDelEquals (ideal id)
ideal	id_Copy (ideal h1, const ring r)
	copy an ideal
ideal	idCopy (ideal A)
ideal	idAdd (ideal h1, ideal h2)
	h1 + h2
BOOLEAN	idInsertPoly (ideal h1, poly h2)
	insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted
BOOLEAN	idInsertPolyOnPos (ideal I, poly p, int pos)
	insert p into I on position pos
BOOLEAN	idInsertPolyWithTests (ideal h1, const int validEntries, const poly h2, const bool zeroOk, const bool duplicateOk)
static ideal	idMult (ideal h1, ideal h2)
	hh := h1 * h2
BOOLEAN	idIs0 (ideal h)
	returns true if h is the zero ideal
static BOOLEAN	idHomIdeal (ideal id, ideal Q=NULL)
static BOOLEAN	idHomModule (ideal m, ideal Q, intvec **w)
BOOLEAN	idTestHomModule (ideal m, ideal Q, intvec *w)
ideal	idMinBase (ideal h1, ideal *SB=NULL)
void	idInitChoise (int r, int beg, int end, BOOLEAN *endch, int *choise)
void	idGetNextChoise (int r, int end, BOOLEAN *endch, int *choise)
int	idGetNumberOfChoise (int t, int d, int begin, int end, int *choise)
int	binom (int n, int r)
ideal	idFreeModule (int i)
ideal	idSect (ideal h1, ideal h2, GbVariant a=GbDefault)
ideal	idMultSect (resolvente arg, int length, GbVariant a=GbDefault)
ideal	idSyzygies (ideal h1, tHomog h, intvec **w, BOOLEAN setSyzComp=TRUE, BOOLEAN setRegularity=FALSE, int *deg=NULL, GbVariant a=GbDefault)
ideal	idLiftStd (ideal h1, matrix *m, tHomog h=testHomog, ideal *syz=NULL, GbVariant a=GbDefault, ideal h11=NULL)
ideal	idLift (ideal mod, ideal submod, ideal *rest=NULL, BOOLEAN goodShape=FALSE, BOOLEAN isSB=TRUE, BOOLEAN divide=FALSE, matrix *unit=NULL, GbVariant a=GbDefault)
	represents the generators of submod in terms of the generators of mod (Matrix(SM)*U-Matrix(rest)) = Matrix(M)*Matrix(result) goodShape: maximal non-zero index in generators of SM <= that of M isSB: generators of M form a Groebner basis divide: allow SM not to be a submodule of M U is an diagonal matrix of units (non-constant only in local rings) rest is: 0 if SM in M, SM if not divide, NF(SM,std(M)) if divide
void	idLiftW (ideal P, ideal Q, int n, matrix &T, ideal &R, int *w=NULL)
ideal	idQuot (ideal h1, ideal h2, BOOLEAN h1IsStb=FALSE, BOOLEAN resultIsIdeal=FALSE)
ideal	idElimination (ideal h1, poly delVar, intvec *hilb=NULL, GbVariant a=GbDefault)
ideal	idElimination2 (ideal h1, poly delVar, bigintmat *hilb=NULL, GbVariant a=GbDefault)
ideal	idMinors (matrix a, int ar, ideal R=NULL)
	compute all ar-minors of the matrix a the caller of mpRecMin the elements of the result are not in R (if R!=NULL)
ideal	idMinEmbedding (ideal arg, BOOLEAN inPlace=FALSE, intvec **w=NULL)
ideal	idMinEmbedding_with_map (ideal arg, intvec **w, ideal &trans)
ideal	idMinEmbedding_with_map_v (ideal arg, intvec **w, ideal &trans, int *red_comp)
ideal	idHead (ideal h)
BOOLEAN	idIsSubModule (ideal id1, ideal id2)
static ideal	idVec2Ideal (poly vec)
ideal	idSeries (int n, ideal M, matrix U=NULL, intvec *w=NULL)
static BOOLEAN	idIsZeroDim (ideal i)
matrix	idDiff (matrix i, int k)
matrix	idDiffOp (ideal I, ideal J, BOOLEAN multiply=TRUE)
static intvec *	idSort (ideal id, BOOLEAN nolex=TRUE)
ideal	idModulo (ideal h1, ideal h2, tHomog h=testHomog, intvec **w=NULL, matrix *T=NULL, GbVariant a=GbDefault)
matrix	idCoeffOfKBase (ideal arg, ideal kbase, poly how)
poly	id_GCD (poly f, poly g, const ring r)
ideal	id_Farey (ideal x, number N, const ring r)
ideal	id_TensorModuleMult (const int m, const ideal M, const ring rRing)
ideal	id_Satstd (const ideal I, ideal J, const ring r)
ideal	id_Sat_principal (const ideal I, ideal J, const ring r)
ideal	idSaturate_intern (ideal I, ideal J, int &ki, BOOLEAN isIdeal, BOOLEAN isSB)
ideal	idSaturate (ideal I, ideal J, int &ki, BOOLEAN isIdeal=TRUE)
ideal	idSaturateGB (ideal I, ideal J, int &ki, BOOLEAN isIdeal=TRUE)
ideal	id_Homogenize (ideal I, int var_num, const ring r)
ideal	id_HomogenizeW (ideal I, int var_num, intvec *w, const ring r)
GbVariant	syGetAlgorithm (char *n, const ring r, const ideal M)

Macro Definition Documentation

idDelete

#define idDelete

(

H

)

Value:

id_Delete((H),currRing)

delete an ideal

Definition at line 29 of file ideals.h.

idIsConstant

#define idIsConstant

(

I

)

Value:

id_IsConstant(I,currRing)

Definition at line 40 of file ideals.h.

idMaxIdeal

#define idMaxIdeal

(

D

)

Value:

id_MaxIdeal(D,currRing)

initialise the maximal ideal (at 0)

Definition at line 33 of file ideals.h.

idPosConstant

#define idPosConstant

(

I

)

Value:

id_PosConstant(I,currRing)

index of generator with leading term in ground ring (if any); otherwise -1

Definition at line 37 of file ideals.h.

idPrint

#define idPrint

(

id

)

Value:

id_Print(id, currRing, currRing)

Definition at line 46 of file ideals.h.

idSimpleAdd

#define idSimpleAdd	(		A,
			B )

Value:

id_SimpleAdd(A,B,currRing)

Definition at line 42 of file ideals.h.

idTest

#define idTest

(

id

)

Value:

id_Test(id, currRing)

Definition at line 47 of file ideals.h.

Typedef Documentation

resolvente

typedef ideal* resolvente

Definition at line 18 of file ideals.h.

Enumeration Type Documentation

GbVariant

enum GbVariant

Enumerator
GbDefault
GbStd
GbSlimgb
GbSba
GbGroebner
GbModstd
GbFfmod
GbNfmod
GbStdSat
GbSingmatic

Definition at line 118 of file ideals.h.

{
  GbDefault=0,
  // internal variants:
  GbStd,
  GbSlimgb,
  GbSba,
  // and the library functions:
  GbGroebner,
  GbModstd,
  GbFfmod,
  GbNfmod,
  GbStdSat,
  GbSingmatic
  // and test variants
};

Function Documentation

binom()

int binom	(	int	n,
		int	r )

Definition at line 1212 of file simpleideals.cc.

{
  int i;
  int64 result;
 
  if (r==0) return 1;
  if (n-r<r) return binom(n,n-r);
  result = n-r+1;
  for (i=2;i<=r;i++)
  {
    result *= n-r+i;
    result /= i;
  }
  if (result>MAX_INT_VAL)
  {
    WarnS("overflow in binomials");
    result=0;
  }
  return (int)result;
}

id_Copy()

ideal id_Copy	(	ideal	h1,
		const ring	r )

copy an ideal

Definition at line 542 of file simpleideals.cc.

{
  id_Test(h1, r);
 
  ideal h2 = idInit(IDELEMS(h1), h1->rank);
  for (int i=IDELEMS(h1)-1; i>=0; i--)
    h2->m[i] = p_Copy(h1->m[i],r);
  return h2;
}

id_Farey()

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

Definition at line 3103 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 3000 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;
}

id_Homogenize()

ideal id_Homogenize	(	ideal	I,
		int	var_num,
		const ring	r )

Definition at line 3608 of file ideals.cc.

{
  ideal II=id_Copy(I,r);
  if (var_num==1)
  {
    ring tmpR=rAssure_Dp_C(r);
    if (tmpR!=r)
    {
      rChangeCurrRing(tmpR);
      II=idrMoveR(II,r,tmpR);
    }
    ideal III=id_Homogen(II,1,tmpR);
    id_Delete(&II,tmpR);
    intvec *ww=NULL;
    II=kStd2(III,currRing->qideal,(tHomog)TRUE,&ww,(bigintmat*)NULL);
    if (ww!=NULL) delete ww;
    id_Delete(&III,tmpR);
    if (tmpR!=r)
    {
      rChangeCurrRing(r);
      II=idrMoveR(II,tmpR,r);
    }
    return II;
  }
  ideal III=idInit(IDELEMS(II),1);
  int *perm=(int*)omAlloc0((rVar(r)+1)*sizeof(int));
  for(int i=rVar(r)-1; i>0; i--) perm[i]=i;
  perm[var_num]=1;
  perm[1]=var_num;
  for(int i=IDELEMS(II)-1; i>=0;i--)
  {
    III->m[i]=p_PermPoly(II->m[i],perm,r,r,ndCopyMap,NULL,0,FALSE);
  }
  id_Delete(&II,r);
  II=id_Homogenize(III,1,r);
  id_Delete(&III,r);
  III=idInit(IDELEMS(II),1);
  for(int i=IDELEMS(II)-1; i>=0;i--)
  {
    III->m[i]=p_PermPoly(II->m[i],perm,r,r,ndCopyMap,NULL,0,FALSE);
  }
  id_Delete(&II,r);
  return III;
}

id_HomogenizeW()

ideal id_HomogenizeW	(	ideal	I,
		int	var_num,
		intvec *	w,
		const ring	r )

Definition at line 3653 of file ideals.cc.

{
  ideal II=id_Copy(I,r);
  if (var_num==1)
  {
    ring tmpR=rAssure_Wp_C(r,w);
    if (tmpR!=r)
    {
      rChangeCurrRing(tmpR);
      II=idrMoveR(II,r,tmpR);
    }
    ideal III=id_Homogen(II,1,tmpR);
    id_Delete(&II,tmpR);
    intvec *ww=NULL;
    II=kStd2(III,currRing->qideal,(tHomog)TRUE,&ww,(bigintmat*)NULL);
    if (ww!=NULL) delete ww;
    id_Delete(&III,tmpR);
    if (tmpR!=r)
    {
      rChangeCurrRing(r);
      II=idrMoveR(II,tmpR,r);
    }
    return II;
  }
  ideal III=idInit(IDELEMS(II),1);
  int *perm=(int*)omAlloc0((rVar(r)+1)*sizeof(int));
  for(int i=rVar(r)-1; i>0; i--) perm[i]=i;
  perm[var_num]=1;
  perm[1]=var_num;
  for(int i=IDELEMS(II)-1; i>=0;i--)
  {
    III->m[i]=p_PermPoly(II->m[i],perm,r,r,ndCopyMap,NULL,0,FALSE);
  }
  id_Delete(&II,r);
  II=id_HomogenizeW(III,1,w,r);
  id_Delete(&III,r);
  III=idInit(IDELEMS(II),1);
  for(int i=IDELEMS(II)-1; i>=0;i--)
  {
    III->m[i]=p_PermPoly(II->m[i],perm,r,r,ndCopyMap,NULL,0,FALSE);
  }
  id_Delete(&II,r);
  return III;
}

id_Sat_principal()

ideal id_Sat_principal	(	const ideal	I,
		ideal	J,
		const ring	r )

Definition at line 3415 of file ideals.cc.

{
  rRingOrder_t    *ord;
  int    *block0,*block1;
  int    **wv;
 
  // construction extension ring
  ord=(rRingOrder_t*)omAlloc0(4*sizeof(rRingOrder_t));
  block0=(int*)omAlloc0(4*sizeof(int));
  block1=(int*)omAlloc0(4*sizeof(int));
  wv=(int**) omAlloc0(4*sizeof(int**));
  wv[0]=(int*)omAlloc0((rVar(origR) + 2)*sizeof(int));
  block0[0] = block0[1] = 1;
  block1[0] = block1[1] = rVar(origR)+1;
  // use this special ordering: like ringorder_a, except that pFDeg, pWeights
  // ignore it
  ord[0] = ringorder_aa;
  wv[0][rVar(origR)]=1;
  BOOLEAN wp=FALSE;
  for (int 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 (int j=0;j<rVar(origR);j++)
      wv[1][j]=p_Weight(j+1,origR);
    ord[1] = ringorder_wp;
  }
  else
    ord[1] = ringorder_dp;
  ord[2] = ringorder_C;
  ord[3] = (rRingOrder_t)0;
  char **names=(char**)omAlloc0((origR->N+1) * sizeof(char *));
  for (int j=0;j<rVar(origR);j++)
    names[j]=origR->names[j];
  names[rVar(origR)]=(char*)"@";
  ring tmpR=rDefault(nCopyCoeff(origR->cf),rVar(origR)+1,names,4,ord,block0,block1,wv);
  omFree(names);
  rComplete(tmpR, 1);
  rChangeCurrRing(tmpR);
  // map I
  ideal II=idrCopyR(I,origR,tmpR);
  // map J
  ideal JJ=idrCopyR(J,origR,tmpR);
  // J[1]*t-1
  poly t=pOne();
  p_SetExp(t,rVar(tmpR),1,tmpR);
  p_Setm(t,tmpR);
  poly p=JJ->m[0];
  p_Norm(p,currRing);
  p=p_Mult_q(p,t,tmpR);
  p=p_Sub(p,pOne(),tmpR);
  JJ->m[0]=p;
  ideal T=id_SimpleAdd(II,JJ,tmpR);
  idTest(T);
  id_Delete(&II,tmpR);
  id_Delete(&JJ,tmpR);
  // elimination
  t=pOne();
  p_SetExp(t,rVar(tmpR),1,tmpR);
  p_Setm(t,tmpR);
  ideal TT=idGroebner(T,0,GbStd);
  p_Delete(&t,tmpR);
  for(int j=0;j<IDELEMS(TT);j++)
  {
    if ((TT->m[j]!=NULL)
    && (p_GetExp(TT->m[j],rVar(tmpR),tmpR)>0))
    {
      p_Delete(&TT->m[j],tmpR);
    }
  }
  // map back
  ideal TTT=idrCopyR(TT,tmpR,origR);
  id_Delete(&TT,tmpR);
  rChangeCurrRing(origR);
  rDelete(tmpR);
  idSkipZeroes(TTT);
  return TTT;
}

id_Satstd()

ideal id_Satstd	(	const ideal	I,
		ideal	J,
		const ring	r )

Definition at line 3363 of file ideals.cc.

{
  ring save=currRing;
  if (currRing!=r) rChangeCurrRing(r);
  idSkipZeroes(J);
  id_satstdSaturatingVariables=(int*)omAlloc0((1+rVar(currRing))*sizeof(int));
  int k=IDELEMS(J);
  if (k>1)
  {
    for (int i=0; i<k; i++)
    {
      poly x = J->m[i];
      int li = p_Var(x,r);
      if (li>0)
        id_satstdSaturatingVariables[li]=1;
      else
      {
        if (currRing!=save) rChangeCurrRing(save);
        WerrorS("ideal generators must be variables");
        return NULL;
      }
    }
  }
  else
  {
    poly x = J->m[0];
    if (pNext(x)!=NULL)
    {
      Werror("generator must be a monomial");
      if (currRing!=save) rChangeCurrRing(save);
      return NULL;
    }
    for (int i=1; i<=r->N; i++)
    {
      int li = p_GetExp(x,i,r);
      if (li==1)
        id_satstdSaturatingVariables[i]=1;
      else if (li>1)
      {
        if (currRing!=save) rChangeCurrRing(save);
        Werror("exponent(x(%d)^%d) must be 0 or 1",i,li);
        return NULL;
      }
    }
  }
  ideal res=kStd2(I,r->qideal,testHomog,NULL,(bigintmat*)NULL,0,0,NULL,id_sat_vars_sp);
  omFreeSize(id_satstdSaturatingVariables,(1+rVar(currRing))*sizeof(int));
  id_satstdSaturatingVariables=NULL;
  if (currRing!=save) rChangeCurrRing(save);
  return res;
}

id_TensorModuleMult()

ideal id_TensorModuleMult	(	const int	m,
		const ideal	M,
		const ring	rRing )

Definition at line 2067 of file simpleideals.cc.

{
// #ifdef DEBU
//  WarnS("tensorModuleMult!!!!");
 
  assume(m > 0);
  assume(M != NULL);
 
  const int n = rRing->N;
 
  assume(M->rank <= m * n);
 
  const int k = IDELEMS(M);
 
  ideal idTemp =  idInit(k,m); // = {f_1, ..., f_k }
 
  for( int i = 0; i < k; i++ ) // for every w \in M
  {
    poly pTempSum = NULL;
 
    poly w = M->m[i];
 
    while(w != NULL) // for each term of w...
    {
      poly h = p_Head(w, rRing);
 
      const int  gen = __p_GetComp(h, rRing); // 1 ...
 
      assume(gen > 0);
      assume(gen <= n*m);
 
      // TODO: write a formula with %, / instead of while!
      /*
      int c = gen;
      int v = 1;
      while(c > m)
      {
        c -= m;
        v++;
      }
      */
 
      int cc = gen % m;
      if( cc == 0) cc = m;
      int vv = 1 + (gen - cc) / m;
 
//      assume( cc == c );
//      assume( vv == v );
 
      //  1<= c <= m
      assume( cc > 0 );
      assume( cc <= m );
 
      assume( vv > 0 );
      assume( vv <= n );
 
      assume( (cc + (vv-1)*m) == gen );
 
      p_IncrExp(h, vv, rRing); // h *= var(j) && //      p_AddExp(h, vv, 1, rRing);
      p_SetComp(h, cc, rRing);
 
      p_Setm(h, rRing);         // adjust degree after the previous steps!
 
      pTempSum = p_Add_q(pTempSum, h, rRing); // it is slow since h will be usually put to the back of pTempSum!!!
 
      pIter(w);
    }
 
    idTemp->m[i] = pTempSum;
  }
 
  // simplify idTemp???
 
  ideal idResult = id_Transp(idTemp, rRing);
 
  id_Delete(&idTemp, rRing);
 
  return(idResult);
}

idAdd()

ideal idAdd ( ideal h1, ideal h2 )

inline

h1 + h2

Definition at line 68 of file ideals.h.

{
  return id_Add(h1, h2, currRing);
}

idCoeffOfKBase()

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

Definition at line 2668 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;
}

idCopy()

ideal idCopy ( ideal A )

inline

Definition at line 60 of file ideals.h.

{
  return id_Copy(A, currRing);
}

idCopyFirstK()

ideal idCopyFirstK ( const ideal ide, const int k )

inlinestatic

Definition at line 20 of file ideals.h.

{
  return id_CopyFirstK(ide, k, currRing);
}

idDelEquals()

void idDelEquals

(

ideal

id

)

Definition at line 3211 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));
}

idDiff()

matrix idDiff	(	matrix	i,
		int	k )

Definition at line 2189 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 = TRUE )

Definition at line 2202 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 = NULL,
		GbVariant	a = GbDefault )

Definition at line 1884 of file ideals.cc.

{
  bigintmat *hh=iv2biv(hilb,coeffs_BIGINT);
  ideal res=idElimination2(h1,delVar,hh,alg);
  if (hh!=NULL) delete hh;
  return res;
}

idElimination2()

ideal idElimination2	(	ideal	h1,
		poly	delVar,
		bigintmat *	hilb = NULL,
		GbVariant	a = GbDefault )

Definition at line 1640 of file ideals.cc.

{
  int    i,j=0,k,l;
  ideal  h,hh, h3;
  rRingOrder_t    *ord;
  int    *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);
  ordersize=rBlocks(origR)+1;
#if 0
  if (rIsPluralRing(origR)) // we have too keep the ordering: 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=(rRingOrder_t*)omAlloc0(4*sizeof(rRingOrder_t));
    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] = (rRingOrder_t)0;
  }
  else
  {
    // we change to an ordering:
    // aa(....),orig_ordering
    ord=(rRingOrder_t*)omAlloc0(ordersize*sizeof(rRingOrder_t));
    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)
      #ifdef HAVE_OMALLOC
        wv[k+1] = (int*) omMemDup(origR->wvhdl[k]);
      #else
      {
        int l=(origR->block1[k]-origR->block0[k]+1)*sizeof(int);
        if (origR->order[k]==ringorder_a64) l*=2;
        wv[k+1]=(int*)omalloc(l);
        memcpy(wv[k+1],origR->wvhdl[k],l);
      }
      #endif
    }
    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 GB
  if ((alg!=GbDefault)
  && (alg!=GbGroebner)
  && (alg!=GbModstd)
  && (alg!=GbSlimgb)
  && (alg!=GbSba)
  && (alg!=GbStd))
  {
    WarnS("wrong algorithm for GB");
    alg=GbDefault;
  }
  hh=idGroebner(h,0,alg,hilb);
  // 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;
}

idFreeModule()

ideal idFreeModule ( int i )

inline

Definition at line 111 of file ideals.h.

{
  return id_FreeModule (i, currRing);
}

idGetNextChoise()

void idGetNextChoise	(	int	r,
		int	end,
		BOOLEAN *	endch,
		int *	choise )

Definition at line 1154 of file simpleideals.cc.

{
  int i = r-1,j;
  while ((i >= 0) && (choise[i] == end))
  {
    i--;
    end--;
  }
  if (i == -1)
    *endch = TRUE;
  else
  {
    choise[i]++;
    for (j=i+1; j<r; j++)
    {
      choise[j] = choise[i]+j-i;
    }
    *endch = FALSE;
  }
}

idGetNumberOfChoise()

int idGetNumberOfChoise	(	int	t,
		int	d,
		int	begin,
		int	end,
		int *	choise )

Definition at line 1180 of file simpleideals.cc.

{
  int * localchoise,i,result=0;
  BOOLEAN b=FALSE;
 
  if (d<=1) return 1;
  localchoise=(int*)omAlloc((d-1)*sizeof(int));
  idInitChoise(d-1,begin,end,&b,localchoise);
  while (!b)
  {
    result++;
    i = 0;
    while ((i<t) && (localchoise[i]==choise[i])) i++;
    if (i>=t)
    {
      i = t+1;
      while ((i<d) && (localchoise[i-1]==choise[i])) i++;
      if (i>=d)
      {
        omFreeSize((ADDRESS)localchoise,(d-1)*sizeof(int));
        return result;
      }
    }
    idGetNextChoise(d-1,end,&b,localchoise);
  }
  omFreeSize((ADDRESS)localchoise,(d-1)*sizeof(int));
  return 0;
}

idHead()

ideal idHead

(

ideal

h

)

idHomIdeal()

BOOLEAN idHomIdeal ( ideal id, ideal Q = NULL )

inlinestatic

Definition at line 91 of file ideals.h.

{
  return id_HomIdeal(id, Q, currRing);
}

idHomModule()

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

inlinestatic

Definition at line 96 of file ideals.h.

{
   return id_HomModule(m, Q, w, currRing);
}

idInitChoise()

void idInitChoise	(	int	r,
		int	beg,
		int	end,
		BOOLEAN *	endch,
		int *	choise )

Definition at line 1132 of file simpleideals.cc.

{
  /*returns the first choise of r numbers between beg and end*/
  int i;
  for (i=0; i<r; i++)
  {
    choise[i] = 0;
  }
  if (r <= end-beg+1)
    for (i=0; i<r; i++)
    {
      choise[i] = beg+i;
    }
  if (r > end-beg+1)
    *endch = TRUE;
  else
    *endch = FALSE;
}

idInsertPoly()

BOOLEAN idInsertPoly	(	ideal	h1,
		poly	h2 )

insert h2 into h1 (if h2 is not the zero polynomial) return TRUE iff h2 was indeed inserted

Definition at line 832 of file simpleideals.cc.

{
  if (h2==NULL) return FALSE;
  assume (h1 != NULL);
 
  int j = IDELEMS(h1) - 1;
 
  while ((j >= 0) && (h1->m[j] == NULL)) j--;
  j++;
  if (j==IDELEMS(h1))
  {
    pEnlargeSet(&(h1->m),IDELEMS(h1),16);
    IDELEMS(h1)+=16;
  }
  h1->m[j]=h2;
  return TRUE;
}

idInsertPolyOnPos()

BOOLEAN idInsertPolyOnPos	(	ideal	I,
		poly	p,
		int	pos )

insert p into I on position pos

Definition at line 851 of file simpleideals.cc.

{
  if (p==NULL) return FALSE;
  assume (I != NULL);
 
  int j = IDELEMS(I) - 1;
 
  while ((j >= 0) && (I->m[j] == NULL)) j--;
  j++;
  if (j==IDELEMS(I))
  {
    pEnlargeSet(&(I->m),IDELEMS(I),IDELEMS(I)+1);
    IDELEMS(I)+=1;
  }
  for(j = IDELEMS(I)-1;j>pos;j--)
    I->m[j] = I->m[j-1];
  I->m[pos]=p;
  return TRUE;
}

idInsertPolyWithTests()

BOOLEAN idInsertPolyWithTests ( ideal h1, const int validEntries, const poly h2, const bool zeroOk, const bool duplicateOk )

inline

Definition at line 75 of file ideals.h.

{
  return id_InsertPolyWithTests (h1, validEntries, h2, zeroOk, duplicateOk, currRing);
}

idIs0()

BOOLEAN idIs0

(

ideal

h

)

returns true if h is the zero ideal

Definition at line 960 of file simpleideals.cc.

{
  if ((h!=NULL) && (h->m!=NULL))
  {
    for( int i = IDELEMS(h)-1; i >= 0; i-- )
      if(h->m[i] != NULL)
        return FALSE;
  }
  return TRUE;
}

idIsSubModule()

BOOLEAN idIsSubModule	(	ideal	id1,
		ideal	id2 )

Definition at line 2099 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;
}

idIsZeroDim()

BOOLEAN idIsZeroDim ( ideal i )

inlinestatic

Definition at line 180 of file ideals.h.

{
  return id_IsZeroDim(i, currRing);
}

idKeepFirstK()

void idKeepFirstK	(	ideal	ide,
		const int	k )

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

Definition at line 3179 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 = NULL,
		BOOLEAN	goodShape = FALSE,
		BOOLEAN	isSB = TRUE,
		BOOLEAN	divide = FALSE,
		matrix *	unit = NULL,
		GbVariant	a = GbDefault )

represents the generators of submod in terms of the generators of mod (Matrix(SM)*U-Matrix(rest)) = Matrix(M)*Matrix(result) goodShape: maximal non-zero index in generators of SM <= that of M isSB: generators of M form a Groebner basis divide: allow SM not to be a submodule of M U is an diagonal matrix of units (non-constant only in local rings) rest is: 0 if SM in M, SM if not divide, NF(SM,std(M)) if divide

Definition at line 1111 of file ideals.cc.

{
  int lsmod =id_RankFreeModule(submod,currRing), j, k;
  int comps_to_add=0;
  int idelems_mod=IDELEMS(mod);
  int idelems_submod=IDELEMS(submod);
  poly p;
 
  if (idIs0(submod))
  {
    if (rest!=NULL)
    {
      *rest=idInit(1,mod->rank);
    }
    idLift_setUnit(idelems_submod,unit);
    return idInit(1,idelems_mod);
  }
  if (idIs0(mod)) /* and not idIs0(submod) */
  {
    if (rest!=NULL)
    {
      *rest=idCopy(submod);
      idLift_setUnit(idelems_submod,unit);
      return idInit(1,idelems_mod);
    }
    else
    {
      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);
  rSetSyzComp(k,syz_ring);
  rChangeCurrRing(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 = idCopy(mod);
    s_temp = idCopy(submod);
  }
  BITSET save2;
  SI_SAVE_OPT2(save2);
 
  if ((rest==NULL)
  && (!rField_is_Ring(currRing))
  && (!rIsNCRing(currRing))
  && (!TEST_OPT_RETURN_SB))
    si_opt_2 |=Sy_bit(V_IDLIFT);
  else
    si_opt_2 &=~Sy_bit(V_IDLIFT);
  ideal s_h3;
  if (isSB && !TEST_OPT_IDLIFT)
  {
    s_h3 = idCopy(s_mod);
    idPrepareStd(s_h3, k+comps_to_add);
  }
  else
  {
    s_h3 = idPrepare(s_mod,NULL,(tHomog)FALSE,k+comps_to_add,NULL,alg);
  }
  SI_RESTORE_OPT2(save2);
  if (errorreported)
  {
    rChangeCurrRing(orig_ring);
    return 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 (rest==NULL)
          {
            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);
          if(syz_ring!=orig_ring)
          {
            idDelete(&s_mod);
            rChangeCurrRing(orig_ring);
            rDelete(syz_ring);
          }
          if (unit!=NULL)
          {
            idLift_setUnit(idelems_submod,unit);
          }
          if (rest!=NULL) *rest=idCopy(submod);
          s_result=idInit(idelems_submod,idelems_mod);
          return s_result;
        }
        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);
      }
    }
  }
  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)
  {
    s_rest->rank=mod->rank;
    *rest = s_rest;
  }
  else
    idDelete(&s_rest);
  if (unit!=NULL)
  {
    *unit=mpNew(idelems_submod,idelems_submod);
    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);
    }
  }
  s_result->rank=idelems_mod;
  return s_result;
}

idLiftStd()

ideal idLiftStd	(	ideal	h1,
		matrix *	m,
		tHomog	h = testHomog,
		ideal *	syz = NULL,
		GbVariant	a = GbDefault,
		ideal	h11 = NULL )

Definition at line 982 of file ideals.cc.

{
  int  inputIsIdeal=id_RankFreeModule(h1,currRing);
  long k;
  intvec *w=NULL;
 
  idDelete((ideal*)T);
  BOOLEAN lift3=FALSE;
  if (S!=NULL) { lift3=TRUE; idDelete(S); }
  if (idIs0(h1))
  {
    *T=mpNew(1,IDELEMS(h1));
    if (lift3)
    {
      *S=idFreeModule(IDELEMS(h1));
    }
    return idInit(1,h1->rank);
  }
 
  BITSET saveOpt1,saveOpt2;
  SI_SAVE_OPT(saveOpt1,saveOpt2);
  si_opt_2|=Sy_bit(V_PURE_GB);
  k=si_max(1,inputIsIdeal);
 
  if ((!lift3)&&(!TEST_OPT_RETURN_SB)) si_opt_2 |=Sy_bit(V_IDLIFT);
 
  ring orig_ring = currRing;
  ring syz_ring = rAssure_SyzOrder(orig_ring,TRUE);
  rSetSyzComp(k,syz_ring);
  rChangeCurrRing(syz_ring);
 
  ideal s_h1;
 
  if (orig_ring != syz_ring)
    s_h1 = idrCopyR_NoSort(h1,orig_ring,syz_ring);
  else
    s_h1 = h1;
  ideal s_h11=NULL;
  if (h11!=NULL)
  {
    s_h11=idrCopyR_NoSort(h11,orig_ring,syz_ring);
  }
 
 
  ideal s_h3=idPrepare(s_h1,s_h11,hi,k,&w,alg); // main (syz) GB computation
 
 
  if (w!=NULL) delete w;
  if (syz_ring!=orig_ring)
  {
    idDelete(&s_h1);
    if (s_h11!=NULL) idDelete(&s_h11);
  }
 
  if (S!=NULL) (*S)=idInit(IDELEMS(s_h3),IDELEMS(h1));
 
  s_h3=idExtractG_T_S(s_h3,T,S,k,IDELEMS(h1),inputIsIdeal,orig_ring,syz_ring);
 
  if (syz_ring!=orig_ring) rDelete(syz_ring);
  s_h3->rank=h1->rank;
  SI_RESTORE_OPT(saveOpt1,saveOpt2);
  return s_h3;
}

idLiftW()

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

Definition at line 1347 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,
		ideal *	SB = NULL )

Definition at line 51 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_std2(h1,currRing->qideal,(tHomog)homog,&wth,h2,(bigintmat*)NULL,0,3);
      idDelete(&re);
      return h2;
    }
  }
  e=idInit(1,h1->rank);
  if (idIs0(h1))
  {
    return e;
  }
  h2 = kStd2(h1,currRing->qideal,isNotHomog,NULL,(bigintmat*)NULL);
  if (SB!=NULL) *SB=h2;
  h3 = idMaxIdeal(1);
  h4=idMult(h2,h3);
  idDelete(&h3);
  h3=kStd2(h4,currRing->qideal,isNotHomog,NULL,(bigintmat*)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]);
      }
    }
  }
  if (SB==NULL) 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 = FALSE,
		intvec **	w = NULL )

Definition at line 2853 of file ideals.cc.

{
  int *red_comp=(int*)omAlloc((arg->rank+1)*sizeof(int));
  int del=0;
  ideal res=idMinEmbedding1(arg,inPlace,w,red_comp,del);
  idDeleteComps(res,red_comp,del);
  omFree(red_comp);
  return res;
}

idMinEmbedding_with_map()

ideal idMinEmbedding_with_map	(	ideal	arg,
		intvec **	w,
		ideal &	trans )

Definition at line 2863 of file ideals.cc.

{
  int *red_comp=(int*)omAlloc((arg->rank+1)*sizeof(int));
  int del=0;
  ideal res=idMinEmbedding1(arg,FALSE,w,red_comp,del);
  trans=idLift(arg,res,NULL,TRUE,FALSE,FALSE,NULL);
  //idDeleteComps(res,red_comp,del);
  omFree(red_comp);
  return res;
}

idMinEmbedding_with_map_v()

ideal idMinEmbedding_with_map_v	(	ideal	arg,
		intvec **	w,
		ideal &	trans,
		int *	red_comp )

Definition at line 2874 of file ideals.cc.

{
  if (idIs0(arg))
  {
    trans=idFreeModule(arg->rank);
    if (g!=NULL)
    {
      for(int i=0;i<arg->rank;i++) g[i]=i+1;
    }
    return arg;
  }
  int *red_comp=(int*)omAlloc((arg->rank+1)*sizeof(int));
  int del=0;
  ideal res=idMinEmbedding1(arg,FALSE,w,red_comp,del);
  trans=idLift(arg,res,NULL,TRUE,FALSE,FALSE,NULL);
  for(int i=1;i<=arg->rank;i++)
  {
    g[i-1]=red_comp[i];
  }
  idDeleteComps(res,red_comp,del);
  return res;
}

idMinors()

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

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 2031 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);
  }
 
  int size=binom(r,ar)*binom(c,ar);
  ideal result = idInit(size,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);
 
  rChangeCurrRing(origR);
  result = idrMoveR(result,tmpR,origR);
  sm_KillModifiedRing(tmpR);
  idTest(result);
  return result;
}

idModulo()

ideal idModulo	(	ideal	h1,
		ideal	h2,
		tHomog	h = testHomog,
		intvec **	w = NULL,
		matrix *	T = NULL,
		GbVariant	a = GbDefault )

Definition at line 2463 of file ideals.cc.

{
#ifdef HAVE_SHIFTBBA
  if (rIsLPRing(currRing))
    return idModuloLP(h2,h1,hom,w,T,alg);
#endif
  intvec *wtmp=NULL;
  if (T!=NULL) idDelete((ideal*)T);
 
  int i,flength=0,slength,length;
 
  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);
  BOOLEAN inputIsIdeal=FALSE;
  if (length==0)
  {
    length = 1;
    inputIsIdeal=TRUE;
  }
  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();
  }
  ideal s_temp1;
  ring orig_ring=currRing;
  ring syz_ring=rAssure_SyzOrder(orig_ring, TRUE);
  rSetSyzComp(length,syz_ring);
  {
    rChangeCurrRing(syz_ring);
    ideal s1,s2;
 
    if (syz_ring != orig_ring)
    {
      s1 = idrCopyR_NoSort(h1, orig_ring, syz_ring);
      s2 = idrCopyR_NoSort(h2, orig_ring, syz_ring);
    }
    else
    {
      s1=idCopy(h1);
      s2=idCopy(h2);
    }
 
    BITSET save_opt,save_opt2;
    SI_SAVE_OPT(save_opt,save_opt2);
    if (T==NULL) si_opt_1 |= Sy_bit(OPT_REDTAIL);
    si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
    s_temp1 = idPrepare(s2,s1,testHomog,length,w,alg);
    SI_RESTORE_OPT(save_opt,save_opt2);
  }
 
  //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;
 
  ideal result=idInit(IDELEMS(s_temp1),IDELEMS(h2));
  s_temp1=idExtractG_T_S(s_temp1,T,&result,length,IDELEMS(h2),inputIsIdeal,orig_ring,syz_ring);
 
  idDelete(&s_temp1);
  if (syz_ring!=orig_ring)
  {
    rDelete(syz_ring);
  }
  idTest(h2);
  idTest(h1);
  idTest(result);
  if (T!=NULL) idTest((ideal)*T);
  return result;
}

idMult()

ideal idMult ( ideal h1, ideal h2 )

inlinestatic

hh := h1 * h2

Definition at line 84 of file ideals.h.

{
  return id_Mult(h1, h2, currRing);
}

idMultSect()

ideal idMultSect	(	resolvente	arg,
		int	length,
		GbVariant	a = GbDefault )

Definition at line 472 of file ideals.cc.

{
  int i,j=0,k=0,l,maxrk=-1,realrki;
  unsigned syzComp;
  ideal bigmat,tempstd,result;
  poly p;
  int isIdeal=0;
 
  /* 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;
 
  BITSET save_opt;
  SI_SAVE_OPT1(save_opt);
  si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
 
  ring orig_ring=currRing;
  ring syz_ring=rAssure_SyzOrder(orig_ring,TRUE);
  rSetSyzComp(syzComp,syz_ring);
  rChangeCurrRing(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 --------------------------------------------*/
  if ((alg!=GbDefault)
  && (alg!=GbGroebner)
  && (alg!=GbModstd)
  && (alg!=GbSlimgb)
  && (alg!=GbStd))
  {
    WarnS("wrong algorithm for GB");
    alg=GbDefault;
  }
  tempstd=idGroebner(bigmat,syzComp,alg);
 
  if(syz_ring!=orig_ring)
    rChangeCurrRing(orig_ring);
 
  /* interpret 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);
  }
  SI_RESTORE_OPT1(save_opt);
  idSkipZeroes(result);
  return result;
}

idQuot()

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

Definition at line 1539 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;
  }
  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);
  rSetSyzComp(kmax-1,syz_ring);
  rChangeCurrRing(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
  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;
  BITSET old_test1;
  SI_SAVE_OPT1(old_test1);
  if (TEST_OPT_RETURN_SB) si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
  if (addOnlyOne)
  {
    if(!rField_is_Ring(currRing)) si_opt_1 |= Sy_bit(OPT_SB_1);
    s_h3 = kStd2(s_h4,currRing->qideal,hom,&weights1,(bigintmat*)NULL,0/*kmax-1*/,IDELEMS(s_h4)-1);
  }
  else
  {
    //s_h3 = kStd2(s_h4,currRing->qideal,hom,&weights1,(bigintmat*)NULL,kmax-1);
    // qideal added in idInitializeQuotient
    s_h3 = kStd2(s_h4,NULL,hom,&weights1,(bigintmat*)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;
}

idSaturate()

ideal idSaturate	(	ideal	I,
		ideal	J,
		int &	ki,
		BOOLEAN	isIdeal = TRUE )

Definition at line 3599 of file ideals.cc.

{
 return idSaturate_intern(I,J,k,isIdeal,FALSE);
}

idSaturate_intern()

ideal idSaturate_intern	(	ideal	I,
		ideal	J,
		int &	ki,
		BOOLEAN	isIdeal,
		BOOLEAN	isSB )

Definition at line 3495 of file ideals.cc.

{
  if(idIs0(J))
  {
     ideal res;
     if(isIdeal)
     {
       res=idInit(1,1);
       res->m[0]=pOne();
     }
     else
     {
       res=idFreeModule(I->rank);
     }
     k=1;
     return(res);
  }
  BITSET save_opt;SI_SAVE_OPT2(save_opt);
  //if (idElem(J)==1)
  //{
  //  idSkipZeroes(J);
  //  return id_Sat_principal(I,J,currRing);
  //}
  //---------------------------------------------------
  if (!rField_is_Ring(currRing))
  {
    BOOLEAN only_vars=TRUE; // enabled for I:x_i
    if (idElem(J)==1)
    {
      for(int j=IDELEMS(J)-1;j>=0;j--)
      {
        poly p=J->m[j];
        if (p!=NULL)
        {
          if (pVar(p)==0)
          {
            only_vars=FALSE;
            break;
          }
        }
      }
    }
    if (only_vars && isIdeal && rOrd_is_Totaldegree_Ordering(currRing)
    && (idElem(J)==1))
    {
      ideal Iquot,Istd;
      intvec *w=NULL;
      Istd=id_Satstd(I,J,currRing);
      si_opt_2|=Sy_bit(V_PURE_GB);
      k=0;
      loop
      {
        k++;
        Iquot=idQuot(Istd,J,TRUE,isIdeal);
        ideal tmp=kNF(Istd,currRing->qideal,Iquot,5);
        int  elem=idElem(tmp);
        id_Delete(&tmp,currRing);
        id_Delete(&Istd,currRing);
        Istd=Iquot;
        w=NULL;
        Istd=kStd2(Iquot,currRing->qideal,testHomog,&w,(bigintmat*)NULL);
        if (w!=NULL) delete w;
        id_Delete(&Iquot,currRing);
        if (elem==0) break;
      }
      k--;
      idSkipZeroes(Istd);
    //PrintS("\nSatstd:\n");
    //iiWriteMatrix((matrix)I,"I",1,currRing,0); PrintLn();
    //iiWriteMatrix((matrix)J,"J",1,currRing,0); PrintLn();
    //iiWriteMatrix((matrix)Istd,"res",1,currRing,0);PrintLn();
    //id_Delete(&Istd,currRing);
      SI_RESTORE_OPT2(save_opt);
      return Istd;
    }
  }
  //--------------------------------------------------
  ideal Iquot,Istd;
  intvec *w=NULL;
  Istd=idCopy(I);
  k=0;
  loop
  {
    k++;
    Iquot=idQuot(Istd,J,isSB,isIdeal);
    isSB=FALSE;
    si_opt_2|=Sy_bit(V_PURE_GB); // used from 2nd loop on
    ideal tmp=kNF(Istd,currRing->qideal,Iquot,5);
    int  elem=idElem(tmp);
    id_Delete(&tmp,currRing);
    id_Delete(&Istd,currRing);
    Istd=Iquot;
    if (elem==0) break;
  }
  k--;
  Istd=kStd2(Iquot,currRing->qideal,testHomog,&w,(bigintmat*)NULL);
  idSkipZeroes(Istd);
  SI_RESTORE_OPT2(save_opt);
  //if (only_vars)
  //{
  //  iiWriteMatrix((matrix)Istd,"org",1,currRing,0);
  //}
  return Istd;
}

idSaturateGB()

ideal idSaturateGB	(	ideal	I,
		ideal	J,
		int &	ki,
		BOOLEAN	isIdeal = TRUE )

Definition at line 3603 of file ideals.cc.

{
 return idSaturate_intern(I,J,k,isIdeal,TRUE);
}

idSect()

ideal idSect	(	ideal	h1,
		ideal	h2,
		GbVariant	a = GbDefault )

Definition at line 315 of file ideals.cc.

{
  int i,j,k;
  unsigned 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);
 
  BITSET save_opt;
  SI_SAVE_OPT1(save_opt);
  si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
 
  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,alg);
    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);
  rSetSyzComp(length,syz_ring);
  rChangeCurrRing(syz_ring);
  si_opt_1 |= Sy_bit(OPT_REDTAIL_SYZ);
 
  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;
 
  if ((alg!=GbDefault)
  && (alg!=GbGroebner)
  && (alg!=GbModstd)
  && (alg!=GbSlimgb)
  && (alg!=GbStd))
  {
    WarnS("wrong algorithm for GB");
    alg=GbDefault;
  }
  temp1=idGroebner(temp,length,alg);
 
  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);
  SI_RESTORE_OPT1(save_opt);
  if (TEST_OPT_RETURN_SB)
  {
     w=NULL;
     temp1=kStd2(result,currRing->qideal,testHomog,&w,(bigintmat*)NULL);
     if (w!=NULL) delete w;
     idDelete(&result);
     idSkipZeroes(temp1);
     return temp1;
  }
  //else
  //  temp1=kInterRed(result,currRing->qideal);
  return result;
}

idSeries()

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

Definition at line 2172 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()

intvec * idSort ( ideal id, BOOLEAN nolex = TRUE )

inlinestatic

Definition at line 188 of file ideals.h.

{
  return id_Sort(id, nolex, currRing);
}

idSyzygies()

ideal idSyzygies	(	ideal	h1,
		tHomog	h,
		intvec **	w,
		BOOLEAN	setSyzComp = TRUE,
		BOOLEAN	setRegularity = FALSE,
		int *	deg = NULL,
		GbVariant	a = GbDefault )

Definition at line 836 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);
  if (setSyzComp) rSetSyzComp(k,syz_ring);
 
  if (orig_ring != syz_ring)
  {
    rChangeCurrRing(syz_ring);
    s_h1=idrCopyR_NoSort(h1,orig_ring,syz_ring);
  }
  else
  {
    s_h1 = h1;
  }
 
  idTest(s_h1);
 
  BITSET save_opt;
  SI_SAVE_OPT1(save_opt);
  si_opt_1|=Sy_bit(OPT_REDTAIL_SYZ);
 
  ideal s_h3=idPrepare(s_h1,NULL,h,k,w,alg); // main (syz) GB computation
 
  SI_RESTORE_OPT1(save_opt);
 
  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))
  )
  {
    assume(orig_ring==syz_ring);
    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 != orig_ring)
    {
      rChangeCurrRing(orig_ring);
      rDelete(dp_C_ring);
    }
  }
  else
  {
    idDelete(&e);
  }
  assume(orig_ring==currRing);
  idTest(s_h3);
  if (currRing->qideal != NULL)
  {
    ideal ts_h3=kStd2(s_h3,currRing->qideal,h,w,(bigintmat*)NULL);
    idDelete(&s_h3);
    s_h3 = ts_h3;
  }
  return s_h3;
}

idTestHomModule()

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

Definition at line 2120 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;
}

idVec2Ideal()

ideal idVec2Ideal ( poly vec )

inlinestatic

Definition at line 173 of file ideals.h.

{
  return id_Vec2Ideal(vec, currRing);
}

syGetAlgorithm()

GbVariant syGetAlgorithm	(	char *	n,
		const ring	r,
		const ideal	M )

Definition at line 3698 of file ideals.cc.

{
  GbVariant alg=GbDefault;
  if (strcmp(n,"default")==0) alg=GbDefault;
  else if (strcmp(n,"slimgb")==0) alg=GbSlimgb;
  else if (strcmp(n,"std")==0) alg=GbStd;
  else if (strcmp(n,"sba")==0) alg=GbSba;
  else if (strcmp(n,"singmatic")==0) alg=GbSingmatic;
  else if (strcmp(n,"groebner")==0) alg=GbGroebner;
  else if (strcmp(n,"modstd")==0) alg=GbModstd;
  else if (strcmp(n,"ffmod")==0) alg=GbFfmod;
  else if (strcmp(n,"nfmod")==0) alg=GbNfmod;
  else if (strcmp(n,"std:sat")==0) alg=GbStdSat;
  else Warn(">>%s<< is an unknown algorithm",n);
 
  if (alg==GbSlimgb) // test conditions for slimgb
  {
    if(rHasGlobalOrdering(r)
    &&(!rIsNCRing(r))
    &&(r->qideal==NULL)
    &&(!rField_is_Ring(r)))
    {
       return GbSlimgb;
    }
    if (TEST_OPT_PROT)
      WarnS("requires: coef:field, commutative, global ordering, not qring");
  }
  else if (alg==GbSba) // cond. for sba
  {
    if(rField_is_Domain(r)
    &&(!rIsNCRing(r))
    &&(rHasGlobalOrdering(r)))
    {
      return GbSba;
    }
    if (TEST_OPT_PROT)
      WarnS("requires: coef:domain, commutative, global ordering");
  }
  else if (alg==GbGroebner) // cond. for groebner
  {
    return GbGroebner;
  }
  else if(alg==GbModstd)  // cond for modstd: Q or Q(a)
  {
    if(ggetid("modStd")==NULL)
    {
      WarnS(">>modStd<< not found");
    }
    else if(rField_is_Q(r)
    &&(!rIsNCRing(r))
    &&(rHasGlobalOrdering(r)))
    {
      return GbModstd;
    }
    if (TEST_OPT_PROT)
      WarnS("requires: coef:QQ, commutative, global ordering");
  }
  else if(alg==GbStdSat)  // cond for std:sat: 2 blocks of variables
  {
    if(ggetid("satstd")==NULL)
    {
      WarnS(">>satstd<< not found");
    }
    else
    {
      return GbStdSat;
    }
  }
 
  return GbStd; // no conditions for std
}