Update PolyBoRi to newest upstream release

[malb]

2009/04/06 The first release candidate of PolyBoRi 0.6 is available 
for download. It comes with a PEP8-conforming python interface and 
new algorithms: FGLM and (experimental) parallel processing of 
Gröbner basis variants. In addition, the documentation was improved 
considerably: the tutorial is more extensive, and the TeX4ht-
Support has been improved. Finally, built-in support for plotting 
the underlying decision diagrams has been added.

This version also allows bigger systems to be solved using the M4RI library (due to an updated M4RI) and makes use of M4RI in shared library mode.

This ticket depends on #5510

CC: @sagetrac-PolyBoRi @burcin @rlmill @boothby

Component: packages: standard

Keywords: M4RI, PolyBoRi

Author: Michael Brickenstein, Alexander Dreyer, Martin Albrecht

Reviewer: David Kirkby, Alex Ghitza, Burcin Erocal, Minh Van Nguyen

Merged: Sage 4.1.2.alpha2

Issue created by migration from https://trac.sagemath.org/ticket/6177

[malb]

Description changed:

--- 
+++ 
@@ -1,6 +1,12 @@

-2009/04/06 The first release candidate of PolyBoRi 0.6 is available for download. It comes with a PEP8-conforming python interface and new algorithms: FGLM and (experimental) parallel processing of Gröbner basis variants. In addition, the documentation was improved considerably: the tutorial is more extensive, and the TeX4ht-Support has been improved. Finally, built-in support for plotting the underlying decision diagrams has been added. +2009/04/06 The first release candidate of PolyBoRi 0.6 is available +for download. It comes with a PEP8-conforming python interface and +new algorithms: FGLM and (experimental) parallel processing of +Gröbner basis variants. In addition, the documentation was improved +considerably: the tutorial is more extensive, and the TeX4ht- +Support has been improved. Finally, built-in support for plotting +the underlying decision diagrams has been added.

 This version also allows bigger systems to be solved using the M4RI library (due to an updated M4RI) and makes use of M4RI in shared library mode.

[malb]

comment:2

The SPKG is here:

http://sage.math.washington.edu/home/malb/spkgs/polybori-0.6.spkg

[malb]

comment:3

TODO:

• write more documentation
• fix FGLM (it doesn't do anything right now)
• expose PolyBoRi ZDD plots

[malb]

comment:4

Michael's notes on the docs:

all_spolys_in_next_degree()
pops all spolys with next sugar degree from the strategy 

clean_top_by_chain_criterion()

contains_one()
1 \in generating system?

faugere_step_dense()
reduces a vector of polynomials using linear algebra

implications()
computes useful implied polynomials of i-th generator, and adds them  to the strategy, if it finds any.

ll_reduce_all()
uses the build in ll-encoded BooleSet of polynomials with linear lexicographical leading term, which coincides  
with leading term in current ordering, to reduce the tails of all polynomials in the strategy

minimalize()
returns a vector of all polynomials with minimal leading terms use that if strat contains a GB

minimalize_and_tail_reduce()
returns a vector of all polynomials with minimal leading terms and does tail reductions use that if strat contains a GB and you want a reduced GB

next_spoly()

nf()

npairs()
Number of pairs in the pair queue

reduction_strategy
ReductionStrategy member of GroebnerStrategy, does all the reductions

small_spolys_in_next_degree()
I am not sure, if it is still used, similar to the next one

some_spolys_in_next_degree(n)

fetches upto n s-polynomials from the strategy, having all a sugar  
value <= the sugar value of the first polynomial/pair in the queue.

suggest_plugin_variable()
some heuristic to suggest a variable, which could be plugged with 0 and 1 to branch the computation

symmGB_F2()
out of date C++ implementation of symmgb, will revived at some point of time

top_sugar()
sugar value of the first "pair" in the queue. Sugar is "some estimated degree".

variable_has_value()
Computes, whether, there exists some polynomial of the form $v+c$ in the Strategy, where c is a constant
in the list of generators

elength()
x+y*z -> 3
for lp (x>y>z)
the interesting case

Note

If this function is called repeatedly with the same I then it is  
advised to use PolyBoRi’s GroebnerStrategy object directly, since that  
will be faster. See the source code of this function for details.

-> ReductionStrategy, as it is smaller and contains everything needed  
for reductions.

[malb]

comment:5

More notes by Michael:

Can you please link: http://polybori.sourceforge.net/zdd.html

A picture says more, than 1000 words.

2. How is the pickling of Boolean polynomials done?

Have a look at parallel.py:

def to_fast_pickable(l):
     """
     to_fast_pickable(l) converts a list of polynomials into a builtin  
Python value, which is fast pickable and compact.
     INPUT:
         - a list of Boolean polynomials
     OUTPUT:
         It is converted to a tuple consisting of
         - codes referring to the polynomials
         - list of conversions of nodes.
             The nodes are sorted, that
             n occurs before n.else_branch(), n.then_branch()
             Nodes are only listed, if they are not constant.

         A node is converted in this way:
             0 -> 0
             1 -> 1
             if_then_else(v,t,e) -> (v, index of then branch +2, index of else branch +2)
             The shift of +2 is for the constant values implicitly   contained in the list.
         Each code c refers to the c-2-th position in the conversion   list, if c >=2, else to
         the corresponding Boolean constant if c in {0, 1}
     EXAMPLES:
         >>> from polybori.PyPolyBoRi import Ring, Variable
         >>> r=Ring(1000)
         >>> x=Variable
         >>> to_fast_pickable([Polynomial(1)])
         [[1], []]
         >>> to_fast_pickable([Polynomial(0)])
         [[0], []]
         >>> to_fast_pickable([x(0)])
         [[2], [(0, 1, 0)]]
         >>> to_fast_pickable([x(0)*x(1)+x(1)])
         [[2], [(0, 3, 3), (1, 1, 0)]]
         >>> to_fast_pickable([x(1)])
         [[2], [(1, 1, 0)]]
         >>> to_fast_pickable([x(0)+1])
         [[2], [(0, 1, 1)]]
         >>> to_fast_pickable([x(0)*x(1)])
         [[2], [(0, 3, 0), (1, 1, 0)]]
         >>> to_fast_pickable([x(0)*x(1)+x(1)])
         [[2], [(0, 3, 3), (1, 1, 0)]]
         >>> to_fast_pickable([x(0)*x(1)+x(2)])
         [[2], [(0, 3, 4), (1, 1, 0), (2, 1, 0)]]
         >>> p=x(5)*x(23) + x(5)*x(24)*x(59) + x(5) + x(6)*x(23)*x(89)   + x(6)*x(60)*x(89) + x(23) + x(24)*x(89) + x(24) + x(60)*x(89) + x(89)   + 1
         >>> from_fast_pickable(to_fast_pickable([p]))==[p]
         True
         >>> to_fast_pickable([x(0)*x(1), Polynomial(0), Polynomial(1), x(3)])
         [[2, 0, 1, 4], [(0, 3, 0), (1, 1, 0), (3, 1, 0)]]
     """

[malb]

comment:6

Btw. I'm posting this all here because I might not get around to do the last required steps in the next 2 weeks.

[malb]

comment:7

Burcin, I came across the RingProxy class which we add to PyPolyBori.py. I don't understand why we need this.

[burcin]

comment:8

AFAIR, the global_ring() function you see in that file is expected to return an object which has a .set() method. This method should change the ordering of the current ring. I didn't want to add a .set() method to the BooleanPolynomialRing, so decided to wrap it in a RingProxy class.

Of course, this was centuries ago, and it's possible that I'm making up all that I wrote above. :)

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:9

I just ported the plotting to the jinja template engine, which is contained in Sage. The only missing dependency is graphviz, which is an optional package. I hope that helps integrating it. I really would wish to be able to plot ZDDs in the Sage notebook. That would be a nice extra feature and would probably help much about the understanding of ZDDs.

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

plot.py patch for jinja, to be contained in a 0.6.2 release (hopefully soon)

[malb]

comment:10

Attachment: jinja.patch.gz

CCing Robert Miller since he is the resident graph expert and is sitting like two seats next to me. Robert, the last two comments are about printing the decision diagrams used by PolyBoRi to represent polynomials, cf. http://polybori.sourceforge.net/zdd.html

[malb]

comment:11

Burcin, I just uploaded my current PolyBoRi SPKG to /home/malb/spkgs so all you should need is the this SPKG + the patch polybori_0_6_1.patch

[malb]

Attachment: polybori_0_6_1.patch.gz

most recent version of the patch

[89c6e537-b2e3-45e6-882d-d4957b74ffe5]

comment:12

CCing Tom Boothby, because he loves decision diagrams for polynomials.

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:13

Hi! Just as a further motivation :-) : That is, how the diagrams will look like. http://polybori.sourceforge.net/zdd.html Michael

[malb]

comment:14

The requires SPKG is available at

http://sage.math.washington.edu/home/malb/spkgs/polybori-0.6.3-20090728.spkg

Only apply polybori-0-6-3.patch.

[malb]

comment:15

See http://groups.google.com/group/sage-support/browse_thread/thread/fa3afaeff5444cf3 for a problem description.

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:16

doesn't build for me (Mac OS X, 64 BIT, but it's not an 64 BIT issue). I have to set FORCE_HASH_MAP=True via custom.py or construct argument.

g++ -o groebner/src/groebner.o -c -m64 -O3 -Wno-long-long -Wreturn-type -g -fPIC -ftemplate-depth-100 -g -fPIC -m64 -O3 -Wno-long-long -Wreturn-type -g -fPIC -DNDEBUG -DHAVE_TR1_UNORDERED_MAP -DPACKED -DHAVE_M4RI -DSIZEOF_VOID_P=8 -DSIZEOF_LONG=8 -DHAVE_IEEE_754 -I/Applications/sage/spkg/build/polybori-0.6.3-20090728/src/boost_1_34_1.cropped -I/Applications/sage/local/include -I/Applications/sage/local/include/python2.6 -Ipolybori/include -IM4RI -ICudd/obj -ICudd/util -ICudd/cudd -ICudd/mtr -ICudd/st -ICudd/epd groebner/src/groebner.cc
/usr/include/c++/4.0.0/tr1/hashtable: In member function 'typename std::tr1::hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys>::const_iterator std::tr1::hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys>::find(const Key&) const [with Key = polybori::BooleExponent, Value = std::pair<const polybori::BooleExponent, int>, Allocator = std::allocator<std::pair<const polybori::BooleExponent, int> >, ExtractKey = Internal::extract1st<std::pair<const polybori::BooleExponent, int> >, Equal = std::equal_to<polybori::BooleExponent>, H1 = polybori::hashes<polybori::BooleExponent>, H2 = Internal::mod_range_hashing, H = Internal::default_ranged_hash, RehashPolicy = Internal::prime_rehash_policy, bool cache_hash_code = false, bool mutable_iterators = true, bool unique_keys = true]':
groebner/src/groebner_alg.h:267:   instantiated from here
/usr/include/c++/4.0.0/tr1/hashtable:1135: error: passing 'const std::tr1::hashtable<polybori::BooleExponent, std::pair<const polybori::BooleExponent, int>, std::allocator<std::pair<const polybori::BooleExponent, int> >, Internal::extract1st<std::pair<const polybori::BooleExponent, int> >, std::equal_to<polybori::BooleExponent>, polybori::hashes<polybori::BooleExponent>, Internal::mod_range_hashing, Internal::default_ranged_hash, Internal::prime_rehash_policy, false, true, true>' as 'this' argument of 'typename std::tr1::hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys>::node* std::tr1::hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys>::find_node(Internal::hash_node<Value, cache_hash_code>*, const Key&, typename std::tr1::hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys>::hash_code_t) [with Key = polybori::BooleExponent, Value = std::pair<const polybori::BooleExponent, int>, Allocator = std::allocator<std::pair<const polybori::BooleExponent, int> >, ExtractKey = Internal::extract1st<std::pair<const polybori::BooleExponent, int> >, Equal = std::equal_to<polybori::BooleExponent>, H1 = polybori::hashes<polybori::BooleExponent>, H2 = Internal::mod_range_hashing, H = Internal::default_ranged_hash, RehashPolicy = Internal::prime_rehash_policy, bool cache_hash_code = false, bool mutable_iterators = true, bool unique_keys = true]' discards qualifiers
scons: *** [groebner/src/groebner.o] Error 1

[malb]

fixes the issue

[malb]

comment:17

Attachment: polybori-0-6-3.patch.gz

The attached patch fixes the wrong GB issue.

[malb]

comment:18

Replying to @sagetrac-PolyBoRi:

doesn't build for me (Mac OS X, 64 BIT, but it's not an 64 BIT issue). I have to set FORCE_HASH_MAP=True via custom.py or construct argument.

Is that a bug in PolyBoRi or how we build it?

[malb]

comment:19

It seems some const is dropped somewhere which makes the C++ compiler choke?

passing 'const std::tr1::hashtable<... as 'this' argument of 'typename std::tr1::hashtable<Key, Valu ...  discards qualifiers

[malb]

comment:20

Michael suggested to pass

scons  FORCE_HASH_MAP=True

on OSX only to work around this issue.

I can't work on this in the near future and would appreciate if someone else could take care of this.

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:21

Hi! I have put a new spkg here:

http://sage.math.washington.edu/home/bricken/polybori-0.6.3-20090806.spkg I have adjusted the custom.py. Actually, I needed most time, until I noticed, that the patched SConstruct was outdated, which I have fixed.

May I ask, what you have fixed about the wrong results due to some interface issues?

Michael

[malb]

comment:22

I added a new term ordering "deglex_asc" which is used instead of "degrevlex" if a Sage ring is constructed from a C++ ring. Also, I changed the hash to include the term ordering.

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:23

'sage.rings.polynomial.pbori.BooleanPolynomialRing' object has no attribute 'clone' The clone method is not wrapped, which does not give us access to our new ll-stuff, which is also very relevant to crypto. I just had a look at the present stuff and tried to speed it up.

[malb]

comment:24

I checked in Michael's changes in the SPKG in

http://sage.math.washington.edu/home/malb/spkgs/polybori-0.6.3-20090807.spkg

under Michael's name.

My Todo List

• wrap clone
• wrap ll_red_nf_noredsb_single_recursive_call
• speed-up Polynomial(p) if p is a boolean polynomial
• check for memory leaks with crypo scripts from bitbucket

[malb]

comment:25

Attachment: polybori-0-6-3.2.patch.gz

The latest patch links in gd

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:26

I have to add that also substitute_variables(vec, poly) is missing, which is an instantiation of substitute_variables<std::vector, BoolePolynomial>

var(i) (our polybori indices) is replaced by vec[i] in poly.

docs:

BoolePolyRing::clone is a flat copy of the ring, as well as the normal copy constructor. In contrast to using the constructor, the new ring will contain its own vector of variable names, so changing a variable name via set_variable_name won't modify the original ring.

ll_red_nf_noredsb_single_recursive call has the same specification as ll_red_nf_noredsb, but a different implementation: This is described in my PHD thesis, the corresponding chapter is available on demand. It is very sensitive to the ordering of variables, however it has the very nice property, that it needs just one recursive call. We provide utilities for determing an appropriate var ordering. It is a matter of research, to find good heuristics here. But I think, that I have a good solution.

[malb]

Attachment: polybori-0-6-3.3.patch.gz

adds the requested functions

[malb]

comment:27

The new patch in combination with http://sage.math.washington.edu/home/malb/spkgs/polybori-0.6.3-20090810.spkg provides the following additional features:

• Polynomial(p) much faster if p is a BooleanPolynomial
• added substitute_variables
• added BooleanPolynomialRing.clone
• added ll_red_nf_noredsb_single_recursive

[malb]

the latest patch swallowed the 'gd' in modules_list.py, this one adds it back

[malb]

Attachment: polybori-0-6-3.4.patch.gz

Attachment: polybori-0-6-3.5.patch.gz

speeds up comparison with zero and fixes a doctest failure

[malb]

comment:28

If one doesn't have #6628 applied one hunk will fail which can safely be ignored.

[bac7d3ea-3f1b-4826-8464-f0b53d5e12d2]

comment:29

This appears to suffer the same issue earlier releases of PolyBoRi had on Solaris. Even if the Sun Studio compiler is not in the path, and CC, CXX are not set, so this attempts to use the Sun C++ compiler. That fails miserably.

Changes had to be made to the earlier PolyBoRi code to allow this to build with gcc on Solaris if the Sun compiler was present. I assume those changes will need to be reintegrated.

Here you can see CC and CXX are not set

drkirkby@smudge:[~/sage/sage-4.1.1] $ echo $CC

drkirkby@smudge:[~/sage/sage-4.1.1] $ echo $CXX

drkirkby@smudge:[~/sage/sage-4.1.1] $

But still the package uses Sun's C++ compiler.

/opt/sunstudio12.1/bin/CC -o polybori/src/BoolePolyRing.o -c -O3 -Wno-long-long -Wreturn-type -g -fPIC -ftemplate-depth-100 -g -fPIC -O3 -Wno-long-long -Wreturn -type -g -fPIC -DNDEBUG -DHAVE_GD -DPACKED -DHAVE_M4RI -DHAVE_GD -DHAVE_IEEE_754  -DBSD -I/export/home/drkirkby/sage/sage-4.1.1/spkg/build/polybori-0.6.3-2009081 0/src/boost_1_34_1.cropped -I/export/home/drkirkby/sage/sage-4.1.1/local/include  -I/export/home/drkirkby/sage/sage-4.1.1/local/include/python2.6 -Ipolybori/incl ude -ICudd/obj -ICudd/util -ICudd/cudd -ICudd/mtr -ICudd/st -ICudd/epd polybori/ src/BoolePolyRing.cc
CC: Warning: Option -Wno-long-long passed to ld, if ld is invoked, ignored other wise
CC: Warning: Option -Wreturn-type passed to ld, if ld is invoked, ignored otherw ise
CC: Warning: Option -fPIC passed to ld, if ld is invoked, ignored otherwise
CC: Warning: Option -ftemplate-depth-100 passed to ld, if ld is invoked, ignored  otherwise
CC: Warning: Option -fPIC passed to ld, if ld is invoked, ignored otherwise
CC: Warning: Option -Wno-long-long passed to ld, if ld is invoked, ignored other wise
CC: Warning: Option -Wreturn-type passed to ld, if ld is invoked, ignored otherw ise
CC: Warning: Option -fPIC passed to ld, if ld is invoked, ignored otherwise
"polybori/include/CDDManager.h", line 103: Warning: Last line in file "polybori/ include/cacheopts.h" is not terminated with a newline.
"polybori/include/CCuddZDD.h", line 308: Warning (Anachronism): Formal argument func of type DdNode*(*)(DdManager*,DdNode*,int) in call to polybori::CCuddDDBase <polybori::CCuddZDD>::apply(DdNode*(*)(DdManager*,DdNode*,int), int) const is be ing passed extern "C" DdNode*(*)(DdManager*,DdNode*,int).
"polybori/include/CCuddZDD.h", line 308: Warning (Anachronism): Formal argument func of type DdNode*(*)(DdManager*,DdNode*,int) in call to polybori::CCuddDDBase <polybori::CCuddZDD>::apply(DdNode*(*)(DdManager*,DdNode*,int), int) const is be ing passed extern "C" DdNode*(*)(DdManager*,DdNode*,int).
"polybori/include/CCuddZDD.h", line 308: Warning (Anachronism): Formal argument func of type DdNode*(*)(DdManager*,DdNode*,int) in call to polybori::CCuddDDBase <polybori::CCuddZDD>::apply(DdNode*(*)(DdManager*,DdNode*,int), int) const is be ing passed extern "C" DdNode*(*)(DdManager*,DdNode*,int).
"polybori/include/CCuddZDD.h", line 313: Warning (Anachronism): Formal argument func of type DdNode*(*)(DdManager*,DdNode*,DdNode*,DdNode*) in call to polybori: :CCuddDDBase<polybori::CCuddZDD>::apply(DdNode*(*)(DdManager*,DdNode*,DdNode*,Dd Node*), const polybori::CCuddZDD&, const polybori::CCuddZDD&) const is being pas sed extern "C" DdNode*(*)(DdManager*,DdNode*,DdNode*,DdNode*).
"polybori/include/CCuddZDD.h", line 322: Warning (Anachronism): Formal argument func of type int(*)(DdManager*,DdNode*) in call to polybori::CCuddDDBase<polybor i::CCuddZDD>::apply(int(*)(DdManager*,DdNode*)) const is being passed extern "C"  int(*)(DdManager*,DdNode*).
"polybori/include/CCuddZDD.h", line 323: Warning (Anachronism): Formal argument func of type int(*)(DdManager*,DdNode*) in call to polybori::CCuddDDBase<polybor i::CCuddZDD>::apply(int(*)(DdManager*,DdNode*)) const is being passed extern "C"  int(*)(DdManager*,DdNode*).
"polybori/include/CCuddZDD.h", line 327: Warning (Anachronism): Formal argument func of type int(*)(DdManager*,DdNode*) in call to polybori::CCuddDDBase<polybor i::CCuddZDD>::memApply<int>(int(*)(DdManager*,DdNode*)) const is being passed ex tern "C" int(*)(DdManager*,DdNode*).
"polybori/include/CCuddZDD.h", line 330: Warning (Anachronism): Formal argument func of type double(*)(DdManager*,DdNode*) in call to polybori::CCuddDDBase<poly bori::CCuddZDD>::memApply<double>(double(*)(DdManager*,DdNode*)) const is being passed extern "C" double(*)(DdManager*,DdNode*).
"polybori/include/CCuddInterface.h", line 192: Warning (Anachronism): Formal arg ument func of type DdNode*(*)(DdManager*,int) in call to polybori::CCuddInterfac e::apply(DdNode*(*)(DdManager*,int), int) const is being passed extern "C" DdNod e*(*)(DdManager*,int).
"polybori/include/CCuddInterface.h", line 195: Warning (Anachronism): Formal arg ument func of type DdNode*(*)(DdManager*,int) in call to polybori::CCuddInterfac e::apply(DdNode*(*)(DdManager*,int), int) const is being passed extern "C" DdNod e*(*)(DdManager*,int).
"polybori/include/CCuddInterface.h", line 198: Warning (Anachronism): Formal arg ument func of type DdNode*(*)(DdManager*) in call to polybori::CCuddInterface::a pply(DdNode*(*)(DdManager*)) const is being passed extern "C" DdNode*(*)(DdManag er*).
"polybori/include/CCuddNavigator.h", line 157: Error: iterator_traits is not a m ember of std.
"polybori/include/CCuddNavigator.h", line 157: Error: A declaration does not spe cify a tag or an identifier.
"polybori/include/CCuddNavigator.h", line 157: Error: Use ";" to terminate decla rations.
"polybori/include/CCuddNavigator.h", line 157: Error: "}" expected instead of "< ".
"polybori/include/CCuddNavigator.h", line 157: Error: Use ";" to terminate decla rations.
"polybori/include/CCuddNavigator.h", line 157: Error: A declaration was expected  instead of "<".
"polybori/include/CCuddNavigator.h", line 157: Error: "," expected instead of "> ".
"polybori/include/CCuddNavigator.h", line 159: Error: value_type is not defined.
"polybori/include/CCuddNavigator.h", line 163: Error: There must be an identifie r to declare.
"polybori/include/CCuddNavigator.h", line 171: Error: "explicit" is not allowed here.
"polybori/include/CCuddNavigator.h", line 171: Error: ")" expected instead of "& ".
"polybori/include/CCuddNavigator.h", line 174: Error: ")" expected instead of "& ".
"polybori/include/CCuddNavigator.h", line 177: Error: Type name expected instead  of "CCuddNavigator".
"polybori/include/CCuddNavigator.h", line 177: Error: Illegal number of argument s for ~file level().
"polybori/include/CCuddNavigator.h", line 180: Error: "," expected instead of "& ".
"polybori/include/CCuddNavigator.h", line 183: Error: self is not defined.
"polybori/include/CCuddNavigator.h", line 183: Error: The function "thenBranch()  const" cannot be declared const.
"polybori/include/CCuddNavigator.h", line 183: Error: Can only use this within a  non-static member function.
"polybori/include/CCuddNavigator.h", line 183: Error: Only a function may be cal led.
"polybori/include/CCuddNavigator.h", line 183: Error: Only a function may be cal led.
"polybori/include/CCuddNavigator.h", line 186: Error: Multiple declaration for s elf.
"polybori/include/CCuddNavigator.h", line 186: Error: "," expected instead of "& ".
"polybori/include/CCuddNavigator.h", line 189: Error: self is not defined.
"polybori/include/CCuddNavigator.h", line 189: Error: The function "elseBranch()  const" cannot be declared const.
"polybori/include/CCuddNavigator.h", line 189: Error: Can only use this within a  non-static member function.
Compilation aborted, too many Error messages.
scons: *** [polybori/src/BoolePolyRing.o] Error 1
scons: building terminated because of errors.
Error building PolyBoRi.

real    0m22.968s
user    0m17.385s
sys     0m4.811s
sage: An error occurred while installing polybori-0.6.3-20090810
Please email sage-devel http://groups.google.com/group/sage-devel
explaining the problem and send the relevant part of
of /export/home/drkirkby/sage/sage-4.1.1/install.log.  Describe your computer, o perating system, etc.
If you want to try to fix the problem, yourself *don't* just cd to
/export/home/drkirkby/sage/sage-4.1.1/spkg/build/polybori-0.6.3-20090810 and typ e 'make'.
Instead type "/export/home/drkirkby/sage/sage-4.1.1/sage -sh"
in order to set all environment variables correctly, then cd to
/export/home/drkirkby/sage/sage-4.1.1/spkg/build/polybori-0.6.3-20090810
(When you are done debugging, you can type "exit" to leave the
subshell.)
make[1]: *** [installed/polybori-0.6.3-20090810] Error 1
make[1]: Leaving directory `/export/home/drkirkby/sage/sage-4.1.1/spkg'

[bac7d3ea-3f1b-4826-8464-f0b53d5e12d2]

comment:30

If you are updating PolyBoRi, take a look at #6582 too.

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:31

I remember, that I used the SConstruct.patch to regenerate the patched SConstruct from a current version. Maybe someone has just hacked the fix into the patched SConstruct and ignored the patch?

Michael

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:32

Hi!

First of all, it is difficult to test the Sage-Wrapper using our tests, since Sage checks the variable names from time to time.

/Applications/sage/local/lib/python2.6/site-packages/polybori/gbcore.pyc in clean_polys(I)
    156     return make_wrapper
    157 def clean_polys(I):
--> 158     zero=Polynomial(0)
    159     I=list(set((Polynomial(p) for p in I if p!=zero)))
    160     return I

/Applications/sage/local/lib/python2.6/site-packages/sage/rings/polynomial/pbori.so in sage.rings.polynomial.pbori.PolynomialFactory.__call__ (sage/rings/polynomial/pbori.cpp:24232)()

/Applications/sage/local/lib/python2.6/site-packages/sage/rings/polynomial/pbori.so in sage.rings.polynomial.pbori.get_cring (sage/rings/polynomial/pbori.cpp:36518)()

/Applications/sage/local/lib/python2.6/site-packages/sage/rings/polynomial/pbori.so in sage.rings.polynomial.pbori.BooleanPolynomialRing_from_PBRing (sage/rings/polynomial/pbori.cpp:37213)()

/Applications/sage/local/lib/python2.6/site-packages/sage/rings/polynomial/multi_polynomial_ring_generic.so in sage.rings.polynomial.multi_polynomial_ring_generic.MPolynomialRing_generic.__init__ (sage/rings/polynomial/multi_polynomial_ring_generic.c:1913)()

/Applications/sage/local/lib/python2.6/site-packages/sage/structure/parent_gens.so in sage.structure.parent_gens.ParentWithGens.__init__ (sage/structure/parent_gens.c:2342)()

/Applications/sage/local/lib/python2.6/site-packages/sage/structure/parent_gens.so in sage.structure.parent_gens.ParentWithGens._assign_names (sage/structure/parent_gens.c:2830)()

/Applications/sage/local/lib/python2.6/site-packages/sage/structure/parent_gens.so in sage.structure.parent_gens.normalize_names (sage/structure/parent_gens.c:2068)()

/Applications/sage/local/lib/python2.6/site-packages/sage/structure/parent_gens.so in sage.structure.parent_gens._certify_names (sage/structure/parent_gens.c:1601)()

Furthermore the ring wrapper has no method n_variables, which is equivalent to ngens.

Michael

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:33

Hi! The following gives me a segfault:

from polybori import *
data=load_file("data/cook.py")

change_ordering(block_dp_asc)
append_ring_block(25)
groebner_basis(data.ideal, prot=True, heuristic=False)

------------------------------------------------------------
Unhandled SIGBUS: A bus error occured in SAGE.
This probably occured because a *compiled* component
of SAGE has a bug in it (typically accessing invalid memory)
or is not properly wrapped with _sig_on, _sig_off.
You might want to run SAGE under gdb with 'sage -gdb' to debug this.
SAGE will now terminate (sorry).
------------------------------------------------------------

sage.bin(2141) malloc: *** error for object 0x10ad1f000: incorrect checksum for freed object - object was probably modified after being freed.
*** set a breakpoint in malloc_error_break to debug
sage.bin(2141) malloc: *** error for object 0x10ad52000: incorrect checksum for freed object - object was probably modified after being freed.
*** set a breakpoint in malloc_error_break to debug
sage.bin(2141) malloc: *** error for object 0x10ad53800: incorrect checksum for freed object - object was probably modified after being freed.
*** set a breakpoint in malloc_error_break to debug

Used it on Mac OS X 10.5 64BIT.

I attach the example file

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

example for segfault

[malb]

Attachment: cook.py.gz

adds n_variables and fixes segfault

[malb]

comment:34

Attachment: polybori-0-6-3.6.patch.gz

The newest version of the patch fixes the segfault and adds n_variables. Note that both Michael and myself are using this patch for more than two weeks now in our research (see above for issues discovered and fixed this way), so it should be (almost) good to go. It mainly needs a review from the Sage side.

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:35

Replying to @malb:

The newest version of the patch fixes the segfault and adds n_variables. Note that both Michael and myself are using this patch for more than two weeks now in our research (see above for issues discovered and fixed this way), so it should be (almost) good to go. It mainly needs a review from the Sage side.

This is also my point of view. Thanks for the update. Michael

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:36

I have found another subtle bug. This is due to, that we are in the quite slow progress to make PolyBoRi more Pythonic: Since Python is dynamically typed, len should be the same on polynomials and monomials, so it's the constant 1-function for us now.

P=BooleanPolynomialRing(3,"x")
sage: m=P.gen(1)*P.gen(2)
sage: m.lead()
x1*x2
sage: len(m.lead())
2
sage: 
Exiting SAGE (CPU time 0m0.13s, Wall time 0m20.23s).

ginkgo:downloads michael$ ipbori

In [1]: p=x(1)*x(2)

In [2]: p.__class__
Out[2]: <class 'polybori.dynamic.PyPolyBoRi.Monomial'>

In [3]: len(p)
Out[3]: 1

Fixing that will break the anf2cnf converter here:

 isinstance(m, BooleanPolynomial):
            if len(m) == 1:
                m = m.lm()
            else:
                raise TypeError, "Input must be monomial."

        if m == 1:
            monomial = self._cnf_literal()
            return (monomial,), ((monomial,),) # adding the clause that 1
                                            # has to be True

Just use .deg instead of len there

[malb]

changes len(m) to be constant 1 if m is a monomial

[malb]

comment:37

Attachment: polybori-0-6-3.7.patch.gz

The attached patch fixes the issue (len(m) == 1 if m is a monomial). I don't see how it breaks anf2cnf but I'll check now (this is orthogonal to accepting this patch anyway)

[malb]

comment:38

Alright, I saw and fixed it on bitbucket (th anf2ncf issue)

[1998e663-c3b5-4cf6-92c3-7f1771ca5185]

comment:39

Hi!

In a similar way as the polynomial constructor, Variable is really slow:

timeit("Variable(0)")
25 loops, best of 3: 8.68 ms per loop

This is no release blocker,

but the following is a bug:

 BooleSet([Monomial()])
Out[1]: {}

correct would be

In [1]: BooleSet([Monomial()])
Out[1]: {{}}

This is implemented in PyPolyBoRi.py

[malb]

Attachment: polybori-0.6.3.patch.gz

rebased and bugfix

[malb]

comment:40

The new SPKG

http://sage.math.washington.edu/home/malb/spkgs/polybori-0.6.3-20090820.spkg

and the new patch polybori-0.6.3.patch improve the performance and fix the bug described above. However, I couldn't make Variable(0) faster because the main bottleneck for some reason is BooleEnv::ring() which we call to get the current ring. The code

  BoolePolyRing __pyx_v__pbring;
  //... some more other Cython stuff
  __pyx_v__pbring = BooleEnv::ring();

seems to be the bottleneck. Any ideas?