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  {
98  int sl=strat->sl;
99  strat->P.GetP();
100  poly p=redNF(strat->P.p,sl,TRUE,strat);
101  if (p==NULL) red_result=0;
102  #ifdef KDEBUG
103  else
104  {
105  if (TEST_OPT_DEBUG)
106  {
107  printf("p: ");p_wrp(p,currRing, currRing); printf("\n");
108  }
109  }
110  #endif
111  }
112  if (red_result!=0)
113  {
114  if (TEST_OPT_PROT) printf("fail: %d, result: %d\n",i,red_result);
115  all_okay=FALSE;
116  }
117  }
118  return all_okay;
119 }
120 
121 BOOLEAN kVerify2(ideal F, ideal Q)
122 {
123 #ifdef HAVE_VSPACE
125  kStrategy strat=new skStrategy;
126  strat->ak = id_RankFreeModule(F,currRing);
127  strat->kModW=kModW=NULL;
128  strat->kHomW=kHomW=NULL;
129  initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
130  initBuchMoraPos(strat);
131  initBba(strat);
132  initBuchMora(F, Q,strat);
133  /*initBuchMora:*/
134  strat->tail = pInit();
135  /*- set s -*/
136  strat->sl = -1;
137  /*- set L -*/
138  strat->Lmax = ((IDELEMS(F)+setmaxLinc-1)/setmaxLinc)*setmaxLinc;
139  strat->Ll = -1;
140  strat->L = initL(strat->Lmax);
141  /*- set B -*/
142  strat->Bmax = setmaxL;
143  strat->Bl = -1;
144  strat->B = initL();
145  /*- set T -*/
146  strat->tl = -1;
147  strat->tmax = setmaxT;
148  strat->T = initT();
149  strat->R = initR();
150  strat->sevT = initsevT();
151  /*- init local data struct.---------------------------------------- -*/
152  strat->P.ecart=0;
153  strat->P.length=0;
154  strat->P.pLength=0;
155  initS(F, Q,strat); /*sets also S, ecartS, fromQ */
156  strat->fromT = FALSE;
157  strat->noTailReduction = FALSE;
158  /*----------------------------------------------------------------------*/
159  /* build pairs */
160  if (strat->fromQ!=NULL)
161  {
162  for(int i=1; i<=strat->sl;i++)
163  {
164  initenterpairs(strat->S[i],i-1,0,strat->fromQ[i],strat);
165  }
166  }
167  else
168  {
169  for(int i=1; i<=strat->sl;i++)
170  {
171  initenterpairs(strat->S[i],i-1,0,FALSE,strat);
172  }
173  }
174  if (TEST_OPT_PROT) printf("%d pairs created\n",strat->Ll+1);
175  if (TEST_OPT_DEBUG) messageSets(strat);
176  /*---------------------------------------------------------------------*/
177  BOOLEAN all_okay=TRUE;
178  int cpus=(int)(long)feOptValue(FE_OPT_CPUS);
179  int parent_pid=getpid();
180  using namespace vspace;
181  vmem_init();
182  // Create a queue of int
183  VRef<Queue<int> > queue = vnew<Queue<int> >();
184  VRef<Queue<int> > rqueue = vnew<Queue<int> >();
185  for(int i=strat->Ll;i>=0; i--)
186  {
187  queue->enqueue(i); // the tasks: process pair L[i]
188  }
189  for(int i=cpus;i>=0;i--)
190  {
191  queue->enqueue(-1); // stop sign, one for each child
192  }
193  int pid;
194  for (int i=0;i<cpus;i++)
195  {
196  pid = fork_process();
197  if (pid==0) break; //child
198  }
199  if (parent_pid!=getpid()) // child ------------------------------------------
200  {
201  loop
202  {
203  int ind=queue->dequeue();
204  if (ind== -1)
205  {
206  if (TEST_OPT_PROT) printf("child: end of queue\n");
207  rqueue->enqueue(0);
208  exit(0);
209  }
210  int red_result=1;
211  /* picks the element from the lazyset L */
212  LObject P;
213  P = strat->L[ind];
214  if (TEST_OPT_PROT) { printf("."); mflush();}
215  if (pNext(P.p) == strat->tail)
216  {
217  // deletes the short spoly
218  pLmFree(P.p);
219  P.p = NULL;
220  poly m1 = NULL, m2 = NULL;
221  /* spoly */
222  kCheckSpolyCreation(&P, strat, m1, m2);
223  ksCreateSpoly(&P, NULL, strat->use_buckets,
224  strat->tailRing, m1, m2, strat->R);
225  }
226  if ((P.p == NULL) && (P.t_p == NULL))
227  {
228  red_result = 0;
229  }
230  else
231  {
232  /* reduction */
233  int sl=strat->sl;
234  P.GetP();
235  poly p=redNF(P.p,sl,TRUE,strat);
236  if (p==NULL) red_result=0;
237  #ifdef KDEBUG
238  else
239  {
240  if (TEST_OPT_DEBUG)
241  {
242  printf("p: ");p_wrp(p,currRing, currRing); printf("\n");
243  }
244  }
245  #endif
246  }
247  if (red_result!=0)
248  {
249  if (TEST_OPT_PROT) printf("fail: result: %d\n",red_result);
250  rqueue->enqueue(1);
251  exit(0); // found fail, no neeed to test further
252  }
253  }
254  exit(0); // all done, quit child
255  }
256  else // parent ---------------------------------------------------
257  {
258  if (TEST_OPT_PROT) printf("childs created\n");
259  // wait for all process to stop:
260  // each process sends an 0 at end or a 1 for failure
261  int res;
262  int remaining_childs=cpus;
263  while(remaining_childs>0)
264  {
265  res=rqueue->dequeue();
266  if (res==0) // a child finished
267  {
268  if (TEST_OPT_PROT) printf("a child finished\n");
269  //waitpid(-1,NULL,0); // ? see sig_chld_hdl
270  remaining_childs--;
271  }
272  else if (res==1) // not a GB - clean up and return 0
273  {
274  if (TEST_OPT_PROT) printf("a child finished res=1\n");
275  remaining_childs--;
276  all_okay=FALSE;
277  // clean queue:
278  int dummy;
279  do
280  {
281  dummy=queue->dequeue();
282  } while (dummy==0);
283  }
284  }
285  // removes queues
286  queue.free();
287  rqueue.free();
288  vmem_deinit();
289  return all_okay;
290  }
291 #else
292  return kVerify1(F,Q);
293 #endif
294 }
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:4080
intvec * kModW
Definition: kutil.h:334
ring tailRing
Definition: kutil.h:342
char noTailReduction
Definition: kutil.h:378
int Ll
Definition: kutil.h:350
TSet T
Definition: kutil.h:323
int Bl
Definition: kutil.h:351
polyset S
Definition: kutil.h:303
LSet B
Definition: kutil.h:325
int ak
Definition: kutil.h:352
TObject ** R
Definition: kutil.h:339
int tl
Definition: kutil.h:349
unsigned long * sevT
Definition: kutil.h:322
intvec * kHomW
Definition: kutil.h:335
poly tail
Definition: kutil.h:333
int tmax
Definition: kutil.h:349
intset fromQ
Definition: kutil.h:318
char use_buckets
Definition: kutil.h:383
char fromT
Definition: kutil.h:379
LObject P
Definition: kutil.h:299
int Lmax
Definition: kutil.h:350
LSet L
Definition: kutil.h:324
int sl
Definition: kutil.h:347
int Bmax
Definition: kutil.h:351
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:1167
void initBba(kStrategy strat)
Definition: kstd1.cc:1659
VAR intvec * kHomW
Definition: kstd1.cc:2394
VAR intvec * kModW
Definition: kstd1.cc:2394
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition: kstd2.cc:2071
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:10322
void initBuchMoraPos(kStrategy strat)
Definition: kutil.cc:10149
void initenterpairs(poly h, int k, int ecart, int isFromQ, kStrategy strat, int atR)
Definition: kutil.cc:3840
void initS(ideal F, ideal Q, kStrategy strat)
Definition: kutil.cc:8156
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition: kutil.cc:11045
void initBuchMoraCrit(kStrategy strat)
Definition: kutil.cc:9997
void messageSets(kStrategy strat)
Definition: kutil.cc:8106
#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:54
BOOLEAN kVerify2(ideal F, ideal Q)
Definition: kverify.cc:121
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_PROT
Definition: options.h:102
#define TEST_OPT_DEBUG
Definition: options.h:107
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:80
void free()
Definition: vspace.h:470