Opened 13 years ago

Closed 13 years ago

#3915 closed defect (fixed)

[with patch, positive review] PolyBoRi interface improvements

Reported by: malb Owned by: malb
Priority: major Milestone: sage-3.1.2
Component: commutative algebra Keywords: polybori
Cc: burcin Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

The attached patch

  • adds an interpolation_polynomial method to BooleanPolynomialRing
  • adds reduce methods to BooleanPolynomial and BooleanPolynomialIdeal
  • improves the documentation slightly
  • makes f in I work for f a BooleanPolynomial

Attachments (2)

pbori_improvements.patch (23.2 KB) - added by malb 13 years ago.
trac_3915_pbori_improvements.patch (23.3 KB) - added by mabshoff 13 years ago.
rebased patch of malb's - all that needed fixing was plot's parameter list

Download all attachments as: .zip

Change History (13)

comment:1 Changed 13 years ago by malb

oh, it also adds a _latex_ method to BooleanPolynomial

comment:2 Changed 13 years ago by PolyBoRi

  • Summary changed from [with patch, needs review] PolyBoRi interface improvements to [with patch, negative review] PolyBoRi interface improvements

The line:

g.minimalizeAndTailReduce()

is nearly meaningless, as it ignores the result. For having a reduced system set the keyword redsb=True for the groebner_basis call. Furthermore, your reduce implementation doesn't necessarily yield a unique (reduced) normal form. For PolyBoRi? >0.4 set strat.optRedTail=True for PolyBoRi? <0.4 apply p=red_tail(strat,p) to a normal form. Michael

comment:3 Changed 13 years ago by malb

  • Summary changed from [with patch, negative review] PolyBoRi interface improvements to [with patch, needs review] PolyBoRi interface improvements

Thanks for the review. The updated patch should address your comments.

comment:4 follow-up: Changed 13 years ago by PolyBoRi

  • Summary changed from [with patch, needs review] PolyBoRi interface improvements to [with patch, needs update] PolyBoRi interface improvements

Looks good, there is still some minor thing, I detected. But this is nothing about the patch, as it was buggy before:

It is possible to pass a deg_bound to groebner_basis . So the result is not garantied to be a GB. In this case it looks strange to set

self.__gb = g

maybe you can check this via

if kwds.get("deg_bound",False) is False:
  self.__gb = g

Then I'll give it a positive review. Michael

comment:5 follow-up: Changed 13 years ago by PolyBoRi

ups: still, comments regarding the patch: These are optional, as they only concern performance:

pbori.pyxline 3144

            s = sum([prod([x[i] for i in xrange(n) if v[i]],  
	            B.one_element()) for v in s],  
                    B.zero_element()) 
            s = s.set()

should be faster with

            s=BooleSet(sum([prod([x[i] for i in xrange(n) if v[i]],  
	            B.one_element()) for v in s]

However, you will have to handle the case of the empty set seperately(when there are no monomials) to make sure, that it is the right ring. I think, if we can make this easier upstream.

Furthermore, if you really want to be clever: The use of prod is quite unoptimal here. If you really want get these multiplications for variables fast, you should multiply them in this way: x1*(x2*(x3*x4))) So first use the indices behind. Note, that indices in PolyBoRi? don't have to be identical to those in sage/Singular lex, degree lex: identical dp(dp_asc): reversed. Blocks of degree lexicographical: identical Blocks of degree reverse lex. : reversed in each block, so quite strange (if it is correctly implemented in sage)

Changed 13 years ago by malb

comment:6 in reply to: ↑ 4 Changed 13 years ago by malb

  • Summary changed from [with patch, needs update] PolyBoRi interface improvements to [with patch, positive review] PolyBoRi interface improvements

Replying to PolyBoRi:

It is possible to pass a deg_bound to groebner_basis.

I check for deg_bound in the updated patch. Thanks a lot for your detailed criticism, it helps (me) a lot! I give the patch a positive review now, since you wrote:

Then I'll give it a positive review. Michael

comment:7 in reply to: ↑ 5 ; follow-up: Changed 13 years ago by malb

Replying to PolyBoRi:

ups: still, comments regarding the patch: These are optional, as they only concern performance:

pbori.pyxline 3144 s=BooleSet?(sum([prod([x[i] for i in xrange(n) if v[i]], B.one_element()) for v in s]

It seems we didn't implement BooleSet?(BooleanPolynomial?) in Sage. I'll check the upstream implementation and fix that.

If you really want get these multiplications for variables fast, you should multiply them in this way: x1*(x2*(x3*x4)))

I don't do anything fancy for now, but I reversed the order of the product. This might be faster in the normal case which is lex if I understand your comment correctly.

comment:8 in reply to: ↑ 7 Changed 13 years ago by PolyBoRi

It seems we didn't implement BooleSet?(BooleanPolynomial?) in Sage. I'll check the upstream implementation and fix that.

sorry, the line was long, without the sum: just

BooleSet([prod([x[i] for ...]

A BooleSet? is a set of monomials. It uses a more sophisticated addition.

If you really want get these multiplications for variables fast, you should multiply them in this way: x1*(x2*(x3*x4)))

I don't do anything fancy for now, but I reversed the order of the product. This might be faster in the normal case which is lex if I understand your comment correctly.

yes, it is much faster in Lex, even from a Python interpreter with boost::python calling overhead (in large examples, high degree monomials)

You have my positive review :-).

comment:9 Changed 13 years ago by mabshoff

  • Summary changed from [with patch, positive review] PolyBoRi interface improvements to [with patch, positive review, needs rebase] PolyBoRi interface improvements

I am seeing slight merge issues with my current alpha2 tree:

mabshoff@sage:/scratch/mabshoff/release-cycle/sage-3.1.2.alpha2/devel/sage$ patch -p1 < trac_3915_pbori_improvements.patch
patching file sage/rings/polynomial/multi_polynomial_ideal.py
Hunk #1 FAILED at 391.
Hunk #2 succeeded at 1948 (offset 47 lines).
1 out of 2 hunks FAILED -- saving rejects to file sage/rings/polynomial/multi_polynomial_ideal.py.rej

The failing hunk deletes contains, so this should be easy to rebase.

Cheers,

Michael

comment:10 Changed 13 years ago by mabshoff

  • Summary changed from [with patch, positive review, needs rebase] PolyBoRi interface improvements to [with patch, positive review] PolyBoRi interface improvements

Martin suggested in IRC just to delete the hunk that fails to apply manually. The reject is cause by some other code being applied in alpha2, so I will sort this out by posting an updated patch of Martin's patch and a second patch that deletes the hunk in question.

Cheers,

Michael

Changed 13 years ago by mabshoff

rebased patch of malb's - all that needed fixing was plot's parameter list

comment:11 Changed 13 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged trac_3915_pbori_improvements.patch in Sage 3.1.2.alpha2

Note: See TracTickets for help on using tickets.