My Project
kverify.cc
Go to the documentation of this file.
1 #include "kernel/mod2.h"
2 
3 #include "misc/mylimits.h"
4 #include "misc/options.h"
5 #include "kernel/ideals.h"
6 #include "kernel/polys.h"
7 #include "polys/monomials/ring.h"
10 #include "Singular/feOpt.h"
11 #include <stdlib.h>
12 #include <string.h>
13 
14 #ifdef HAVE_VSPACE
16 #include <sys/types.h>
17 #include <sys/wait.h>
18 #endif
19 
20 BOOLEAN kVerify1(ideal F, ideal Q)
21 {
23  kStrategy strat=new skStrategy;
24  strat->ak = id_RankFreeModule(F,currRing);
25  strat->kModW=kModW=NULL;
26  strat->kHomW=kHomW=NULL;
27  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
28  initBuchMoraPos(strat);
29  initBba(strat);
30  initBuchMora(F, Q,strat);
31  /*initBuchMora:*/
32  strat->tail = pInit();
33  /*- set s -*/
34  strat->sl = -1;
35  /*- set L -*/
36  strat->Lmax = ((IDELEMS(F)+setmaxLinc-1)/setmaxLinc)*setmaxLinc;
37  strat->Ll = -1;
38  strat->L = initL(strat->Lmax);
39  /*- set B -*/
40  strat->Bmax = setmaxL;
41  strat->Bl = -1;
42  strat->B = initL();
43  /*- set T -*/
44  strat->tl = -1;
45  strat->tmax = setmaxT;
46  strat->T = initT();
47  strat->R = initR();
48  strat->sevT = initsevT();
49  /*- init local data struct.---------------------------------------- -*/
50  strat->P.ecart=0;
51  strat->P.length=0;
52  strat->P.pLength=0;
53  initS(F, Q,strat); /*sets also S, ecartS, fromQ */
54  strat->fromT = FALSE;
55  strat->noTailReduction = FALSE;
56  /*----------------------------------------------------------------------*/
57  /* build pairs */
58  if (strat->fromQ!=NULL)
59  {
60  for(int i=1; i<=strat->sl;i++)
61  {
62  initenterpairs(strat->S[i],i-1,0,strat->fromQ[i],strat);
63  }
64  }
65  else
66  {
67  for(int i=1; i<=strat->sl;i++)
68  {
69  initenterpairs(strat->S[i],i-1,0,FALSE,strat);
70  }
71  }
72  if (TEST_OPT_PROT) printf("%d pairs created\n",strat->Ll+1);
73  if (TEST_OPT_DEBUG) messageSets(strat);
74  /*---------------------------------------------------------------------*/
75  BOOLEAN all_okay=TRUE;
76  for(int i=strat->Ll;i>=0; i--)
77  {
78  /* spolys */
79  int red_result=1;
80  /* picks the last element from the lazyset L */
81  strat->P = strat->L[i];
82  if (pNext(strat->P.p) == strat->tail)
83  {
84  // deletes the short spoly
85  pLmFree(strat->P.p);
86  strat->P.p = NULL;
87  poly m1 = NULL, m2 = NULL;
88  kCheckSpolyCreation(&(strat->P), strat, m1, m2);
89  ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
90  strat->tailRing, m1, m2, strat->R);
91  }
92  if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
93  {
94  red_result = 0;
95  }
96  else
97  {
99  && (currRing->pFDeg(strat->P.p,currRing)>Kstd1_deg))
100  {
101  /*
102  * omit pair
103  * if 24 IN test and the degree of P is bigger then
104  *a predefined number Kstd1_deg
105  */
106  strat->P.Delete();
107  red_result=0;
108  if (TEST_OPT_PROT) { printf("D"); mflush(); }
109  }
110  else
111  {
112  int sl=strat->sl;
113  strat->P.GetP();
114  poly p=redNF(strat->P.p,sl,TRUE,strat);
115  if (p==NULL) red_result=0;
116  #ifdef KDEBUG
117  else
118  {
119  if (TEST_OPT_DEBUG)
120  {
121  printf("p: ");p_wrp(p,currRing, currRing); printf("\n");
122  }
123  }
124  #endif
125  }
126  }
127  if (red_result!=0)
128  {
129  if (TEST_OPT_PROT) printf("fail: %d, result: %d\n",i,red_result);
130  all_okay=FALSE;
131  }
132  }
133  return all_okay;
134 }
135 
136 BOOLEAN kVerify2(ideal F, ideal Q)
137 {
138 #ifdef HAVE_VSPACE
140  kStrategy strat=new skStrategy;
141  strat->ak = id_RankFreeModule(F,currRing);
142  strat->kModW=kModW=NULL;
143  strat->kHomW=kHomW=NULL;
144  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
145  initBuchMoraPos(strat);
146  initBba(strat);
147  initBuchMora(F, Q,strat);
148  /*initBuchMora:*/
149  strat->tail = pInit();
150  /*- set s -*/
151  strat->sl = -1;
152  /*- set L -*/
153  strat->Lmax = ((IDELEMS(F)+setmaxLinc-1)/setmaxLinc)*setmaxLinc;
154  strat->Ll = -1;
155  strat->L = initL(strat->Lmax);
156  /*- set B -*/
157  strat->Bmax = setmaxL;
158  strat->Bl = -1;
159  strat->B = initL();
160  /*- set T -*/
161  strat->tl = -1;
162  strat->tmax = setmaxT;
163  strat->T = initT();
164  strat->R = initR();
165  strat->sevT = initsevT();
166  /*- init local data struct.---------------------------------------- -*/
167  strat->P.ecart=0;
168  strat->P.length=0;
169  strat->P.pLength=0;
170  initS(F, Q,strat); /*sets also S, ecartS, fromQ */
171  strat->fromT = FALSE;
172  strat->noTailReduction = FALSE;
173  /*----------------------------------------------------------------------*/
174  /* build pairs */
175  if (strat->fromQ!=NULL)
176  {
177  for(int i=1; i<=strat->sl;i++)
178  {
179  initenterpairs(strat->S[i],i-1,0,strat->fromQ[i],strat);
180  }
181  }
182  else
183  {
184  for(int i=1; i<=strat->sl;i++)
185  {
186  initenterpairs(strat->S[i],i-1,0,FALSE,strat);
187  }
188  }
189  if (TEST_OPT_PROT) printf("%d pairs created\n",strat->Ll+1);
190  if (TEST_OPT_DEGBOUND)
191  {
192  for(int i=strat->Ll; i>=0; i--)
193  {
194  if (currRing->pFDeg(strat->L[i].p,currRing)>Kstd1_deg)
195  {
196  /*
197  * omit pairs if 24 IN test and the degree of L[i] is bigger then
198  *a predefined number Kstd1_deg
199  */
200  deleteInL(strat->L,&strat->Ll,i,strat);
201  if (TEST_OPT_PROT) { printf("D"); mflush(); }
202  }
203  }
204  }
205  if (TEST_OPT_DEBUG) messageSets(strat);
206  /*---------------------------------------------------------------------*/
207  BOOLEAN all_okay=TRUE;
208  int cpus=(int)(long)feOptValue(FE_OPT_CPUS);
209  int parent_pid=getpid();
210  using namespace vspace;
211  vmem_init();
212  // Create a queue of int
213  VRef<Queue<int> > queue = vnew<Queue<int> >();
214  VRef<Queue<int> > rqueue = vnew<Queue<int> >();
215  for(int i=strat->Ll;i>=0; i--)
216  {
217  queue->enqueue(i); // the tasks: process pair L[i]
218  }
219  for(int i=cpus;i>=0;i--)
220  {
221  queue->enqueue(-1); // stop sign, one for each child
222  }
223  int pid;
224  for (int i=0;i<cpus;i++)
225  {
226  pid = fork_process();
227  if (pid==0) break; //child
228  }
229  if (parent_pid!=getpid()) // child ------------------------------------------
230  {
231  loop
232  {
233  int ind=queue->dequeue();
234  if (ind== -1)
235  {
236  if (TEST_OPT_PROT) printf("child: end of queue\n");
237  rqueue->enqueue(0);
238  exit(0);
239  }
240  int red_result=1;
241  /* picks the element from the lazyset L */
242  LObject P;
243  P = strat->L[ind];
244  if (TEST_OPT_PROT) { printf("."); mflush();}
245  if (pNext(P.p) == strat->tail)
246  {
247  // deletes the short spoly
248  pLmFree(P.p);
249  P.p = NULL;
250  poly m1 = NULL, m2 = NULL;
251  /* spoly */
252  kCheckSpolyCreation(&P, strat, m1, m2);
253  ksCreateSpoly(&P, NULL, strat->use_buckets,
254  strat->tailRing, m1, m2, strat->R);
255  }
256  if ((P.p == NULL) && (P.t_p == NULL))
257  {
258  red_result = 0;
259  }
260  else
261  {
262  /* reduction */
263  int sl=strat->sl;
264  P.GetP();
265  poly p=redNF(P.p,sl,TRUE,strat);
266  if (p==NULL) red_result=0;
267  #ifdef KDEBUG
268  else
269  {
270  if (TEST_OPT_DEBUG)
271  {
272  printf("p: ");p_wrp(p,currRing, currRing); printf("\n");
273  }
274  }
275  #endif
276  }
277  if (red_result!=0)
278  {
279  if (TEST_OPT_PROT) printf("fail: result: %d\n",red_result);
280  rqueue->enqueue(1);
281  exit(0); // found fail, no neeed to test further
282  }
283  }
284  exit(0); // all done, quit child
285  }
286  else // parent ---------------------------------------------------
287  {
288  if (TEST_OPT_PROT) printf("%d children created\n",cpus);
289  // wait for all process to stop:
290  // each process sends an 0 at end or a 1 for failure
291  int res;
292  int remaining_children=cpus;
293  while(remaining_children>0)
294  {
295  res=rqueue->dequeue();
296  if (res==0) // a child finished
297  {
298  if (TEST_OPT_PROT) { printf("c");mflush(); }
299  //waitpid(-1,NULL,0); // ? see sig_chld_hdl
300  remaining_children--;
301  }
302  else if (res==1) // not a GB - clean up and return 0
303  {
304  if (TEST_OPT_PROT) { printf("C"); mflush(); }
305  remaining_children--;
306  all_okay=FALSE;
307  // clean queue:
308  int dummy;
309  do
310  {
311  dummy=queue->dequeue();
312  } while (dummy==0);
313  }
314  }
315  // removes queues
316  queue.free();
317  rqueue.free();
318  vmem_deinit();
319  return all_okay;
320  }
321 #else
322  return kVerify1(F,Q);
323 #endif
324 }
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
int i
Definition: cfEzgcd.cc:132
int p
Definition: cfModGcd.cc:4078
intvec * kModW
Definition: kutil.h:335
ring tailRing
Definition: kutil.h:343
char noTailReduction
Definition: kutil.h:378
int Ll
Definition: kutil.h:351
TSet T
Definition: kutil.h:326
int Bl
Definition: kutil.h:352
polyset S
Definition: kutil.h:306
LSet B
Definition: kutil.h:328
int ak
Definition: kutil.h:353
TObject ** R
Definition: kutil.h:340
int tl
Definition: kutil.h:350
unsigned long * sevT
Definition: kutil.h:325
intvec * kHomW
Definition: kutil.h:336
poly tail
Definition: kutil.h:334
int tmax
Definition: kutil.h:350
intset fromQ
Definition: kutil.h:321
char use_buckets
Definition: kutil.h:383
char fromT
Definition: kutil.h:379
LObject P
Definition: kutil.h:302
int Lmax
Definition: kutil.h:351
LSet L
Definition: kutil.h:327
int sl
Definition: kutil.h:348
int Bmax
Definition: kutil.h:352
CanonicalForm res
Definition: facAbsFact.cc:60
static void * feOptValue(feOptIndex opt)
Definition: feOpt.h:40
STATIC_VAR jList * Q
Definition: janet.cc:30
KINLINE unsigned long * initsevT()
Definition: kInline.h:100
KINLINE TSet initT()
Definition: kInline.h:84
KINLINE TObject ** initR()
Definition: kInline.h:95
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition: kspoly.cc:1185
void initBba(kStrategy strat)
Definition: kstd1.cc:1676
VAR intvec * kHomW
Definition: kstd1.cc:2408
VAR intvec * kModW
Definition: kstd1.cc:2408
EXTERN_VAR int Kstd1_deg
Definition: kstd1.h:49
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition: kstd2.cc:2131
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10019
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:9846
void initenterpairs(poly h, int k, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.cc:3864
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:7853
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:10753
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition: kutil.cc:1270
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9694
void messageSets(kStrategy strat)
Definition: kutil.cc:7803
#define setmaxL
Definition: kutil.h:30
static LSet initL(int nr=setmaxL)
Definition: kutil.h:421
#define setmaxT
Definition: kutil.h:33
#define setmaxLinc
Definition: kutil.h:31
class sLObject LObject
Definition: kutil.h:58
BOOLEAN kVerify2(ideal F, ideal Q)
Definition: kverify.cc:136
BOOLEAN kVerify1(ideal F, ideal Q)
Definition: kverify.cc:20
#define assume(x)
Definition: mod2.h:387
#define pNext(p)
Definition: monomials.h:36
Definition: vspace.cc:9
pid_t fork_process()
Definition: vspace.cc:419
static void vmem_deinit()
Definition: vspace.h:407
static Status vmem_init()
Definition: vspace.h:403
#define NULL
Definition: omList.c:12
#define TEST_OPT_DEGBOUND
Definition: options.h:113
#define TEST_OPT_PROT
Definition: options.h:103
#define TEST_OPT_DEBUG
Definition: options.h:108
void p_wrp(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:373
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
Compatiblity layer for legacy polynomial operations (over currRing)
static void pLmFree(poly p)
frees the space of the monomial m, assumes m != NULL coef is not freed, m is not advanced
Definition: polys.h:70
#define pInit()
allocates a new monomial and initializes everything to 0
Definition: polys.h:61
#define mflush()
Definition: reporter.h:58
static BOOLEAN rIsNCRing(const ring r)
Definition: ring.h:421
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
#define loop
Definition: structs.h:79
void free()
Definition: vspace.h:470