My Project  debian-1:4.1.1-p2+ds-4build4
Macros | Functions
syz0.cc File Reference
#include "kernel/mod2.h"
#include "misc/options.h"
#include "omalloc/omalloc.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/kbuckets.h"
#include "polys/prCopy.h"

Go to the source code of this file.

Macros

#define OLD_SEARCH
 

Functions

static void syInitSort (ideal arg, intvec **modcomp)
 
static void syCreatePairs (polyset F, int lini, int wend, int k, int j, int i, polyset pairs, int regularPairs=0, ideal mW=NULL)
 
static poly syRedtail2 (poly p, polyset redWith, intvec *modcomp)
 
static ideal sySchreyersSyzygiesFM (ideal arg, intvec **modcomp)
 
poly sySpecNormalize (poly toNorm, ideal mW=NULL)
 
static ideal sySchreyersSyzygiesFB (ideal arg, intvec **modcomp, ideal mW, BOOLEAN redTail=TRUE)
 
void syReOrderResolventFB (resolvente res, int length, int initial)
 
BOOLEAN syTestOrder (ideal M)
 
resolvente sySchreyerResolvente (ideal arg, int maxlength, int *length, BOOLEAN isMonomial, BOOLEAN)
 
syStrategy sySchreyer (ideal arg, int maxlength)
 

Macro Definition Documentation

◆ OLD_SEARCH

#define OLD_SEARCH

Function Documentation

◆ syCreatePairs()

static void syCreatePairs ( polyset  F,
int  lini,
int  wend,
int  k,
int  j,
int  i,
polyset  pairs,
int  regularPairs = 0,
ideal  mW = NULL 
)
static

Definition at line 69 of file syz0.cc.

71 {
72  int l,ii=0,jj;
73  poly p,q;
74 
75  while (((k<wend) && (pGetComp(F[k]) == i)) ||
76  ((currRing->qideal!=NULL) && (k<regularPairs+IDELEMS(currRing->qideal))))
77  {
78  p = pOne();
79  if ((k<wend) && (pGetComp(F[k]) == i) && (k!=j))
80  pLcm(F[j],F[k],p);
81  else if (ii<IDELEMS(currRing->qideal))
82  {
83  q = pHead(F[j]);
84  if (mW!=NULL)
85  {
86  for(jj=1;jj<=(currRing->N);jj++)
87  pSetExp(q,jj,pGetExp(q,jj) -pGetExp(mW->m[pGetComp(q)-1],jj));
88  pSetm(q);
89  }
90  pLcm(q,currRing->qideal->m[ii],p);
91  if (mW!=NULL)
92  {
93  for(jj=1;jj<=(currRing->N);jj++)
94  pSetExp(p,jj,pGetExp(p,jj) +pGetExp(mW->m[pGetComp(p)-1],jj));
95  pSetm(p);
96  }
97  pDelete(&q);
98  k = regularPairs+ii;
99  ii++;
100  }
101  l=lini;
102  while ((l<k) && ((pairs[l]==NULL) || (!pDivisibleBy(pairs[l],p))))
103  {
104  if ((pairs[l]!=NULL) && (pDivisibleBy(p,pairs[l])))
105  pDelete(&(pairs[l]));
106  l++;
107  }
108  if (l==k)
109  {
110  pSetm(p);
111  pairs[l] = p;
112  }
113  else
114  pDelete(&p);
115  k++;
116  }
117 }
int l
Definition: cfEzgcd.cc:93
int i
Definition: cfEzgcd.cc:125
int k
Definition: cfEzgcd.cc:92
int p
Definition: cfModGcd.cc:4019
int j
Definition: facHensel.cc:105
void pairs()
#define NULL
Definition: omList.c:10
ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
#define pDelete(p_ptr)
Definition: polys.h:173
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition: polys.h:67
#define pSetm(p)
Definition: polys.h:257
#define pGetComp(p)
Component.
Definition: polys.h:37
#define pGetExp(p, i)
Exponent.
Definition: polys.h:41
#define pDivisibleBy(a, b)
returns TRUE, if leading monom of a divides leading monom of b i.e., if there exists a expvector c > ...
Definition: polys.h:138
#define pSetExp(p, i, v)
Definition: polys.h:42
#define pOne()
Definition: polys.h:301
#define pLcm(a, b, m)
Definition: polys.h:281
#define IDELEMS(i)
Definition: simpleideals.h:24

◆ syInitSort()

static void syInitSort ( ideal  arg,
intvec **  modcomp 
)
static

Definition at line 24 of file syz0.cc.

25 {
26  int i,j,k,kk,kkk,jj;
27  idSkipZeroes(arg);
28  polyset F,oldF=arg->m;
29  int Fl=IDELEMS(arg);
30  int rkF=id_RankFreeModule(arg,currRing);
31  int syComponentOrder=currRing->ComponentOrder;
32 
33  while ((Fl!=0) && (oldF[Fl-1]==NULL)) Fl--;
34  if (*modcomp!=NULL) delete modcomp;
35  *modcomp = new intvec(rkF+2);
36  F=(polyset)omAlloc0(IDELEMS(arg)*sizeof(poly));
37  j=0;
38  for(i=0;i<=rkF;i++)
39  {
40  k=0;
41  jj = j;
42  (**modcomp)[i] = j;
43  while (k<Fl)
44  {
45  while ((k<Fl) && (pGetComp(oldF[k]) != i)) k++;
46  if (k<Fl)
47  {
48  kk=jj;
49  while ((kk<Fl) && (F[kk]) && (pLmCmp(oldF[k],F[kk])!=syComponentOrder))
50  {
51  kk++;
52  }
53  for (kkk=j;kkk>kk;kkk--)
54  {
55  F[kkk] = F[kkk-1];
56  }
57  F[kk] = oldF[k];
58 //Print("Element %d: ",kk);pWrite(F[kk]);
59  j++;
60  k++;
61  }
62  }
63  }
64  (**modcomp)[rkF+1] = Fl;
65  arg->m = F;
66  omFreeSize((ADDRESS)oldF,IDELEMS(arg)*sizeof(poly));
67 }
void * ADDRESS
Definition: auxiliary.h:133
Definition: intvec.h:21
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define pLmCmp(p, q)
returns 0|1|-1 if p=q|p>q|p<q w.r.t monomial ordering
Definition: polys.h:105
poly * polyset
Definition: polys.h:246
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size

◆ syRedtail2()

static poly syRedtail2 ( poly  p,
polyset  redWith,
intvec modcomp 
)
static

Definition at line 119 of file syz0.cc.

120 {
121  poly h, hn;
122  int hncomp,nxt;
123  int j;
124 
125  h = p;
126  hn = pNext(h);
127  while(hn != NULL)
128  {
129  hncomp = pGetComp(hn);
130  j = (*modcomp)[hncomp];
131  nxt = (*modcomp)[hncomp+1];
132  while (j < nxt)
133  {
134  if (pLmDivisibleByNoComp(redWith[j], hn))
135  {
136  //if (TEST_OPT_PROT) PrintS("r");
137  hn = ksOldSpolyRed(redWith[j],hn);
138  if (hn == NULL)
139  {
140  pNext(h) = NULL;
141  return p;
142  }
143  hncomp = pGetComp(hn);
144  j = (*modcomp)[hncomp];
145  nxt = (*modcomp)[hncomp+1];
146  }
147  else
148  {
149  j++;
150  }
151  }
152  h = pNext(h) = hn;
153  hn = pNext(h);
154  }
155  return p;
156 }
static Poly * h
Definition: janet.cc:972
KINLINE poly ksOldSpolyRed(poly p1, poly p2, poly spNoether)
Definition: kInline.h:1057
#define pNext(p)
Definition: monomials.h:43
#define pLmDivisibleByNoComp(a, b)
like pLmDivisibleBy, does not check components
Definition: polys.h:142

◆ syReOrderResolventFB()

void syReOrderResolventFB ( resolvente  res,
int  length,
int  initial 
)

Definition at line 741 of file syz0.cc.

742 {
743  int syzIndex=length-1,i,j;
744  poly p;
745 
746  while ((syzIndex!=0) && (res[syzIndex]==NULL)) syzIndex--;
747  while (syzIndex>=initial)
748  {
749  for(i=0;i<IDELEMS(res[syzIndex]);i++)
750  {
751  p = res[syzIndex]->m[i];
752 
753  while (p!=NULL)
754  {
755  if (res[syzIndex-1]->m[pGetComp(p)-1]!=NULL)
756  {
757  for(j=1;j<=(currRing->N);j++)
758  {
759  pSetExp(p,j,pGetExp(p,j)
760  -pGetExp(res[syzIndex-1]->m[pGetComp(p)-1],j));
761  }
762  }
763  else
764  PrintS("error in the resolvent\n");
765  pSetm(p);
766  pIter(p);
767  }
768  }
769  syzIndex--;
770  }
771 }
int m
Definition: cfEzgcd.cc:121
CanonicalForm res
Definition: facAbsFact.cc:64
poly initial(const poly p, const ring r, const gfan::ZVector &w)
Returns the initial form of p with respect to w.
Definition: initial.cc:30
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:267
#define pIter(p)
Definition: monomials.h:44
void PrintS(const char *s)
Definition: reporter.cc:284

◆ sySchreyer()

syStrategy sySchreyer ( ideal  arg,
int  maxlength 
)

Definition at line 1019 of file syz0.cc.

1020 {
1021  int rl;
1022  resolvente fr = sySchreyerResolvente(arg,maxlength,&(rl));
1023  if (fr==NULL) return NULL;
1024 
1025  // int typ0;
1027  result->length=rl;
1028  result->fullres = (resolvente)omAlloc0((rl /*result->length*/+1)*sizeof(ideal));
1029  for (int i=rl /*result->length*/-1;i>=0;i--)
1030  {
1031  if (fr[i]!=NULL)
1032  {
1033  result->fullres[i] = fr[i];
1034  fr[i] = NULL;
1035  }
1036  }
1037  if (currRing->qideal!=NULL)
1038  {
1039  for (int i=0; i<rl; i++)
1040  {
1041  if (result->fullres[i]!=NULL)
1042  {
1043  ideal t=kNF(currRing->qideal,NULL,result->fullres[i]);
1044  idDelete(&result->fullres[i]);
1045  result->fullres[i]=t;
1046  if (i<rl-1)
1047  {
1048  for(int j=IDELEMS(t)-1;j>=0; j--)
1049  {
1050  if ((t->m[j]==NULL) && (result->fullres[i+1]!=NULL))
1051  {
1052  for(int k=IDELEMS(result->fullres[i+1])-1;k>=0; k--)
1053  {
1054  if (result->fullres[i+1]->m[k]!=NULL)
1055  {
1056  pDeleteComp(&(result->fullres[i+1]->m[k]),j+1);
1057  }
1058  }
1059  }
1060  }
1061  }
1062  idSkipZeroes(result->fullres[i]);
1063  }
1064  }
1065  if ((rl>maxlength) && (result->fullres[rl-1]!=NULL))
1066  {
1067  idDelete(&result->fullres[rl-1]);
1068  }
1069  }
1070  omFreeSize((ADDRESS)fr,(rl /*result->length*/)*sizeof(ideal));
1071  return result;
1072 }
return result
Definition: facAbsBiFact.cc:76
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
ideal * resolvente
Definition: ideals.h:18
poly kNF(ideal F, ideal Q, poly p, int syzComp, int lazyReduce)
Definition: kstd1.cc:2813
#define pDeleteComp(p, k)
Definition: polys.h:347
resolvente sySchreyerResolvente(ideal arg, int maxlength, int *length, BOOLEAN isMonomial, BOOLEAN)
Definition: syz0.cc:856
ssyStrategy * syStrategy
Definition: syz.h:35

◆ sySchreyerResolvente()

resolvente sySchreyerResolvente ( ideal  arg,
int  maxlength,
int *  length,
BOOLEAN  isMonomial,
BOOLEAN  notReplace 
)

Definition at line 856 of file syz0.cc.

858 {
859  ideal mW=NULL;
860  int i,syzIndex = 0,j=0;
861  intvec * modcomp=NULL,*w=NULL;
862  // int ** wv=NULL;
863  tHomog hom=(tHomog)idHomModule(arg,NULL,&w);
864  ring origR = currRing;
865  ring syRing = NULL;
866 
867  if ((!isMonomial) && syTestOrder(arg))
868  {
869  WerrorS("sres only implemented for modules with ordering ..,c or ..,C");
870  return NULL;
871  }
872  *length = 4;
873  resolvente res = (resolvente)omAlloc0(4*sizeof(ideal)),newres;
874  res[0] = idCopy(arg);
875 
876  while ((!idIs0(res[syzIndex])) && ((maxlength==-1) || (syzIndex<maxlength)))
877  {
878  i = IDELEMS(res[syzIndex]);
879  //while ((i!=0) && (!res[syzIndex]->m[i-1])) i--;
880  if (syzIndex+1==*length)
881  {
882  newres = (resolvente)omAlloc0((*length+4)*sizeof(ideal));
883  // for (j=0;j<*length+4;j++) newres[j] = NULL;
884  for (j=0;j<*length;j++) newres[j] = res[j];
885  omFreeSize((ADDRESS)res,*length*sizeof(ideal));
886  *length += 4;
887  res=newres;
888  }
889 
890  if ((hom==isHomog)|| (rHasGlobalOrdering(origR)))
891  {
892  if (syzIndex==0) syInitSort(res[0],&modcomp);
893 
894  if ((syzIndex==0) && !rRing_has_CompLastBlock(currRing))
895  res[syzIndex+1] = sySchreyersSyzygiesFB(res[syzIndex],&modcomp,mW,FALSE);
896  else
897  res[syzIndex+1] = sySchreyersSyzygiesFB(res[syzIndex],&modcomp,mW);
898 
899  if (errorreported)
900  {
901  for (j=0;j<*length;j++) idDelete( &res[j] );
902  omFreeSize((ADDRESS)res,*length*sizeof(ideal));
903  return NULL;
904  }
905 
906  mW = res[syzIndex];
907  }
908 //idPrint(res[syzIndex+1]);
909 
910  if ( /*(*/ syzIndex==0 /*)*/ )
911  {
912  if ((hom==isHomog)|| (rHasGlobalOrdering(origR)))
913  {
914  syRing = rAssure_CompLastBlock(origR, TRUE);
915  if (syRing != origR)
916  {
917  rChangeCurrRing(syRing);
918  for (i=0; i<IDELEMS(res[1]); i++)
919  {
920  res[1]->m[i] = prMoveR( res[1]->m[i], origR, syRing);
921  }
922  }
923  idTest(res[1]);
924  }
925  else
926  {
927  syRing = rAssure_SyzComp_CompLastBlock(origR);
928  if (syRing != origR)
929  {
930  rChangeCurrRing(syRing);
931  for (i=0; i<IDELEMS(res[0]); i++)
932  {
933  res[0]->m[i] = prMoveR( res[0]->m[i], origR, syRing);
934  }
935  }
936  idTest(res[0]);
937  }
938  }
939  if ((hom!=isHomog) && (rHasLocalOrMixedOrdering(origR)))
940  {
941  if (syzIndex==0) syInitSort(res[0],&modcomp);
942  res[syzIndex+1] = sySchreyersSyzygiesFM(res[syzIndex],&modcomp);
943  if (errorreported)
944  {
945  for (j=0;j<*length;j++) idDelete( &res[j] );
946  omFreeSize((ADDRESS)res,*length*sizeof(ideal));
947  return NULL;
948  }
949  }
950  syzIndex++;
951  if (TEST_OPT_PROT) Print("[%d]\n",syzIndex);
952  }
953  //syPrintResolution(res,1,*length);
954  if ((hom!=isHomog) && (rHasLocalOrMixedOrdering(origR)))
955  {
956  syzIndex = 1;
957  while ((syzIndex < *length) && (!idIs0(res[syzIndex])))
958  {
959  id_Shift(res[syzIndex],-rGetMaxSyzComp(syzIndex, currRing),currRing);
960  syzIndex++;
961  }
962  }
963  if ((hom==isHomog) || (rHasGlobalOrdering(origR)))
964  syzIndex = 1;
965  else
966  syzIndex = 0;
967  syReOrderResolventFB(res,*length,syzIndex+1);
968  if (/*ringOrderChanged:*/ origR!=syRing && syRing != NULL)
969  {
970  rChangeCurrRing(origR);
971  // Thomas: Here I assume that all (!) polys of res live in tmpR
972  while ((syzIndex < *length) && (res[syzIndex]))
973  {
974  for (i=0;i<IDELEMS(res[syzIndex]);i++)
975  {
976  if (res[syzIndex]->m[i])
977  {
978  res[syzIndex]->m[i] = prMoveR( res[syzIndex]->m[i], syRing, origR);
979  }
980  }
981  syzIndex++;
982  }
983 // j = 0; while (currRing->order[j]!=0) j++; // What was this for???!
984  rDelete(syRing);
985  }
986  else
987  {
988  // Thomas -- are you sure that you have to "reorder" here?
989  while ((syzIndex < *length) && (res[syzIndex]))
990  {
991  for (i=0;i<IDELEMS(res[syzIndex]);i++)
992  {
993  if (res[syzIndex]->m[i])
994  res[syzIndex]->m[i] = pSortCompCorrect(res[syzIndex]->m[i]);
995  }
996  syzIndex++;
997  }
998  }
999  if ((hom==isHomog) || (rHasGlobalOrdering(origR)))
1000  {
1001  if (res[1]!=NULL)
1002  {
1004  for (i=0;i<IDELEMS(res[1]);i++)
1005  {
1006  if (res[1]->m[i])
1007  res[1]->m[i] = pSort(res[1]->m[i]);
1008  }
1009  }
1010  }
1011  //syPrintResolution(res,0,*length);
1012 
1013  //syMergeSortResolventFB(res,*length);
1014  if (modcomp!=NULL) delete modcomp;
1015  if (w!=NULL) delete w;
1016  return res;
1017 }
#define TRUE
Definition: auxiliary.h:98
#define FALSE
Definition: auxiliary.h:94
#define Print
Definition: emacs.cc:80
const CanonicalForm & w
Definition: facAbsFact.cc:55
void WerrorS(const char *s)
Definition: feFopen.cc:24
short errorreported
Definition: feFopen.cc:23
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
#define idTest(id)
Definition: ideals.h:47
ideal idCopy(ideal A)
Definition: ideals.h:60
#define TEST_OPT_PROT
Definition: options.h:102
void rChangeCurrRing(ring r)
Definition: polys.cc:15
#define pSort(p)
Definition: polys.h:205
#define pSortCompCorrect(p)
Assume: If considerd only as poly in any component of p (say, monomials of other components of p are ...
Definition: polys.h:214
poly prMoveR(poly &p, ring src_r, ring dest_r)
Definition: prCopy.cc:90
BOOLEAN rRing_has_CompLastBlock(ring r)
Definition: ring.cc:5094
int rGetMaxSyzComp(int i, const ring r)
return the max-comonent wchich has syzIndex i Assume: i<= syzIndex_limit
Definition: ring.cc:5045
ring rAssure_SyzComp_CompLastBlock(const ring r)
makes sure that c/C ordering is last ordering and SyzIndex is first
Definition: ring.cc:4650
void rDelete(ring r)
unconditionally deletes fields in r
Definition: ring.cc:439
ring rAssure_CompLastBlock(ring r, BOOLEAN complete)
makes sure that c/C ordering is last ordering
Definition: ring.cc:4595
BOOLEAN rHasGlobalOrdering(const ring r)
Definition: ring.h:751
BOOLEAN rHasLocalOrMixedOrdering(const ring r)
Definition: ring.h:752
void id_Shift(ideal M, int s, const ring r)
tHomog
Definition: structs.h:38
@ isHomog
Definition: structs.h:40
static ideal sySchreyersSyzygiesFB(ideal arg, intvec **modcomp, ideal mW, BOOLEAN redTail=TRUE)
Definition: syz0.cc:500
static void syInitSort(ideal arg, intvec **modcomp)
Definition: syz0.cc:24
static ideal sySchreyersSyzygiesFM(ideal arg, intvec **modcomp)
Definition: syz0.cc:163
void syReOrderResolventFB(resolvente res, int length, int initial)
Definition: syz0.cc:741
BOOLEAN syTestOrder(ideal M)
Definition: syz0.cc:830

◆ sySchreyersSyzygiesFB()

static ideal sySchreyersSyzygiesFB ( ideal  arg,
intvec **  modcomp,
ideal  mW,
BOOLEAN  redTail = TRUE 
)
static

Definition at line 500 of file syz0.cc.

501 {
502  kBucket_pt sy0buck = kBucketCreate(currRing);
503 
504  int Fl=IDELEMS(arg);
505  while ((Fl!=0) && (arg->m[Fl-1]==NULL)) Fl--;
506  ideal result=idInit(16,Fl);
507  int i,j,l,k,kkk,/*rkF,*/Sl=0,syComponentOrder=currRing->ComponentOrder;
508  int /*fstart,*/wend,lini,ltR,gencQ=0;
509  intvec *newmodcomp;
510  int *Flength;
511  polyset pairs,F=arg->m,*Shdl=&(result->m);
512  poly /*p,*/q,toRed,syz,lastmonom,multWith;
513  BOOLEAN isNotReduced=TRUE;
514 
515 //#define WRITE_BUCKETS
516 #ifdef WRITE_BUCKETS
517  PrintS("Input: \n");
518  ideal twr=idHead(arg);
519  idPrint(arg);
520  idDelete(&twr);
521  if (modcomp!=NULL) (*modcomp)->show(0,0);
522 #endif
523 
524  newmodcomp = new intvec(Fl+2);
525  //for (j=0;j<Fl;j++) pWrite(F[j]);
526  //PrintLn();
527  if (currRing->qideal==NULL)
528  pairs=(polyset)omAlloc0(Fl*sizeof(poly));
529  else
530  {
531  gencQ = IDELEMS(currRing->qideal);
532  pairs=(polyset)omAlloc0((Fl+gencQ)*sizeof(poly));
533  }
534  // rkF=id_RankFreeModule(arg,currRing);
535  Flength = (int*)omAlloc0(Fl*sizeof(int));
536  for(j=0;j<Fl;j++)
537  {
538  Flength[j] = pLength(F[j]);
539  }
540  for(j=0;j<Fl;j++)
541  {
542  (*newmodcomp)[j+1] = Sl;
543  if (TEST_OPT_PROT)
544  {
545  Print("(%d)",Fl-j);
546  mflush();
547  }
548  i = pGetComp(F[j]);
549  if (syComponentOrder==1)
550  {
551  lini=k=j+1;
552  wend=Fl;
553  }
554  else
555  {
556  lini=k=0;
557  while ((k<j) && (pGetComp(F[k]) != i)) k++;
558  wend=j;
559  }
560  syCreatePairs(F,lini,wend,k,j,i,pairs,Fl,mW);
561  if (currRing->qideal!=NULL) wend = Fl+gencQ;
562  for (k=lini;k<wend;k++)
563  {
564  if (pairs[k]!=NULL)
565  {
566  if (TEST_OPT_PROT)
567  {
568  PrintS(".");
569  mflush();
570  }
571  //begins to construct the syzygy
572  if (k<Fl)
573  {
574  number an=nCopy(pGetCoeff(F[k])),bn=nCopy(pGetCoeff(F[j]));
575  /*int ct =*/ (void) ksCheckCoeff(&an, &bn, currRing->cf);
576  syz = pCopy(pairs[k]);
577  //syz->coef = nCopy(F[k]->coef);
578  syz->coef = an;
579  //syz->coef = nInpNeg(syz->coef);
580  pNext(syz) = pairs[k];
581  lastmonom = pNext(syz);
582  //lastmonom->coef = nCopy(F[j]->coef);
583  lastmonom->coef = bn;
584  lastmonom->coef = nInpNeg(lastmonom->coef);
585  pSetComp(lastmonom,k+1);
586  }
587  else
588  {
589  syz = pairs[k];
590  syz->coef = nCopy(currRing->qideal->m[k-Fl]->coef);
591  syz->coef = nInpNeg(syz->coef);
592  lastmonom = syz;
593  multWith = pMDivide(syz,F[j]);
594  multWith->coef = nCopy(currRing->qideal->m[k-Fl]->coef);
595  }
596  pSetComp(syz,j+1);
597  pairs[k] = NULL;
598  //the next term of the syzygy
599  //constructs the spoly
600  if (TEST_OPT_DEBUG)
601  {
602  if (k<Fl)
603  {
604  PrintS("pair: ");pWrite0(F[j]);PrintS(" ");pWrite(F[k]);
605  }
606  else
607  {
608  PrintS("pair: ");pWrite0(F[j]);PrintS(" ");pWrite(currRing->qideal->m[k-Fl]);
609  }
610  }
611  if (k<Fl)
612  toRed = ksOldCreateSpoly(F[j],F[k]);
613  else
614  {
615  q = pMult_mm(pCopy(F[j]),multWith);
616  toRed = sySpecNormalize(q,mW);
617  pDelete(&multWith);
618  }
619  kBucketInit(sy0buck,toRed,-1);
620  toRed = kBucketGetLm(sy0buck);
621  isNotReduced = TRUE;
622  while (toRed!=NULL)
623  {
624  if (TEST_OPT_DEBUG)
625  {
626  PrintS("toRed: ");pWrite(toRed);
627  }
628 // l=0;
629 // while ((l<Fl) && (!pDivisibleBy(F[l],toRed))) l++;
630 // if (l>=Fl)
631  l = (**modcomp)[pGetComp(toRed)+1]-1;
632  kkk = (**modcomp)[pGetComp(toRed)];
633  while ((l>=kkk) && (!pDivisibleBy(F[l],toRed))) l--;
634 #ifdef WRITE_BUCKETS
635  kBucketClear(sy0buck,&toRed,&ltR);
636  printf("toRed in Pair[%d, %d]:", j, k);
637  pWrite(toRed);
638  kBucketInit(sy0buck,toRed,-1);
639 #endif
640 
641  if (l<kkk)
642  {
643  if ((currRing->qideal!=NULL) && (isNotReduced))
644  {
645  kBucketClear(sy0buck,&toRed,&ltR);
646  toRed = sySpecNormalize(toRed,mW);
647 #ifdef WRITE_BUCKETS
648  printf("toRed in Pair[%d, %d]:", j, k);
649  pWrite(toRed);
650 #endif
651  kBucketInit(sy0buck,toRed,-1);
652  toRed = kBucketGetLm(sy0buck);
653  isNotReduced = FALSE;
654  }
655  else
656  {
657  pDelete(&toRed);
658 
659  pDelete(&syz);
660  for(k=j;k<Fl;k++) pDelete(&(pairs[k]));
661  omFreeSize((ADDRESS)pairs,(Fl + gencQ)*sizeof(poly));
662 
663 
664  for(k=0;k<IDELEMS(result);k++) pDelete(&((*Shdl)[k]));
665 
666  kBucketDestroy(&(sy0buck));
667 
668  //no polynom for reduction
669  WerrorS("ideal not a standard basis");
670 
671  return result;
672  }
673  }
674  else
675  {
676  //the next monom of the syzygy
677  isNotReduced = TRUE;
678  if (TEST_OPT_DEBUG)
679  {
680  PrintS("reduced with: ");pWrite(F[l]);
681  }
682  pNext(lastmonom) = pHead(toRed);
683  pIter(lastmonom);
684  lastmonom->coef = nDiv(lastmonom->coef,F[l]->coef);
685  //lastmonom->coef = nInpNeg(lastmonom->coef);
686  pSetComp(lastmonom,l+1);
687  //computes the new toRed
688  number up = kBucketPolyRed(sy0buck,F[l],Flength[l],NULL);
689  if (! nIsOne(up))
690  {
691  // Thomas: Now do whatever you need to do
692 #ifdef WRITE_BUCKETS
693  PrintS("multiplied with: ");nWrite(up);PrintLn();
694 #endif
695  syz=__p_Mult_nn(syz,up,currRing);
696  }
697  nDelete(&up);
698 
699  toRed = kBucketGetLm(sy0buck);
700  //the module component of the new monom
701 //pWrite(toRed);
702  }
703  }
704  kBucketClear(sy0buck,&toRed,&ltR); //Zur Sichereheit
705 //PrintLn();
706  if (syz!=NULL)
707  {
708  if (Sl>=IDELEMS(result))
709  {
710  pEnlargeSet(Shdl,IDELEMS(result),16);
711  IDELEMS(result) += 16;
712  }
713  pNorm(syz);
714  if (BTEST1(OPT_REDTAIL) && redTail)
715  {
716  (*newmodcomp)[j+2] = Sl;
717  (*Shdl)[Sl] = syRedtail2(syz,*Shdl,newmodcomp);
718  (*newmodcomp)[j+2] = 0;
719  }
720  else
721  (*Shdl)[Sl] = syz;
722  Sl++;
723  }
724  }
725  }
726 // for(k=j;k<Fl;k++) pDelete(&(pairs[k]));
727  }
728  (*newmodcomp)[Fl+1] = Sl;
729  if (currRing->qideal==NULL)
730  omFreeSize((ADDRESS)pairs,Fl*sizeof(poly));
731  else
732  omFreeSize((ADDRESS)pairs,(Fl+IDELEMS(currRing->qideal))*sizeof(poly));
733  omFreeSize((ADDRESS)Flength,Fl*sizeof(int));
734  delete *modcomp;
735  *modcomp = newmodcomp;
736 
737  kBucketDestroy(&(sy0buck));
738  return result;
739 }
int BOOLEAN
Definition: auxiliary.h:85
ideal idHead(ideal h)
#define idPrint(id)
Definition: ideals.h:46
KINLINE poly ksOldCreateSpoly(poly p1, poly p2, poly spNoether, ring r)
Definition: kInline.h:1077
void kBucketClear(kBucket_pt bucket, poly *p, int *length)
Definition: kbuckets.cc:503
void kBucketDestroy(kBucket_pt *bucket_pt)
Definition: kbuckets.cc:213
void kBucketInit(kBucket_pt bucket, poly lm, int length)
Definition: kbuckets.cc:475
kBucket_pt kBucketCreate(const ring bucket_ring)
Creation/Destruction of buckets.
Definition: kbuckets.cc:206
number kBucketPolyRed(kBucket_pt bucket, poly p1, int l1, poly spNoether)
Definition: kbuckets.cc:1061
const poly kBucketGetLm(kBucket_pt bucket)
Definition: kbuckets.cc:488
int ksCheckCoeff(number *a, number *b)
static number & pGetCoeff(poly p)
return an alias to the leading coefficient of p assumes that p != NULL NOTE: not copy
Definition: monomials.h:51
#define nDiv(a, b)
Definition: numbers.h:33
#define nWrite(n)
Definition: numbers.h:30
#define nDelete(n)
Definition: numbers.h:17
#define nInpNeg(n)
Definition: numbers.h:22
#define nCopy(n)
Definition: numbers.h:16
#define nIsOne(n)
Definition: numbers.h:26
#define OPT_REDTAIL
Definition: options.h:90
#define BTEST1(a)
Definition: options.h:34
#define TEST_OPT_DEBUG
Definition: options.h:107
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3633
static unsigned pLength(poly a)
Definition: p_polys.h:192
#define __p_Mult_nn(p, n, r)
Definition: p_polys.h:927
#define pSetComp(p, v)
Definition: polys.h:38
void pWrite0(poly p)
Definition: polys.h:295
void pWrite(poly p)
Definition: polys.h:294
void pNorm(poly p, const ring R=currRing)
Definition: polys.h:349
#define pMult_mm(p, m)
Definition: polys.h:189
#define pMDivide(a, b)
Definition: polys.h:279
#define pCopy(p)
return a copy of the poly
Definition: polys.h:172
void PrintLn()
Definition: reporter.cc:310
#define mflush()
Definition: reporter.h:57
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:37
static void syCreatePairs(polyset F, int lini, int wend, int k, int j, int i, polyset pairs, int regularPairs=0, ideal mW=NULL)
Definition: syz0.cc:69
poly sySpecNormalize(poly toNorm, ideal mW=NULL)
Definition: syz0.cc:457
static poly syRedtail2(poly p, polyset redWith, intvec *modcomp)
Definition: syz0.cc:119

◆ sySchreyersSyzygiesFM()

static ideal sySchreyersSyzygiesFM ( ideal  arg,
intvec **  modcomp 
)
static

Definition at line 163 of file syz0.cc.

164 {
165  int Fl=IDELEMS(arg);
166  while ((Fl!=0) && (arg->m[Fl-1]==NULL)) Fl--;
167  ideal result=idInit(16,arg->rank+Fl);
168  polyset F=arg->m,*Shdl=&(result->m);
169  if (Fl==0) return result;
170 
171  int i,j,l,k,totalToRed,ecartToRed,kk;
172  int bestEcart,totalmax,rkF,Sl=0,smax,tmax,tl;
173  int *ecartS, *ecartT, *totalS,
174  *totalT=NULL, *temp=NULL;
175  polyset pairs,S,T,ST/*,oldF*/;
176  poly p,q,toRed;
177  BOOLEAN notFound = FALSE;
178  intvec * newmodcomp = new intvec(Fl+2);
179  intvec * tempcomp;
180 
181 //Print("Naechster Modul\n");
182 //idPrint(arg);
183 /*-------------initializing the sets--------------------*/
184  ST=(polyset)omAlloc0(Fl*sizeof(poly));
185  S=(polyset)omAlloc0(Fl*sizeof(poly));
186  ecartS=(int*)omAlloc(Fl*sizeof(int));
187  totalS=(int*)omAlloc(Fl*sizeof(int));
188  T=(polyset)omAlloc0(2*Fl*sizeof(poly));
189  ecartT=(int*)omAlloc(2*Fl*sizeof(int));
190  totalT=(int*)omAlloc(2*Fl*sizeof(int));
191  pairs=(polyset)omAlloc0(Fl*sizeof(poly));
192 
193  smax = Fl;
194  tmax = 2*Fl;
195  for (j=1;j<IDELEMS(arg);j++)
196  {
197  if (arg->m[j] != NULL)
198  {
199  assume (arg->m[j-1] != NULL);
200  assume (pGetComp(arg->m[j-1])-pGetComp(arg->m[j])<=0);
201  }
202  }
203  rkF=id_RankFreeModule(arg,currRing);
204 /*----------------construction of the new ordering----------*/
205  if (rkF>0)
206  rSetSyzComp(rkF, currRing);
207  else
208  rSetSyzComp(1, currRing);
209 /*----------------creating S--------------------------------*/
210  for(j=0;j<Fl;j++)
211  {
212  S[j] = pCopy(F[j]);
213  totalS[j] = p_LDeg(S[j],&k,currRing);
214  ecartS[j] = totalS[j]-p_FDeg(S[j],currRing);
215 //Print("%d", pGetComp(S[j]));PrintS(" ");
216  p = S[j];
217  if (rkF==0) pSetCompP(p,1);
218  while (pNext(p)!=NULL) pIter(p);
219  pNext(p) = pHead(F[j]);
220  pIter(p);
221  if (rkF==0)
222  pSetComp(p,j+2);
223  else
224  pSetComp(p,rkF+j+1);
225  pSetmComp(p);
226  }
227 //PrintLn();
228  if (rkF==0) rkF = 1;
229 /*---------------creating the initial for T----------------*/
230  j=0;
231  l=-1;
232  totalmax=-1;
233  for (k=0;k<smax;k++)
234  if (totalS[k]>totalmax) totalmax=totalS[k];
235  for (kk=1;kk<=rkF;kk++)
236  {
237  for (k=0;k<=totalmax;k++)
238  {
239  for (l=0;l<smax;l++)
240  {
241  if ((pGetComp(S[l])==kk) && (totalS[l]==k))
242  {
243  ST[j] = S[l];
244  totalT[j] = totalS[l];
245  ecartT[j] = ecartS[l];
246 //Print("%d", totalS[l]);PrintS(" ");
247  j++;
248  }
249  }
250  }
251  }
252 //PrintLn();
253  for (j=0;j<smax;j++)
254  {
255  totalS[j] = totalT[j];
256  ecartS[j] = ecartT[j];
257  }
258 
259 /*---------------computing---------------------------------*/
260  for(j=0;j<smax;j++)
261  {
262  (*newmodcomp)[j+1] = Sl;
263  i = pGetComp(S[j]);
264  int syComponentOrder= currRing->ComponentOrder;
265  int lini,wend;
266  if (syComponentOrder==1)
267  {
268  lini=k=j+1;
269  wend=Fl;
270  }
271  else
272  {
273  lini=k=0;
274  while ((k<j) && (pGetComp(S[k]) != i)) k++;
275  wend=j;
276  }
277  if (TEST_OPT_PROT)
278  {
279  Print("(%d)",Fl-j);
280  mflush();
281  }
282  syCreatePairs(S,lini,wend,k,j,i,pairs);
283  for (k=lini;k<wend;k++)
284  {
285  if (pairs[k]!=NULL)
286  {
287 /*--------------creating T----------------------------------*/
288  for (l=0;l<smax;l++)
289  {
290  ecartT[l] = ecartS[l];
291  totalT[l] = totalS[l];
292  T[l] = ST[l];
293  }
294  tl = smax;
295  tempcomp = ivCopy(*modcomp);
296 /*--------------begin to reduce-----------------------------*/
297  toRed = ksOldCreateSpoly(S[j],S[k]);
298  ecartToRed = 1;
299  bestEcart = 1;
300  if (TEST_OPT_DEBUG)
301  {
302  PrintS("pair: ");pWrite0(S[j]);PrintS(" ");pWrite(S[k]);
303  }
304  if (TEST_OPT_PROT)
305  {
306  PrintS(".");
307  mflush();
308  }
309 //Print("Reduziere Paar %d,%d (ecart %d): \n",j,k,ecartToRed);
310 //Print("Poly %d: ",j);pWrite(S[j]);
311 //Print("Poly %d: ",k);pWrite(S[k]);
312 //Print("Spoly: ");pWrite(toRed);
313  while (pGetComp(toRed)<=rkF)
314  {
315  if (TEST_OPT_DEBUG)
316  {
317  PrintS("toRed: ");pWrite(toRed);
318  }
319 /*
320 * if ((bestEcart) || (ecartToRed!=0))
321 * {
322 */
323  totalToRed = p_LDeg(toRed,&kk,currRing);
324  ecartToRed = totalToRed-p_FDeg(toRed,currRing);
325 /*
326 * }
327 */
328 //Print("toRed now (neuer ecart %d): ",ecartToRed);pWrite(toRed);
329  notFound = TRUE;
330  bestEcart = 32000; //a very large integer
331  p = NULL;
332  int l=0;
333 #define OLD_SEARCH
334 #ifdef OLD_SEARCH
335  while ((l<tl) && (pGetComp(T[l])<pGetComp(toRed))) l++;
336  //assume (l==(**modcomp)[pGetComp(toRed)]);
337  while ((l<tl) && (notFound))
338 #else
339  l = (**modcomp)[pGetComp(toRed)];
340  int kkk = (**modcomp)[pGetComp(toRed)+1];
341  while ((l<kkk) && (notFound))
342 #endif
343  {
344  if ((ecartT[l]<bestEcart) && (pDivisibleBy(T[l],toRed)))
345  {
346  if (ecartT[l]<=ecartToRed) notFound = FALSE;
347  p = T[l];
348  bestEcart = ecartT[l];
349  }
350  l++;
351  }
352  if (p==NULL)
353  {
354  pDelete(&toRed);
355  for(k=j;k<Fl;k++) pDelete(&(pairs[k]));
356  omFreeSize((ADDRESS)pairs,Fl*sizeof(poly));
357  omFreeSize((ADDRESS)ST,Fl*sizeof(poly));
358  omFreeSize((ADDRESS)S,Fl*sizeof(poly));
359  omFreeSize((ADDRESS)T,tmax*sizeof(poly));
360  omFreeSize((ADDRESS)ecartT,tmax*sizeof(int));
361  omFreeSize((ADDRESS)totalT,tmax*sizeof(int));
362  omFreeSize((ADDRESS)ecartS,Fl*sizeof(int));
363  omFreeSize((ADDRESS)totalS,Fl*sizeof(int));
364  for(k=0;k<IDELEMS(result);k++) pDelete(&((*Shdl)[k]));
365  WerrorS("ideal not a standard basis");//no polynom for reduction
366  return result;
367  }
368  else
369  {
370 //Print("reduced with (ecart %d): ",bestEcart);wrp(p);PrintLn();
371  if (notFound)
372  {
373  if (tl>=tmax)
374  {
375  pEnlargeSet(&T,tmax,16);
376  tmax += 16;
377  temp = (int*)omAlloc((tmax+16)*sizeof(int));
378  for(l=0;l<tmax;l++) temp[l]=totalT[l];
379  totalT = temp;
380  temp = (int*)omAlloc((tmax+16)*sizeof(int));
381  for(l=0;l<tmax;l++) temp[l]=ecartT[l];
382  ecartT = temp;
383  }
384 //PrintS("t");
385  int comptR=pGetComp(toRed);
386  for (l=tempcomp->length()-1;l>comptR;l--)
387  {
388  if ((*tempcomp)[l]>0)
389  (*tempcomp)[l]++;
390  }
391  l=0;
392  while ((l<tl) && (comptR>pGetComp(T[l]))) l++;
393  while ((l<tl) && (totalT[l]<=totalToRed)) l++;
394  for (kk=tl;kk>l;kk--)
395  {
396  T[kk]=T[kk-1];
397  totalT[kk]=totalT[kk-1];
398  ecartT[kk]=ecartT[kk-1];
399  }
400  q = pCopy(toRed);
401  pNorm(q);
402  T[l] = q;
403  totalT[l] = totalToRed;
404  ecartT[l] = ecartToRed;
405  tl++;
406  }
407  toRed = ksOldSpolyRed(p,toRed);
408  }
409  }
410 //Print("toRed finally (neuer ecart %d): ",ecartToRed);pWrite(toRed);
411 //PrintS("s");
412  if (pGetComp(toRed)>rkF)
413  {
414  if (Sl>=IDELEMS(result))
415  {
416  pEnlargeSet(Shdl,IDELEMS(result),16);
417  IDELEMS(result) += 16;
418  }
419  //p_Shift(&toRed,-rkF,currRing);
420  pNorm(toRed);
421  (*Shdl)[Sl] = toRed;
422  Sl++;
423  }
424 /*----------------deleting all polys not from ST--------------*/
425  for(l=0;l<tl;l++)
426  {
427  kk=0;
428  while ((kk<smax) && (T[l] != S[kk])) kk++;
429  if (kk>=smax)
430  {
431  pDelete(&T[l]);
432 //Print ("#");
433  }
434  }
435  delete tempcomp;
436  }
437  }
438  for(k=lini;k<wend;k++) pDelete(&(pairs[k]));
439  }
440  (*newmodcomp)[Fl+1] = Sl;
441  omFreeSize((ADDRESS)pairs,Fl*sizeof(poly));
442  omFreeSize((ADDRESS)ST,Fl*sizeof(poly));
443  omFreeSize((ADDRESS)S,Fl*sizeof(poly));
444  omFreeSize((ADDRESS)T,tmax*sizeof(poly));
445  omFreeSize((ADDRESS)ecartT,tmax*sizeof(int));
446  omFreeSize((ADDRESS)totalT,tmax*sizeof(int));
447  omFreeSize((ADDRESS)ecartS,Fl*sizeof(int));
448  omFreeSize((ADDRESS)totalS,Fl*sizeof(int));
449  delete *modcomp;
450  *modcomp = newmodcomp;
451  return result;
452 }
int length() const
Definition: intvec.h:92
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
intvec * ivCopy(const intvec *o)
Definition: intvec.h:133
static jList * T
Definition: janet.cc:31
#define assume(x)
Definition: mod2.h:390
#define omAlloc(size)
Definition: omAllocDecl.h:210
static long p_FDeg(const poly p, const ring r)
Definition: p_polys.h:380
static long p_LDeg(const poly p, int *l, const ring r)
Definition: p_polys.h:381
#define pSetCompP(a, i)
Definition: polys.h:289
#define pSetmComp(p)
TODO:
Definition: polys.h:259
void rSetSyzComp(int k, const ring r)
Definition: ring.cc:4973

◆ sySpecNormalize()

poly sySpecNormalize ( poly  toNorm,
ideal  mW = NULL 
)

Definition at line 457 of file syz0.cc.

458 {
459  int j,i=0;
460  poly p;
461 
462  if (toNorm==NULL) return NULL;
463  p = pHead(toNorm);
464  if (mW!=NULL)
465  {
466  for(j=1;j<=(currRing->N);j++)
467  pSetExp(p,j,pGetExp(p,j) -pGetExp(mW->m[pGetComp(p)-1],j));
468  }
469  while ((p!=NULL) && (i<IDELEMS(currRing->qideal)))
470  {
471  if (pDivisibleBy(currRing->qideal->m[i],p))
472  {
473  //pNorm(toNorm);
474  toNorm = ksOldSpolyRed(currRing->qideal->m[i],toNorm);
475  pDelete(&p);
476  if (toNorm==NULL) return NULL;
477  p = pHead(toNorm);
478  if (mW!=NULL)
479  {
480  for(j=1;j<=(currRing->N);j++)
481  pSetExp(p,j,pGetExp(p,j) -pGetExp(mW->m[pGetComp(p)-1],j));
482  }
483  i = 0;
484  }
485  else
486  {
487  i++;
488  }
489  }
490  pDelete(&p);
491  return toNorm;
492 }

◆ syTestOrder()

BOOLEAN syTestOrder ( ideal  M)

Definition at line 830 of file syz0.cc.

831 {
833  if (i == 0) return FALSE;
834  int j=0;
835 
836  while ((currRing->order[j]!=ringorder_c) && (currRing->order[j]!=ringorder_C))
837  j++;
838  if (currRing->order[j+1]!=0)
839  return TRUE;
840  return FALSE;
841 }
@ ringorder_C
Definition: ring.h:80
@ ringorder_c
Definition: ring.h:79
#define M
Definition: sirandom.c:24