1 | /////////////////////////////////////////////////////////////////// |
---|
2 | version="$Id$"; |
---|
3 | category="Miscellaneous"; |
---|
4 | |
---|
5 | // summary description of the library |
---|
6 | |
---|
7 | info=" |
---|
8 | LIBRARY: polybori.lib A Singular Library Interface for PolyBoRi |
---|
9 | AUTHORS: Maximilian Kammermeier: Max0791@gmx.de |
---|
10 | Susanne Scherer: sscherer90@yahoo.de |
---|
11 | |
---|
12 | SEE ALSO: Libraries, pyobject, User defined types |
---|
13 | |
---|
14 | |
---|
15 | @* |
---|
16 | |
---|
17 | OVERVIEW: A library for using @code{PolyBoRi} in the SINGULAR interface, with |
---|
18 | procedures that convert structures (polynomials, rings, ideals) in both |
---|
19 | directions. Therefore, it is possible to compute boolean groebner basis |
---|
20 | via @ref{boolean_std}. Polynomials can be converted to zero-supressed decision |
---|
21 | diagrams (zdd) and vice versa. |
---|
22 | |
---|
23 | For usability it defines the @code{PolyBoRi} types @code{bideal}, @code{bpoly}, |
---|
24 | and @code{bring} which are equivalent to Singular's @code{ideal}, @code{poly}, |
---|
25 | and @code{ring}, as well as @code{bset} which corresponds to the type @code{zdd} |
---|
26 | introduced here. In addition @code{bvar(i)} constructs the Boolean variable corresponding |
---|
27 | to @code{var(i)} from current @code{ring}; |
---|
28 | |
---|
29 | For convenience, the corresponding types can be converted explictely or implicitely |
---|
30 | while assigning. |
---|
31 | Also several SINGULAR operators were overloaded: @code{bring} comes with @code{nvars}, |
---|
32 | @code{bpoly} implements @code{lead}, @code{leadmonom} and @code{leadcoef}. |
---|
33 | Objects of this type may be added and multiplied, too. |
---|
34 | Finally, @code{bideal} yields @code{std} and @code{size} as well as addition and element access. |
---|
35 | |
---|
36 | |
---|
37 | Hence, by using these types @code{PolyBoRi} functionality |
---|
38 | can be carried out seamlessly in SINGULAR: |
---|
39 | |
---|
40 | @code{> LIB \"polybori.lib\";} @* |
---|
41 | @code{> ring r0=2,x(1..4),lp;} @* |
---|
42 | @code{> def x=bvar; // enforce Boolean variables} @* |
---|
43 | |
---|
44 | @code{> bpoly f1=x(1)+x(4);} @* |
---|
45 | @code{> bpoly f2=x(1)+x(3)*x(1);} @* |
---|
46 | @code{> bideal bI=list(f1,f2);} @* |
---|
47 | |
---|
48 | @code{> std(bI);} @* |
---|
49 | @code{_[1] = x(1) + x(4)} @* |
---|
50 | @code{_[2] = x(3)*x(4) + x(4)} @* |
---|
51 | |
---|
52 | |
---|
53 | NOTE: For using this library SINGULAR's @code{python} interface must be available |
---|
54 | on your system. |
---|
55 | Please @code{./configure --with-python} when building SINGULAR for this purpose. |
---|
56 | |
---|
57 | There are prebuilt binary packages for @code{PolyBoRi} available |
---|
58 | from @code{http://polybori.sf.net/}. |
---|
59 | |
---|
60 | For building your own @code{PolyBoRi} please ensure that you have @code{scons} and a |
---|
61 | development version of the boost libaries installed on you system. |
---|
62 | Then you may execute the following commands in a @code{bash}-style shell |
---|
63 | to build @code{PolyBoRi} available to @code{python}: |
---|
64 | |
---|
65 | @code{PBDIR=/path/to/custom/polybori} @* |
---|
66 | @code{wget http://downloads.sf.net/project/polybori/polybori/\\}@* |
---|
67 | @code{0.8.2/polybori-0.8.2.tar.gz} @* |
---|
68 | @code{tar -xvzf polybori-0.8.2.tar.gz} @* |
---|
69 | @code{cd polybori-0.8.2} @* |
---|
70 | @code{scons install PREFIX=$PBDIR PYINSTALLPREFIX=$PBDIR/python} @* |
---|
71 | @code{export PYTHONPATH=$PBDIR/python:$PYTHONPATH} @* |
---|
72 | |
---|
73 | |
---|
74 | REFERENCES: |
---|
75 | See @code{http://polybori.sf.net} for details about @code{PolyBoRi}. |
---|
76 | |
---|
77 | PROCEDURES: |
---|
78 | boolean_std(bideal); Singular ideal of boolean groebner basis of I |
---|
79 | |
---|
80 | boolean_poly_ring(ring); convert ring |
---|
81 | boolean_constant(int[, bring]); convert constant |
---|
82 | boolean_poly(poly[, int, bring]) convert polynomial |
---|
83 | direct_boolean_poly(poly[, bring]); convert polynomial direct |
---|
84 | recursive_boolean_poly(poly[, bring]); convert polynomial recursively |
---|
85 | boolean_ideal(ideal[, bring]); convert ideal |
---|
86 | boolean_set(zdd[, bring]); convert zdd |
---|
87 | |
---|
88 | |
---|
89 | from_boolean_constant(bpoly); convert boolean constant |
---|
90 | from_boolean_poly(bpoly[, int]); convert boolean polynomial |
---|
91 | direct_from_boolean_poly(bpoly); convert boolean polynomial direct |
---|
92 | recursive_from_boolean_poly(bpoly); convert boolean polynomial recursively |
---|
93 | from_boolean_ideal(bpoly); convert to ideal |
---|
94 | from_boolean_set(bset); convert to zdd |
---|
95 | |
---|
96 | |
---|
97 | bvar(i); return i-th Boolean variable |
---|
98 | poly2zdd(poly); return zdd of a given polynomial |
---|
99 | zdd2poly(zdd); return polynomial representation of a given zdd |
---|
100 | disp_zdd(zdd); return string with a visualization of a given |
---|
101 | |
---|
102 | KEYWORDS: library, polybori.lib; polybori; polybori.lib; library; pyobject; newstruct; zdd |
---|
103 | |
---|
104 | "; |
---|
105 | |
---|
106 | /////////////////////////////////////////////////////////////////////// |
---|
107 | // initialization of datatypes and constant structures |
---|
108 | |
---|
109 | static proc mod_init() |
---|
110 | "USAGE: mod_init() |
---|
111 | RETURN: none |
---|
112 | NOTE: load PolyBoRi and introduce the structures zdd and bpoly |
---|
113 | SEE ALSO: boolean_ideal, boolean_std |
---|
114 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
115 | " |
---|
116 | { |
---|
117 | if (typeof(Pyobject)!="package") |
---|
118 | { |
---|
119 | LIB("pyobject.so"); |
---|
120 | } |
---|
121 | if (typeof(zdd_one)=="?unknown type?") |
---|
122 | { |
---|
123 | python_import("polybori"); |
---|
124 | |
---|
125 | // install new types |
---|
126 | |
---|
127 | newstruct("zdd","int idx,def thenBranch,def elseBranch"); |
---|
128 | newstruct("bpoly","pyobject boolpoly"); |
---|
129 | newstruct("bideal","pyobject pylist"); |
---|
130 | newstruct("bring", "pyobject pyring"); |
---|
131 | newstruct("bset", "pyobject pyset"); |
---|
132 | |
---|
133 | // install type operations |
---|
134 | |
---|
135 | system("install", "zdd", "==", zdd_check,2); |
---|
136 | system("install", "bpoly", "==", bpoly_check,2); |
---|
137 | system("install", "bpoly", "*", bpoly_mult,2); |
---|
138 | system("install", "bpoly", "+", bpoly_add,2); |
---|
139 | system("install", "zdd", "print", print_zdd, 1); |
---|
140 | system("install", "bpoly", "print", print_bpoly,1); |
---|
141 | system("install", "bideal", "print", print_bideal,1); |
---|
142 | system("install", "bideal", "size", size_bideal,1); |
---|
143 | system("install", "bpoly", "lead", lead_bpoly, 1); |
---|
144 | system("install", "bpoly", "leadmonom",lead_monom_bpoly, 1); |
---|
145 | system("install", "bpoly", "leadcoef", lead_coef_bpoly, 1); |
---|
146 | system("install", "bideal", "[", op_getitem, 2); |
---|
147 | system("install", "bideal", "+", bideal_add, 2); |
---|
148 | system("install", "bideal", "std", boolean_std, 4); |
---|
149 | |
---|
150 | // install type conversions |
---|
151 | |
---|
152 | // implemented typecasts (both directions) |
---|
153 | // SINGULAR BOOLEAN OBJECTS |
---|
154 | // ring bring |
---|
155 | // poly bpoly |
---|
156 | // zdd bset |
---|
157 | // ideal bideal |
---|
158 | // |
---|
159 | // furthermore, it is possible to switch between poly <-> zdd and bpoly <-> bset |
---|
160 | |
---|
161 | system("install", "bring", "=", ring2bring, 1); |
---|
162 | system("install", "bring", "nvars", nvars_bring, 1); |
---|
163 | |
---|
164 | system("install", "pyobject", "poly", from_boolean_poly, 1); |
---|
165 | system("install", "pyobject", "size", size_pyobject, 1); |
---|
166 | |
---|
167 | system("install", "pyobject", "bideal", pyobject2bideal,1); |
---|
168 | system("install", "bideal", "pyobject", bideal2pyobject,1); |
---|
169 | |
---|
170 | system("install", "bideal", "ideal", bideal2ideal, 4); |
---|
171 | system("install", "bideal", "=", type2bideal, 1); |
---|
172 | |
---|
173 | |
---|
174 | |
---|
175 | system("install", "zdd", "poly", zdd2poly, 1); |
---|
176 | system("install", "zdd", "=", poly2zdd, 1); |
---|
177 | |
---|
178 | system("install", "zdd", "pyobject", boolean_set, 1); |
---|
179 | system("install", "pyobject", "zdd", from_boolean_set, 1); |
---|
180 | |
---|
181 | system("install", "bset", "zdd", bset2zdd, 1); |
---|
182 | system("install", "zdd", "bset", zdd2bset, 1); |
---|
183 | |
---|
184 | system("install", "bpoly", "bset", bpoly2bset, 1); |
---|
185 | system("install", "bset", "bpoly", bset2bpoly, 1); |
---|
186 | |
---|
187 | system("install", "pyobject", "bpoly", pyobject2bpoly,1); |
---|
188 | system("install", "bpoly", "pyobject", bpoly2pyobject,1); |
---|
189 | |
---|
190 | system("install", "bpoly", "poly", bpoly2poly,1); |
---|
191 | system("install", "bpoly", "bideal", bpoly2bideal,1); |
---|
192 | system("install", "bpoly", "=", poly2bpoly,1); |
---|
193 | |
---|
194 | |
---|
195 | |
---|
196 | // initialize constant zdds |
---|
197 | |
---|
198 | zdd zdd_one; |
---|
199 | zdd_one.idx=0; |
---|
200 | zdd_one.thenBranch=int(1); |
---|
201 | zdd_one.elseBranch=int(0); |
---|
202 | zdd zdd_zero; |
---|
203 | zdd_zero.idx=0; |
---|
204 | zdd_zero.thenBranch=int(0); |
---|
205 | zdd_zero.elseBranch=int(0); |
---|
206 | export(zdd_one); |
---|
207 | export(zdd_zero); |
---|
208 | |
---|
209 | python_run("def if_then_else_idx(idx,b,c): return b.set().change(idx).union(c)"); |
---|
210 | python_run("_SINGULAR_RINGS = dict()"); |
---|
211 | python_run("_SINGULAR_RINGS_ACCESSED = 0"); |
---|
212 | python_run("def _SINGULAR_DECACHE_RING(arg): val = arg(); return 0 if val is None else val"); |
---|
213 | } |
---|
214 | } |
---|
215 | |
---|
216 | /////////////////////////////////////////////////////////////////////// |
---|
217 | // computes the leading term of a bpoly |
---|
218 | |
---|
219 | proc lead_bpoly(bpoly pp) |
---|
220 | { |
---|
221 | pyobject zero=0; |
---|
222 | bpoly zero2; |
---|
223 | zero2.boolpoly=zero; |
---|
224 | if (pp==zero2) |
---|
225 | { |
---|
226 | return(0); |
---|
227 | } |
---|
228 | else |
---|
229 | { |
---|
230 | pyobject ppb=pp.boolpoly."lead"(); |
---|
231 | return(ppb); |
---|
232 | } |
---|
233 | } |
---|
234 | |
---|
235 | /////////////////////////////////////////////////////////////////////// |
---|
236 | // computes the leading monomial of a bpoly |
---|
237 | |
---|
238 | proc lead_monom_bpoly(bpoly pp) |
---|
239 | { |
---|
240 | if (pp.boolpoly == 0) { return(0); } |
---|
241 | |
---|
242 | pyobject ppb=pp.boolpoly."lead"(); |
---|
243 | return(ppb); |
---|
244 | } |
---|
245 | |
---|
246 | /////////////////////////////////////////////////////////////////////// |
---|
247 | // computes the leading coefficient of a bpoly |
---|
248 | |
---|
249 | proc lead_coef_bpoly(bpoly pp) |
---|
250 | { |
---|
251 | if (int(pp.is_zero())) { return(0); } |
---|
252 | return(1); |
---|
253 | } |
---|
254 | |
---|
255 | /////////////////////////////////////////////////////////////////////// |
---|
256 | // converts a Singular ring into a Boolean ring |
---|
257 | |
---|
258 | proc ring2bring(r) |
---|
259 | { |
---|
260 | bring rb; |
---|
261 | rb.pyring = boolean_poly_ring(r); |
---|
262 | return(rb); |
---|
263 | } |
---|
264 | /////////////////////////////////////////////////////////////////////// |
---|
265 | // Generate an ideal from one constructor |
---|
266 | proc bpoly2bideal(bpoly bp) |
---|
267 | { |
---|
268 | pyobject obj = list(bp); |
---|
269 | bideal bI = obj; |
---|
270 | return (bI); |
---|
271 | } |
---|
272 | |
---|
273 | /////////////////////////////////////////////////////////////////////// |
---|
274 | // get number of variables of a Boolean ring |
---|
275 | |
---|
276 | proc nvars_bring(bring rb) |
---|
277 | { |
---|
278 | return (int(rb.pyring.n_variables())); |
---|
279 | } |
---|
280 | |
---|
281 | /////////////////////////////////////////////////////////////////////// |
---|
282 | // get variable of Boolean ring corresponding to current basering |
---|
283 | |
---|
284 | proc bvar(int i) |
---|
285 | "USAGE: bvar(i); int i |
---|
286 | RETURN: i-th variable of Boolean ring corresponding to current basering |
---|
287 | SEE ALSO: boolean_poly_ring, var |
---|
288 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
289 | EXAMPLE: example bvar; shows an example" |
---|
290 | { |
---|
291 | bpoly re = var(i); |
---|
292 | return (re); |
---|
293 | } |
---|
294 | example |
---|
295 | { "EXAMPLE:"; echo=2; |
---|
296 | ring r = 2,(x,y,z),Dp; |
---|
297 | bvar(1); // -> x |
---|
298 | } |
---|
299 | |
---|
300 | /////////////////////////////////////////////////////////////////////// |
---|
301 | // Internal functions for caching converted ring |
---|
302 | /////////////////////////////////////////////////////////////////////// |
---|
303 | |
---|
304 | |
---|
305 | // Mark cache as accessed and clear garbage every 100 accesses |
---|
306 | static proc bring_mark_cache(list #) |
---|
307 | { |
---|
308 | if (int(python_eval("_SINGULAR_RINGS_ACCESSED >= 100"))) { |
---|
309 | python_run("_SINGULAR_RINGS_ACCESSED = 0"); |
---|
310 | def erased = python_eval("[_k for (_k,_v) in _SINGULAR_RINGS.items() if _v() is None]"); |
---|
311 | erased = python_eval("(lambda _keys: [_SINGULAR_RINGS.pop(_k) for _k in _keys])")(erased); |
---|
312 | } |
---|
313 | python_run("_SINGULAR_RINGS_ACCESSED += 1"); |
---|
314 | } |
---|
315 | |
---|
316 | // look up whether we cached this conversion before |
---|
317 | static proc bring_from_cache(r) |
---|
318 | { |
---|
319 | bring_mark_cache(); |
---|
320 | def result1 = python_eval("_SINGULAR_RINGS.get('" + string(r) + "', (lambda: None))"); |
---|
321 | def result = python_eval("_SINGULAR_DECACHE_RING")(result1); |
---|
322 | return (result); |
---|
323 | } |
---|
324 | |
---|
325 | // insert computed result into cache |
---|
326 | static proc bring_to_cache(r, pyobject newring) |
---|
327 | { |
---|
328 | def value = WeakRingRef(newring); |
---|
329 | python_eval("_SINGULAR_RINGS")."__setitem__"(string(r), value); |
---|
330 | } |
---|
331 | |
---|
332 | /////////////////////////////////////////////////////////////////////// |
---|
333 | // converts a Singular ring into a python ring |
---|
334 | |
---|
335 | proc boolean_poly_ring(r) |
---|
336 | { |
---|
337 | def cached = bring_from_cache(r); |
---|
338 | if (int(cached != int(0))) { return (cached); } |
---|
339 | |
---|
340 | def rl = ringlist(r); |
---|
341 | list blocks; |
---|
342 | string ordering; |
---|
343 | pyobject orders = python_eval("dict(lp=OrderCode.lp)"); |
---|
344 | if (size(rl[3]) >2) |
---|
345 | { |
---|
346 | orders.update(python_eval("dict(Dp=OrderCode.block_dlex)")); |
---|
347 | } |
---|
348 | else |
---|
349 | { |
---|
350 | orders.update(python_eval("dict(Dp=OrderCode.dlex)")); |
---|
351 | } |
---|
352 | |
---|
353 | int i; |
---|
354 | int counter=0; |
---|
355 | for (i=1; i<=size(ringlist(r)[3]); i++) |
---|
356 | { |
---|
357 | if (rl[3][i][1]<>"C") |
---|
358 | { |
---|
359 | ordering=rl[3][i][1]; |
---|
360 | if (counter) { blocks = blocks + list(counter) }; |
---|
361 | counter = counter + size(rl[3][i][2]); |
---|
362 | } |
---|
363 | } |
---|
364 | if(int(orders.has_key(ordering)==0)) |
---|
365 | { |
---|
366 | "// Warning: Unsupported ordering, using 'lp`!"; |
---|
367 | } |
---|
368 | |
---|
369 | def result = Ring(nvars(r), orders.get(ordering, 0), rl[2], blocks); |
---|
370 | bring_to_cache(r, result); |
---|
371 | return (result); |
---|
372 | } |
---|
373 | |
---|
374 | /////////////////////////////////////////////////////////////////////// |
---|
375 | // returns ith entry of a bideal |
---|
376 | |
---|
377 | proc op_getitem(bideal arg, def idx) |
---|
378 | { |
---|
379 | if (typeof(idx) == "int") { return (arg.pylist[idx-1]); } |
---|
380 | |
---|
381 | bideal re = (python_eval("lambda ll, idx: [ll[i] for i in idx]")(arg.pylist, idx-1)); |
---|
382 | return (re); |
---|
383 | } |
---|
384 | |
---|
385 | /////////////////////////////////////////////////////////////////////// |
---|
386 | // concatenate generators of bideals |
---|
387 | |
---|
388 | proc bideal_add(bideal arg1, bideal arg2) |
---|
389 | { |
---|
390 | pyobject tmp = python_eval("lambda x, y: list(sorted(set(x).union(set(y))))"); |
---|
391 | bideal re = tmp(arg1.pylist,arg2.pylist); |
---|
392 | return (re); |
---|
393 | } |
---|
394 | |
---|
395 | /////////////////////////////////////////////////////////////////////// |
---|
396 | // checks the equality of two bpolys |
---|
397 | |
---|
398 | proc bpoly_check(bpoly pb1, pb2) |
---|
399 | { |
---|
400 | return(pb1.boolpoly==pb2.boolpoly); |
---|
401 | } |
---|
402 | |
---|
403 | /////////////////////////////////////////////////////////////////////// |
---|
404 | // computes the multiplication of two bpolys |
---|
405 | |
---|
406 | proc bpoly_mult(bpoly pb1, pb2) |
---|
407 | { |
---|
408 | bpoly bpol; |
---|
409 | bpol.boolpoly=pb1.boolpoly*pb2.boolpoly; |
---|
410 | return(bpol); |
---|
411 | } |
---|
412 | |
---|
413 | /////////////////////////////////////////////////////////////////////// |
---|
414 | // computes the addition of two bpolys |
---|
415 | |
---|
416 | proc bpoly_add(bpoly pb1, bpoly pb2) |
---|
417 | { |
---|
418 | bpoly bpol; |
---|
419 | bpol.boolpoly=pb1.boolpoly+pb2.boolpoly; |
---|
420 | return(bpol); |
---|
421 | } |
---|
422 | |
---|
423 | /////////////////////////////////////////////////////////////////////// |
---|
424 | // convert bpoly to pyobject |
---|
425 | |
---|
426 | proc bpoly2pyobject(bpoly pb) |
---|
427 | { |
---|
428 | return(pb.boolpoly); |
---|
429 | } |
---|
430 | |
---|
431 | /////////////////////////////////////////////////////////////////////// |
---|
432 | // convert bideal to pyobject |
---|
433 | |
---|
434 | proc bideal2pyobject(bideal Ib) |
---|
435 | { |
---|
436 | return(Ib.pylist); |
---|
437 | } |
---|
438 | |
---|
439 | /////////////////////////////////////////////////////////////////////// |
---|
440 | // convert poly to bpoly |
---|
441 | |
---|
442 | proc poly2bpoly(poly p) |
---|
443 | { |
---|
444 | bpoly bpol; |
---|
445 | bpol.boolpoly=boolean_poly(p); |
---|
446 | return(bpol); |
---|
447 | } |
---|
448 | |
---|
449 | /////////////////////////////////////////////////////////////////////// |
---|
450 | // convert zdd to bset |
---|
451 | |
---|
452 | proc zdd2bset(zdd ss) |
---|
453 | { |
---|
454 | bset bs; |
---|
455 | bs.pyset=boolean_set(ss); |
---|
456 | return(bs); |
---|
457 | } |
---|
458 | |
---|
459 | /////////////////////////////////////////////////////////////////////// |
---|
460 | // convert bpoly to bset |
---|
461 | |
---|
462 | proc bpoly2bset(bpoly ss) |
---|
463 | { |
---|
464 | bset bs; |
---|
465 | bs.pyset=ss.boolpoly.set(); |
---|
466 | return(bs); |
---|
467 | } |
---|
468 | |
---|
469 | /////////////////////////////////////////////////////////////////////// |
---|
470 | // convert bset to zdd |
---|
471 | |
---|
472 | proc bset2zdd(bset ss) |
---|
473 | { |
---|
474 | zdd bs; |
---|
475 | bs=from_boolean_set(ss.pyset); |
---|
476 | return(bs); |
---|
477 | } |
---|
478 | |
---|
479 | /////////////////////////////////////////////////////////////////////// |
---|
480 | // convert bset to bpoly |
---|
481 | |
---|
482 | proc bset2bpoly(bset ss) |
---|
483 | { |
---|
484 | bpoly pb; |
---|
485 | pb.boolpoly=python_eval("Polynomial")(ss.pyset); |
---|
486 | return(pb); |
---|
487 | } |
---|
488 | |
---|
489 | /////////////////////////////////////////////////////////////////////// |
---|
490 | // convert type (ideal or list) to bideal |
---|
491 | |
---|
492 | proc type2bideal(def I) |
---|
493 | { |
---|
494 | if (typeof(I) == "ideal") { return (boolean_ideal(I)); } |
---|
495 | |
---|
496 | bideal bid; |
---|
497 | pyobject pylist; |
---|
498 | |
---|
499 | if (typeof(I) == "list") |
---|
500 | { |
---|
501 | pylist = python_eval("list()"); |
---|
502 | int i; int nlen=size(I); bpoly elt; |
---|
503 | for (i=1; i <= nlen; i++) { |
---|
504 | elt = I[i]; |
---|
505 | pylist.append(pyobject(elt)); |
---|
506 | } |
---|
507 | } |
---|
508 | else { pylist = I; } |
---|
509 | bid.pylist = pylist; |
---|
510 | return (bid); |
---|
511 | } |
---|
512 | |
---|
513 | /////////////////////////////////////////////////////////////////////// |
---|
514 | // convert bpoly to poly |
---|
515 | |
---|
516 | proc bpoly2poly(bpoly pb) |
---|
517 | { |
---|
518 | poly h=poly(pb.boolpoly); |
---|
519 | return(h); |
---|
520 | } |
---|
521 | |
---|
522 | |
---|
523 | /////////////////////////////////////////////////////////////////////// |
---|
524 | // convert bideal to ideal |
---|
525 | |
---|
526 | proc bideal2ideal(bideal Ib) |
---|
527 | { |
---|
528 | ideal I; |
---|
529 | I=from_boolean_ideal(Ib); |
---|
530 | return(I); |
---|
531 | } |
---|
532 | |
---|
533 | /////////////////////////////////////////////////////////////////////// |
---|
534 | // convert pyobject to bpoly |
---|
535 | |
---|
536 | proc pyobject2bpoly(pyobject pb) |
---|
537 | { |
---|
538 | bpoly bpol; |
---|
539 | bpol.boolpoly=pb; |
---|
540 | return(bpol); |
---|
541 | } |
---|
542 | |
---|
543 | /////////////////////////////////////////////////////////////////////// |
---|
544 | // convert pyobject to bideal |
---|
545 | |
---|
546 | proc pyobject2bideal(pyobject Ib) |
---|
547 | { |
---|
548 | bideal bid; |
---|
549 | bid.pylist=Ib; |
---|
550 | return(bid); |
---|
551 | } |
---|
552 | |
---|
553 | /////////////////////////////////////////////////////////////////////// |
---|
554 | // print bpoly |
---|
555 | |
---|
556 | proc print_bpoly(bpoly pb) |
---|
557 | { |
---|
558 | pb.boolpoly; |
---|
559 | } |
---|
560 | |
---|
561 | /////////////////////////////////////////////////////////////////////// |
---|
562 | // print bideal |
---|
563 | |
---|
564 | proc print_bideal(bideal Ib) |
---|
565 | { |
---|
566 | int nlen = size(Ib); |
---|
567 | for (int i = 1; i <= nlen; i++) |
---|
568 | { |
---|
569 | "_[" + string(i)+"] = " + string(Ib[i]); |
---|
570 | } |
---|
571 | } |
---|
572 | |
---|
573 | /////////////////////////////////////////////////////////////////////// |
---|
574 | // get size of pyobject |
---|
575 | |
---|
576 | proc size_pyobject(pyobject obj) |
---|
577 | { |
---|
578 | return (int(python_eval("len")(obj))); |
---|
579 | } |
---|
580 | |
---|
581 | /////////////////////////////////////////////////////////////////////// |
---|
582 | // get size of bideal |
---|
583 | |
---|
584 | proc size_bideal(bideal Ib) |
---|
585 | { |
---|
586 | return (size(Ib.pylist)); |
---|
587 | } |
---|
588 | |
---|
589 | |
---|
590 | /////////////////////////////////////////////////////////////////////// |
---|
591 | // print zdd |
---|
592 | |
---|
593 | proc print_zdd(zdd ss) |
---|
594 | { |
---|
595 | "zdd: "; |
---|
596 | disp_zdd(ss); |
---|
597 | } |
---|
598 | |
---|
599 | /////////////////////////////////////////////////////////////////////// |
---|
600 | // check equality |
---|
601 | |
---|
602 | proc zdd_check(zdd zdd1,zdd zdd2) |
---|
603 | "USAGE: zdd_check(zdd1,zdd2); zdd zdd1, zdd zdd2 |
---|
604 | RETURN: 0 or 1 " |
---|
605 | { |
---|
606 | if (zdd1.idx != zdd2.idx) { return (int(0)); } |
---|
607 | |
---|
608 | if (zdd1.idx == 0) { return (int(zdd1.thenBranch == zdd2.thenBranch)); } |
---|
609 | |
---|
610 | return (zdd_check(zdd1.thenBranch,zdd2.thenBranch)*zdd_check(zdd1.elseBranch,zdd2.elseBranch)); |
---|
611 | } |
---|
612 | |
---|
613 | /////////////////////////////////////////////////////////////////////// |
---|
614 | |
---|
615 | proc boolean_set(zdd ss,list #) |
---|
616 | "USAGE: boolean_set(ss[, rb]); ss zdd, rb boolean ring |
---|
617 | RETURN: default: boolean set ss in the representation of a Polybori boolean set |
---|
618 | in the ring rb==boolean_poly_ring(basering); optional input: boolean ring rb |
---|
619 | SEE ALSO: boolean_ideal, boolean_std |
---|
620 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
621 | EXAMPLE: example boolean_set; shows an example" |
---|
622 | { |
---|
623 | pyobject rb; |
---|
624 | rb=check_additional_ring(#); |
---|
625 | pyobject newthen,newelse,unbek,outp; |
---|
626 | if (ss.idx==0) |
---|
627 | { |
---|
628 | if (zdd_check(ss,zdd_one)==1) { return (boolean_constant(1,rb)); } |
---|
629 | return (boolean_constant(0,rb)); |
---|
630 | } |
---|
631 | newthen=(boolean_set(ss.thenBranch,rb)); |
---|
632 | newelse=(boolean_set(ss.elseBranch,rb)); |
---|
633 | outp=if_then_else_idx(ss.idx-1,newthen,newelse); |
---|
634 | return (outp); |
---|
635 | } |
---|
636 | |
---|
637 | example |
---|
638 | { "EXAMPLE:"; echo=2; |
---|
639 | ring rs=0,(x,y,z),Dp; |
---|
640 | poly ps=(x+1)*(y+1)*(z+1); |
---|
641 | zdd fz=ps; |
---|
642 | boolean_set(fz); |
---|
643 | |
---|
644 | poly g=x*y*z+1; |
---|
645 | zdd gz=g; |
---|
646 | boolean_set(gz); |
---|
647 | |
---|
648 | ring R=0,(x(1..4)),Dp; |
---|
649 | def Rb=boolean_poly_ring(R); |
---|
650 | poly h=(x(1)+1)*(x(2)+1)*(x(3)+1)*(x(4)+1); |
---|
651 | zdd hz=h; |
---|
652 | boolean_set(hz); |
---|
653 | } |
---|
654 | |
---|
655 | /////////////////////////////////////////////////////////////////////// |
---|
656 | |
---|
657 | proc from_boolean_set(def s) |
---|
658 | "USAGE: from_boolean_set(sb); sb boolean set |
---|
659 | RETURN: Boolean set sb in the representation of a zdd |
---|
660 | SEE ALSO: boolean_ideal, boolean_std |
---|
661 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
662 | EXAMPLE: example from_boolean_set; shows an example" |
---|
663 | { |
---|
664 | bpoly bp = s; |
---|
665 | pyobject sb = bp; |
---|
666 | def rb=boolean_poly_ring(basering); |
---|
667 | zdd result; |
---|
668 | def nav=sb.navigation(); |
---|
669 | int ind=int(nav.value()); |
---|
670 | def navout_then=nav.then_branch(); |
---|
671 | def navout_else=nav.else_branch(); |
---|
672 | def pb=Polynomial(sb); |
---|
673 | |
---|
674 | if (int(nav.constant())) |
---|
675 | { |
---|
676 | if (pb==1) { return(zdd_one); } |
---|
677 | return(zdd_zero); |
---|
678 | } |
---|
679 | |
---|
680 | result.idx=ind+1; |
---|
681 | pyobject one=1; |
---|
682 | def substpoly=one*rb.variable(ind); |
---|
683 | |
---|
684 | if (int(navout_then.constant())) |
---|
685 | { |
---|
686 | result.thenBranch=zdd_one; |
---|
687 | } |
---|
688 | else |
---|
689 | { |
---|
690 | result.thenBranch=from_boolean_set(BooleSet(navout_then,rb)); |
---|
691 | } |
---|
692 | if (int(navout_else.constant())) |
---|
693 | { |
---|
694 | if (subst(from_boolean_poly(pb),from_boolean_poly(substpoly),0)==1) |
---|
695 | { |
---|
696 | result.elseBranch=zdd_one; |
---|
697 | } |
---|
698 | else |
---|
699 | { |
---|
700 | result.elseBranch=zdd_zero; |
---|
701 | } |
---|
702 | } |
---|
703 | else |
---|
704 | { |
---|
705 | result.elseBranch=from_boolean_set(BooleSet(navout_else,rb)); |
---|
706 | } |
---|
707 | return(result); |
---|
708 | } |
---|
709 | |
---|
710 | example |
---|
711 | { "EXAMPLE:"; echo=2; |
---|
712 | ring r=0,(x,y,z),Dp; |
---|
713 | poly f=(x+1)*(y+1)*(z+1); |
---|
714 | bpoly fb=f; |
---|
715 | bset fs=fb; |
---|
716 | from_boolean_set(fs); |
---|
717 | |
---|
718 | poly g=x*y*z+1; |
---|
719 | bpoly gb=g; |
---|
720 | bset gs=gb; |
---|
721 | from_boolean_set(gs); |
---|
722 | |
---|
723 | ring R=0,(x(1..4)),Dp; |
---|
724 | poly h=(x(1)+1)*(x(2)+1)*(x(3)+1)*(x(4)+1); |
---|
725 | pyobject hb=boolean_poly(h); |
---|
726 | def hs=hb.set(); |
---|
727 | from_boolean_set(hs); |
---|
728 | } |
---|
729 | |
---|
730 | ////////////////////////////////////////////////////////////////////// |
---|
731 | |
---|
732 | proc direct_from_boolean_poly(def p) |
---|
733 | "USAGE: from_boolean_poly(pb); pb boolean polynomial |
---|
734 | RETURN: polynomial in Singular |
---|
735 | SEE ALSO: from_boolean_ideal, boolean_ideal, boolean_poly, boolean_poly_ring, |
---|
736 | boolean_std |
---|
737 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
738 | EXAMPLE: example from_boolean_poly; shows an example" |
---|
739 | { |
---|
740 | pyobject pb = p; |
---|
741 | poly result = 0; |
---|
742 | def terms = python_eval("list")(pb.terms()); |
---|
743 | int nlen = size(terms); |
---|
744 | for (int i = 0; i < nlen; i++) |
---|
745 | { |
---|
746 | result=from_boolean_poly_update(result,terms[i]); |
---|
747 | } |
---|
748 | return (result); |
---|
749 | } |
---|
750 | |
---|
751 | example |
---|
752 | { "EXAMPLE:"; echo=2; |
---|
753 | ring r=0,(x,y,z),Dp; |
---|
754 | pyobject rb=boolean_poly_ring(r); |
---|
755 | poly f=x^2+2*y^3+3*z^3; |
---|
756 | bpoly pp=f; |
---|
757 | direct_from_boolean_poly(pp); |
---|
758 | |
---|
759 | poly g=0; |
---|
760 | bpoly pp=g; |
---|
761 | direct_from_boolean_poly(pp); |
---|
762 | } |
---|
763 | |
---|
764 | /////////////////////////////////////////////////////////////////////// |
---|
765 | // one iteration in direct_from_boolean_poly |
---|
766 | |
---|
767 | static proc from_boolean_poly_update(poly ps, pyobject pb) |
---|
768 | "USAGE: from_boolean_poly_update(ps,pb); ps polynomial, pb boolean polynomial, |
---|
769 | RETURN: update of the Singular polynomial in from_boolean_poly in one iteration |
---|
770 | SEE ALSO: from_boolean_poly |
---|
771 | { |
---|
772 | pyobject current = pb."variables"(); |
---|
773 | pyobject vars = python_eval("list")(current); |
---|
774 | int j, index; |
---|
775 | poly term = 1; |
---|
776 | pyobject currentvar; |
---|
777 | int tlen = size(vars); |
---|
778 | for (j = 0; j < tlen; j++) |
---|
779 | { |
---|
780 | currentvar = vars[j]; |
---|
781 | index = int(currentvar.index()); |
---|
782 | term = term * var(index+1); |
---|
783 | } |
---|
784 | return(ps + term); |
---|
785 | } |
---|
786 | |
---|
787 | /////////////////////////////////////////////////////////////////////// |
---|
788 | // return 1, iff int is 1 modulo 2 and 0 else |
---|
789 | |
---|
790 | static proc coeff_check(int const) |
---|
791 | "USAGE: coeff_check(const); const int |
---|
792 | RETURN: 1 iff the coefficient equals 1 modulo 2 and 0 else |
---|
793 | NOTE: helps to handle leading coefficients of rings in arbitrary characteristic |
---|
794 | SEE ALSO: recursive_boolean_poly, boolean_poly |
---|
795 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
796 | EXAMPLE: example coeff_check; shows an example" |
---|
797 | { |
---|
798 | if (char(basering)==2) { return (const); } |
---|
799 | |
---|
800 | return ((const%2)*(const%2)); |
---|
801 | } |
---|
802 | example |
---|
803 | { "EXAMPLE:"; echo = 2; |
---|
804 | ring R1=5,x(1..4),lp; |
---|
805 | poly f=3*x(1)+x(2)^2; |
---|
806 | coeff_check(int(leadcoef(f))); |
---|
807 | } |
---|
808 | |
---|
809 | /////////////////////////////////////////////////////////////////////// |
---|
810 | |
---|
811 | static proc check_additional_ring(list #) |
---|
812 | "USAGE: check_additional_ring(#); |
---|
813 | NOTE: Help function to check whether an additional ring exists and if it is a |
---|
814 | bring or a ring in python." |
---|
815 | { |
---|
816 | pyobject rb; |
---|
817 | bring rbhelp; |
---|
818 | if (size(#)==0) |
---|
819 | { |
---|
820 | rb=boolean_poly_ring(basering); |
---|
821 | } |
---|
822 | else |
---|
823 | { |
---|
824 | if (typeof(#[1])=="bring") |
---|
825 | { |
---|
826 | rbhelp=#[1]; |
---|
827 | rb=rbhelp.pyring; |
---|
828 | } |
---|
829 | else |
---|
830 | { |
---|
831 | rb=#[1]; |
---|
832 | } |
---|
833 | } |
---|
834 | return(rb); |
---|
835 | } |
---|
836 | /////////////////////////////////////////////////////////////////////// |
---|
837 | |
---|
838 | proc boolean_constant(int const, list #) |
---|
839 | "USAGE: boolean_constant(const[, rb]); const constant and rb boolean ring |
---|
840 | RETURN: default: constant const in the representation of the boolean ring |
---|
841 | rb==boolean_poly_ring(basering); optional input: rb=boolean ring rb |
---|
842 | SEE ALSO: boolean_ideal, boolean_std |
---|
843 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
844 | EXAMPLE: example boolean_constant; shows an example" |
---|
845 | { |
---|
846 | pyobject rb = check_additional_ring(#); |
---|
847 | if (coeff_check(const)==0) { return (rb.zero()); } |
---|
848 | |
---|
849 | return (rb.one()); |
---|
850 | } |
---|
851 | |
---|
852 | example |
---|
853 | { "EXAMPLE:"; echo = 2; |
---|
854 | ring r=7,(x,y),Dp; |
---|
855 | pyobject rb=boolean_poly_ring(r); |
---|
856 | boolean_constant(int(3)); |
---|
857 | typeof(boolean_constant(int(3))); |
---|
858 | boolean_constant(int(0)); |
---|
859 | typeof(boolean_constant(int(0))); |
---|
860 | } |
---|
861 | |
---|
862 | /////////////////////////////////////////////////////////////////////// |
---|
863 | |
---|
864 | proc boolean_poly(poly ps, list #) |
---|
865 | "USAGE: boolean_poly(ps[, dir, rb]); ps polynomial, dir integer zero or one, rb |
---|
866 | boolean ring |
---|
867 | RETURN: default: polynomial ps in the representation of the boolean ring |
---|
868 | rb==boolean_poly_ring(basering); optional input: boolean ring rb |
---|
869 | NOTE: via the optional input dir, one can choose the computation method (either |
---|
870 | direct[dir==0] or recursive[dir==1]). default: recursive |
---|
871 | SEE ALSO: boolean_ideal, boolean_std |
---|
872 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
873 | EXAMPLE: example boolean_poly; shows an example" |
---|
874 | { |
---|
875 | if (size(#)==0) |
---|
876 | { |
---|
877 | return(recursive_boolean_poly(ps)); |
---|
878 | } |
---|
879 | if (size(#)==1) |
---|
880 | { |
---|
881 | if (typeof(#[1])=="int") |
---|
882 | { |
---|
883 | if (#[1]==0) { return(direct_boolean_poly(ps)); } |
---|
884 | |
---|
885 | return(recursive_boolean_poly(ps)); |
---|
886 | } |
---|
887 | return(direct_boolean_poly(ps,#[1])); |
---|
888 | } |
---|
889 | if (#[1]==0) { return(direct_boolean_poly(ps,#[2])); } |
---|
890 | |
---|
891 | return(recursive_boolean_poly(ps,#[2])); |
---|
892 | } |
---|
893 | example |
---|
894 | { "EXAMPLE:"; echo = 2; |
---|
895 | ring r=0,x(1..5),Dp; |
---|
896 | poly f=x(2)*(x(3)-x(1))+x(4)*x(5); |
---|
897 | bring rb=r; |
---|
898 | boolean_poly(f); |
---|
899 | boolean_poly(f,0); |
---|
900 | boolean_poly(f,0,boolean_poly_ring(r)); |
---|
901 | boolean_poly(f,0,rb); |
---|
902 | |
---|
903 | |
---|
904 | poly g=0; |
---|
905 | boolean_poly(g); |
---|
906 | |
---|
907 | poly g=1; |
---|
908 | boolean_poly(g); |
---|
909 | } |
---|
910 | |
---|
911 | /////////////////////////////////////////////////////////////////////// |
---|
912 | |
---|
913 | proc from_boolean_poly(def p, list #) |
---|
914 | "USAGE: from_boolean_poly(ps[, dir]); ps polynomial, dir integer zero or one |
---|
915 | RETURN: default: polynomial ps in the representation of the boolean ring |
---|
916 | NOTE: via the optional input dir, one can choose the computation method (either |
---|
917 | direct[dir==0] or recursive[dir==1]). default: direct |
---|
918 | SEE ALSO: boolean_ideal, boolean_std |
---|
919 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
920 | EXAMPLE: example from_boolean_poly; shows an example" |
---|
921 | { |
---|
922 | pyobject pb = pyobject(p); |
---|
923 | |
---|
924 | if (size(#)==0) { return(direct_from_boolean_poly(pb)); } |
---|
925 | if (#[1]==0) { return(direct_from_boolean_poly(pb)); } |
---|
926 | |
---|
927 | return(recursive_from_boolean_poly(pb)); |
---|
928 | } |
---|
929 | |
---|
930 | example |
---|
931 | { "EXAMPLE:"; echo = 2; |
---|
932 | ring r=0,(x,y,z),Dp; |
---|
933 | def rb=boolean_poly_ring(r); |
---|
934 | poly f=x^2+2*y+5*z^4; |
---|
935 | bpoly pp=f; |
---|
936 | from_boolean_poly(pp); |
---|
937 | from_boolean_poly(pp,1); |
---|
938 | |
---|
939 | ring r2=5,(x,y,z),Dp; |
---|
940 | def rb2=boolean_poly_ring(r2); |
---|
941 | poly f2=x+y+z; |
---|
942 | bpoly pp2=f2; |
---|
943 | from_boolean_poly(pp); |
---|
944 | from_boolean_poly(pp,1); |
---|
945 | } |
---|
946 | |
---|
947 | /////////////////////////////////////////////////////////////////////// |
---|
948 | |
---|
949 | proc direct_boolean_poly(poly ps, list #) |
---|
950 | "USAGE: boolean_poly(ps[, rb]); ps polynomial, rb boolean ring |
---|
951 | RETURN: default: polynomial ps in the representation of the boolean ring |
---|
952 | rb==boolean_poly_ring(basering); optional input: boolean ring rb |
---|
953 | SEE ALSO: boolean_ideal, boolean_std |
---|
954 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
955 | EXAMPLE: example boolean_poly; shows an example" |
---|
956 | { |
---|
957 | pyobject resultbool,rb; |
---|
958 | rb=check_additional_ring(#); |
---|
959 | |
---|
960 | int nmax= size(ps); |
---|
961 | resultbool = Polynomial(rb.zero()); |
---|
962 | for (int i = 1; i <= nmax; i++) |
---|
963 | { |
---|
964 | if ( coeff_check(int(leadcoef(ps[i]))) == 1 ) |
---|
965 | { |
---|
966 | resultbool=boolean_poly_update(resultbool,ps[i],rb); |
---|
967 | } |
---|
968 | } |
---|
969 | return (resultbool); |
---|
970 | } |
---|
971 | |
---|
972 | example |
---|
973 | { "EXAMPLE:"; echo = 2; |
---|
974 | ring r0=2,x(1..4),lp; |
---|
975 | bring rb=r0; |
---|
976 | poly f=x(1)^2+2*x(2)*(x(3))-x(4)^3; |
---|
977 | direct_boolean_poly(f); |
---|
978 | direct_boolean_poly(f,rb); |
---|
979 | |
---|
980 | ring r1=0,x,Dp; |
---|
981 | poly f=x3+2x+1; |
---|
982 | direct_boolean_poly(f); |
---|
983 | |
---|
984 | ring r2=32003,(x,y,z),Dp; |
---|
985 | poly f=xyz+20*x^2*y-3*xz+15; |
---|
986 | direct_boolean_poly(f); |
---|
987 | } |
---|
988 | |
---|
989 | /////////////////////////////////////////////////////////////////////// |
---|
990 | // one iteration in direct_boolean_poly |
---|
991 | |
---|
992 | static proc boolean_poly_update(def pb, poly ps, pyobject rb) |
---|
993 | "USAGE: boolean_poly_update(pb,ps,rb); pb boolean polynomial, ps polynomial, |
---|
994 | rb boolean ring |
---|
995 | RETURN: update of the boolean polynomial in boolean_poly in one iteration |
---|
996 | SEE ALSO: boolean_poly |
---|
997 | { |
---|
998 | intvec current = leadexp(ps); |
---|
999 | int j; |
---|
1000 | pyobject term, var_rb; |
---|
1001 | term = python_eval("Monomial")(rb); |
---|
1002 | for (j = 1; j <= size(current); j=j+1) |
---|
1003 | { |
---|
1004 | var_rb = rb.variable(j-1); |
---|
1005 | if (current[j] > 0) { term = term * var_rb; } |
---|
1006 | } |
---|
1007 | return (pb + term); |
---|
1008 | } |
---|
1009 | |
---|
1010 | /////////////////////////////////////////////////////////////////////// |
---|
1011 | |
---|
1012 | proc recursive_boolean_poly(poly ps, list #) |
---|
1013 | "USAGE: boolean_poly(ps[, rb]); ps polynomial, rb boolean ring |
---|
1014 | RETURN: default: polynomial ps in the representation of the boolean ring |
---|
1015 | rb==boolean_poly_ring(basering); optional input: rb boolean ring |
---|
1016 | SEE ALSO: boolean_ideal, boolean_std |
---|
1017 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
1018 | EXAMPLE: example recursive_boolean_poly; shows an example" |
---|
1019 | { |
---|
1020 | pyobject rb; |
---|
1021 | if (size(#)==0) |
---|
1022 | { |
---|
1023 | #[1]=boolean_poly_ring(basering); |
---|
1024 | #[2]=0; |
---|
1025 | } |
---|
1026 | if (size(#)==1) |
---|
1027 | { |
---|
1028 | #[2]=0; |
---|
1029 | } |
---|
1030 | rb=check_additional_ring(#[1]); |
---|
1031 | if (#[2]==int(rb.n_variables())) |
---|
1032 | { |
---|
1033 | return (boolean_constant(int(leadcoef(ps)),rb)); |
---|
1034 | } |
---|
1035 | else |
---|
1036 | { |
---|
1037 | def xsu=var(#[2]+1); |
---|
1038 | poly p0=subst(ps,xsu,0); |
---|
1039 | poly p1=subst(ps-p0,xsu,1); |
---|
1040 | def ahelp=recursive_boolean_poly(p1,rb,#[2]+1); |
---|
1041 | def bhelp=recursive_boolean_poly(p0,rb,#[2]+1); |
---|
1042 | return (rb.variable(#[2])*ahelp+bhelp); |
---|
1043 | } |
---|
1044 | } |
---|
1045 | |
---|
1046 | example |
---|
1047 | { "EXAMPLE:"; echo = 2; |
---|
1048 | ring r0=2,x(1..4),lp; |
---|
1049 | poly f=x(1)^2+2*x(2)*(x(3))-x(4)^3; |
---|
1050 | recursive_boolean_poly(f); |
---|
1051 | |
---|
1052 | ring r1=0,x,Dp; |
---|
1053 | poly f=x3+2x+1; |
---|
1054 | recursive_boolean_poly(f); |
---|
1055 | |
---|
1056 | ring r2=32003,(x,y,z),Dp; |
---|
1057 | def br2=boolean_poly_ring(r2); |
---|
1058 | bring bbr2=r2; |
---|
1059 | poly f=xyz+20*x^2*y-3*xz+15; |
---|
1060 | recursive_boolean_poly(f,br2); |
---|
1061 | recursive_boolean_poly(f,bbr2); |
---|
1062 | } |
---|
1063 | |
---|
1064 | /////////////////////////////////////////////////////////////////////// |
---|
1065 | |
---|
1066 | proc boolean_ideal(ideal Is, list #) |
---|
1067 | "USAGE: boolean_ideal(Is[, rb]); Is Ideal, rb boolean ring |
---|
1068 | RETURN: default: ideal Is in the representation of the boolean ring |
---|
1069 | rb==boolean_poly_ring(basering); optional input: rb boolean ring |
---|
1070 | SEE ALSO: boolean_std |
---|
1071 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
1072 | EXAMPLE: example boolean_ideal; shows an example" |
---|
1073 | { |
---|
1074 | pyobject rb; |
---|
1075 | rb=check_additional_ring(#); |
---|
1076 | int len=size(Is); |
---|
1077 | pyobject Ib = python_eval("list()"); |
---|
1078 | for (int i=1; i<=len; i++) |
---|
1079 | { |
---|
1080 | Ib.append(boolean_poly(Is[i],rb)); |
---|
1081 | } |
---|
1082 | bideal re; |
---|
1083 | re.pylist = Ib; |
---|
1084 | |
---|
1085 | return(re); |
---|
1086 | } |
---|
1087 | |
---|
1088 | example |
---|
1089 | { "EXAMPLE:"; echo = 2; |
---|
1090 | ring r0=2,x(1..4),lp; |
---|
1091 | poly f1=x(1)^2+2*x(2)*(x(3))-x(4)^3; |
---|
1092 | poly f2=x(1)^2-x(3)*x(1); |
---|
1093 | poly f3=x(2)+5-2*x(1); |
---|
1094 | poly f4=x(1)*x(2)-x(3); |
---|
1095 | ideal I=f1,f2,f3,f4; |
---|
1096 | boolean_ideal(I); |
---|
1097 | |
---|
1098 | ring r1=0,x,Dp; |
---|
1099 | poly f1=x3+2*x+1; |
---|
1100 | poly f2=x10-x5+2x; |
---|
1101 | poly f3=19; |
---|
1102 | ideal I=f1,f2,f3; |
---|
1103 | boolean_ideal(I); |
---|
1104 | |
---|
1105 | ring r2=32003,(x,y,z),Dp; |
---|
1106 | bring bbr2=r2; |
---|
1107 | poly f1=xyz+20*x^2*y-3*xz+15; |
---|
1108 | poly f2=32002*xy+z2; |
---|
1109 | poly f3=19; |
---|
1110 | ideal I=f1,f2,f3; |
---|
1111 | boolean_ideal(I); |
---|
1112 | boolean_ideal(I,bbr2); |
---|
1113 | } |
---|
1114 | |
---|
1115 | //////////////////////////////////////////////////////////////// |
---|
1116 | |
---|
1117 | proc from_boolean_ideal(bideal I) |
---|
1118 | "USAGE: from_boolean_ideal(I); I boolean ideal |
---|
1119 | RETURN: ideal in Singular |
---|
1120 | SEE ALSO: from_boolean_poly, boolean_ideal, boolean_poly, boolean_std, |
---|
1121 | boolean_poly_ring |
---|
1122 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
1123 | EXAMPLE: example from_boolean_ideal; shows an example" |
---|
1124 | { |
---|
1125 | ideal re; |
---|
1126 | int i; |
---|
1127 | int nlen = size(I); |
---|
1128 | for (i = 1; i <= nlen; i++) |
---|
1129 | { |
---|
1130 | re[i] = from_boolean_poly(I[i]); |
---|
1131 | } |
---|
1132 | return (re); |
---|
1133 | } |
---|
1134 | |
---|
1135 | example |
---|
1136 | { "EXAMPLE:"; echo=2; |
---|
1137 | ring rs=0,(x,y,z),Dp; |
---|
1138 | def rb3=boolean_poly_ring(rs); |
---|
1139 | poly f1=x+y; |
---|
1140 | poly f2=x+z; |
---|
1141 | bpoly pp =f1; |
---|
1142 | bpoly p = f2; |
---|
1143 | bideal Ib; |
---|
1144 | list K=(p,pp); |
---|
1145 | Ib=K; |
---|
1146 | from_boolean_ideal(Ib); |
---|
1147 | |
---|
1148 | ring rs2=5,(x,y,z),Dp; |
---|
1149 | def rb4=boolean_poly_ring(rs2); |
---|
1150 | poly p1=x+y; |
---|
1151 | poly p2=x+z; |
---|
1152 | poly p3=y+z; |
---|
1153 | bpoly p = p1; |
---|
1154 | bpoly pp = p2; |
---|
1155 | bpoly ppp = p3; |
---|
1156 | bideal Ib; |
---|
1157 | list K=(p,pp,ppp); |
---|
1158 | Ib=K; |
---|
1159 | from_boolean_ideal(Ib); |
---|
1160 | } |
---|
1161 | |
---|
1162 | /////////////////////////////////////////////////////////////////////// |
---|
1163 | |
---|
1164 | proc boolean_std(bideal Is) |
---|
1165 | "USAGE: boolean_std(Is); Is ideal |
---|
1166 | RETURN: Singular ideal of the boolean groebner basis of Is |
---|
1167 | SEE ALSO: from_boolean_poly, boolean_ideal, boolean_poly, from_boolean_ideal, |
---|
1168 | boolean_poly_ring |
---|
1169 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
1170 | EXAMPLE: example boolean_std; shows an example" |
---|
1171 | { |
---|
1172 | pyobject Ib = Is; |
---|
1173 | |
---|
1174 | def redIb=groebner_basis(Ib); |
---|
1175 | bideal result = redIb; |
---|
1176 | return(result); |
---|
1177 | } |
---|
1178 | |
---|
1179 | example |
---|
1180 | { "EXAMPLE:"; echo = 2; |
---|
1181 | ring r0=2,x(1..4),lp; |
---|
1182 | poly f1=x(1)^2+2*x(2)*(x(3))-x(4)^3; |
---|
1183 | poly f2=x(1)^2-x(3)*x(1); |
---|
1184 | poly f3=x(2)+5-2*x(1); |
---|
1185 | poly f4=x(1)*x(2)-x(3); |
---|
1186 | ideal I=f1,f2,f3,f4; |
---|
1187 | |
---|
1188 | boolean_std(I); // implicitely add x(i)^2-x(i) |
---|
1189 | |
---|
1190 | bideal bI=I; // alternative syntax |
---|
1191 | bideal re = std(bI); // Continue PolyBoRi computations |
---|
1192 | std(re[1..2]); |
---|
1193 | |
---|
1194 | ring r1=0,x,Dp; |
---|
1195 | poly f1=x3+2*x+1; |
---|
1196 | poly f2=x10-x5+2x; |
---|
1197 | poly f3=19; |
---|
1198 | ideal I=f1,f2,f3; |
---|
1199 | boolean_std(I); |
---|
1200 | |
---|
1201 | ring r2=32003,(x,y,z),Dp; |
---|
1202 | poly f1=xz+y+20*x^2*y; |
---|
1203 | poly f2=32002*xy+xz2+y; |
---|
1204 | ideal I=f1,f2; |
---|
1205 | boolean_std(I); |
---|
1206 | |
---|
1207 | ring r2=32003,(x,y,z),Dp; |
---|
1208 | poly f1=xyz+20*x^2*y-3*xz+15; |
---|
1209 | poly f2=32002*xy+z2; |
---|
1210 | poly f3=19*x5y; |
---|
1211 | ideal I=f1,f2,f3; |
---|
1212 | boolean_std(I); |
---|
1213 | } |
---|
1214 | |
---|
1215 | ///////////////////////////////////////////////////////////////////////// |
---|
1216 | |
---|
1217 | proc from_boolean_constant(def p) |
---|
1218 | "USAGE: from_boolean_constant(pb); pb pyobject |
---|
1219 | RETURN: constant polynomial |
---|
1220 | SEE ALSO: boolean_ideal, boolean_std |
---|
1221 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
1222 | EXAMPLE: example from_boolean_constant; shows an example" |
---|
1223 | { |
---|
1224 | pyobject pb = p; |
---|
1225 | if (pb==0) { return (poly(0)); } |
---|
1226 | |
---|
1227 | return (poly(1)); |
---|
1228 | } |
---|
1229 | |
---|
1230 | example |
---|
1231 | { "EXAMPLE:"; echo = 2; |
---|
1232 | ring rs=0,(x,y,z),Dp; |
---|
1233 | def rsb=boolean_poly_ring(rs); |
---|
1234 | poly f=(x+y)*x+z; |
---|
1235 | bpoly pp=f; |
---|
1236 | from_boolean_constant(0); |
---|
1237 | from_boolean_constant(1); |
---|
1238 | from_boolean_constant(pp); |
---|
1239 | } |
---|
1240 | |
---|
1241 | /////////////////////////////////////////////////////////////////////// |
---|
1242 | |
---|
1243 | proc recursive_from_boolean_poly(def p) |
---|
1244 | "USAGE: recursive_from_boolean_poly(pb); pb boolean polynomial |
---|
1245 | RETURN: polynomial in Singular |
---|
1246 | SEE ALSO: from_boolean_poly, boolean_ideal, boolean_poly, from_boolean_ideal, |
---|
1247 | boolean_poly_ring |
---|
1248 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
1249 | EXAMPLE: example recursive_from_boolean_poly; shows an example" |
---|
1250 | { |
---|
1251 | pyobject pb = p; |
---|
1252 | |
---|
1253 | if (pb==0) { return(0); } |
---|
1254 | if (pb==1) { return(1); } |
---|
1255 | |
---|
1256 | int idx = int(pb.navigation().value()); |
---|
1257 | def p0=Polynomial(pb.set().subset0(idx)); |
---|
1258 | def p1 = Polynomial(pb.set().subset1(idx)); |
---|
1259 | |
---|
1260 | return (var(idx+1)*recursive_from_boolean_poly(p1)+recursive_from_boolean_poly(p0)); |
---|
1261 | } |
---|
1262 | |
---|
1263 | example |
---|
1264 | { "EXAMPLE:"; echo = 2; |
---|
1265 | ring rs=0,(x,y,z),Dp; |
---|
1266 | def rsb=boolean_poly_ring(rs); |
---|
1267 | poly f=(x+y)*x+z; |
---|
1268 | bpoly pp=f; |
---|
1269 | recursive_from_boolean_poly(pp); |
---|
1270 | |
---|
1271 | ring rs2=2,(x,y,z),Dp; |
---|
1272 | def rsb2=boolean_poly_ring(rs2); |
---|
1273 | poly f2=(x+y)*x+x; |
---|
1274 | bpoly pp2=f2; |
---|
1275 | recursive_from_boolean_poly(pp); |
---|
1276 | } |
---|
1277 | |
---|
1278 | ///////////////////////////////////////////////////////////////////////// |
---|
1279 | |
---|
1280 | proc poly2zdd(poly ps) |
---|
1281 | "USAGE: poly2zdd(poly ps); polynomial ps |
---|
1282 | RETURN: polynomial ps in zdd representation |
---|
1283 | SEE ALSO: boolean_poly, from_boolean_set |
---|
1284 | KEYWORDS: PolyBoRi, zero-supressed decision diagram |
---|
1285 | EXAMPLE: example poly2zdd; shows an example" |
---|
1286 | { |
---|
1287 | pyobject pp=boolean_poly(ps); |
---|
1288 | pyobject pset = pp.set(); |
---|
1289 | zdd result = from_boolean_set(pset); |
---|
1290 | return(result); |
---|
1291 | } |
---|
1292 | |
---|
1293 | example |
---|
1294 | { "EXAMPLE:"; echo = 2; |
---|
1295 | ring r=0,x(1..5),Dp; |
---|
1296 | poly f=(x(1)+1)*(x(2)+1)*(x(3)+1)*x(4)*x(5); |
---|
1297 | poly2zdd(f); |
---|
1298 | |
---|
1299 | poly g=x(3); |
---|
1300 | poly2zdd(g); |
---|
1301 | } |
---|
1302 | |
---|
1303 | ///////////////////////////////////////////////////////////////////////// |
---|
1304 | |
---|
1305 | proc zdd2poly(zdd ss) |
---|
1306 | "USAGE: zdd2poly(ss); zero-supressed decision diagram ss |
---|
1307 | RETURN: zdd ss in polynomial representation |
---|
1308 | SEE ALSO:from_boolean_poly, boolean_set |
---|
1309 | KEYWORDS: PolyBoRi, Boolean Groebner Basis |
---|
1310 | EXAMPLE: example poly2zdd; shows an example" |
---|
1311 | { |
---|
1312 | def ps=boolean_set(ss); |
---|
1313 | return(from_boolean_poly(Polynomial(ps))); |
---|
1314 | } |
---|
1315 | |
---|
1316 | example |
---|
1317 | { "EXAMPLE:"; echo = 2; |
---|
1318 | ring r=0,x(1..5),Dp; |
---|
1319 | poly f=(x(1)+1)*(x(2)+1)*(x(3)+1)*x(4)*x(5); |
---|
1320 | zdd2poly(poly2zdd(f)); |
---|
1321 | |
---|
1322 | poly g=x(3); |
---|
1323 | zdd2poly(poly2zdd(g)); |
---|
1324 | |
---|
1325 | poly g=0; |
---|
1326 | zdd2poly(poly2zdd(0)); |
---|
1327 | |
---|
1328 | poly g=1; |
---|
1329 | zdd2poly(poly2zdd(01)); |
---|
1330 | } |
---|
1331 | |
---|
1332 | ///////////////////////////////////////////////////////////////////////// |
---|
1333 | |
---|
1334 | proc disp_zdd(zdd ss, list #) |
---|
1335 | "USAGE: disp_zdd(ss); zero-supressed decision diagram ss |
---|
1336 | RETURN: string containing visualization of ss |
---|
1337 | NOTE: the resulting string is the visualization of the polynomial that corresponds |
---|
1338 | to ss, but with a additional structure that comes from the zdd. Every reached else- |
---|
1339 | Branch induces a new line in the string. |
---|
1340 | SEE ALSO:zdd2poly, poly2zdd |
---|
1341 | KEYWORDS: Polybori, Boolean Groebner Basis |
---|
1342 | EXAMPLE: example disp_zdd; shows an example" |
---|
1343 | { |
---|
1344 | int dist,i; |
---|
1345 | string str,space; |
---|
1346 | if (size(#)==0) |
---|
1347 | { |
---|
1348 | dist=1; |
---|
1349 | str=" "; |
---|
1350 | } |
---|
1351 | else |
---|
1352 | { |
---|
1353 | dist=#[1]; |
---|
1354 | str=#[2]; |
---|
1355 | } |
---|
1356 | for (i=1;i<=dist+3;i++) |
---|
1357 | { |
---|
1358 | space=space+" "; |
---|
1359 | } |
---|
1360 | if (ss.idx==0) |
---|
1361 | { |
---|
1362 | if (size(space)>5) |
---|
1363 | { |
---|
1364 | return(str); |
---|
1365 | } |
---|
1366 | else |
---|
1367 | { |
---|
1368 | if (ss==zdd_one) |
---|
1369 | { |
---|
1370 | return (1); |
---|
1371 | } |
---|
1372 | else |
---|
1373 | { |
---|
1374 | return (0); |
---|
1375 | } |
---|
1376 | } |
---|
1377 | } |
---|
1378 | else |
---|
1379 | { |
---|
1380 | str=str,"x",string(ss.idx); |
---|
1381 | if (ss.thenBranch.idx!=0) |
---|
1382 | { |
---|
1383 | str=str,"("; |
---|
1384 | str=disp_zdd(ss.thenBranch,dist+3,str); |
---|
1385 | str=str,")"; |
---|
1386 | } |
---|
1387 | if ((ss.elseBranch.idx!=0)||(ss.elseBranch==zdd_one)) |
---|
1388 | { |
---|
1389 | if (ss.elseBranch==zdd_one) |
---|
1390 | { |
---|
1391 | str=str+"+1"; |
---|
1392 | } |
---|
1393 | else |
---|
1394 | { |
---|
1395 | str=str,"+"+newline+space; |
---|
1396 | str=disp_zdd(ss.elseBranch,dist+3,str); |
---|
1397 | } |
---|
1398 | } |
---|
1399 | return(str); |
---|
1400 | } |
---|
1401 | } |
---|
1402 | |
---|
1403 | example |
---|
1404 | { "EXAMPLE:"; echo = 2; |
---|
1405 | ring r1=0,(x,y,z),Dp; |
---|
1406 | poly f1=xyz+xy+xz+yz+y+z+x+1; |
---|
1407 | zdd s1=f1; |
---|
1408 | disp_zdd(s1); |
---|
1409 | |
---|
1410 | ring r2=0,x(1..6),Dp; |
---|
1411 | poly f2=x(1)+x(2)+x(3)+x(5)^2+x(6); |
---|
1412 | zdd s2=f2; |
---|
1413 | disp_zdd(s2); |
---|
1414 | |
---|
1415 | ring r4=0,x(1..6),Dp; |
---|
1416 | poly f2=x(1)+1; |
---|
1417 | zdd s2=f2; |
---|
1418 | disp_zdd(s2); |
---|
1419 | |
---|
1420 | ring r2=0,x(1..6),Dp; |
---|
1421 | poly f2=x(1)*x(2)*(x(3)-x(5)^2*x(6))+3*x(4)*x(5)-3; |
---|
1422 | zdd s2=f2; |
---|
1423 | disp_zdd(s2); |
---|
1424 | |
---|
1425 | poly f4=0; |
---|
1426 | zdd s4=f4; |
---|
1427 | disp_zdd(s4); |
---|
1428 | |
---|
1429 | poly f5=1; |
---|
1430 | zdd s5=f5; |
---|
1431 | disp_zdd(s5); |
---|
1432 | } |
---|