My Project
Functions
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 intvecsyPrepareModComp (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)
 
intvecsyBetti (resolvente res, int length, int *regularity, intvec *weights, BOOLEAN tomin, int *row_shift)
 
ideal syMinBase (ideal arg)
 

Function Documentation

◆ syBetti()

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

Definition at line 770 of file syz.cc.

772 {
773 //#define BETTI_WITH_ZEROS
774  //tomin = FALSE;
775  int i,j=0,k=0,l,rows,cols,mr;
776  int *temp1,*temp2,*temp3;/*used to compute degrees*/
777  int *tocancel; /*(BOOLEAN)tocancel[i]=element is superfluous*/
778  int r0_len;
779 
780  /*------ compute size --------------*/
781  *regularity = -1;
782  cols = length;
783  while ((cols>0)
784  && ((res[cols-1]==NULL)
785  || (idIs0(res[cols-1]))))
786  {
787  cols--;
788  }
789  intvec * result;
790  if (idIs0(res[0]))
791  {
792  if (res[0]==NULL)
793  result = new intvec(1,1,1);
794  else
795  result = new intvec(1,1,res[0]->rank);
796  return result;
797  }
798  intvec *w=NULL;
799  if (weights!=NULL)
800  {
801  if (!idTestHomModule(res[0],currRing->qideal,weights))
802  {
803  WarnS("wrong weights given(3):");weights->show();PrintLn();
804  idHomModule(res[0],currRing->qideal,&w);
805  if (w!=NULL) { w->show();PrintLn();}
806  weights=NULL;
807  }
808  }
809 #if 0
810  if (idHomModule(res[0],currRing->qideal,&w)!=isHomog)
811  {
812  WarnS("betti-command: Input is not homogeneous!");
813  weights=NULL;
814  }
815 #endif
816  if (weights==NULL) weights=w;
817  else delete w;
818  r0_len=IDELEMS(res[0]);
819  while ((r0_len>0) && (res[0]->m[r0_len-1]==NULL)) r0_len--;
820  #ifdef SHOW_W
821  PrintS("weights:");if (weights!=NULL) weights->show(); else Print("NULL"); PrintLn();
822  #endif
823  int rkl=l = si_max(id_RankFreeModule(res[0],currRing),res[0]->rank);
824  i = 0;
825  while ((i<length) && (res[i]!=NULL))
826  {
827  if (IDELEMS(res[i])>l) l = IDELEMS(res[i]);
828  i++;
829  }
830  temp1 = (int*)omAlloc0((l+1)*sizeof(int));
831  temp2 = (int*)omAlloc((l+1)*sizeof(int));
832  rows = 1;
833  mr = 1;
834  cols++;
835  for (i=0;i<cols-1;i++)
836  {
837  if ((i==0) && (weights!=NULL)) p_SetModDeg(weights, currRing);
838  memset(temp2,0,(l+1)*sizeof(int));
839  for (j=0;j<IDELEMS(res[i]);j++)
840  {
841  if (res[i]->m[j]!=NULL)
842  {
843  if ((pGetComp(res[i]->m[j])>l)
844  // usual resolutions do not the following, but artifulal built may: (tr. #763)
845  //|| ((i>1) && (res[i-1]->m[pGetComp(res[i]->m[j])-1]==NULL))
846  )
847  {
848  WerrorS("input not a resolution");
849  omFreeSize((ADDRESS)temp1,(l+1)*sizeof(int));
850  omFreeSize((ADDRESS)temp2,(l+1)*sizeof(int));
851  return NULL;
852  }
853  temp2[j+1] = p_FDeg(res[i]->m[j],currRing)+temp1[pGetComp(res[i]->m[j])];
854  if (temp2[j+1]-i>rows) rows = temp2[j+1]-i;
855  if (temp2[j+1]-i<mr) mr = temp2[j+1]-i;
856  }
857  }
858  if ((i==0) && (weights!=NULL)) p_SetModDeg(NULL, currRing);
859  temp3 = temp1;
860  temp1 = temp2;
861  temp2 = temp3;
862  }
863  mr--;
864  if (weights!=NULL)
865  {
866  for(j=0;j<weights->length();j++)
867  {
868  if (rows <(*weights)[j]+1) rows=(-mr)+(*weights)[j]+1;
869  }
870  }
871  /*------ computation betti numbers --------------*/
872  rows -= mr;
873  result = new intvec(rows+1,cols,0);
874  if (weights!=NULL)
875  {
876  for(j=0;j<weights->length();j++)
877  {
878  IMATELEM((*result),(-mr)+(*weights)[j]+1,1) ++;
879  //Print("imat(%d,%d)++ -> %d\n",(-mr)+(*weights)[j]+1, 1, IMATELEM((*result),(-mr)+(*weights)[j]+1,1));
880  }
881  }
882  else
883  {
884  (*result)[(-mr)*cols] = /*idRankFreeModule(res[0])*/ rkl;
885  if ((!idIs0(res[0])) && ((*result)[(-mr)*cols]==0))
886  (*result)[(-mr)*cols] = 1;
887  }
888  tocancel = (int*)omAlloc0((rows+1)*sizeof(int));
889  memset(temp1,0,(l+1)*sizeof(int));
890  if (weights!=NULL)
891  {
892  memset(temp2,0,l*sizeof(int));
893  p_SetModDeg(weights, currRing);
894  }
895  else
896  memset(temp2,0,l*sizeof(int));
897  syDetect(res[0],0,TRUE,temp2,tocancel);
898  if (weights!=NULL) p_SetModDeg(NULL, currRing);
899  if (tomin)
900  {
901  //(*result)[(-mr)*cols] -= dummy;
902  for(j=0;j<=rows+mr;j++)
903  {
904  //Print("tocancel[%d]=%d imat(%d,%d)=%d\n",j,tocancel[j],(-mr)+j+1,1,IMATELEM((*result),(-mr)+j+1,1));
905  IMATELEM((*result),(-mr)+j+1,1) -= tocancel[j];
906  }
907  }
908  for (i=0;i<cols-1;i++)
909  {
910  if ((i==0) && (weights!=NULL)) p_SetModDeg(weights, currRing);
911  memset(temp2,0,l*sizeof(int));
912  for (j=0;j<IDELEMS(res[i]);j++)
913  {
914  if (res[i]->m[j]!=NULL)
915  {
916  temp2[j+1] = p_FDeg(res[i]->m[j],currRing)+temp1[pGetComp(res[i]->m[j])];
917  //(*result)[i+1+(temp2[j+1]-i-1)*cols]++;
918  //if (temp2[j+1]>i) IMATELEM((*result),temp2[j+1]-i-mr,i+2)++;
919  IMATELEM((*result),temp2[j+1]-i-mr,i+2)++;
920  }
921  else if (i==0)
922  {
923  if (j<r0_len) IMATELEM((*result),-mr,2)++;
924  }
925  }
926  /*------ computation betti numbers, if res not minimal --------------*/
927  if (tomin)
928  {
929  for (j=mr;j<rows+mr;j++)
930  {
931  //(*result)[i+1+j*cols] -= tocancel[j+1];
932  IMATELEM((*result),j+1-mr,i+2) -= tocancel[j+1];
933  }
934  if ((i<length-1) && (res[i+1]!=NULL))
935  {
936  memset(tocancel,0,(rows+1)*sizeof(int));
937  syDetect(res[i+1],i+1,TRUE,temp2,tocancel);
938  for (j=0;j<rows;j++)
939  {
940  //(*result)[i+1+j*cols] -= tocancel[j];
941  IMATELEM((*result),j+1,i+2) -= tocancel[j];
942  }
943  }
944  }
945  temp3 = temp1;
946  temp1 = temp2;
947  temp2 = temp3;
948  for (j=0;j<=rows;j++)
949  {
950  // if (((*result)[i+1+j*cols]!=0) && (j>*regularity)) *regularity = j;
951  if ((IMATELEM((*result),j+1,i+2)!=0) && (j>*regularity)) *regularity = j;
952  }
953  if ((i==0) && (weights!=NULL)) p_SetModDeg(NULL, currRing);
954  }
955  // Print("nach minim:\n"); result->show(); PrintLn();
956  /*------ clean up --------------*/
957  omFreeSize((ADDRESS)tocancel,(rows+1)*sizeof(int));
958  omFreeSize((ADDRESS)temp1,(l+1)*sizeof(int));
959  omFreeSize((ADDRESS)temp2,(l+1)*sizeof(int));
960  if ((tomin) && (mr<0)) // deletes the first (zero) line
961  {
962  for (j=1;j<=rows+mr+1;j++)
963  {
964  for (k=1;k<=cols;k++)
965  {
966  IMATELEM((*result),j,k) = IMATELEM((*result),j-mr,k);
967  }
968  }
969  for (j=rows+mr+1;j<=rows+1;j++)
970  {
971  for (k=1;k<=cols;k++)
972  {
973  IMATELEM((*result),j,k) = 0;
974  }
975  }
976  }
977  j = 0;
978  k = 0;
979  for (i=1;i<=result->rows();i++)
980  {
981  for(l=1;l<=result->cols();l++)
982  if (IMATELEM((*result),i,l) != 0)
983  {
984  j = si_max(j, i-1);
985  k = si_max(k, l-1);
986  }
987  }
988  intvec * exactresult=new intvec(j+1,k+1,0);
989  for (i=0;i<exactresult->rows();i++)
990  {
991  for (j=0;j<exactresult->cols();j++)
992  {
993  IMATELEM(*exactresult,i+1,j+1) = IMATELEM(*result,i+1,j+1);
994  }
995  }
996  if (row_shift!=NULL) *row_shift = mr;
997  delete result;
998  return exactresult;
999 }
static int si_max(const int a, const int b)
Definition: auxiliary.h:124
#define TRUE
Definition: auxiliary.h:100
void * ADDRESS
Definition: auxiliary.h:119
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Definition: intvec.h:23
void show(int mat=0, int spaces=0) const
Definition: intvec.cc:149
int length() const
Definition: intvec.h:94
int cols() const
Definition: intvec.h:95
int rows() const
Definition: intvec.h:96
#define Print
Definition: emacs.cc:80
#define WarnS
Definition: emacs.cc:78
return result
Definition: facAbsBiFact.cc:75
CanonicalForm res
Definition: facAbsFact.cc:60
const CanonicalForm & w
Definition: facAbsFact.cc:51
int j
Definition: facHensel.cc:110
void WerrorS(const char *s)
Definition: feFopen.cc:24
BOOLEAN idTestHomModule(ideal m, ideal Q, intvec *w)
Definition: ideals.cc:2053
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
static BOOLEAN idHomModule(ideal m, ideal Q, intvec **w)
Definition: ideals.h:96
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
#define IMATELEM(M, I, J)
Definition: intvec.h:85
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define NULL
Definition: omList.c:12
void p_SetModDeg(intvec *w, ring r)
Definition: p_polys.cc:3743
static long p_FDeg(const poly p, const ring r)
Definition: p_polys.h:380
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
#define pGetComp(p)
Component.
Definition: polys.h:37
void PrintS(const char *s)
Definition: reporter.cc:284
void PrintLn()
Definition: reporter.cc:310
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
#define IDELEMS(i)
Definition: simpleideals.h:23
@ isHomog
Definition: structs.h:42
int syDetect(ideal id, int index, BOOLEAN homog, int *degrees, int *tocancel)
Definition: syz.cc:701

◆ syDeleteAbove()

static void syDeleteAbove ( ideal  up,
int  k 
)
static

Definition at line 66 of file syz.cc.

67 {
68  if (up!=NULL)
69  {
70  for (int i=0;i<IDELEMS(up);i++)
71  {
72  if (up->m[i]!=NULL)
73  pDeleteComp(&(up->m[i]),k+1);
74  }
75  }
76 }
#define pDeleteComp(p, k)
Definition: polys.h:361

◆ syDeleteAbove1()

static void syDeleteAbove1 ( ideal  up,
int  k 
)
static

Definition at line 245 of file syz.cc.

246 {
247  poly p/*,pp*/;
248  if (up!=NULL)
249  {
250  for (int i=0;i<IDELEMS(up);i++)
251  {
252  p = up->m[i];
253  while ((p!=NULL) && (pGetComp(p)==k))
254  {
255  /*
256  pp = pNext(p);
257  pNext(p) = NULL;
258  pDelete(&p);
259  p = pp;
260  */
261  pLmDelete(&p);
262  }
263  up->m[i] = p;
264  if (p!=NULL)
265  {
266  while (pNext(p)!=NULL)
267  {
268  if (pGetComp(pNext(p))==k)
269  {
270  /*
271  pp = pNext(pNext(p));
272  pNext(pNext(p)) = NULL;
273  pDelete(&pNext(p));
274  pNext(p) = pp;
275  */
276  pLmDelete(&pNext(p));
277  }
278  else
279  pIter(p);
280  }
281  }
282  }
283  }
284 }
int p
Definition: cfModGcd.cc:4080
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
#define pLmDelete(p)
assume p != NULL, deletes Lm(p)->coef and Lm(p)
Definition: polys.h:76

◆ syDetect() [1/2]

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

Definition at line 701 of file syz.cc.

702 {
703  int i, j, k, subFromRank=0;
704  ideal temp;
705 
706  if (idIs0(id)) return 0;
707  temp = idInit(IDELEMS(id),id->rank);
708  for (i=0;i<IDELEMS(id);i++)
709  {
710  temp->m[i] = sypCopyConstant(id->m[i]);
711  }
712  i = IDELEMS(id);
713  while ((i>0) && (temp->m[i-1]==NULL)) i--;
714  if (i==0)
715  {
716  idDelete(&temp);
717  return 0;
718  }
719  j = 0;
720  while ((j<i) && (temp->m[j]==NULL)) j++;
721  while (j<i)
722  {
723  if (homog)
724  {
725  if (index==0) k = p_FDeg(temp->m[j],currRing)+degrees[pGetComp(temp->m[j])];
726  else k = degrees[pGetComp(temp->m[j])];
727  if (k>=index) tocancel[k-index]++;
728  if ((k>=0) && (index==0)) subFromRank++;
729  }
730  else
731  {
732  tocancel[0]--;
733  }
734  syGaussForOne(temp,j,pGetComp(temp->m[j]),j+1,i);
735  j++;
736  while ((j<i) && (temp->m[j]==NULL)) j++;
737  }
738  idDelete(&temp);
739  return subFromRank;
740 }
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
static poly sypCopyConstant(poly inp)
Definition: syz.cc:679
void syGaussForOne(ideal syz, int elnum, int ModComp, int from, int till)
Definition: syz.cc:218

◆ syDetect() [2/2]

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

Definition at line 742 of file syz.cc.

744 {
745  int * deg=NULL;
746  int * tocan=(int*) omAlloc0(tocancel->length()*sizeof(int));
747  int i;
748 
749  if (homog)
750  {
751  deg = (int*) omAlloc0(degrees->length()*sizeof(int));
752  for (i=degrees->length();i>0;i--)
753  deg[i-1] = (*degrees)[i-1]-rsmin;
754  }
755  syDetect(id,index,homog,deg,tocan);
756  for (i=tocancel->length();i>0;i--)
757  (*tocancel)[i-1] = tocan[i-1];
758  if (homog)
759  omFreeSize((ADDRESS)deg,degrees->length()*sizeof(int));
760  omFreeSize((ADDRESS)tocan,tocancel->length()*sizeof(int));
761 }

◆ syGaussForOne()

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

Definition at line 218 of file syz.cc.

219 {
220  int /*k,j,i,*/lu;
221  poly unit1,unit2;
222  poly actWith=syz->m[elnum];
223 
224  if (from<0) from = 0;
225  if ((till<=0) || (till>IDELEMS(syz))) till = IDELEMS(syz);
226  syz->m[elnum] = NULL;
228 /*--makes Gauss alg. for the column ModComp--*/
229  pTakeOutComp(&(actWith), ModComp, &unit1, &lu);
230  while (from<till)
231  {
232  poly tmp=syz->m[from];
233  if (/*syz->m[from]*/ tmp!=NULL)
234  {
235  pTakeOutComp(&(tmp), ModComp, &unit2, &lu);
236  tmp = pMult(pCopy(unit1),tmp);
237  syz->m[from] = pSub(tmp,
238  pMult(unit2,pCopy(actWith)));
239  }
240  from++;
241  }
242  pDelete(&actWith);
243  pDelete(&unit1);
244 }
poly p_Cleardenom(poly p, const ring r)
Definition: p_polys.cc:2900
#define pDelete(p_ptr)
Definition: polys.h:186
#define pSub(a, b)
Definition: polys.h:287
#define pMult(p, q)
Definition: polys.h:207
void pTakeOutComp(poly *p, long comp, poly *q, int *lq, const ring R=currRing)
Splits *p into two polys: *q which consists of all monoms with component == comp and *p of all other ...
Definition: polys.h:339
#define pCopy(p)
return a copy of the poly
Definition: polys.h:185
static BOOLEAN rField_has_simple_inverse(const ring r)
Definition: ring.h:553

◆ syMinBase()

ideal syMinBase ( ideal  arg)

Definition at line 1004 of file syz.cc.

1005 {
1006  intvec ** weights=NULL;
1007  int leng;
1008  if (idIs0(arg)) return idInit(1,arg->rank);
1009  resolvente res=syResolvente(arg,1,&leng,&weights,TRUE);
1010  ideal result=res[0];
1011  omFreeSize((ADDRESS)res,leng*sizeof(ideal));
1012  if (weights!=NULL)
1013  {
1014  if (*weights!=NULL)
1015  {
1016  delete (*weights);
1017  *weights=NULL;
1018  }
1019  if ((leng>=1) && (*(weights+1)!=NULL))
1020  {
1021  delete *(weights+1);
1022  *(weights+1)=NULL;
1023  }
1024  }
1026  return result;
1027 }
ideal * resolvente
Definition: ideals.h:18
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
resolvente syResolvente(ideal arg, int maxlength, int *length, intvec ***weights, BOOLEAN minim)
Definition: syz.cc:389

◆ syMinimizeResolvente()

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

Definition at line 355 of file syz.cc.

356 {
357  int syzIndex=first;
358  intvec *dummy;
359 
360  if (syzIndex<1) syzIndex=1;
361  if ((syzIndex==1) && (!rIsPluralRing(currRing)) && (idHomModule(res[0],currRing->qideal,&dummy)))
362  {
364  delete dummy;
365  return;
366  }
367  while ((syzIndex<length-1) && (res[syzIndex]!=NULL) && (res[syzIndex+1]!=NULL))
368  {
369  syMinStep(res[syzIndex-1],res[syzIndex],FALSE,res[syzIndex+1]);
370  syzIndex++;
371  }
372  if (res[syzIndex]!=NULL)
373  syMinStep(res[syzIndex-1],res[syzIndex]);
374  if (!idIs0(res[0]))
375  idMinEmbedding(res[0],TRUE);
376 }
#define FALSE
Definition: auxiliary.h:96
ideal idMinEmbedding(ideal arg, BOOLEAN inPlace, intvec **w)
Definition: ideals.cc:2671
static BOOLEAN rIsPluralRing(const ring r)
we must always have this test!
Definition: ring.h:400
static void syMinStep1(resolvente res, int length)
Definition: syz.cc:289
static void syMinStep(ideal mod, ideal &syz, BOOLEAN final=FALSE, ideal up=NULL, tHomog h=isNotHomog)
Definition: syz.cc:82

◆ 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.

84 {
85  poly Unit1,Unit2,actWith;
86  int len,i,j,ModComp,m,k,l;
87  BOOLEAN searchUnit,existsUnit;
88 
89  if (TEST_OPT_PROT) PrintS("m");
90  if ((final) && (h==isHomog))
91  /*minim is TRUE, we are in the module: maxlength, maxlength <>0*/
92  {
93  ideal deg0=id_Jet(syz,0,currRing);
94  id_Delete(&syz,currRing);
95  idSkipZeroes(deg0);
96  syz=deg0;
97  }
98 /*--cancels empty entees and their related components above--*/
99  j = IDELEMS(syz);
100  while ((j>0) && (!syz->m[j-1])) j--;
101  k = 0;
102  while (k<j)
103  {
104  if (syz->m[k]!=NULL)
105  k++;
106  else
107  {
108  if (TEST_OPT_PROT) PrintS(".");
109  for (l=k;l<j-1;l++) syz->m[l] = syz->m[l+1];
110  syz->m[j-1] = NULL;
111  syDeleteAbove(up,k);
112  j--;
113  }
114  }
115 /*--searches for syzygies coming from superfluous elements
116 * in the module below--*/
117  searchUnit = TRUE;
118  int curr_syz_limit = rGetCurrSyzLimit(currRing);
119  BOOLEAN bHasGlobalOrdering=rHasGlobalOrdering(currRing);
120  BOOLEAN bField_has_simple_inverse=rField_has_simple_inverse(currRing);
121  while (searchUnit)
122  {
123  i=0;
124  j=IDELEMS(syz);
125  while ((j>0) && (syz->m[j-1]==NULL)) j--;
126  existsUnit = FALSE;
127  if (bHasGlobalOrdering)
128  {
129  while ((i<j) && (!existsUnit))
130  {
131  existsUnit = pVectorHasUnitB(syz->m[i],&ModComp);
132  i++;
133  }
134  }
135  else
136  {
137  int I=0;
138  l = 0;
139  len=0;
140  for (i=0;i<IDELEMS(syz);i++)
141  {
142  if (syz->m[i]!=NULL)
143  {
144  pVectorHasUnit(syz->m[i],&m, &l);
145  if ((len==0) ||((l>0) && (l<len)))
146  {
147  len = l;
148  ModComp = m;
149  I = i;
150  }
151  }
152  }
153 //Print("Laenge ist: %d\n",len);
154  if (len>0) existsUnit = TRUE;
155  i = I+1;
156  }
157  if (existsUnit)
158  {
159  i--;
160 //--takes out the founded syzygy--
161  if (TEST_OPT_PROT) PrintS("f");
162  actWith = syz->m[i];
163  if (!bField_has_simple_inverse) p_Cleardenom(actWith, currRing);
164 //Print("actWith: ");pWrite(actWith);
165  syz->m[i] = NULL;
166  for (k=i;k<j-1;k++) syz->m[k] = syz->m[k+1];
167  syz->m[j-1] = NULL;
168  syDeleteAbove(up,i);
169  j--;
170 //--makes Gauss alg. for the column ModComp--
171  Unit1 = pTakeOutComp(&(actWith), ModComp);
172 //PrintS("actWith now: ");pWrite(actWith);
173 //Print("Unit1: ");pWrite(Unit1);
174  k=0;
175 //Print("j= %d",j);
176  while (k<j)
177  {
178  if (syz->m[k]!=NULL)
179  {
180  Unit2 = pTakeOutComp(&(syz->m[k]), ModComp);
181 //Print("element %d: ",k);pWrite(syz->m[k]);
182 //PrintS("Unit2: ");pWrite(Unit2);
183  syz->m[k] = pMult(pCopy(Unit1),syz->m[k]);
184  syz->m[k] = pSub(syz->m[k],
185  pMult(Unit2,pCopy(actWith)));
186  if (syz->m[k]==NULL)
187  {
188  for (l=k;l<j-1;l++)
189  syz->m[l] = syz->m[l+1];
190  syz->m[j-1] = NULL;
191  j--;
192  syDeleteAbove(up,k);
193  k--;
194  }
195  }
196  k++;
197  }
198  pDelete(&actWith);
199  pDelete(&Unit1);
200 //--deletes superfluous elements from the module below---
201  pDelete(&(mod->m[ModComp-1 - curr_syz_limit]));
202  for (k=ModComp-1 - curr_syz_limit;k<IDELEMS(mod)-1;k++)
203  mod->m[k] = mod->m[k+1];
204  mod->m[IDELEMS(mod)-1] = NULL;
205  }
206  else
207  searchUnit = FALSE;
208  }
209  if (TEST_OPT_PROT) PrintLn();
210  idSkipZeroes(mod);
211  idSkipZeroes(syz);
212 }
int BOOLEAN
Definition: auxiliary.h:87
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
STATIC_VAR Poly * h
Definition: janet.cc:971
#define TEST_OPT_PROT
Definition: options.h:102
#define pVectorHasUnitB(p, k)
Definition: polys.h:332
#define pVectorHasUnit(p, k, l)
Definition: polys.h:333
static int rGetCurrSyzLimit(const ring r)
Definition: ring.h:728
BOOLEAN rHasGlobalOrdering(const ring r)
Definition: ring.h:764
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
ideal id_Jet(const ideal i, int d, const ring R)
static void syDeleteAbove(ideal up, int k)
Definition: syz.cc:66

◆ syMinStep1()

static void syMinStep1 ( resolvente  res,
int  length 
)
static

Definition at line 289 of file syz.cc.

290 {
291  int i,j,k,index=0;
292  poly p;
293  intvec *have_del=NULL,*to_del=NULL;
294 
295  while ((index<length) && (res[index]!=NULL))
296  {
297 /*---we take out dependend elements from syz---------------------*/
298  if (res[index+1]!=NULL)
299  {
300  ideal deg0 = id_Jet(res[index+1],0,currRing);
301  ideal reddeg0 = kInterRedOld(deg0);
302  idDelete(&deg0);
303  have_del = new intvec(IDELEMS(res[index]));
304  for (i=0;i<IDELEMS(reddeg0);i++)
305  {
306  if (reddeg0->m[i]!=NULL)
307  {
308  j = pGetComp(reddeg0->m[i]);
309  pDelete(&(res[index]->m[j-1]));
310  /*res[index]->m[j-1] = NULL;*/
311  (*have_del)[j-1] = 1;
312  }
313  }
314  idDelete(&reddeg0);
315  }
316  if (index>0)
317  {
318 /*--- we search for units and perform Gaussian elimination------*/
319  j = to_del->length();
320  while (j>0)
321  {
322  if ((*to_del)[j-1]==1)
323  {
324  k = 0;
325  while (k<IDELEMS(res[index]))
326  {
327  p = res[index]->m[k];
328  while ((p!=NULL) && ((!pLmIsConstantComp(p)) || (pGetComp(p)!=j)))
329  pIter(p);
330  if ((p!=NULL) && (pLmIsConstantComp(p)) && (pGetComp(p)==j)) break;
331  k++;
332  }
333  if (k>=IDELEMS(res[index]))
334  {
335  PrintS("out of range\n");
336  }
338  if (res[index+1]!=NULL)
339  syDeleteAbove1(res[index+1],k+1);
340  (*to_del)[j-1] = 0;
341  }
342  j--;
343  }
344  }
345  if (to_del!=NULL) delete to_del;
346  to_del = have_del;
347  have_del = NULL;
348  index++;
349  }
350  if (TEST_OPT_PROT) PrintLn();
352  if (to_del!=NULL) delete to_del;
353 }
ideal kInterRedOld(ideal F, ideal Q)
Definition: kstd1.cc:3382
#define pLmIsConstantComp(p)
like above, except that p must be != NULL
Definition: polys.h:242
static void syDeleteAbove1(ideal up, int k)
Definition: syz.cc:245
void syKillEmptyEntres(resolvente res, int length)
Definition: syz1.cc:2199

◆ sypCopyConstant()

static poly sypCopyConstant ( poly  inp)
static

Definition at line 679 of file syz.cc.

680 {
681  poly outp=NULL,q;
682 
683  while (inp!=NULL)
684  {
685  if (pLmIsConstantComp(inp))
686  {
687  if (outp==NULL)
688  {
689  q = outp = pHead(inp);
690  }
691  else
692  {
693  pNext(q) = pHead(inp);
694  pIter(q);
695  }
696  }
697  pIter(inp);
698  }
699  return outp;
700 }
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition: polys.h:67

◆ syPrepareModComp()

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

Definition at line 25 of file syz.cc.

26 {
27  intvec *w1 = NULL;
28  int i;
29  BOOLEAN isIdeal=FALSE;
30 
31  if ((w==NULL) || (*w==NULL)) return w1;
32  int maxxx = (*w)->length();
33  if (maxxx==1)
34  {
35  maxxx = 2;
36  isIdeal = TRUE;
37  }
38  w1 = new intvec(maxxx+IDELEMS(arg));
39  if (!isIdeal)
40  {
41  for (i=0;i<maxxx;i++)
42  {
43  (*w1)[i] = (**w)[i];
44  }
45  }
46  for (i=maxxx;i<maxxx+IDELEMS(arg);i++)
47  {
48  if (arg->m[i-maxxx]!=NULL)
49  {
50  (*w1)[i] = p_FDeg(arg->m[i-maxxx],currRing);
51  if (pGetComp(arg->m[i-maxxx])!=0)
52  {
53  (*w1)[i]+=(**w)[pGetComp(arg->m[i-maxxx])-1];
54  }
55  }
56  }
57  delete (*w);
58  *w = new intvec(IDELEMS(arg)+1);
59  for (i=0;i<IDELEMS(arg);i++)
60  {
61  (**w)[i+1] = (*w1)[i+maxxx];
62  }
63  return w1;
64 }

◆ syResolution()

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

Definition at line 613 of file syz.cc.

614 {
615 
616 #ifdef HAVE_PLURAL
617  const ideal idSaveCurrRingQuotient = currRing->qideal;
618  if( rIsSCA(currRing) )
619  {
621  {
622  currRing->qideal = SCAQuotient(currRing);
623  }
624  const unsigned int m_iFirstAltVar = scaFirstAltVar(currRing);
625  const unsigned int m_iLastAltVar = scaLastAltVar(currRing);
626  arg = id_KillSquares(arg, m_iFirstAltVar, m_iLastAltVar, currRing, false); // kill suares in input!
627  }
628 #endif
629 
631 
632  if ((w!=NULL) && (!idTestHomModule(arg,currRing->qideal,w))) // is this right in SCA case???
633  {
634  WarnS("wrong weights given(2):");w->show();PrintLn();
635  idHomModule(arg,currRing->qideal,&w);
636  w->show();PrintLn();
637  w=NULL;
638  }
639  if (w!=NULL)
640  {
641  result->weights = (intvec**)omAlloc0Bin(char_ptr_bin);
642  (result->weights)[0] = ivCopy(w);
643  result->length = 1;
644  }
645  resolvente fr = syResolvente(arg,maxlength,&(result->length),&(result->weights),minim);
646  resolvente fr1;
647  if (minim)
648  {
649  result->minres = (resolvente)omAlloc0((result->length+1)*sizeof(ideal));
650  fr1 = result->minres;
651  }
652  else
653  {
654  result->fullres = (resolvente)omAlloc0((result->length+1)*sizeof(ideal));
655  fr1 = result->fullres;
656  }
657  for (int i=result->length-1;i>=0;i--)
658  {
659  if (fr[i]!=NULL)
660  fr1[i] = fr[i];
661  fr[i] = NULL;
662  }
663  omFreeSize((ADDRESS)fr,(result->length)*sizeof(ideal));
664 
665 #ifdef HAVE_PLURAL
666  if( rIsSCA(currRing) )
667  {
669  {
670  currRing->qideal = idSaveCurrRingQuotient;
671  }
672  id_Delete(&arg, currRing);
673  }
674 #endif
675 
676  return result;
677 }
intvec * ivCopy(const intvec *o)
Definition: intvec.h:135
static bool rIsSCA(const ring r)
Definition: nc.h:190
bool ncExtensions(int iMask)
Definition: old.gring.cc:94
const int TESTSYZSCAMASK
Definition: nc.h:342
ideal id_KillSquares(const ideal id, const short iFirstAltVar, const short iLastAltVar, const ring r, const bool bSkipZeroes)
Definition: sca.cc:1520
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
ideal SCAQuotient(const ring r)
Definition: sca.h:10
static short scaLastAltVar(ring r)
Definition: sca.h:25
static short scaFirstAltVar(ring r)
Definition: sca.h:18
EXTERN_VAR omBin char_ptr_bin
Definition: structs.h:82
ssyStrategy * syStrategy
Definition: syz.h:35

◆ syResolvente()

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

Definition at line 389 of file syz.cc.

391 {
392  BITSET save1;
393  SI_SAVE_OPT1(save1);
394  resolvente newres;
395  tHomog hom=isNotHomog;
396  intvec *w = NULL,**tempW;
397  int i,k,syzIndex = 0,j,rk_arg=si_max(1,(int)id_RankFreeModule(arg,currRing));
398  int Kstd1_OldDeg=Kstd1_deg;
399  BOOLEAN completeMinim;
400  BOOLEAN oldDegBound=TEST_OPT_DEGBOUND;
401  BOOLEAN setRegularity=TRUE;
402  int wlength=*length;
403 
404  if (maxlength!=-1) *length = maxlength+1;
405  else *length = 5;
406  if ((wlength!=0) && (*length!=wlength))
407  {
408  intvec **wtmp = (intvec**)omAlloc0((*length)*sizeof(intvec*));
409  wtmp[0]=(*weights)[0];
410  omFreeSize((ADDRESS)*weights,wlength*sizeof(intvec*));
411  *weights=wtmp;
412  }
413  resolvente res = (resolvente)omAlloc0((*length)*sizeof(ideal));
414 
415 /*--- initialize the syzygy-ring -----------------------------*/
416  ring origR = currRing;
417  ring syz_ring = rAssure_SyzComp(origR, TRUE); // will do rChangeCurrRing if needed
418  rSetSyzComp(rk_arg, syz_ring);
419 
420  if (syz_ring != origR)
421  {
422  rChangeCurrRing(syz_ring);
423  res[0] = idrCopyR_NoSort(arg, origR, syz_ring);
424  }
425  else
426  {
427  res[0] = idCopy(arg);
428  }
429 
430 /*--- creating weights for the module components ---------------*/
431  if ((weights!=NULL) && (*weights!=NULL)&& ((*weights)[0]!=NULL))
432  {
433  if (!idTestHomModule(res[0],currRing->qideal,(*weights)[0]))
434  {
435  WarnS("wrong weights given(1):"); (*weights)[0]->show();PrintLn();
436  idHomModule(res[0],currRing->qideal,&w);
437  w->show();PrintLn();
438  *weights=NULL;
439  }
440  }
441 
442  if ((weights==NULL) || (*weights==NULL) || ((*weights)[0]==NULL))
443  {
444  hom=(tHomog)idHomModule(res[0],currRing->qideal,&w);
445  if (hom==isHomog)
446  {
447  *weights = (intvec**)omAlloc0((*length)*sizeof(intvec*));
448  if (w!=NULL) (*weights)[0] = ivCopy(w);
449  }
450  }
451  else
452  {
453  if ((weights!=NULL) && (*weights!=NULL)&& ((*weights)[0]!=NULL))
454  {
455  w = ivCopy((*weights)[0]);
456  hom = isHomog;
457  }
458  }
459 
460 #ifdef HAVE_PLURAL
462  {
463 // quick solution; need theory to apply homog GB stuff for G-Algebras
464  hom = isNotHomog;
465  }
466 #endif // HAVE_PLURAL
467 
468  if (hom==isHomog)
469  {
470  intvec *w1 = syPrepareModComp(res[0],&w);
471  if (w!=NULL) { delete w;w=NULL; }
472  w = w1;
473  j = 0;
474  while ((j<IDELEMS(res[0])) && (res[0]->m[j]==NULL)) j++;
475  if (j<IDELEMS(res[0]))
476  {
477  if (p_FDeg(res[0]->m[j],currRing)!=pTotaldegree(res[0]->m[j]))
478  setRegularity = FALSE;
479  }
480  }
481  else
482  {
483  setRegularity = FALSE;
484  }
485 
486 /*--- the main loop --------------------------------------*/
487  while ((res[syzIndex]!=NULL) && (!idIs0(res[syzIndex])) &&
488  ((maxlength==-1) || (syzIndex<=maxlength)))
489  // (syzIndex<maxlength+(int)minim)))
490 /*--- compute one step more for minimizing-----------------*/
491  {
492  if (Kstd1_deg!=0) Kstd1_deg++;
493  if (syzIndex+1==*length)
494  {
495  newres = (resolvente)omAlloc0((*length+5)*sizeof(ideal));
496  tempW = (intvec**)omAlloc0((*length+5)*sizeof(intvec*));
497  for (j=0;j<*length;j++)
498  {
499  newres[j] = res[j];
500  if (*weights!=NULL) tempW[j] = (*weights)[j];
501  /*else tempW[j] = NULL;*/
502  }
503  omFreeSize((ADDRESS)res,*length*sizeof(ideal));
504  if (*weights != NULL) omFreeSize((ADDRESS)*weights,*length*sizeof(intvec*));
505  *length += 5;
506  res=newres;
507  *weights = tempW;
508  }
509 /*--- interreducing first -----------------------------------*/
510  if (syzIndex>0)
511  {
512  int rkI=id_RankFreeModule(res[syzIndex],currRing);
513  rSetSyzComp(rkI, currRing);
514  }
515  if(! TEST_OPT_NO_SYZ_MINIM )
516  if (minim || (syzIndex!=0))
517  {
518  ideal temp = kInterRedOld(res[syzIndex],currRing->qideal);
519  idDelete(&res[syzIndex]);
520  idSkipZeroes(temp);
521  res[syzIndex] = temp;
522  }
523 /*--- computing the syzygy modules --------------------------------*/
524  if ((currRing->qideal==NULL)&&(syzIndex==0)&& (!TEST_OPT_DEGBOUND))
525  {
526  res[/*syzIndex+*/1] = idSyzygies(res[0/*syzIndex*/],hom,&w,FALSE,setRegularity,&Kstd1_deg);
527  if ((!TEST_OPT_NOTREGULARITY) && (Kstd1_deg>0)
528  && (!rField_is_Ring(currRing))
530  }
531  else
532  {
533  res[syzIndex+1] = idSyzygies(res[syzIndex],hom,&w,FALSE);
534  }
535  completeMinim=(syzIndex!=maxlength) || (maxlength ==-1) || (hom!=isHomog);
536  syzIndex++;
537  if (TEST_OPT_PROT) Print("[%d]\n",syzIndex);
538 
539  if(! TEST_OPT_NO_SYZ_MINIM )
540  {
541  if ((minim)||(syzIndex>1))
542  syMinStep(res[syzIndex-1],res[syzIndex],!completeMinim,NULL,hom);
543  if (!completeMinim)
544  /*minim is TRUE, we are in the module: maxlength, maxlength <>0*/
545  {
546  idDelete(&res[syzIndex]);
547  }
548  }
549 /*---creating the iterated weights for module components ---------*/
550  if ((hom == isHomog) && (res[syzIndex]!=NULL) && (!idIs0(res[syzIndex])))
551  {
552 //Print("die %d Modulegewichte sind:\n",w1->length());
553 //w1->show();
554 //PrintLn();
555  int max_comp = id_RankFreeModule(res[syzIndex],currRing);
556  k = max_comp - rGetCurrSyzLimit(currRing);
557  assume(w != NULL);
558  if (w != NULL)
559  w->resize(max_comp+IDELEMS(res[syzIndex]));
560  else
561  w = new intvec(max_comp+IDELEMS(res[syzIndex]));
562  (*weights)[syzIndex] = new intvec(k);
563  for (i=0;i<k;i++)
564  {
565  if (res[syzIndex-1]->m[i]!=NULL) // hs
566  {
567  (*w)[i + rGetCurrSyzLimit(currRing)] = p_FDeg(res[syzIndex-1]->m[i],currRing);
568  if (pGetComp(res[syzIndex-1]->m[i])>0)
569  (*w)[i + rGetCurrSyzLimit(currRing)]
570  += (*w)[pGetComp(res[syzIndex-1]->m[i])-1];
571  (*((*weights)[syzIndex]))[i] = (*w)[i+rGetCurrSyzLimit(currRing)];
572  }
573  }
574  for (i=k;i<k+IDELEMS(res[syzIndex]);i++)
575  {
576  if (res[syzIndex]->m[i-k]!=NULL)
577  (*w)[i+rGetCurrSyzLimit(currRing)] = p_FDeg(res[syzIndex]->m[i-k],currRing)
578  +(*w)[pGetComp(res[syzIndex]->m[i-k])-1];
579  }
580  }
581  }
582 /*--- end of the main loop --------------------------------------*/
583 /*--- deleting the temporare data structures --------------------*/
584  if ((syzIndex!=0) && (res[syzIndex]!=NULL) && (idIs0(res[syzIndex])))
585  idDelete(&res[syzIndex]);
586  if (w !=NULL) delete w;
587 
588  Kstd1_deg=Kstd1_OldDeg;
589  if (!oldDegBound)
591 
592  for (i=1; i<=syzIndex; i++)
593  {
594  if ((res[i]!=NULL) && ! idIs0(res[i]))
595  {
597  }
598  }
599 /*--- going back to the original ring -------------------------*/
600  if (origR != syz_ring)
601  {
602  rChangeCurrRing(origR); // should not be needed now?
603  for (i=0; i<=syzIndex; i++)
604  {
605  res[i] = idrMoveR_NoSort(res[i], syz_ring, origR);
606  }
607  rDelete(syz_ring);
608  }
609  SI_RESTORE_OPT1(save1);
610  return res;
611 }
ideal idSyzygies(ideal h1, tHomog h, intvec **w, BOOLEAN setSyzComp, BOOLEAN setRegularity, int *deg, GbVariant alg)
Definition: ideals.cc:830
ideal idCopy(ideal A)
Definition: ideals.h:60
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:49
#define assume(x)
Definition: mod2.h:387
VAR unsigned si_opt_1
Definition: options.c:5
#define SI_SAVE_OPT1(A)
Definition: options.h:21
#define SI_RESTORE_OPT1(A)
Definition: options.h:24
#define Sy_bit(x)
Definition: options.h:31
#define TEST_OPT_DEGBOUND
Definition: options.h:112
#define TEST_OPT_NOTREGULARITY
Definition: options.h:119
#define OPT_DEGBOUND
Definition: options.h:89
#define TEST_OPT_NO_SYZ_MINIM
Definition: options.h:123
void rChangeCurrRing(ring r)
Definition: polys.cc:15
static long pTotaldegree(poly p)
Definition: polys.h:282
ideal idrMoveR_NoSort(ideal &id, ring src_r, ring dest_r)
Definition: prCopy.cc:260
ideal idrCopyR_NoSort(ideal id, ring src_r, ring dest_r)
Definition: prCopy.cc:204
ring rAssure_SyzComp(const ring r, BOOLEAN complete)
Definition: ring.cc:4426
int rGetMaxSyzComp(int i, const ring r)
return the max-comonent wchich has syzIndex i Assume: i<= syzIndex_limit
Definition: ring.cc:5108
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:449
void rSetSyzComp(int k, const ring r)
Definition: ring.cc:5036
static BOOLEAN rField_is_Ring(const ring r)
Definition: ring.h:489
void id_Shift(ideal M, int s, const ring r)
tHomog
Definition: structs.h:40
@ isNotHomog
Definition: structs.h:41
#define BITSET
Definition: structs.h:20
static intvec * syPrepareModComp(ideal arg, intvec **w)
Definition: syz.cc:25