Homework 07 - Multivariate Polynomials

Allowed libraries: sympy

Forbidden methods: sympy.polys.polytools.reduced, sympy.polys.polytools.groebner

1. Multivariate Polynomial Division Algorithm

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.

Input/Output specifications for poly_div:

  1. f : Poly object
  2. divs : list of Poly objects
  3. mo : String
  4. Return value : dictionary with 2 keys “q” and “r”, whose values according to the division algorithm are the list of quotient polynomials (list of Poly objects) and the remainder of the division (Poly object) w.r.t. the specified monomial ordering mo, respectively.
For the explanation of how to work with Poly objects see Sympy documentation.
According to Sympy documentation, monomial ordering mo can take the following values:
  1. “lex” - lexicographic order
  2. “grlex” - graded lexicographic order
  3. “grevlex” - graded reversed lexicographic order

2. Buchberger's Algorithm

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.

Input/Output specifications for groebner_basis:

  1. F : list of Poly objects
  2. mo : String
  3. Return value : list of Poly objects that is a Gröbner basis of F w.r.t. the specified monomial ordering mo.
Testing groebner_basis using sympy.polys.polytools.groebner: $$$$ If $F \subset \mathbb{Q}[x_1, \dots, x_n]$ is a set of polynomials and $\geq$ is a monomial ordering, then $G$ is a Groebner basis of the polynomial ideal $J = \langle F \rangle$ w.r.t. $\geq$ if

$$ 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

Upload a zip archive hw07.zip (via the course ware) containing the following files:

  1. hw07.py - python script containing the implemented function poly_div, groebner_basis
courses/pkr/labs/hw07.txt · Last modified: 2024/12/01 18:38 by korotvik