My Project
Loading...
Searching...
No Matches
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"
6#include "kernel/ideals.h"
7#include "kernel/polys.h"
11#include "Singular/feOpt.h"
12#include <stdlib.h>
13#include <string.h>
14
15#ifdef HAVE_VSPACE
17#include <sys/types.h>
18#include <sys/wait.h>
19#include <unistd.h>
20#endif
21
22BOOLEAN kVerify1(ideal F, ideal Q)
23/* sequential version */
24{
26 kStrategy strat=new skStrategy;
27 strat->ak = id_RankFreeModule(F,currRing);
28 strat->kModW=kModW=NULL;
29 strat->kHomW=kHomW=NULL;
30 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
31 initBuchMoraPos(strat);
32 initBba(strat);
33 initBuchMora(F, Q,strat);
34 /*initBuchMora:*/
35 strat->tail = pInit();
36 /*- set s -*/
37 strat->sl = -1;
38 /*- set L -*/
40 strat->Ll = -1;
41 strat->L = initL(strat->Lmax);
42 /*- set B -*/
43 strat->Bmax = setmaxL;
44 strat->Bl = -1;
45 strat->B = initL();
46 /*- set T -*/
47 strat->tl = -1;
48 strat->tmax = setmaxT;
49 strat->T = initT();
50 strat->R = initR();
51 strat->sevT = initsevT();
52 /*- init local data struct.---------------------------------------- -*/
53 strat->P.ecart=0;
54 strat->P.length=0;
55 strat->P.pLength=0;
56 initS(F, Q,strat); /*sets also S, ecartS, fromQ */
57 strat->fromT = FALSE;
58 strat->noTailReduction = FALSE;
59 /*----------------------------------------------------------------------*/
60 /* build pairs */
61 if (strat->fromQ!=NULL)
62 {
63 for(int i=1; i<=strat->sl;i++)
64 {
65 initenterpairs(strat->S[i],i-1,0,strat->fromQ[i],strat);
66 }
67 }
68 else
69 {
70 for(int i=1; i<=strat->sl;i++)
71 {
72 initenterpairs(strat->S[i],i-1,0,FALSE,strat);
73 }
74 }
75 if (TEST_OPT_PROT) printf("%d pairs created\n",strat->Ll+1);
76 if (TEST_OPT_DEBUG) messageSets(strat);
77 /*---------------------------------------------------------------------*/
78 BOOLEAN all_okay=TRUE;
79 for(int i=strat->Ll;i>=0; i--)
80 {
81 /* spolys */
82 int red_result=1;
83 /* picks the last element from the lazyset L */
84 strat->P = strat->L[i];
85 if (pNext(strat->P.p) == strat->tail)
86 {
87 // deletes the short spoly
88 pLmFree(strat->P.p);
89 strat->P.p = NULL;
90 poly m1 = NULL, m2 = NULL;
91 kCheckSpolyCreation(&(strat->P), strat, m1, m2);
92 ksCreateSpoly(&(strat->P), NULL, strat->use_buckets,
93 strat->tailRing, m1, m2, strat->R);
94 }
95 if ((strat->P.p == NULL) && (strat->P.t_p == NULL))
96 {
97 red_result = 0;
98 }
99 else
100 {
102 && (currRing->pFDeg(strat->P.p,currRing)>Kstd1_deg))
103 {
104 /*
105 * omit pair
106 * if 24 IN test and the degree of P is bigger then
107 *a predefined number Kstd1_deg
108 */
109 strat->P.Delete();
110 red_result=0;
111 if (TEST_OPT_PROT) { printf("D"); mflush(); }
112 }
113 else
114 {
115 int sl=strat->sl;
116 strat->P.GetP();
117 poly p=redNF(strat->P.p,sl,TRUE,strat);
118 if (p==NULL) red_result=0;
119 #ifdef KDEBUG
120 else
121 {
122 if (TEST_OPT_DEBUG)
123 {
124 printf("p: ");p_wrp(p,currRing, currRing); printf("\n");
125 }
126 }
127 #endif
128 }
129 }
130 if (red_result!=0)
131 {
132 if (TEST_OPT_PROT) printf("fail: %d, result: %d\n",i,red_result);
133 all_okay=FALSE;
134 }
135 }
136 return all_okay;
137}
138
139BOOLEAN kVerify2(ideal F, ideal Q)
140/* parallel version */
141{
142#ifdef HAVE_VSPACE
144 kStrategy strat=new skStrategy;
145 strat->ak = id_RankFreeModule(F,currRing);
146 strat->kModW=kModW=NULL;
147 strat->kHomW=kHomW=NULL;
148 initBuchMoraCrit(strat); /*set Gebauer, honey, sugarCrit*/
149 initBuchMoraPos(strat);
150 initBba(strat);
151 initBuchMora(F, Q,strat);
152 /*initBuchMora:*/
153 strat->tail = pInit();
154 /*- set s -*/
155 strat->sl = -1;
156 /*- set L -*/
157 strat->Lmax = ((IDELEMS(F)+setmaxLinc-1)/setmaxLinc)*setmaxLinc;
158 strat->Ll = -1;
159 strat->L = initL(strat->Lmax);
160 /*- set B -*/
161 strat->Bmax = setmaxL;
162 strat->Bl = -1;
163 strat->B = initL();
164 /*- set T -*/
165 strat->tl = -1;
166 strat->tmax = setmaxT;
167 strat->T = initT();
168 strat->R = initR();
169 strat->sevT = initsevT();
170 /*- init local data struct.---------------------------------------- -*/
171 strat->P.ecart=0;
172 strat->P.length=0;
173 strat->P.pLength=0;
174 initS(F, Q,strat); /*sets also S, ecartS, fromQ */
175 strat->fromT = FALSE;
176 strat->noTailReduction = FALSE;
177 /*----------------------------------------------------------------------*/
178 /* build pairs */
179 if (strat->fromQ!=NULL)
180 {
181 for(int i=1; i<=strat->sl;i++)
182 {
183 initenterpairs(strat->S[i],i-1,0,strat->fromQ[i],strat);
184 }
185 }
186 else
187 {
188 for(int i=1; i<=strat->sl;i++)
189 {
190 initenterpairs(strat->S[i],i-1,0,FALSE,strat);
191 }
192 }
193 if (TEST_OPT_PROT) printf("%d pairs created\n",strat->Ll+1);
195 {
196 for(int i=strat->Ll; i>=0; i--)
197 {
198 if (currRing->pFDeg(strat->L[i].p,currRing)>Kstd1_deg)
199 {
200 /*
201 * omit pairs if 24 IN test and the degree of L[i] is bigger then
202 *a predefined number Kstd1_deg
203 */
204 deleteInL(strat->L,&strat->Ll,i,strat);
205 if (TEST_OPT_PROT) { printf("D"); mflush(); }
206 }
207 }
208 }
209 if (TEST_OPT_DEBUG) messageSets(strat);
210 /*---------------------------------------------------------------------*/
211 BOOLEAN all_okay=TRUE;
212 int cpus=(int)(long)feOptValue(FE_OPT_CPUS);
215 /* start no more than MAX_PROCESS-1 children */
216 int parent_pid=getpid();
217 using namespace vspace;
218 vmem_init();
219 // Create a queue of int
220 VRef<Queue<int> > queue = vnew<Queue<int> >();
221 VRef<Queue<int> > rqueue = vnew<Queue<int> >();
222 for(int i=strat->Ll;i>=0; i--)
223 {
224 queue->enqueue(i); // the tasks: process pair L[i]
225 }
226 for(int i=cpus;i>=0;i--)
227 {
228 queue->enqueue(-1); // stop sign, one for each child
229 }
230 int pid;
231 for (int i=0;i<cpus;i++)
232 {
233 pid = fork_process();
234 if (pid==0) break; //child
235 }
236 if (parent_pid!=getpid()) // child ------------------------------------------
237 {
238 loop
239 {
240 int ind=queue->dequeue();
241 if (ind== -1)
242 {
243 if (TEST_OPT_PROT) printf("child: end of queue\n");
244 rqueue->enqueue(0);
245 exit(0);
246 }
247 int red_result=1;
248 /* picks the element from the lazyset L */
249 LObject P;
250 P = strat->L[ind];
251 if (TEST_OPT_PROT) { printf("."); mflush();}
252 if (pNext(P.p) == strat->tail)
253 {
254 // deletes the short spoly
255 pLmFree(P.p);
256 P.p = NULL;
257 poly m1 = NULL, m2 = NULL;
258 /* spoly */
259 kCheckSpolyCreation(&P, strat, m1, m2);
260 ksCreateSpoly(&P, NULL, strat->use_buckets,
261 strat->tailRing, m1, m2, strat->R);
262 }
263 if ((P.p == NULL) && (P.t_p == NULL))
264 {
265 red_result = 0;
266 }
267 else
268 {
269 /* reduction */
270 int sl=strat->sl;
271 P.GetP();
272 poly p=redNF(P.p,sl,TRUE,strat);
273 if (p==NULL) red_result=0;
274 #ifdef KDEBUG
275 else
276 {
277 if (TEST_OPT_DEBUG)
278 {
279 printf("p: ");p_wrp(p,currRing, currRing); printf("\n");
280 }
281 }
282 #endif
283 }
284 if (red_result!=0)
285 {
286 if (TEST_OPT_PROT) printf("fail: result: %d\n",red_result);
287 rqueue->enqueue(1);
288 exit(0); // found fail, no need to test further
289 }
290 }
291 exit(0); // all done, quit child
292 }
293 else // parent ---------------------------------------------------
294 {
295 if (TEST_OPT_PROT) printf("%d children created\n",cpus);
296 // wait for all process to stop:
297 // each process sends an 0 at end or a 1 for failure
298 int res;
299 int remaining_children=cpus;
300 while(remaining_children>0)
301 {
302 res=rqueue->dequeue();
303 if (res==0) // a child finished
304 {
305 if (TEST_OPT_PROT) { printf("c");mflush(); }
306 si_waitpid(-1,NULL,0); // ? see sig_chld_hdl
307 remaining_children--;
308 }
309 else if (res==1) // not a GB - clean up and return 0
310 {
311 if (TEST_OPT_PROT) { printf("C"); mflush(); }
312 remaining_children--;
313 all_okay=FALSE;
314 // clean queue:
315 int dummy;
316 do
317 {
318 dummy=queue->dequeue(); // remove remaining tasks
319 } while (dummy==0);
320 }
321 }
322 sleep(1); // let all the children finish
323 // removes queues
324 queue.free();
325 rqueue.free();
326 vmem_deinit();
327 return all_okay;
328 }
329#else
330 return kVerify1(F,Q);
331#endif
332}
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:4086
intvec * kModW
Definition kutil.h:335
ring tailRing
Definition kutil.h:343
char noTailReduction
Definition kutil.h:376
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:381
char fromT
Definition kutil.h:377
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
KINLINE TSet initT()
Definition kInline.h:84
KINLINE TObject ** initR()
Definition kInline.h:95
KINLINE unsigned long * initsevT()
Definition kInline.h:100
void ksCreateSpoly(LObject *Pair, poly spNoether, int use_buckets, ring tailRing, poly m1, poly m2, TObject **R)
Definition kspoly.cc:1203
void initBba(kStrategy strat)
Definition kstd1.cc:1682
VAR intvec * kHomW
Definition kstd1.cc:2407
VAR intvec * kModW
Definition kstd1.cc:2407
EXTERN_VAR int Kstd1_deg
Definition kstd1.h:52
poly redNF(poly h, int &max_ind, int nonorm, kStrategy strat)
Definition kstd2.cc:2315
void initBuchMora(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:9745
void initBuchMoraPos(kStrategy strat)
Definition kutil.cc:9574
void initenterpairs(poly h, int k, int ecart, int isFromQ, kStrategy strat, int atR)
Definition kutil.cc:3814
void initS(ideal F, ideal Q, kStrategy strat)
Definition kutil.cc:7588
BOOLEAN kCheckSpolyCreation(LObject *L, kStrategy strat, poly &m1, poly &m2)
Definition kutil.cc:10479
void deleteInL(LSet set, int *length, int j, kStrategy strat)
Definition kutil.cc:1213
void initBuchMoraCrit(kStrategy strat)
Definition kutil.cc:9429
void messageSets(kStrategy strat)
Definition kutil.cc:7538
#define setmaxL
Definition kutil.h:30
static LSet initL(int nr=setmaxL)
Definition kutil.h:418
#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:139
BOOLEAN kVerify1(ideal F, ideal Q)
Definition kverify.cc:22
#define assume(x)
Definition mod2.h:387
#define pNext(p)
Definition monomials.h:36
static const int MAX_PROCESS
Definition vspace.h:1419
#define NULL
Definition omList.c:12
#define TEST_OPT_DEGBOUND
Definition options.h:115
#define TEST_OPT_PROT
Definition options.h:105
#define TEST_OPT_DEBUG
Definition options.h:110
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
Compatibility 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:426
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
#define IDELEMS(i)
#define Q
Definition sirandom.c:26
#define loop
Definition structs.h:75
void free()
Definition vspace.h:1805