shiftgb.cc File Reference

#include "kernel/mod2.h"
#include "polys/monomials/ring.h"
#include "kernel/polys.h"
#include "coeffs/numbers.h"
#include "kernel/ideals.h"
#include "polys/matpol.h"
#include "polys/kbuckets.h"
#include "kernel/GBEngine/kstd1.h"
#include "polys/sbuckets.h"
#include "polys/operations/p_Mult_q.h"
#include "kernel/GBEngine/kutil.h"
#include "kernel/structs.h"
#include "omalloc/omalloc.h"
#include "kernel/GBEngine/khstd.h"
#include "polys/weight.h"
#include "misc/intvec.h"
#include "kernel/GBEngine/kInline.h"
#include "kernel/combinatorics/stairc.h"
#include "kernel/GBEngine/shiftgb.h"
#include "polys/nc/sca.h"

Go to the source code of this file.

Macros
#define	freeT(A, v)   omFreeSize((ADDRESS)A,(v+1)*sizeof(int))

Functions
poly	p_LPshiftT (poly p, int sh, int uptodeg, int lV, kStrategy strat, const ring r)
poly	p_LPshift (poly p, int sh, int uptodeg, int lV, const ring r)
poly	p_mLPshift (poly p, int sh, int uptodeg, int lV, const ring r)
int	p_LastVblockT (poly p, int lV, kStrategy strat, const ring r)
int	p_LastVblock (poly p, int lV, const ring r)
int	p_mLastVblock (poly p, int lV, const ring r)
int	pFirstVblock (poly p, int lV)
int	pmFirstVblock (poly p, int lV)
int	isInV (poly p, int lV)
int	poly_isInV (poly p, int lV)
int	ideal_isInV (ideal I, int lV)
int	itoInsert (poly p, int uptodeg, int lV, const ring r)
poly	p_ShrinkT (poly p, int lV, kStrategy strat, const ring r)
poly	p_Shrink (poly p, int lV, const ring r)
poly	p_mShrink (poly p, int lV, const ring r)

Macro Definition Documentation

freeT

#define freeT	(		A,
			v
	)		omFreeSize((ADDRESS)A,(v+1)*sizeof(int))

Definition at line 35 of file shiftgb.cc.

Function Documentation

ideal_isInV()

int ideal_isInV	(	ideal	I,
		int	lV
	)

Definition at line 304 of file shiftgb.cc.

{
  /* tests whether each polynomial of an ideal I lies in in V */
  int i;
  int s    = IDELEMS(I)-1;
  for(i = 0; i <= s; i++)
  {
    if ( !poly_isInV(I->m[i],lV) )
    {
      return(0);
    }
  }
  return(1);

isInV()

int isInV	(	poly	p,
		int	lV
	)

Definition at line 237 of file shiftgb.cc.

{
  /* investigate only the leading monomial of p in currRing */
  if ( pTotaldegree(p)==0 ) return(1);
  if (lV <= 0) return(0);
  /* returns 1 iff p is in V */
  /* that is in each block up to a certain one there is only one nonzero exponent */
  /* lV = the length of V = the number of orig vars */
  int *e = (int *)omAlloc0((currRing->N+1)*sizeof(int));
  int  b = (int)((currRing->N +lV-1)/lV); /* the number of blocks */
  //int b  = (int)(currRing->N)/lV;
  int *B = (int *)omAlloc0((b+1)*sizeof(int)); /* the num of elements in a block */
  p_GetExpV(p,e,currRing);
  int i,j;
  for (j=1; j<=b; j++)
  {
    /* we go through all the vars */
    /* by blocks in lV vars */
    for (i=(j-1)*lV + 1; i<= j*lV; i++)
    {
      if (e[i]) B[j] = B[j]+1;
    }
  }
  //  j = b;
  //  while ( (!B[j]) && (j>=1)) j--;
  for (j=b; j>=1; j--)
  {
    if (B[j]!=0) break;
  }
  /* do not need e anymore */
  freeT(e, currRing->N);
 
  if (j==0) goto ret_true;
//   {
//     /* it is a zero exp vector, which is in V */
//     freeT(B, b);
//     return(1);
//   }
  /* now B[j] != 0 and we test place-squarefreeness */
  for (; j>=1; j--)
  {
    if (B[j]!=1)
    {
      freeT(B, b);
      return(0);
    }
  }
 ret_true:
  freeT(B, b);
  return(1);

itoInsert()

int itoInsert	(	poly	p,
		int	uptodeg,
		int	lV,
		const ring	r
	)

Definition at line 320 of file shiftgb.cc.

{
  /* for poly in lmCR/tailTR presentation */
  /* the below situation (commented out) might happen! */
//   if (r == currRing)
//   {
//     "Current ring is not expected in toInsert";
//     return(0);
//   }
  /* compute the number of insertions */
  int i = p_mLastVblock(p, lV, currRing);
  if (pNext(p) != NULL)
  {
    i = si_max(i, p_LastVblock(pNext(p), lV, r) );
  }
  //  i = uptodeg  - i +1;
  i = uptodeg  - i;
  //  p_wrp(p,currRing,r); Print("----i:%d",i); PrintLn();
  return(i);

p_LastVblock()

int p_LastVblock	(	poly	p,
		int	lV,
		const ring	r
	)

Definition at line 155 of file shiftgb.cc.

{
  /* returns the number of maximal block */
  /* appearing among the monomials of p */
  /* the 0th block is the 1st one */
  poly q = p;
  int ans = 0;
  int ansnew = 0;
  while (q!=NULL)
  {
    ansnew = p_mLastVblock(q, lV, r);
    ans    = si_max(ans,ansnew);
    pIter(q);
  }
  return(ans);

p_LastVblockT()

int p_LastVblockT	(	poly	p,
		int	lV,
		kStrategy	strat,
		const ring	r
	)

Definition at line 132 of file shiftgb.cc.

{
  /* returns the number of maximal block */
  /* appearing among the monomials of p */
  /* the 0th block is the 1st one */
 
  /* p is like TObject: lm in currRing = r, tail in tailRing  */
  assume(p_LmCheckIsFromRing(p,r));
  assume(p_CheckIsFromRing(pNext(p),strat->tailRing));
 
  int ans = p_mLastVblock(p, lV, r); // Block of LM
  poly q = pNext(p);
  int ansnew = 0;
  while (q != NULL)
  {
    ansnew = p_mLastVblock(q, lV, strat->tailRing);
    ans       = si_max(ans,ansnew);
    pIter(q);
  }
  /* do not need to delete q */
  return(ans);

p_LPshift()

poly p_LPshift	(	poly	p,
		int	sh,
		int	uptodeg,
		int	lV,
		const ring	r
	)

Definition at line 73 of file shiftgb.cc.

{
  /* assume shift takes place */
  /* shifts the poly p from the ring r by sh */
 
  /* assume sh and uptodeg agree TODO check */
  assume(sh>=0);
 
  if (sh == 0) return(p); /* the zero shift */
 
  poly q  = NULL;
  poly pp = p;
  while (pp!=NULL)
  {
    poly h=pp;
    pIter(pp);
    pNext(h)=NULL;
    h=p_mLPshift(h,sh,uptodeg,lV,r);
    q = p_Add_q(q, h,r);
  }
  return(q);

p_LPshiftT()

poly p_LPshiftT	(	poly	p,
		int	sh,
		int	uptodeg,
		int	lV,
		kStrategy	strat,
		const ring	r
	)

Definition at line 41 of file shiftgb.cc.

{
  /* assume shift takes place, shifts the poly p by sh */
  /* p is like TObject: lm in currRing = r, tail in tailRing  */
  /* copies p */
 
  if (p==NULL) return(p);
 
  assume(p_LmCheckIsFromRing(p,r));
  assume(p_CheckIsFromRing(pNext(p),strat->tailRing));
 
  /* assume sh and uptodeg agree  TODO check */
 
  if (sh == 0) return(p); /* the zero shift */
 
  poly q   = NULL;
  poly s   = p_mLPshift(p_Head(p,r), sh, uptodeg, lV, r); // lm in currRing
  /* pNext(s) will be fixed below */
  poly pp = pNext(p);
 
  while (pp != NULL)
  {
    poly h=p_mLPshift(p_Head(pp,strat->tailRing),sh,uptodeg,lV,strat->tailRing);
    pIter(pp);
 
    q = p_Add_q(q, h,strat->tailRing);
  }
  pNext(s) = q;
  /* int version: returns TRUE if it was successful */
  return(s);

p_mLastVblock()

int p_mLastVblock	(	poly	p,
		int	lV,
		const ring	r
	)

Definition at line 172 of file shiftgb.cc.

{
  /* for a monomial p, returns the number of the last block */
  /* where a nonzero exponent is sitting */
  if (p_LmIsConstant(p,r))
  {
    return(0);
  }
  int *e=(int *)omAlloc0((r->N+1)*sizeof(int));
  p_GetExpV(p,e,r);
  int j,b;
  j = r->N;
  while ( (!e[j]) && (j>=1) ) j--;
  freeT(e, r->N);
  assume(j>0);
  b = (int)((j+lV-1)/lV); /* the number of the block, >=1 */
  return (b);

p_mLPshift()

poly p_mLPshift	(	poly	p,
		int	sh,
		int	uptodeg,
		int	lV,
		const ring	r
	)

Definition at line 96 of file shiftgb.cc.

{
  /* p is a monomial from the ring r */
 
  if (sh == 0) return(p); /* the zero shift */
 
  assume(sh>=0);
  int L = p_mLastVblock(p,lV,r);
  assume(L+sh<=uptodeg);
 
  int *e=(int *)omAlloc0((r->N+1)*sizeof(int));
  int *s=(int *)omAlloc0((r->N+1)*sizeof(int));
  p_GetExpV(p,e,r);
 
  int j;
  //  for (j=1; j<=r->N; j++)
  // L*lV gives the last position of the last block
  for (j=1; j<= L*lV ; j++)
  {
    assume(e[j]<=1);
    if (e[j]==1)
    {
      assume(j + (sh*lV)<=r->N);
      s[j + (sh*lV)] = e[j]; /* actually 1 */
    }
  }
  p_SetExpV(p,s,r);
  freeT(e, r->N);
  freeT(s, r->N);
  /*  pSetm(m); */ /* done in the pSetExpV */
  /* think on the component and coefficient */
  //  number c = pGetCoeff(p);
  //  p_SetCoeff0(m,p_GetCoeff(p,r),r);
  return(p);

p_mShrink()

poly p_mShrink	(	poly	p,
		int	lV,
		const ring	r
	)

Definition at line 389 of file shiftgb.cc.

{
  /* shrinks the monomial p in ring r */
  /* lV = the length of V = the number of orig vars */
 
  /* check assumes/exceptions */
  /* r->N is a multiple of lV */
 
  int *e = (int *)omAlloc0((r->N+1)*sizeof(int));
  int  b = (int)((r->N +lV-1)/lV); /* the number of blocks */
  //  int *B = (int *)omAlloc0((b+1)*sizeof(int)); /* the num of elements in a block */
  int *S = (int *)omAlloc0((r->N+1)*sizeof(int)); /* the shrinked exponent */
  p_GetExpV(p,e,r);
  int i,j; int cnt = 1; //counter for blocks in S
  for (j=1; j<=b; j++)
  {
    /* we go through all the vars */
    /* by blocks in lV vars */
    for (i=(j-1)*lV + 1; i<= j*lV; i++)
    {
      if (e[i]==1)
      {
         //      B[j] = B[j]+1; // for control in V?
         S[(cnt-1)*lV + (i - (j-1)*lV)] = e[i];
         /* assuming we are in V, can interrupt here */
         cnt++;
         //  break; //results in incomplete shrink!
         i = j*lV; // manual break under assumption p is in V
      }
    }
  }
#ifdef PDEBUG
  //  Print("p_mShrink: cnt = [%d], b = %d\n",cnt,b);
#endif
  // cnt -1 <= b  must hold!
  //  freeT(B, b);
  poly s = p_One(r);
  p_SetExpV(s,S,r);
  freeT(e, r->N);
  freeT(S, r->N);
  /*  p_Setm(s,r); // done by p_SetExpV */
  p_SetComp(s,p_GetComp(p,r),r); // component is preserved
  p_SetCoeff(s,n_Copy(p_GetCoeff(p,r),r->cf),r);  // coeff is preserved
#ifdef PDEBUG
  //  Print("p_mShrink: from "); p_wrp(p,r); Print(" to "); p_wrp(s,r); PrintLn();
#endif
  return(s);

p_Shrink()

poly p_Shrink	(	poly	p,
		int	lV,
		const ring	r
	)

Definition at line 369 of file shiftgb.cc.

{
  /* proc shrinks the poly p in ring r */
  /* lV = the length of V = the number of orig vars */
  /* check assumes/exceptions */
  /* r->N is a multiple of lV */
 
  if (p==NULL) return(p);
  assume(p_CheckIsFromRing(p,r));
  poly q = NULL;
  poly pp = p;
 
  while (pp != NULL)
  {
    q = p_Add_q(q, p_mShrink(pp,lV,r),r);
    pIter(pp);
  }
  return(q);

p_ShrinkT()

poly p_ShrinkT	(	poly	p,
		int	lV,
		kStrategy	strat,
		const ring	r
	)

Definition at line 341 of file shiftgb.cc.

{
  /* p is like TObject: lm in currRing = r, tail in tailRing  */
  /* proc shrinks the poly p in ring r */
  /* lV = the length of V = the number of orig vars */
  /* check assumes/exceptions */
  /* r->N is a multiple of lV */
 
  if (p==NULL) return(p);
 
  assume(p_LmCheckIsFromRing(p,r));
  assume(p_CheckIsFromRing(pNext(p),strat->tailRing));
 
  poly q   = NULL;
  poly s   = p_mShrink(p, lV, r); // lm in currRing
  poly pp = pNext(p);
 
  while (pp != NULL)
  {
    //    q = p_Add_q(q, p_mShrink(pp,uptodeg,lV,strat->tailRing),strat->tailRing);
    q = p_Add_q(q, p_mShrink(pp,lV,strat->tailRing),strat->tailRing);
    pIter(pp);
  }
  pNext(s) = q;
  return(s);

pFirstVblock()

int pFirstVblock	(	poly	p,
		int	lV
	)

Definition at line 191 of file shiftgb.cc.

{
  /* returns the number of maximal block */
  /* appearing among the monomials of p */
  /* the 0th block is the 1st one */
  poly q = p; //p_Copy(p,currRing); /* need it ? */
  int ans = 0;
  int ansnew = 0;
  while (q!=NULL)
  {
    ansnew = pmFirstVblock(q,lV);
    ans    = si_min(ans,ansnew);
    pIter(q);
  }
  /* do not need to delete q */
  return(ans);

pmFirstVblock()

int pmFirstVblock	(	poly	p,
		int	lV
	)

Definition at line 209 of file shiftgb.cc.

{
  if (pIsConstantPoly(p))
  {
    return(int(0));
  }
  /* for a monomial p, returns the number of the first block */
  /* where a nonzero exponent is sitting */
  int *e=(int *)omAlloc0((currRing->N+1)*sizeof(int));
  p_GetExpV(p,e,currRing);
  int j,b;
  j = 1;
  while ( (!e[j]) && (j<=currRing->N-1) ) j++;
  if (j==currRing->N + 1)
  {
#ifdef PDEBUG
    PrintS("pmFirstVblock: unexpected zero exponent vector\n");
#endif
    return(j);
  }
  b = (int)(j/lV)+1; /* the number of the block, 1<= N <= currRing->N  */
  return (b);

poly_isInV()

int poly_isInV	(	poly	p,
		int	lV
	)

Definition at line 289 of file shiftgb.cc.

{
  /* tests whether the whole polynomial p in in V */
  poly q = p;
  while (q!=NULL)
  {
    if ( !isInV(q,lV) )
    {
      return(0);
    }
    q = pNext(q);
  }
  return(1);