#13103: Makes BooleanPolynomial more compatible with MPolynomial
---------------------------------------+------------------------------------
Reporter: Bouillaguet | Owner: malb
Type: enhancement | Status: new
Priority: minor | Milestone: sage-5.1
Component: commutative algebra | Resolution:
Keywords: polybori | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Charles Bouillaguet | Merged in:
Dependencies: | Stopgaps:
---------------------------------------+------------------------------------
Comment (by Bouillaguet):
The cause of the bug in "positive" dimension (without the field equations)
is that BooleanPolynomialIdeal.groebner_basis() computes a groebner basis
'''modulo the field equations''', but this is not a Groebner basis in
general.
Obvious fix :
a) Compute GB modulo field equations with
BooleanPolynomialIdeal.groebner_basis()
b) cast to MPolynomial
c) Add field equations
d) use MPolynomial.variety()
This is guaranteed to be correct, but is probably a bit sub-optimal.
Adding the field equations may destroy the Groebner basis, but my guess is
that running the buchberger algorithm again should do little work.
This is implemented by the second patch.
Performance-wise, the gain is decent (as expected from the use of
PolyBoRi):
{{{
sage: n = 14
sage: R = BooleanPolynomialRing(n, ['x%d'%(i+1) for i in range(n)],
order='lex')
sage: polys = [ sum([ GF(2).random_element() * R.gen(i) * R.gen(j) for i
in range(n) for j in range(n)]) for k in range(n)]
sage: I = R.ideal( polys )
sage: time V1 = I.variety()
Time: CPU 0.51 s, Wall: 0.54 s
sage: R = PolynomialRing(GF(2), n, ['x%d'%(i+1) for i in range(n)],
order='lex')
sage: I = R.ideal( polys )
sage: time V2 = (I + sage.rings.ideal.FieldIdeal(R)).variety()
Time: CPU 9.12 s, Wall: 9.16 s
sage: V1 == V2
True
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13103#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
