walkSupport.h File Reference

#include "misc/intvec.h"
#include "misc/int64vec.h"

Go to the source code of this file.

Macros
#define	idealSize(I)   IDELEMS(I)

Functions
int	tdeg (poly p)
int	getMaxTdeg (ideal I)
int	getMaxPosOfNthRow (intvec *v, int n)
int64	getInvEps64 (ideal G, intvec *targm, int pertdeg)
int	invEpsOk64 (ideal I, intvec *targm, int pertdeg, int64 inveps64)
intvec *	getNthRow (intvec *v, int n)
int64vec *	getNthRow64 (intvec *v, int n)
void	gett64 (int64vec *listw, int64vec *currw, int64vec *targw, int64 &t1, int64 &t2)
void	nextt64 (ideal G, int64vec *currw, int64vec *targw, int64 &t1, int64 &t2)
int64vec *	nextw64 (int64vec *currw, int64vec *targw, int64 nexttvec0, int64 nexttvec1)
int	DIFFspy (ideal G)
intvec *	DIFF (ideal G)
ideal	init64 (ideal G, int64vec *currw)
BOOLEAN	currwOnBorder64 (ideal I, int64vec *currw64)
void	getTaun64 (ideal G, intvec *targm, int pertdeg, int64vec **v64, int64 &i64)
ideal	idStd (ideal G)
ideal	idInterRed (ideal G)
matrix	matIdLift (ideal Gomega, ideal M)
void	rCopyAndChangeA (int64vec *w)
int64vec *	rGetGlobalOrderMatrix (ring r)
int64vec *	rGetGlobalOrderWeightVec (ring r)
BOOLEAN	noPolysWithMoreThanTwoTerms (ideal Gw)
int	ivSize (intvec *v)
int	iv64Size (int64vec *v)
intvec *	leadExp (poly p)
int64vec *	leadExp64 (poly p)
void	setPosOfIM (intvec *im, int i, int j, int val)
poly	getNthPolyOfId (ideal I, int n)
int	gcd (int a, int b)
int64	gcd64 (int64 a, int64 b)
int64	abs64 (int64 i)
ideal	sortRedSB (ideal G)
intvec *	int64VecToIntVec (int64vec *source)

Macro Definition Documentation

idealSize

#define idealSize

(

I

)

IDELEMS(I)

Definition at line 35 of file walkSupport.h.

Function Documentation

abs64()

int64 abs64 ( int64  i )

inline

Definition at line 44 of file walkSupport.h.

{ return ABS(i); }

currwOnBorder64()

BOOLEAN currwOnBorder64	(	ideal	I,
		int64vec *	currw64
	)

Definition at line 350 of file walkSupport.cc.

{
  ideal J=init64(G,currw64);
  int length=idealSize(J);
  BOOLEAN res=FALSE;
  for(int i=length; i>0; i--)
  {
    //if(pLength(getNthPolyOfId(J,i))>1)
    poly p=getNthPolyOfId(J,i);
    if ((p!=NULL) && (pNext(p)!=NULL))
    {
      res=TRUE;break;
    }
  }
  idDelete(&J);
  return res;
}

DIFF()

intvec * DIFF

(

ideal

G

)

Definition at line 435 of file walkSupport.cc.

{
  intvec  *v,*w;
  poly p;
  int s=idealSize(G);
  int n=rVar(currRing);
  int m=DIFFspy(G);
  intvec* diffm=new intvec(m,n,0);
  int j,l;
  int inc=0;
  for (j=1; j<=s; j++)
  {
    p=getNthPolyOfId(G,j);
    v=leadExp(p);
    pIter(p);
    while(p!=NULL)
    {
      inc++;
      intvec *lep=leadExp(p);
      w=ivSub(v,lep /*leadExp(p)*/);
      delete lep;
      pIter(p);
      for (l=1; l<=n; l++)
      {
        // setPosOfIM(diffm,inc,l,(*w)[l-1]);
        IMATELEM(*diffm,inc,l) =(*w)[l-1] ;
      }
      delete w;
    }
    delete v;
  }
  return(diffm);
}

DIFFspy()

int DIFFspy

(

ideal

G

)

Definition at line 407 of file walkSupport.cc.

{
  int s=idealSize(G);
  int j;
  int temp;
  int sum=0;
  poly p;
  for (j=1; j<=s; j++)
  {
    p=getNthPolyOfId(G,j);
    if((temp=pLength(p))>0) {sum += (temp-1);}
  }
  return(sum);
}

gcd()

int gcd	(	int	a,
		int	b
	)

Definition at line 836 of file walkSupport.cc.

{
  int r, p0 = a, p1 = b;
  if(p0 < 0)
    p0 = -p0;
 
  if(p1 < 0)
    p1 = -p1;
  while(p1 != 0)
  {
    r = p0 % p1;
    p0 = p1;
    p1 = r;
  }
  return p0;
}

gcd64()

int64 gcd64	(	int64	a,
		int64	b
	)

Definition at line 864 of file walkSupport.cc.

{
  int64 r, p0 = a, p1 = b;
  if(p0 < 0)
    p0 = -p0;
 
  if(p1 < 0)
    p1 = -p1;
 
  while(p1 != ((int64)0) )
  {
    r = p0 % p1;
    p0 = p1;
    p1 = r;
  }
 
  return p0;
}

getInvEps64()

int64 getInvEps64	(	ideal	G,
		intvec *	targm,
		int	pertdeg
	)

Definition at line 109 of file walkSupport.cc.

{
  int n;
  int64 temp64;
  int64 sum64=0;
//think n=2 is enough (instead of n=1)
  for (n=pertdeg; n>1; n--)
  {
    temp64=getMaxPosOfNthRow(targm,n);
    sum64 += temp64;
  }
  int64 inveps64=getMaxTdeg(G)*sum64+1;
 
  //overflow test
  if( sum64!=0 && (((inveps64-1)/sum64)!=getMaxTdeg(G)) )
    overflow_error=11;
 
  return(inveps64);
}

getMaxPosOfNthRow()

int getMaxPosOfNthRow	(	intvec *	v,
		int	n
	)

Definition at line 80 of file walkSupport.cc.

{
  int res=0;
  assume( (0<n) && (n<=(v->rows())) );
  {
    int c=v->cols();
    int cc=(n-1)*c;
    res=abs((*v)[0+cc /*(n-1)*c*/]);
    for (int i=c-1;i>=0;i--)
    {
      int temp=abs((*v)[i+cc /*(n-1)*c*/]);
      if(temp>res){res=temp;}
    }
  }
 return(res);
}

getMaxTdeg()

int getMaxTdeg

(

ideal

I

)

Definition at line 54 of file walkSupport.cc.

{
  int res=-1;
  int length=(int)I->ncols;
  for(int j=length-1;j>=0;j--)
  {
    if ((I->m)[j]!=NULL)
    {
      int temp=pTotaldegree((I->m)[j]);
      if(temp>res) {res=temp;}
    }
  }
  return(res);
}

getNthPolyOfId()

poly getNthPolyOfId	(	ideal	I,
		int	n
	)

Definition at line 686 of file walkSupport.cc.

{
  if(0<n && n<=((int)I->ncols))
  {
    return (I->m)[n-1];
  }
  else
  {
    return(NULL);
  }
}

getNthRow()

intvec * getNthRow	(	intvec *	v,
		int	n
	)

Definition at line 165 of file walkSupport.cc.

{
  int r=v->rows();
  int c=v->cols();
  intvec *res=new intvec(c);
  if((0<n) && (n<=r))
  {
    int cc=(n-1)*c;
    for (int i=0; i<c; i++)
    {
      (*res)[i]=(*v)[i+cc /*(n-1)*c*/ ];
    }
  }
  return(res);
}

getNthRow64()

int64vec * getNthRow64	(	intvec *	v,
		int	n
	)

Definition at line 181 of file walkSupport.cc.

{
  int r=v->rows();
  int c=v->cols();
  int64vec *res=new int64vec(c);
  if((0<n) && (n<=r))
  {
    int cc=(n-1)*c;
    for (int i=0; i<c; i++)
    {
      (*res)[i]=(int64)(*v)[i+cc /*(n-1)*c*/ ];
    }
  }
  return(res);
}

gett64()

void gett64	(	int64vec *	listw,
		int64vec *	currw,
		int64vec *	targw,
		int64 &	t1,
		int64 &	t2
	)

getTaun64()

void getTaun64	(	ideal	G,
		intvec *	targm,
		int	pertdeg,
		int64vec **	v64,
		int64 &	i64
	)

Definition at line 209 of file walkSupport.cc.

{
  int64vec* taun64=getNthRow64(targm,1);
  int64vec *temp64,*add64;
  int64 inveps64=1;
  if (pertdeg>1) inveps64=getInvEps64(G,targm,pertdeg);
 
  int n;
  //temp64 is used to check for overflow:
  for (n=2; n<=pertdeg; n++)
  {
    if (inveps64!=1)
    {
      temp64=iv64Copy(taun64);
      (*taun64)*=inveps64;
      for(int i=0; i<rVar(currRing);i++)
      {
        if((*temp64)[i]!=0 && (((*taun64)[i])/((*temp64)[i]))!=inveps64)
        overflow_error=12;
      }
      delete temp64;
    }
    temp64=iv64Copy(taun64);
    add64=getNthRow64(targm,n);
    taun64=iv64Add(add64,taun64);
    for(int i=0; i<rVar(currRing);i++)
    {
      if( ( ((*temp64)[i]) > 0 ) && ( ((*add64)[i]) > 0 ) )
      {
        if( ((*taun64)[i]) < ((*temp64)[i])  )
          overflow_error=13;
      }
      if( ( ((*temp64)[i]) < 0 ) && ( ((*add64)[i]) < 0 ) )
      {
        if( ((*taun64)[i]) > ((*temp64)[i])  )
          overflow_error=13;
      }
    }
    delete temp64;
  }
 
  //lists taunlist64=makeTaunList64(taun64,inveps64);
  //return(taunlist64);
  *v64=taun64;
  i64=inveps64;
}

idInterRed()

ideal idInterRed

(

ideal

G

)

Definition at line 958 of file walkSupport.cc.

{
  assume(G != NULL);
 
  ideal GG = kInterRedOld(G, NULL);
  idDelete(&G);
  return GG;
}

idStd()

ideal idStd

(

ideal

G

)

Definition at line 938 of file walkSupport.cc.

{
  ideal GG = kStd(G, NULL, testHomog, NULL);
  idSkipZeroes(GG);
  return GG;
}

init64()

ideal init64	(	ideal	G,
		int64vec *	currw
	)

Definition at line 299 of file walkSupport.cc.

{
  int length=IDELEMS(G);
  ideal I=idInit(length,G->rank);
  int j;
  int64 leadingweight,templeadingweight;
  poly p=NULL;
  poly leadp=NULL;
  for (j=1; j<=length; j++)
  {
    p=getNthPolyOfId(G,j);
    int64vec *tt=leadExp64(p);
    leadingweight=scalarProduct64(currw64,tt /*leadExp64(p)*/);
    delete tt;
    while (p!=NULL)
    {
      tt=leadExp64(p);
      templeadingweight=scalarProduct64(currw64,tt /*leadExp64(p)*/);
      delete tt;
      if(templeadingweight==leadingweight)
      {
        leadp=pAdd(leadp,pHead(p));
      }
      if(templeadingweight>leadingweight)
      {
        pDelete(&leadp);
        leadp=pHead(p);
        leadingweight=templeadingweight;
      }
      pIter(p);
    }
    (I->m)[j-1]=leadp;
    p=NULL;
    leadp=NULL;
  }
  return(I);
}

int64VecToIntVec()

intvec * int64VecToIntVec

(

int64vec *

source

)

Definition at line 1181 of file walkSupport.cc.

{
  int r=source->rows();
  int c=source->cols();
  intvec* res=new intvec(r,c,0);
  for(int i=0;i<r;i++){
    for(int j=0;j<c;j++){
      (*res)[i*c+j]=(int)(*source)[i*c+j];
    }
  }
  delete source;
  return(res);
}

invEpsOk64()

int invEpsOk64	(	ideal	I,
		intvec *	targm,
		int	pertdeg,
		int64	inveps64
	)

Definition at line 141 of file walkSupport.cc.

{
  int64 temp64=getInvEps64(I,targm,pertdeg);
  if (inveps64>=temp64)
  {
    return(1);
  }
  else
  {
    return(0);
  }
}

iv64Size()

int iv64Size ( int64vec *  v )

inline

Definition at line 37 of file walkSupport.h.

{ return((v->rows())*(v->cols())); }

ivSize()

int ivSize ( intvec *  v )

inline

Definition at line 36 of file walkSupport.h.

{ return((v->rows())*(v->cols())); }

leadExp()

intvec * leadExp

(

poly

p

)

Definition at line 746 of file walkSupport.cc.

{
  int N=rVar(currRing);
  int *e=(int*)omAlloc((N+1)*sizeof(int));
  p_GetExpV(p,e,currRing);
  intvec* iv=new intvec(N);
  for(int i=N;i>0;i--) { (*iv)[i-1]=e[i];}
  omFree(e);
  return(iv);
}

leadExp64()

int64vec * leadExp64

(

poly

p

)

Definition at line 769 of file walkSupport.cc.

{
  int N=rVar(currRing);
  int *e=(int*)omAlloc((N+1)*sizeof(int));
  p_GetExpV(p,e,currRing);
  int64vec* iv64=new int64vec(N);
  for(int i=N;i>0;i--) { (*iv64)[i-1]=(int64)e[i];}
  omFree(e);
  return(iv64);
}

matIdLift()

matrix matIdLift	(	ideal	Gomega,
		ideal	M
	)

Definition at line 978 of file walkSupport.cc.

{
  ideal Mtmp = idLift(Gomega, M, NULL, FALSE, FALSE, TRUE, NULL);
  int rows=IDELEMS(Gomega);
  int cols=IDELEMS(Mtmp);
  matrix res=id_Module2formatedMatrix(Mtmp,rows,cols,currRing);
  return res;
}

nextt64()

void nextt64	(	ideal	G,
		int64vec *	currw,
		int64vec *	targw,
		int64 &	t1,
		int64 &	t2
	)

Definition at line 560 of file walkSupport.cc.

{
  intvec* diffm=DIFF(G);
  int s=diffm->rows();
  tvec0=(int64)2;
  tvec1=(int64)0;
  intvec *tt;
  for(int j=1; j<=s; j++)
  {
    tt=getNthRow(diffm,j);
    int64 temptvec0, temptvec1;
    gett64(tt,currw64,targw64,temptvec0, temptvec1);
    delete tt;
 
    //if tempt>0 both parts will be>0
    if ( (temptvec1!=0) //that tempt is defined
       &&
       (temptvec0>0) && (temptvec1>0) //that tempt>0
     )
    {
      if( ( (temptvec0) <= (temptvec1) ) //that tempt<=1
        &&
        ( ( (temptvec0) * (tvec1) ) <
          ( (temptvec1) * (tvec0) ) )
      )
      {  //that tempt<t
        tvec0=temptvec0;
        tvec1=temptvec1;
      }
    }
  }
  delete diffm;
  return;
}

nextw64()

int64vec * nextw64	(	int64vec *	currw,
		int64vec *	targw,
		int64	nexttvec0,
		int64	nexttvec1
	)

Definition at line 604 of file walkSupport.cc.

{
  //to do (targw-currw)*tvec[0]+currw*tvec[1]
  int64vec* tempv;
  int64vec* nextweight;
  int64vec* a=iv64Sub(targw,currw);
  //no overflow can occur since both are>=0
 
  //to test overflow
  tempv=iv64Copy(a);
  *a *= (nexttvec0);
  for(int i=0; i<rVar(currRing); i++)
  {
    if( (nexttvec0) !=0 &&
        (((*a)[i])/(nexttvec0))!=((*tempv)[i]) )
    {
      overflow_error=7;
      break;
    }
  }
  delete tempv;
  int64vec* b=currw;
  tempv=iv64Copy(b);
  *b *= (nexttvec1);
  for(int i=0; i<rVar(currRing); i++)
  {
    if( (nexttvec1) !=0 &&
        (((*b)[i])/(nexttvec1))!=((*tempv)[i]) )
    {
      overflow_error=8;
      break;
    }
  }
  delete tempv;
  nextweight=iv64Add(a,b);
 
  for(int i=0; i<rVar(currRing); i++)
  {
    if( (((*a)[i])>=0 && ((*b)[i])>=0) ||
        (((*a)[i])<0 && ((*b)[i])<0) )
    {
      if( (abs64((*a)[i]))>abs64((*nextweight)[i]) ||
          (abs64((*b)[i]))>abs64((*nextweight)[i])
        )
      {
        overflow_error=9;
        break;
      }
    }
  }
 
  //to reduce common factors of nextweight
  int s=iv64Size(nextweight);
  int64 g,temp;
  g=(*nextweight)[0];
  for (int i=1; i<s; i++)
  {
    temp=(*nextweight)[i];
    g=gcd64(g,temp);
    if (g==1) break;
  }
 
  if (g!=1) *nextweight /= g;
 
  return(nextweight);
}

noPolysWithMoreThanTwoTerms()

BOOLEAN noPolysWithMoreThanTwoTerms

(

ideal

Gw

)

Definition at line 380 of file walkSupport.cc.

{
  int length=idealSize(Gw);
  for(int i=length; i>0; i--)
  {
    //if(pLength(getNthPolyOfId(Gw,i))>2)
    poly p=getNthPolyOfId(Gw,i);
    if ((p!=NULL) && (pNext(p)!=NULL) && (pNext(pNext(p))!=NULL))
    {
      return FALSE;
    }
  }
  return TRUE;
}

rCopyAndChangeA()

void rCopyAndChangeA

(

int64vec *

w

)

Definition at line 1000 of file walkSupport.cc.

{
  ring rnew=rCopy0(currRing);
  rComplete(rnew);
  rSetWeightVec(rnew,w->iv64GetVec());
  rChangeCurrRing(rnew);
}

rGetGlobalOrderMatrix()

int64vec * rGetGlobalOrderMatrix

(

ring

r

)

Definition at line 1019 of file walkSupport.cc.

{
  int n=rVar(r);
  int64vec* res=new int64vec(n,n,(int64)0);
  if (rHasLocalOrMixedOrdering(r)) return res;
  int pos1=0;
  int pos2=0;
  int i=0;
  while(r->order[i]!=0 && pos2<n)
  {
    pos2=pos2+r->block1[i] - r->block0[i];
 
    if(r->order[i]==ringorder_lp)
    {
      for(int j=pos1; j<=pos2; j++)
        (*res)[j*n+j]=(int64)1;
    }
    else if(r->order[i]==ringorder_dp)
    {
      for(int j=pos1;j<=pos2;j++)
        (*res)[pos1*n+j]=(int64)1;
      for(int j=1;j<=(pos2-pos1);j++)
        (*res)[(pos1+j)*n+(pos2+1-j)]=(int64)-1;
    }
    else if(r->order[i]==ringorder_Dp)
    {
      for(int j=pos1;j<=pos2;j++)
        (*res)[pos1*n+j]=(int64)1;
      for(int j=1;j<=(pos2-pos1);j++)
        (*res)[(pos1+j)*n+(pos1+j-1)]=(int64)1;
    }
    else if(r->order[i]==ringorder_wp)
    {
      int* weights=r->wvhdl[i];
      for(int j=pos1;j<=pos2;j++)
        (*res)[pos1*n+j]=(int64)weights[j-pos1];
      for(int j=1;j<=(pos2-pos1);j++)
        (*res)[(pos1+j)*n+(pos2+1-j)]=(int64)-1;
    }
    else if(r->order[i]==ringorder_Wp)
    {
      int* weights=r->wvhdl[i];
      for(int j=pos1;j<=pos2;j++)
        (*res)[pos1*n+j]=(int64)weights[j-pos1];
      for(int j=1;j<=(pos2-pos1);j++)
        (*res)[(pos1+j)*n+(pos1+j-1)]=(int64)1;
    }
 
    else if(r->order[0]==ringorder_M)
    {
      int* weights=r->wvhdl[0];
      for(int j=pos1;j<((pos2+1)*(pos2+1));j++)
        (*res)[j]=(int64)weights[j];
    }
 
    pos1=pos2+1;
    pos2=pos2+1;
    i++;
  }
 
  return(res);
}

rGetGlobalOrderWeightVec()

int64vec * rGetGlobalOrderWeightVec

(

ring

r

)

Definition at line 1094 of file walkSupport.cc.

{
  int n=rVar(r);
  int64vec* res=new int64vec(n);
 
  if (rHasLocalOrMixedOrdering(r)) return res;
 
  int length;
 
  if(r->order[0]==ringorder_lp)
  {
    (*res)[0]=(int64)1;
  }
  else if( (r->order[0]==ringorder_dp) || (r->order[0]==ringorder_Dp) )
  {
    length=r->block1[0] - r->block0[0];
    for (int j=0;j<=length;j++)
      (*res)[j]=(int64)1;
  }
  else if( (r->order[0]==ringorder_wp) || (r->order[0]==ringorder_Wp) ||
      (r->order[0]==ringorder_a)  || (r->order[0]==ringorder_M)    )
  {
    int* weights=r->wvhdl[0];
    length=r->block1[0] - r->block0[0];
    for (int j=0;j<=length;j++)
      (*res)[j]=(int64)weights[j];
  }
  else if(  /*(*/ r->order[0]==ringorder_a64 /*)*/  )
  {
    int64* weights=(int64*)r->wvhdl[0];
    length=r->block1[0] - r->block0[0];
    for (int j=0;j<=length;j++)
      (*res)[j]=weights[j];
  }
 
  return(res);
}

setPosOfIM()

void setPosOfIM	(	intvec *	im,
		int	i,
		int	j,
		int	val
	)

sortRedSB()

ideal sortRedSB

(

ideal

G

)

Definition at line 1146 of file walkSupport.cc.

{
  int s=idealSize(G);
  poly* m=G->m;
  poly p,q;
  for (int i=0; i<(s-1); i++)
  {
    for (int j=0; j<((s-1)-i); j++)
    {
      p=m[j];
      q=m[j+1];
      if (pLmCmp(p,q)==1)
      {
        m[j+1]=p;
        m[j]=q;
      }
    }
  }
  return(G);
}

tdeg()

int tdeg

(

poly

p

)

Definition at line 35 of file walkSupport.cc.

{
  int res=0;
  if(p!=NULL) res=pTotaldegree(p);
  return(res);
}