syz.cc File Reference

#include "kernel/mod2.h"
#include "misc/options.h"
#include "kernel/polys.h"
#include "kernel/GBEngine/kstd1.h"
#include "kernel/GBEngine/kutil.h"
#include "kernel/combinatorics/stairc.h"
#include "misc/intvec.h"
#include "coeffs/numbers.h"
#include "kernel/ideals.h"
#include "polys/monomials/ring.h"
#include "kernel/GBEngine/syz.h"
#include "polys/prCopy.h"
#include "polys/nc/sca.h"

Go to the source code of this file.

Functions
static intvec *	syPrepareModComp (ideal arg, intvec **w)
static void	syDeleteAbove (ideal up, int k)
static void	syMinStep (ideal mod, ideal &syz, BOOLEAN final=FALSE, ideal up=NULL, tHomog h=isNotHomog)
void	syGaussForOne (ideal syz, int elnum, int ModComp, int from, int till)
static void	syDeleteAbove1 (ideal up, int k)
static void	syMinStep1 (resolvente res, int length)
void	syMinimizeResolvente (resolvente res, int length, int first)
resolvente	syResolvente (ideal arg, int maxlength, int *length, intvec ***weights, BOOLEAN minim)
syStrategy	syResolution (ideal arg, int maxlength, intvec *w, BOOLEAN minim)
static poly	sypCopyConstant (poly inp)
int	syDetect (ideal id, int index, BOOLEAN homog, int *degrees, int *tocancel)
void	syDetect (ideal id, int index, int rsmin, BOOLEAN homog, intvec *degrees, intvec *tocancel)
intvec *	syBetti (resolvente res, int length, int *regularity, intvec *weights, BOOLEAN tomin, int *row_shift)
ideal	syMinBase (ideal arg)
syStrategy	syMres_with_map (ideal arg, int maxlength, intvec *w, ideal &trans)
void	syMinimize_with_map (syStrategy res, ideal &trans)
syStrategy	syMinimizeCopy (syStrategy org)
void	syFix (syStrategy r)

Function Documentation

syBetti()

intvec * syBetti	(	resolvente	res,
		int	length,
		int *	regularity,
		intvec *	weights,
		BOOLEAN	tomin,
		int *	row_shift
	)

Definition at line 787 of file syz.cc.

{
//#define BETTI_WITH_ZEROS
  //tomin = FALSE;
  int i,j=0,k=0,l,rows,cols,mr;
  int *temp1,*temp2,*temp3;/*used to compute degrees*/
  int *tocancel; /*(BOOLEAN)tocancel[i]=element is superfluous*/
  int r0_len;
 
  /*------ compute size --------------*/
  *regularity = -1;
  cols = length;
  while ((cols>0)
  && ((res[cols-1]==NULL)
    || (idIs0(res[cols-1]))))
  {
    cols--;
  }
  intvec * result;
  if (idIs0(res[0]))
  {
    if (res[0]==NULL)
      result = new intvec(1,1,1);
    else
      result = new intvec(1,1,res[0]->rank);
    return result;
  }
  intvec *w=NULL;
  if (weights!=NULL)
  {
    if (!idTestHomModule(res[0],currRing->qideal,weights))
    {
      WarnS("wrong weights given(3):");weights->show();PrintLn();
      idHomModule(res[0],currRing->qideal,&w);
      if (w!=NULL) { w->show();PrintLn();}
      weights=NULL;
    }
  }
#if 0
  if (idHomModule(res[0],currRing->qideal,&w)!=isHomog)
  {
    WarnS("betti-command: Input is not homogeneous!");
    weights=NULL;
  }
#endif
  if (weights==NULL) weights=w;
  else delete w;
  r0_len=IDELEMS(res[0]);
  while ((r0_len>0) && (res[0]->m[r0_len-1]==NULL)) r0_len--;
  #ifdef SHOW_W
  PrintS("weights:");if (weights!=NULL) weights->show(); else Print("NULL"); PrintLn();
  #endif
  int rkl=l = si_max(id_RankFreeModule(res[0],currRing),res[0]->rank);
  i = 0;
  while ((i<length) && (res[i]!=NULL))
  {
    if (IDELEMS(res[i])>l) l = IDELEMS(res[i]);
    i++;
  }
  temp1 = (int*)omAlloc0((l+1)*sizeof(int));
  temp2 = (int*)omAlloc((l+1)*sizeof(int));
  rows = 1;
  mr = 1;
  cols++;
  for (i=0;i<cols-1;i++)
  {
    if ((i==0) && (weights!=NULL)) p_SetModDeg(weights, currRing);
    memset(temp2,0,(l+1)*sizeof(int));
    for (j=0;j<IDELEMS(res[i]);j++)
    {
      if (res[i]->m[j]!=NULL)
      {
        if ((pGetComp(res[i]->m[j])>l)
        // usual resolutions do not the following, but artifulal built may: (tr. #763)
        //|| ((i>1) && (res[i-1]->m[pGetComp(res[i]->m[j])-1]==NULL))
        )
        {
          WerrorS("input not a resolution");
          omFreeSize((ADDRESS)temp1,(l+1)*sizeof(int));
          omFreeSize((ADDRESS)temp2,(l+1)*sizeof(int));
          return NULL;
        }
        temp2[j+1] = p_FDeg(res[i]->m[j],currRing)+temp1[pGetComp(res[i]->m[j])];
        if (temp2[j+1]-i>rows) rows = temp2[j+1]-i;
        if (temp2[j+1]-i<mr) mr = temp2[j+1]-i;
      }
    }
    if ((i==0) && (weights!=NULL)) p_SetModDeg(NULL, currRing);
    temp3 = temp1;
    temp1 = temp2;
    temp2 = temp3;
  }
  mr--;
  if (weights!=NULL)
  {
    for(j=0;j<weights->length();j++)
    {
      if (rows <(*weights)[j]+1) rows=(-mr)+(*weights)[j]+1;
    }
  }
  /*------ computation betti numbers --------------*/
  rows -= mr;
  result = new intvec(rows+1,cols,0);
  if (weights!=NULL)
  {
    for(j=0;j<weights->length();j++)
    {
      IMATELEM((*result),(-mr)+(*weights)[j]+1,1) ++;
      //Print("imat(%d,%d)++ -> %d\n",(-mr)+(*weights)[j]+1, 1, IMATELEM((*result),(-mr)+(*weights)[j]+1,1));
    }
  }
  else
  {
    (*result)[(-mr)*cols] = /*idRankFreeModule(res[0])*/ rkl;
    if ((!idIs0(res[0])) && ((*result)[(-mr)*cols]==0))
      (*result)[(-mr)*cols] = 1;
  }
  tocancel = (int*)omAlloc0((rows+1)*sizeof(int));
  memset(temp1,0,(l+1)*sizeof(int));
  if (weights!=NULL)
  {
    memset(temp2,0,l*sizeof(int));
    p_SetModDeg(weights, currRing);
  }
  else
    memset(temp2,0,l*sizeof(int));
  syDetect(res[0],0,TRUE,temp2,tocancel);
  if (weights!=NULL) p_SetModDeg(NULL, currRing);
  if (tomin)
  {
    //(*result)[(-mr)*cols] -= dummy;
    for(j=0;j<=rows+mr;j++)
    {
      //Print("tocancel[%d]=%d imat(%d,%d)=%d\n",j,tocancel[j],(-mr)+j+1,1,IMATELEM((*result),(-mr)+j+1,1));
      IMATELEM((*result),(-mr)+j+1,1) -= tocancel[j];
    }
  }
  for (i=0;i<cols-1;i++)
  {
    if ((i==0) && (weights!=NULL)) p_SetModDeg(weights, currRing);
    memset(temp2,0,l*sizeof(int));
    for (j=0;j<IDELEMS(res[i]);j++)
    {
      if (res[i]->m[j]!=NULL)
      {
        temp2[j+1] = p_FDeg(res[i]->m[j],currRing)+temp1[pGetComp(res[i]->m[j])];
        //(*result)[i+1+(temp2[j+1]-i-1)*cols]++;
        //if (temp2[j+1]>i) IMATELEM((*result),temp2[j+1]-i-mr,i+2)++;
        IMATELEM((*result),temp2[j+1]-i-mr,i+2)++;
      }
      else if (i==0)
      {
        if (j<r0_len) IMATELEM((*result),-mr,2)++;
      }
    }
  /*------ computation betti numbers, if res not minimal --------------*/
    if (tomin)
    {
      for (j=mr;j<rows+mr;j++)
      {
        //(*result)[i+1+j*cols] -= tocancel[j+1];
        IMATELEM((*result),j+1-mr,i+2) -= tocancel[j+1];
      }
      if ((i<length-1) && (res[i+1]!=NULL))
      {
        memset(tocancel,0,(rows+1)*sizeof(int));
        syDetect(res[i+1],i+1,TRUE,temp2,tocancel);
        for (j=0;j<rows;j++)
        {
          //(*result)[i+1+j*cols] -= tocancel[j];
          IMATELEM((*result),j+1,i+2) -= tocancel[j];
        }
      }
    }
    temp3 = temp1;
    temp1 = temp2;
    temp2 = temp3;
    for (j=0;j<=rows;j++)
    {
    //  if (((*result)[i+1+j*cols]!=0) && (j>*regularity)) *regularity = j;
      if ((IMATELEM((*result),j+1,i+2)!=0) && (j>*regularity)) *regularity = j;
    }
    if ((i==0) && (weights!=NULL)) p_SetModDeg(NULL, currRing);
  }
  // Print("nach minim:\n"); result->show(); PrintLn();
  /*------ clean up --------------*/
  omFreeSize((ADDRESS)tocancel,(rows+1)*sizeof(int));
  omFreeSize((ADDRESS)temp1,(l+1)*sizeof(int));
  omFreeSize((ADDRESS)temp2,(l+1)*sizeof(int));
  if ((tomin) && (mr<0))  // deletes the first (zero) line
  {
    for (j=1;j<=rows+mr+1;j++)
    {
      for (k=1;k<=cols;k++)
      {
        IMATELEM((*result),j,k) = IMATELEM((*result),j-mr,k);
      }
    }
    for (j=rows+mr+1;j<=rows+1;j++)
    {
      for (k=1;k<=cols;k++)
      {
        IMATELEM((*result),j,k) = 0;
      }
    }
  }
  j = 0;
  k = 0;
  for (i=1;i<=result->rows();i++)
  {
    for(l=1;l<=result->cols();l++)
    if (IMATELEM((*result),i,l) != 0)
    {
      j = si_max(j, i-1);
      k = si_max(k, l-1);
    }
  }
  intvec * exactresult=new intvec(j+1,k+1,0);
  for (i=0;i<exactresult->rows();i++)
  {
    for (j=0;j<exactresult->cols();j++)
    {
      IMATELEM(*exactresult,i+1,j+1) = IMATELEM(*result,i+1,j+1);
    }
  }
  if (row_shift!=NULL) *row_shift = mr;
  delete result;
  return exactresult;
}

syDeleteAbove()

static void syDeleteAbove ( ideal  up, int  k  )

static

Definition at line 66 of file syz.cc.

{
  if (up!=NULL)
  {
    for (int i=0;i<IDELEMS(up);i++)
    {
      if (up->m[i]!=NULL)
        pDeleteComp(&(up->m[i]),k+1);
    }
  }
}

syDeleteAbove1()

static void syDeleteAbove1 ( ideal  up, int  k  )

static

Definition at line 264 of file syz.cc.

{
  poly p/*,pp*/;
  if (up!=NULL)
  {
    for (int i=0;i<IDELEMS(up);i++)
    {
      p = up->m[i];
      while ((p!=NULL) && ((int)__p_GetComp(p,currRing)==k))
      {
        pLmDelete(&p);
      }
      up->m[i] = p;
      if (p!=NULL)
      {
        while (pNext(p)!=NULL)
        {
          if ((int)__p_GetComp(pNext(p),currRing)==k)
          {
            pLmDelete(&pNext(p));
          }
          else
            pIter(p);
        }
      }
    }
  }
}

syDetect() [1/2]

int syDetect	(	ideal	id,
		int	index,
		BOOLEAN	homog,
		int *	degrees,
		int *	tocancel
	)

Definition at line 718 of file syz.cc.

{
  int i, j, k, subFromRank=0;
  ideal temp;
 
  if (idIs0(id)) return 0;
  temp = idInit(IDELEMS(id),id->rank);
  for (i=0;i<IDELEMS(id);i++)
  {
    temp->m[i] = sypCopyConstant(id->m[i]);
  }
  i = IDELEMS(id);
  while ((i>0) && (temp->m[i-1]==NULL)) i--;
  if (i==0)
  {
    idDelete(&temp);
    return 0;
  }
  j = 0;
  while ((j<i) && (temp->m[j]==NULL)) j++;
  while (j<i)
  {
    if (homog)
    {
      if (index==0) k = p_FDeg(temp->m[j],currRing)+degrees[pGetComp(temp->m[j])];
      else          k = degrees[pGetComp(temp->m[j])];
      if (k>=index) tocancel[k-index]++;
      if ((k>=0) && (index==0)) subFromRank++;
    }
    else
    {
      tocancel[0]--;
    }
    syGaussForOne(temp,j,pGetComp(temp->m[j]),j+1,i);
    j++;
    while ((j<i) && (temp->m[j]==NULL)) j++;
  }
  idDelete(&temp);
  return subFromRank;
}

syDetect() [2/2]

void syDetect	(	ideal	id,
		int	index,
		int	rsmin,
		BOOLEAN	homog,
		intvec *	degrees,
		intvec *	tocancel
	)

Definition at line 759 of file syz.cc.

{
  int * deg=NULL;
  int * tocan=(int*) omAlloc0(tocancel->length()*sizeof(int));
  int i;
 
  if (homog)
  {
    deg = (int*) omAlloc0(degrees->length()*sizeof(int));
    for (i=degrees->length();i>0;i--)
      deg[i-1] = (*degrees)[i-1]-rsmin;
  }
  syDetect(id,index,homog,deg,tocan);
  for (i=tocancel->length();i>0;i--)
    (*tocancel)[i-1] = tocan[i-1];
  if (homog)
    omFreeSize((ADDRESS)deg,degrees->length()*sizeof(int));
  omFreeSize((ADDRESS)tocan,tocancel->length()*sizeof(int));
}

syFix()

void syFix

(

syStrategy

r

)

Definition at line 1230 of file syz.cc.

{
  if (r->fullres==NULL)
  {
    if(r->minres==NULL)
    {
      return;
    }
  }
  int found=-1;
  for(int i=1;i<r->length;i++)
  {
    // search (0)
    if((r->fullres!=NULL) && (r->fullres[i]!=NULL))
    {
      if (idIs0(r->fullres[i])) {found=i;break;}
    }
    if((r->fullres!=NULL) && (r->fullres[i]==NULL)) 
      break;
    if((r->minres!=NULL) && (r->minres[i]!=NULL))
    {
      if (idIs0(r->minres[i])) {found=i;break;}
    }
    if((r->minres!=NULL) && (r->minres[i]==NULL))
      break;
  }
  if (found>0) // delete trailing stuff
  {
    for(int i=found+1;i<r->length;i++)
    {
      if ((r->fullres!=NULL) && (r->fullres[i]!=NULL))
        id_Delete(&r->fullres[i],currRing);
      if ((r->minres!=NULL) && (r->minres[i]!=NULL))
        id_Delete(&r->minres[i],currRing);
    }
    r->list_length=found;
  }
  else
  {
    // append (0)
    for(int i=1;i<r->length;i++)
    {
      if ((r->fullres!=NULL) && (r->fullres[i]==NULL))
      {
        r->fullres[i]=idInit(1,IDELEMS(r->fullres[i-1]));
        if ((r->minres!=NULL) && (r->minres[i-1]==NULL))
        {
          r->minres[i]=idInit(1,IDELEMS(r->minres[i-1]));
        }
        break;
      }
      else
      {
        if ((r->minres!=NULL) && (r->minres[i]==NULL))
        {
          r->minres[i]=idInit(1,IDELEMS(r->minres[i-1]));
          break;
        }
      }
    }
  }
}

syGaussForOne()

void syGaussForOne	(	ideal	syz,
		int	elnum,
		int	ModComp,
		int	from,
		int	till
	)

Definition at line 218 of file syz.cc.

{
  int /*k,j,i,*/lu;
  poly unit1,unit2;
  poly actWith=syz->m[elnum];
  syz->m[elnum] = NULL;
 
  if (from<0) from = 0;
  if ((till<=0) || (till>IDELEMS(syz))) till = IDELEMS(syz);
  if (!rField_has_simple_inverse(currRing)) p_Cleardenom(actWith, currRing);
/*--makes Gauss alg. for the column ModComp--*/
  pTakeOutComp(&(actWith), ModComp, &unit1, &lu);
  if (lu==1) /*p_IsConstantComp(unit1,currRing)*/
  {
    number n_unit1=pGetCoeff(unit1);
    while (from<till)
    {
      poly tmp=syz->m[from];
      if (/*syz->m[from]*/ tmp!=NULL)
      {
        pTakeOutComp(&tmp, ModComp, &unit2, &lu);
        tmp = p_Mult_nn(tmp,n_unit1,currRing);
        syz->m[from] = pSub(tmp,
          pMult(unit2,pCopy(actWith)));
      }
      from++;
    }
  }
  else
  {
    while (from<till)
    {
      poly tmp=syz->m[from];
      if (/*syz->m[from]*/ tmp!=NULL)
      {
        pTakeOutComp(&tmp, ModComp, &unit2, &lu);
        tmp = pMult(pCopy(unit1),tmp);
        syz->m[from] = pSub(tmp,
          pMult(unit2,pCopy(actWith)));
      }
      from++;
    }
  }
  pDelete(&actWith);
  pDelete(&unit1);
}

syMinBase()

ideal syMinBase

(

ideal

arg

)

Definition at line 1021 of file syz.cc.

{
  intvec ** weights=NULL;
  int leng;
  if (idIs0(arg)) return idInit(1,arg->rank);
  resolvente res=syResolvente(arg,1,&leng,&weights,TRUE);
  ideal result=res[0];
  omFreeSize((ADDRESS)res,leng*sizeof(ideal));
  if (weights!=NULL)
  {
    if (*weights!=NULL)
    {
      delete (*weights);
      *weights=NULL;
    }
    if ((leng>=1) && (*(weights+1)!=NULL))
    {
      delete *(weights+1);
      *(weights+1)=NULL;
    }
  }
  idSkipZeroes(result);
  return result;
}

syMinimize_with_map()

void syMinimize_with_map	(	syStrategy	res,
		ideal &	trans
	)

Definition at line 1189 of file syz.cc.

{
  ideal *r=res->minres;
  if (r==NULL) r=res->fullres;
  ideal org=idCopy(r[0]);
  res=syMinimize(res);
  r=res->minres;
  if (r==NULL) r=res->fullres;
  trans=idLift(org,r[0],NULL,TRUE,FALSE,FALSE,NULL);
}

syMinimizeCopy()

syStrategy syMinimizeCopy

(

syStrategy

org

)

Definition at line 1200 of file syz.cc.

{
  syStrategy result=(syStrategy)omAlloc0(sizeof(ssyStrategy));
 
  result->length=org->length;
  if (org->weights!=NULL)
  {
    result->weights=(intvec**)omAlloc0(org->length*sizeof(intvec*));
    for (int i=org->length-1;i>=0;i--)
    {
      if (org->weights[i]!=NULL)
      {
        result->weights[i]=ivCopy(org->weights[i]);
      }
    }
  }
  result->fullres = (resolvente)omAlloc0((result->length+1)*sizeof(ideal));
  resolvente fr = org->minres;
  if (fr==NULL) fr=org->fullres;
 
  for (int i=result->length-1;i>=0;i--)
  {
    if (fr[i]!=NULL)
      result->fullres[i] = idCopy(fr[i]);
  }
  result->list_length=result->length;
  result=syMinimize(result);
  return result;
}

syMinimizeResolvente()

void syMinimizeResolvente	(	resolvente	res,
		int	length,
		int	first
	)

Definition at line 367 of file syz.cc.

{
  int syzIndex=first;
  intvec *dummy;
 
  if (syzIndex<1) syzIndex=1;
  if ((syzIndex==1) && (!rIsPluralRing(currRing)) && (idHomModule(res[0],currRing->qideal,&dummy)))
  {
    syMinStep1(res,length);
    delete dummy;
    return;
  }
  while ((syzIndex<length-1) && (res[syzIndex]!=NULL) && (res[syzIndex+1]!=NULL))
  {
    syMinStep(res[syzIndex-1],res[syzIndex],FALSE,res[syzIndex+1]);
    syzIndex++;
  }
  if (res[syzIndex]!=NULL)
    syMinStep(res[syzIndex-1],res[syzIndex]);
  if (!idIs0(res[0]))
    idMinEmbedding(res[0],TRUE);
  if((length>0) && (res[length]!=NULL) && idIs0(res[length]))
    idDelete(&res[length]);
}

syMinStep()

static void syMinStep ( ideal  mod, ideal &  syz, BOOLEAN  final = FALSE, ideal  up = NULL, tHomog  h = isNotHomog  )

static

Definition at line 82 of file syz.cc.

{
  poly Unit1,Unit2,actWith;
  int len,i,j,ModComp,m,k,l;
  BOOLEAN searchUnit,existsUnit;
 
  if (TEST_OPT_PROT) PrintS("m");
  if ((final) && (h==isHomog))
  /*minim is TRUE, we are in the module: maxlength, maxlength <>0*/
  {
    ideal deg0=id_Jet0(syz,currRing);
    id_Delete(&syz,currRing);
    idSkipZeroes0(deg0);
    syz=deg0;
  }
/*--cancels empty entees and their related components above--*/
  j = IDELEMS(syz);
  while ((j>0) && (!syz->m[j-1])) j--;
  k = 0;
  while (k<j)
  {
    if (syz->m[k]!=NULL)
      k++;
    else
    {
      if (TEST_OPT_PROT) PrintS(".");
      for (l=k;l<j-1;l++) syz->m[l] = syz->m[l+1];
      syz->m[j-1] = NULL;
      syDeleteAbove(up,k);
      j--;
    }
  }
/*--searches for syzygies coming from superfluous elements
* in the module below--*/
  searchUnit = TRUE;
  int curr_syz_limit = rGetCurrSyzLimit(currRing);
  BOOLEAN bHasGlobalOrdering=rHasGlobalOrdering(currRing);
  BOOLEAN bField_has_simple_inverse=rField_has_simple_inverse(currRing);
  while (searchUnit)
  {
    i=0;
    j=IDELEMS(syz);
    while ((j>0) && (syz->m[j-1]==NULL)) j--;
    existsUnit = FALSE;
    if (bHasGlobalOrdering)
    {
      while ((i<j) && (!existsUnit))
      {
        existsUnit = pVectorHasUnitB(syz->m[i],&ModComp);
        i++;
      }
    }
    else
    {
      int I=0;
      l = 0;
      len=0;
      for (i=0;i<IDELEMS(syz);i++)
      {
        if (syz->m[i]!=NULL)
        {
          pVectorHasUnit(syz->m[i],&m, &l);
          if ((len==0) ||((l>0) && (l<len)))
          {
            len = l;
            ModComp = m;
            I = i;
          }
        }
      }
//Print("Laenge ist: %d\n",len);
      if (len>0) existsUnit = TRUE;
      i = I+1;
    }
    if (existsUnit)
    {
      i--;
//--takes out the founded syzygy--
      if (TEST_OPT_PROT) PrintS("f");
      actWith = syz->m[i];
      if (!bField_has_simple_inverse) p_Cleardenom(actWith, currRing);
//Print("actWith: ");pWrite(actWith);
      syz->m[i] = NULL;
      for (k=i;k<j-1;k++)  syz->m[k] = syz->m[k+1];
      syz->m[j-1] = NULL;
      syDeleteAbove(up,i);
      j--;
//--makes Gauss alg. for the column ModComp--
      Unit1 = pTakeOutComp(&(actWith), ModComp);
//PrintS("actWith now: ");pWrite(actWith);
//Print("Unit1: ");pWrite(Unit1);
      k=0;
//Print("j= %d",j);
      while (k<j)
      {
        if (syz->m[k]!=NULL)
        {
          Unit2 = pTakeOutComp(&(syz->m[k]), ModComp);
//Print("element %d: ",k);pWrite(syz->m[k]);
//PrintS("Unit2: ");pWrite(Unit2);
          syz->m[k] = pMult(pCopy(Unit1),syz->m[k]);
          syz->m[k] = pSub(syz->m[k],
            pMult(Unit2,pCopy(actWith)));
          if (syz->m[k]==NULL)
          {
            for (l=k;l<j-1;l++)
              syz->m[l] = syz->m[l+1];
            syz->m[j-1] = NULL;
            j--;
            syDeleteAbove(up,k);
            k--;
          }
        }
        k++;
      }
      pDelete(&actWith);
      pDelete(&Unit1);
//--deletes superfluous elements from the module below---
      pDelete(&(mod->m[ModComp-1 - curr_syz_limit]));
      for (k=ModComp-1 - curr_syz_limit;k<IDELEMS(mod)-1;k++)
        mod->m[k] = mod->m[k+1];
      mod->m[IDELEMS(mod)-1] = NULL;
    }
    else
      searchUnit = FALSE;
  }
  if (TEST_OPT_PROT) PrintLn();
  idSkipZeroes(mod);
  idSkipZeroes(syz);
}

syMinStep1()

static void syMinStep1 ( resolvente  res, int  length  )

static

Definition at line 296 of file syz.cc.

{
  int i,j,k,index=0;
  poly p;
  intvec *have_del=NULL,*to_del=NULL;
 
  while ((index<length) && (res[index]!=NULL))
  {
/*---we take out dependent elements from syz---------------------*/
    if (res[index+1]!=NULL)
    {
      ideal deg0 = id_Jet0(res[index+1],currRing);
      ideal reddeg0 = kInterRedOld(deg0);
      idDelete(&deg0);
      have_del = new intvec(IDELEMS(res[index]));
      for (i=0;i<IDELEMS(reddeg0);i++)
      {
        if (reddeg0->m[i]!=NULL)
        {
          j = (int)__p_GetComp(reddeg0->m[i],currRing);
          pDelete(&(res[index]->m[j-1]));
          /*res[index]->m[j-1] = NULL;*/
          (*have_del)[j-1] = 1;
        }
      }
      idDelete(&reddeg0);
    }
    if (index>0)
    {
/*--- we search for units and perform Gaussian elimination------*/
      j = to_del->length();
      while (j>0)
      {
        if ((*to_del)[j-1]==1)
        {
          k = 0;
          while (k<IDELEMS(res[index]))
          {
            p = res[index]->m[k];
            while ((p!=NULL)
            && ((!pLmIsConstantComp(p)) || ((int)__p_GetComp(p,currRing)!=j)))
              pIter(p);
            if ((p!=NULL)
            && (pLmIsConstantComp(p))
            && ((int)__p_GetComp(p,currRing)==j)) break;
            k++;
          }
          #ifndef SING_NDEBUG
          if (k>=IDELEMS(res[index]))
          {
            PrintS("out of range\n");
          }
          #endif
          syGaussForOne(res[index],k,j);
          if (res[index+1]!=NULL)
            syDeleteAbove1(res[index+1],k+1);
          (*to_del)[j-1] = 0;
        }
        j--;
      }
    }
    if (to_del!=NULL) delete to_del;
    to_del = have_del;
    have_del = NULL;
    index++;
  }
  if (TEST_OPT_PROT) PrintLn();
  syKillEmptyEntres(res,length);
  if (to_del!=NULL) delete to_del;
}

syMres_with_map()

syStrategy syMres_with_map	(	ideal	arg,
		int	maxlength,
		intvec *	w,
		ideal &	trans
	)

Definition at line 1180 of file syz.cc.

{
  syStrategy res=syResolution(arg,maxlength,w,1);
  ideal *r=res->minres;
  if (r==NULL) r=res->fullres;
  trans=idLift(arg,r[0],NULL,TRUE,FALSE,FALSE,NULL);
  return res;
}

sypCopyConstant()

static poly sypCopyConstant ( poly  inp )

static

Definition at line 696 of file syz.cc.

{
  poly outp=NULL,q;
 
  while (inp!=NULL)
  {
    if (pLmIsConstantComp(inp))
    {
      if (outp==NULL)
      {
        q = outp = pHead(inp);
      }
      else
      {
        pNext(q) = pHead(inp);
        pIter(q);
      }
    }
    pIter(inp);
  }
  return outp;
}

syPrepareModComp()

static intvec * syPrepareModComp ( ideal  arg, intvec **  w  )

static

Definition at line 25 of file syz.cc.

{
  intvec *w1 = NULL;
  int i;
  BOOLEAN isIdeal=FALSE;
 
  if ((w==NULL) || (*w==NULL)) return w1;
  int maxxx = (*w)->length();
  if (maxxx==1)
  {
    maxxx = 2;
    isIdeal = TRUE;
  }
  w1 = new intvec(maxxx+IDELEMS(arg));
  if (!isIdeal)
  {
    for (i=0;i<maxxx;i++)
    {
      (*w1)[i] = (**w)[i];
    }
  }
  for (i=maxxx;i<maxxx+IDELEMS(arg);i++)
  {
    if (arg->m[i-maxxx]!=NULL)
    {
      (*w1)[i] = p_FDeg(arg->m[i-maxxx],currRing);
      if (pGetComp(arg->m[i-maxxx])!=0)
      {
        (*w1)[i]+=(**w)[pGetComp(arg->m[i-maxxx])-1];
      }
    }
  }
  delete (*w);
  *w = new intvec(IDELEMS(arg)+1);
  for (i=0;i<IDELEMS(arg);i++)
  {
     (**w)[i+1] = (*w1)[i+maxxx];
  }
  return w1;
}

syResolution()

syStrategy syResolution	(	ideal	arg,
		int	maxlength,
		intvec *	w,
		BOOLEAN	minim
	)

Definition at line 625 of file syz.cc.

{
 
#ifdef HAVE_PLURAL
  const ideal idSaveCurrRingQuotient = currRing->qideal;
  if( rIsSCA(currRing) )
  {
    if( ncExtensions(TESTSYZSCAMASK) )
    {
      currRing->qideal = SCAQuotient(currRing);
    }
    const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
    const unsigned int m_iLastAltVar  = scaLastAltVar(currRing);
    arg = id_KillSquares(idCopy(arg), m_iFirstAltVar, m_iLastAltVar, currRing, false); // kill squares in input!
  }
#endif
 
  syStrategy result=(syStrategy)omAlloc0(sizeof(ssyStrategy));
 
  if ((w!=NULL) && (!idTestHomModule(arg,currRing->qideal,w))) // is this right in SCA case???
  {
    WarnS("wrong weights given(2):");w->show();PrintLn();
    idHomModule(arg,currRing->qideal,&w);
    w->show();PrintLn();
    w=NULL;
  }
  if (w!=NULL)
  {
    result->weights = (intvec**)omAlloc0Bin(char_ptr_bin);
    (result->weights)[0] = ivCopy(w);
    result->length = 1;
  }
  resolvente fr = syResolvente(arg,maxlength,&(result->length),&(result->weights),minim);
  resolvente fr1;
  if (minim)
  {
    result->minres = (resolvente)omAlloc0((result->length+1)*sizeof(ideal));
    fr1 =  result->minres;
  }
  else
  {
    result->fullres = (resolvente)omAlloc0((result->length+1)*sizeof(ideal));
    fr1 =  result->fullres;
  }
  for (int i=result->length-1;i>=0;i--)
  {
    if (fr[i]!=NULL)
      fr1[i] = fr[i];
    fr[i] = NULL;
  }
  for (int i=result->length-1;i>0;i--)
  {
    if (fr1[i]!=NULL)
      fr1[i]->rank=IDELEMS(fr1[i-1]);
  }
  omFreeSize((ADDRESS)fr,(result->length)*sizeof(ideal));
 
#ifdef HAVE_PLURAL
  if( rIsSCA(currRing) )
  {
    if( ncExtensions(TESTSYZSCAMASK) )
    {
      currRing->qideal = idSaveCurrRingQuotient;
    }
    id_Delete(&arg, currRing);
  }
#endif
 
  return result;
}

syResolvente()

resolvente syResolvente	(	ideal	arg,
		int	maxlength,
		int *	length,
		intvec ***	weights,
		BOOLEAN	minim
	)

Definition at line 403 of file syz.cc.

{
  BITSET save1;
  SI_SAVE_OPT1(save1);
  resolvente newres;
  tHomog hom=isNotHomog;
  intvec *w = NULL,**tempW;
  int i,k,syzIndex = 0,j,rk_arg=si_max(1,(int)id_RankFreeModule(arg,currRing));
  int Kstd1_OldDeg=Kstd1_deg;
  BOOLEAN completeMinim;
  BOOLEAN setRegularity=TRUE;
  int wlength=*length;
 
  if (maxlength!=-1) *length = maxlength+1;
  else              *length = 5;
  if ((wlength!=0) && (*length!=wlength))
  {
    intvec **wtmp = (intvec**)omAlloc0((*length)*sizeof(intvec*));
    wtmp[0]=(*weights)[0];
    omFreeSize((ADDRESS)*weights,wlength*sizeof(intvec*));
    *weights=wtmp;
  }
  resolvente res = (resolvente)omAlloc0((*length)*sizeof(ideal));
 
/*--- initialize the syzygy-ring -----------------------------*/
  ring origR = currRing;
  ring syz_ring = rAssure_SyzComp(origR, TRUE); // will do rChangeCurrRing if needed
  rSetSyzComp(rk_arg, syz_ring);
 
  if (syz_ring != origR)
  {
    rChangeCurrRing(syz_ring);
    res[0] = idrCopyR_NoSort(arg, origR, syz_ring);
  }
  else
  {
    res[0] = idCopy(arg);
  }
 
/*--- creating weights for the module components ---------------*/
  if ((weights!=NULL) && (*weights!=NULL)&& ((*weights)[0]!=NULL))
  {
    if (!idTestHomModule(res[0],currRing->qideal,(*weights)[0]))
    {
      WarnS("wrong weights given(1):"); (*weights)[0]->show();PrintLn();
      idHomModule(res[0],currRing->qideal,&w);
      w->show();PrintLn();
      *weights=NULL;
    }
  }
 
  if ((weights==NULL) || (*weights==NULL) || ((*weights)[0]==NULL))
  {
    hom=(tHomog)idHomModule(res[0],currRing->qideal,&w);
    if (hom==isHomog)
    {
      *weights = (intvec**)omAlloc0((*length)*sizeof(intvec*));
      if (w!=NULL) (*weights)[0] = ivCopy(w);
    }
  }
  else
  {
    if ((weights!=NULL) && (*weights!=NULL)&& ((*weights)[0]!=NULL))
    {
      w = ivCopy((*weights)[0]);
      hom = isHomog;
    }
  }
 
#ifdef HAVE_PLURAL
  if (rIsPluralRing(currRing) && !rIsSCA(currRing) )
  {
// quick solution; need theory to apply homog GB stuff for G-Algebras
    hom = isNotHomog;
  }
#endif // HAVE_PLURAL
 
  if (hom==isHomog)
  {
    intvec *w1 = syPrepareModComp(res[0],&w);
    if (w!=NULL) { delete w;w=NULL; }
    w = w1;
    j = 0;
    while ((j<IDELEMS(res[0])) && (res[0]->m[j]==NULL)) j++;
    if (j<IDELEMS(res[0]))
    {
      if (p_FDeg(res[0]->m[j],currRing)!=pTotaldegree(res[0]->m[j]))
        setRegularity = FALSE;
    }
  }
  else
  {
    setRegularity = FALSE;
  }
 
/*--- the main loop --------------------------------------*/
  while ((res[syzIndex]!=NULL) && (!idIs0(res[syzIndex])) &&
         ((maxlength==-1) || (syzIndex<=maxlength)))
   // (syzIndex<maxlength+(int)minim)))
/*--- compute one step more for minimizing-----------------*/
  {
    if (Kstd1_deg!=0) Kstd1_deg++;
    if (syzIndex+1==*length)
    {
      newres = (resolvente)omAlloc0((*length+5)*sizeof(ideal));
      tempW = (intvec**)omAlloc0((*length+5)*sizeof(intvec*));
      for (j=0;j<*length;j++)
      {
        newres[j] = res[j];
        if (*weights!=NULL) tempW[j] = (*weights)[j];
        /*else              tempW[j] = NULL;*/
      }
      omFreeSize((ADDRESS)res,*length*sizeof(ideal));
      if (*weights != NULL) omFreeSize((ADDRESS)*weights,*length*sizeof(intvec*));
      *length += 5;
      res=newres;
      *weights = tempW;
    }
/*--- interreducing first -----------------------------------*/
    if (syzIndex>0)
    {
      int rkI=id_RankFreeModule(res[syzIndex],currRing);
      rSetSyzComp(rkI, currRing);
    }
    if(! TEST_OPT_NO_SYZ_MINIM )
    if (minim || (syzIndex!=0))
    {
      ideal temp = kInterRedOld(res[syzIndex],currRing->qideal);
      idDelete(&res[syzIndex]);
      idSkipZeroes(temp);
      res[syzIndex] = temp;
    }
/*--- computing the syzygy modules --------------------------------*/
    if ((currRing->qideal==NULL)&&(syzIndex==0)&& (!TEST_OPT_DEGBOUND))
    {
      res[/*syzIndex+*/1] = idSyzygies(res[0/*syzIndex*/],hom,&w,FALSE,setRegularity,&Kstd1_deg);
      if ((!TEST_OPT_NOTREGULARITY) && (Kstd1_deg>0)
      && (!rField_is_Ring(currRing))
      ) si_opt_1 |= Sy_bit(OPT_DEGBOUND);
    }
    else
    {
        res[syzIndex+1] = idSyzygies(res[syzIndex],hom,&w,FALSE);
    }
    completeMinim=(syzIndex!=maxlength) || (maxlength ==-1) || (hom!=isHomog);
    syzIndex++;
    if (TEST_OPT_PROT) Print("[%d]\n",syzIndex);
 
    if(! TEST_OPT_NO_SYZ_MINIM )
    {
      if ((minim)||(syzIndex>1))
        syMinStep(res[syzIndex-1],res[syzIndex],!completeMinim,NULL,hom);
      if (!completeMinim)
      /*minim is TRUE, we are in the module: maxlength, maxlength <>0*/
      {
        idDelete(&res[syzIndex]);
      }
    }
/*---creating the iterated weights for module components ---------*/
    if ((hom == isHomog) && (res[syzIndex]!=NULL) && (!idIs0(res[syzIndex])))
    {
//Print("die %d Modulegewichte sind:\n",w1->length());
//w1->show();
//PrintLn();
      int max_comp = id_RankFreeModule(res[syzIndex],currRing);
      k = max_comp - rGetCurrSyzLimit(currRing);
      assume(w != NULL);
      if (w != NULL)
        w->resize(max_comp+IDELEMS(res[syzIndex]));
      else
        w = new intvec(max_comp+IDELEMS(res[syzIndex]));
      (*weights)[syzIndex] = new intvec(k);
      for (i=0;i<k;i++)
      {
        if (res[syzIndex-1]->m[i]!=NULL) // hs
        {
          (*w)[i + rGetCurrSyzLimit(currRing)] = p_FDeg(res[syzIndex-1]->m[i],currRing);
          if (pGetComp(res[syzIndex-1]->m[i])>0)
            (*w)[i + rGetCurrSyzLimit(currRing)]
              += (*w)[pGetComp(res[syzIndex-1]->m[i])-1];
          (*((*weights)[syzIndex]))[i] = (*w)[i+rGetCurrSyzLimit(currRing)];
        }
      }
      for (i=k;i<k+IDELEMS(res[syzIndex]);i++)
      {
        if (res[syzIndex]->m[i-k]!=NULL)
          (*w)[i+rGetCurrSyzLimit(currRing)] = p_FDeg(res[syzIndex]->m[i-k],currRing)
                    +(*w)[pGetComp(res[syzIndex]->m[i-k])-1];
      }
    }
  }
/*--- end of the main loop --------------------------------------*/
/*--- deleting the temporare data structures --------------------*/
  if ((syzIndex!=0) && (res[syzIndex]!=NULL) && (idIs0(res[syzIndex])))
    idDelete(&res[syzIndex]);
  if (w !=NULL) delete w;
 
  Kstd1_deg=Kstd1_OldDeg;
 
  for (i=1; i<=syzIndex; i++)
  {
    if ((res[i]!=NULL) && ! idIs0(res[i]))
    {
      id_Shift(res[i],-rGetMaxSyzComp(i, currRing),currRing);
      res[i]->rank=idElem(res[i-1]);
    }
  }
/*--- going back to the original ring -------------------------*/
  if (origR != syz_ring)
  {
    rChangeCurrRing(origR); // should not be needed now?
    for (i=0; i<=syzIndex; i++)
    {
      res[i] = idrMoveR_NoSort(res[i], syz_ring, origR);
    }
    rDelete(syz_ring);
  }
  SI_RESTORE_OPT1(save1);
  return res;
}