Warning

## 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 lab slides from week 8 or 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:

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 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 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
For the explanation of how to work with Poly objects see 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:

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.