My Project
Loading...
Searching...
No Matches
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:2069
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:3673
static long p_FDeg(const poly p, const ring r)
Definition: p_polys.h:378
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:37
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:360

◆ 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:4078
#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:2845
#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:338
#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:548

◆ 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]))
376}
#define FALSE
Definition: auxiliary.h:96
ideal idMinEmbedding(ideal arg, BOOLEAN inPlace, intvec **w)
Definition: ideals.cc:2687
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();
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:104
#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:723
BOOLEAN rHasGlobalOrdering(const ring r)
Definition: ring.h:759
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 dependent 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)
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:3409
#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:2198

◆ 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:145
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:338
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:77
ssyStrategy * syStrategy
Definition: syz.h:36

◆ 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 }
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);
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
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)
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)
590 si_opt_1 &= ~Sy_bit(OPT_DEGBOUND);
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:389
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:114
#define TEST_OPT_NOTREGULARITY
Definition: options.h:121
#define OPT_DEGBOUND
Definition: options.h:91
#define TEST_OPT_NO_SYZ_MINIM
Definition: options.h:125
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:261
ideal idrCopyR_NoSort(ideal id, ring src_r, ring dest_r)
Definition: prCopy.cc:205
ring rAssure_SyzComp(const ring r, BOOLEAN complete)
Definition: ring.cc:4435
int rGetMaxSyzComp(int i, const ring r)
return the max-comonent wchich has syzIndex i Assume: i<= syzIndex_limit
Definition: ring.cc:5158
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:450
void rSetSyzComp(int k, const ring r)
Definition: ring.cc:5086
#define rField_is_Ring(R)
Definition: ring.h:485
void id_Shift(ideal M, int s, const ring r)
tHomog
Definition: structs.h:35
@ isNotHomog
Definition: structs.h:36
#define BITSET
Definition: structs.h:16
static intvec * syPrepareModComp(ideal arg, intvec **w)
Definition: syz.cc:25