~~NOTOC~~
===== Homework 06 - Multivariate Polynomials =====
**Allowed libraries**: sympy
**Forbidden methods**: sympy.polys.polytools.reduced, sympy.polys.polytools.groebner
=== Polynomial Division Algorithm ===
Implement the algorithm of multivariate polynomial division for more than one divisor (the examples and pseudo-algorithm of polynomial division can be found in [[https://cw.fel.cvut.cz/b221/_media/courses/pkr/labs/lab08.pdf|lab slides from week 8]] or [[https://cw.fel.cvut.cz/b221/_media/courses/pro/02_slides_solving_equation.pdf|lecture slides from week 9 and 10]]. )
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 are the list of quotient polynomials (list of ''Poly'' objects) and the remainder of the division (''Poly'' object), respectively. That is,
$$ f = \sum_{i}q[i]\cdot divs[i] + r, \quad \mathrm{LT}_{\mathrm{mo}}(r) \text{ is not divisible by any of } \mathrm{LT}_{\mathrm{mo}}(divs[i]) \;\text{ or }\; r = 0. $$
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
For the explanation of how to work with ''Poly'' objects see [[https://docs.sympy.org/latest/modules/polys/reference.html|Sympy documentation]].
=== Buchberger's Algorithm ===
Implement the Buchberger's algorithm 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''.
=== Upload ===
Upload a zip archive ''hw06.zip'' (via the [[https://cw.felk.cvut.cz/upload/|course ware]]) containing the following files:
- ''hw06.py'' - python script containing the implemented function ''poly_div'', ''groebner_basis''