Search
Forbidden methods: sympy.polys.polytools.reduced, sympy.polys.polytools.groebner
Implement the multivariate polynomial division algorithm for more than one divisor.
Create a function poly_div(f, divs, mo) for dividing the polynomial f by the list of polynomials divs using the specified monomial ordering mo.
poly_div(f, divs, mo)
f
divs
mo
Input/Output specifications for poly_div:
poly_div
Poly
“q”
“r”
“lex”
“grlex”
“grevlex”
Implement the Buchberger's algorithm (or its improved version) for Gröbner basis computation.
Create a function groebner_basis(F, mo) for computing a Gröbner basis of the list of polynomials F w.r.t. the monomial ordering mo.
groebner_basis(F, mo)
F
Input/Output specifications for groebner_basis:
groebner_basis
sympy.polys.polytools.groebner
$$ G \subset J \quad \text{and} \quad \langle \{\mathrm{LM}_{\geq}(g) \;|\; g \in G \} \rangle = \langle \{\mathrm{LM}_{\geq}(f) \;|\; f \in J\} \rangle. $$
Such a definition implies that $G$ is another generating set of $J$, i.e. $\langle G \rangle = J$. Hence if we have a Groebner basis $G$ of $J$ and a subset $G' \subset J$ which we would like to test for being a Groebner basis of $J$, we need to verify that
$$ G' \subset \langle G \rangle \quad \text{and} \quad \langle \{\mathrm{LM}_{\geq}(g') \;|\; g' \in G' \} \rangle = \langle \{\mathrm{LM}_{\geq}(g) \;|\; g \in G \} \rangle. $$
In order to test whether $G' \subset \langle G \rangle$ we can use another property of a Groebner basis which states that
$$ f \in \langle G \rangle \iff \overline{f}^{(G, \geq)} = 0, $$
where $\overline{f}^{(G, \geq)}$ is the remainder of the division of $f$ by $G$ w.r.t. $\geq$. As for the equality of monomial ideals (i.e. ideals generated by monomials), if we have two sets of monomials $M_1$ and $M_2$, then
$$ \langle M_1 \rangle \subset \langle M_2 \rangle \iff \forall \mathbf{x}^{\boldsymbol{\alpha}} \in M_1: \;\exists \mathbf{x}^{\boldsymbol{\beta}} \in M_2: \;\mathbf{x}^{\boldsymbol{\beta}} \;|\; \mathbf{x}^{\boldsymbol{\alpha}}, $$
where the notation $\mathbf{x}^{\boldsymbol{\beta}} \;|\; \mathbf{x}^{\boldsymbol{\alpha}}$ means that $\mathbf{x}^{\boldsymbol{\beta}}$ divides $\mathbf{x}^{\boldsymbol{\alpha}}$. The equality $\langle M_1 \rangle = \langle M_2 \rangle$ can be then checked by verifying that the two inclusions hold true.
Upload a zip archive hw07.zip (via the course ware) containing the following files:
hw07.zip
hw07.py