~~NOTOC~~

===== Homework 07 - Multivariate Polynomials =====

<note warning>
**Allowed libraries**: sympy

**Forbidden methods**: sympy.polys.polytools.reduced, sympy.polys.polytools.groebner
</note>

==== 1. Multivariate Polynomial Division Algorithm ====

Implement the {{courses:pkr:labs:hw07-polydiv.pdf|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'':
  - ''f'' : ''Poly'' object
  - ''divs'' : list of ''Poly'' objects
  - ''mo'' : String
  - **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.

<note tip>

For the explanation of how to work with ''Poly'' objects see [[https://docs.sympy.org/latest/modules/polys/reference.html|Sympy documentation]].

</note>

<note>

According to [[https://docs.sympy.org/latest/modules/polys/reference.html|Sympy documentation]], monomial ordering ''mo'' can take the following values:
    - ''"lex"''       - lexicographic order
    - ''"grlex"''     - graded lexicographic order
    - ''"grevlex"''   - graded reversed lexicographic order

</note>

==== 2. Buchberger's Algorithm ====

Implement the {{courses:pkr:labs:hw07-buchberger.pdf|Buchberger's algorithm}} (or its {{courses:pkr:labs:hw07-improved-buchberger.pdf|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'':
  - ''F'' : list of ''Poly'' objects
  - ''mo'' : String
  - **Return value** : list of ''Poly'' objects that is a Gröbner basis of ''F'' w.r.t. the specified monomial ordering ''mo''.

<note tip>

**1. Verifying that the return value of ''groebner_basis'' is a Groebner basis (of some polynomial system)**:
$$$$
Suppose $G = (g_1, \dots, g_t)$ is an ordered tuple of polynomials from $\mathbb{Q}[x_1,\dots,x_n]$. Then $G$ is a Groebner basis w.r.t. a monomial ordering $\geq$ if and only if

$$ \overline{S_{\geq}(g_i, g_j)}^{(G, \geq)} = 0 \quad \forall i, j \in \{1,\dots,t\}, i \neq j. $$

**2. Verifying that the return value of ''groebner_basis'' is a Groebner basis of the input polynomial system 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.

</note>

==== Upload ====

Upload a zip archive ''hw07.zip'' (via the [[https://cw.felk.cvut.cz/upload/|course ware]]) containing the following files:
  - ''hw07.py'' - python script containing the implemented function ''poly_div'', ''groebner_basis''