# source:sage/rings/polynomial/polybori.pyx@7578:c647cb656137

Revision 7578:c647cb656137, 6.5 KB checked in by Burcin Erocal <burcin@…>, 6 years ago (diff)

Add more basic functionality to BooleanPolynomial?.

Line
1r"""
2Boolean Polynomials via PolyBoRi.
3
4We call boolean polynomials elements of the quotient ring
5
6    \$F_2[x_1,...,x_n]/<x_1^2+x_1,...,x_n^2+x_n>\$.
7
8AUTHOR:
9    -- Burcin Erocal <burcin@erocal.org>
10    -- Martin Albrecht <malb@informatik.uni-bremen.de>
11
12REFERENCES:
13    Michael Brickenstein, Alexander Dreyer; 'POLYBORI: A Groebner basis
14    framework for Boolean polynomials';
16
17"""
18
19include "../../ext/interrupt.pxi"
20include "../../ext/stdsage.pxi"
21include "../../ext/cdefs.pxi"
22include '../../libs/polybori/decl.pxi'
23
24from sage.structure.element cimport RingElement
25from sage.structure.element cimport ModuleElement
26
27from sage.rings.polynomial.multi_polynomial_ideal import MPolynomialIdeal
28from sage.rings.finite_field import GF
29
30order_dict= {"lp":      lp,
31             "dlex":    dlex,
32             "dp_asc":  dp_asc,
33             "bdlex":   block_dlex,
34             "bdp_asc": block_dp_asc,
35             }
36
37cdef class BooleanPolynomialRing(MPolynomialRing_generic):
38    """
39    Boolean Polynomial Ring.
40    """
41    def __init__(self, n, names, order='lp'):
42        cdef char *_n
43
44        PBRing_construct(&self._R, n, order_dict.get(order, lp))
45        MPolynomialRing_generic.__init__(self, GF(2), n, names, order)
46
47        for i in range(self.ngens()):
48            _n = self._names[i]
49            self._R.setRingVariableName(i,_n)
50
51        self._zero_element = new_BP(self)
52        PBPoly_construct_int(&(<BooleanPolynomial>self._zero_element)._P, 0)
53        self._one_element  = new_BP(self)
54        PBPoly_construct_int(&(<BooleanPolynomial>self._one_element)._P, 1)
55
56    def __dealloc__(self):
57        PBRing_destruct(&self._R)
58
59    def ngens(self):
60        return self._R.nVariables()
61
62    def gen(self, int n=0):
63        """
64        """
65        return new_BP_from_DD(self, self._R.variable(n))
66
67    def gens(self):
68        """
69        """
70        return [new_BP_from_DD(self, self._R.variable(i)) \
71                for i in xrange(self.ngens())]
72
73    def _repr_(self):
74        self._R.activate()
75        gens = ", ".join(map(str,self.gens()))
76        return "Boolean PolynomialRing in %s"%(gens)
77
78    cdef _coerce_c_impl(self, other):
79        """
80        """
81        cdef int i
82        cdef BooleanPolynomial p
83        i = int(other)
84        i = i % 2
85        p = new_BP(self)
86        PBPoly_construct_int(&p._P,i)
87        return p
88
89    def __call__(self, other):
90        return self._coerce_c(other)
91
92    def __hash__(self):
93        """
94        """
95        return hash(str(self))
96
97    def ideal(self, gens, coerce=True):
98        if coerce:
99            gens = [self(p) for p in gens]
100        return BooleanPolynomialIdeal(self, gens)
101
102cdef class BooleanPolynomial(MPolynomial):
103    def __init__(self, parent):
104        PBPoly_construct(&self._P)
105        self._parent = <ParentWithBase>parent
106
107    def __dealloc__(self):
108        PBPoly_destruct(&self._P)
109
110    def __repr__(self):
111        (<BooleanPolynomialRing>self._parent)._R.activate()
112        return str(PBPoly_to_str(&self._P))
113
114    cdef ModuleElement _add_c_impl(left, ModuleElement right):
115        cdef BooleanPolynomial p = new_BP((<BooleanPolynomial>left)._parent)
117        return p
118
119    cdef ModuleElement _sub_c_impl(left, ModuleElement right):
121
122    cdef ModuleElement _rmul_c_impl(self, RingElement left):
123        if left:
124            return new_BP_from_PBPoly(left._parent, self._P)
125        else:
126            return 0
127
128    cdef ModuleElement _lmul_c_impl(self, RingElement right):
129        return self._rmul_c_impl(right)
130
131    cdef RingElement _mul_c_impl(left, RingElement right):
132        cdef BooleanPolynomial p = new_BP((<BooleanPolynomial>left)._parent)
133        p._P = PBPoly_mul((<BooleanPolynomial>left)._P, (<BooleanPolynomial>right)._P)
134        return p
135
136    def __pow__(BooleanPolynomial self, int exp, ignored):
137        """
138        """
139        if exp > 0:
140            return self
141        elif exp == 0:
142            return self._parent._one_element
143        elif self._P.isConstant():
144            return self
145        else:
146            raise NotImplementedError, "Negative exponents for non constant polynomials are not implemented."
147
148
149    def __neg__(BooleanPolynomial self):
150        """
151        """
152        return self
153
154    def total_degree(BooleanPolynomial self):
155        """
156        """
157        return self._P.deg()
158
159    def lm(BooleanPolynomial self):
160        """
161        """
163
164    def lt(BooleanPolynomial self):
165        """
166        """
167        return self.lm()
168
169    def is_zero(BooleanPolynomial self):
170        """
171        """
172        return self._P.isZero()
173
174    def is_one(BooleanPolynomial self):
175        """
176        """
177        return self._P.isOne()
178
179    def is_unit(BooleanPolynomial self):
180        """
181        """
182        return self._P.isOne()
183
184class BooleanPolynomialIdeal(MPolynomialIdeal):
185    def __init__(self, ring, gens=[], coerce=True):
186        MPolynomialIdeal.__init__(self, ring, gens, coerce)
187
188    def groebner_basis(self):
189        return groebner_basis_c_impl(self.ring(), self.gens())
190
191cdef groebner_basis_c_impl(BooleanPolynomialRing R, g):
192    cdef int i
193    cdef PBPoly t
194    cdef BooleanPolynomial p, r
195    cdef PBPoly_vector vec
196    cdef GBStrategy strat
197
198    GBStrategy_construct(&strat)
199    for p in g:
201    strat.symmGB_F2()
202    vec = strat.minimalize()
203    lvec = vec.size()
204    res = []
205    for i from 0 <= i < lvec:
206        r = new_BP_from_PBPoly(R, vec.get(i) )
207        res.append(r)
208    return res
209
210cdef inline BooleanPolynomial new_BP(BooleanPolynomialRing parent):
211    cdef BooleanPolynomial p
212    p = <BooleanPolynomial>PY_NEW(BooleanPolynomial)
213    p._parent = parent
214    return p
215
216cdef inline BooleanPolynomial new_BP_from_DD(BooleanPolynomialRing parent, PBDD juice):
217    """
218    Construct a new BooleanPolynomial element
219    """
220    cdef BooleanPolynomial p = new_BP(parent)
221    PBPoly_construct_dd(&p._P,juice)
222    return p
223
224cdef inline BooleanPolynomial new_BP_from_PBPoly(BooleanPolynomialRing parent, PBPoly juice):
225    """
226    Construct a new BooleanPolynomial element
227    """
228    cdef BooleanPolynomial p = new_BP(parent)
229    PBPoly_construct_pbpoly(&p._P,juice)
230    return p
231
232cdef inline BooleanPolynomial new_BP_from_PBMonom(BooleanPolynomialRing parent, PBMonom juice):
233    """
234    Construct a new BooleanPolynomial element
235    """
236    cdef BooleanPolynomial p = new_BP(parent)
237    PBPoly_construct_pbmonom(&p._P,juice)
238    return p
239
Note: See TracBrowser for help on using the repository browser.